具体过程
- 开始看题，由于开的 \(linux\) 所以有点慢，不过还好。
- 开始写T1，首先用的是统计入度个数，但是不知道为啥炸了
- 调了很久的输入输出调不出来，感觉很生气，因为gyf已经A了，于是去做并查集做法。
- 然后一发入魂，开始做T2
- T2写了很久，期间翻了翻最段路模板，在建图上卡了很久，后来想到可以把无色点都pass掉。。
- 一发入魂，此时还有半小时结束
- 用10分钟快速写一个T3暴力，结果全T
- 剩下时间开始写T4正解，写不出，开始写暴力，暴力只那了20pts好伤心
- 最终rank 2，真的是太烂了。
后记
3/22 中午A了T3，T4，补上代码
经验教训
- 无论如何要先调试好集成开发环境，比如T2写一半 \(Code:Blocks\) 炸裂，只能用 \(Sublime Text\) 和命令行编译。
- 平时做题少看题解！不然真的自己想不出！
- 一个做法调不出来就别死磕，重构代码yyds。
- 要多刷难题，锻炼思维，例如平时做蓝或绿（主要因为黄也都做了百来道了）
- 重刷模板题。
- 最后啊啊我还是太弱了怎么这种比赛还能考这个分。
代码
T1：
#include<bits/stdc++.h>
using namespace std;
int read(){
int x=0;
int f=1;
char c=getchar();
while(c>'9'||c<'0'){
if(c=='-')f=-1;
c=getchar();
}
while(c>='0'&&c<='9'){
x=(x<<1)+(x<<3)+(c^'0');
c=getchar();
}
return x*f;
}
int f[100001];
int find(int x){
if(f[x]!=x)f[x]=find(f[x]);
return f[x];
}
inline void uniond(int x,int y){
f[x]=y;
}
int main(){
for(int j=1;;j++){
int x,y;
int maxnode=-1;
int flag=0;
scanf("%d%d",&x,&y);
for(int i=1;i<=100000;i++){
f[i]=i;
}
if(x<0&&y<0){
break;
}
if(x==0&&y==0){
printf("Case %d is a tree.\n",j);
continue;
}
while(x>0&&y>0){
if(find(x)==find(y)){
flag=1;
}
uniond(find(x),find(y));
scanf("%d%d",&x,&y);
}
if(flag==0)
printf("Case %d is a tree.\n",j);
else{
printf("Case %d is not a tree.\n",j);
}
}
return 0;
}
T2:
#include<bits/stdc++.h>
using namespace std;
#define inf 0x3f3f3f3f
int read(){
int x=0;
int f=1;
char c=getchar();
while(c>'9'||c<'0'){
if(c=='-')f=-1;
c=getchar();
}
while(c>='0'&&c<='9'){
x=(x<<1)+(x<<3)+(c^'0');
c=getchar();
}
return x*f;
}
int n,m;
inline int flat(int x,int y){
return (x-1)*m+y;
}
struct lines{
int to,val;
};
struct point{
int id,distance;
bool operator < (const point & a)const{
return distance>a.distance;
}
};
struct colorpoint{
int x,y,color;
};
vector<colorpoint>aa;
priority_queue<point>q;
int dis[1010];
bool vis[1010];
vector<lines>g[1010];
int s,e;
void dij(){
for(int i=1;i<=n;i++){
if(i==s)continue;
dis[i]=inf;
}
q.push({s,0});
while(!q.empty()){
point now=q.top();
q.pop();
if(vis[now.id])continue;
vis[now.id]=1;
int u=now.id;
int a=g[u].size();
for(int i=0;i<a;i++){
if(dis[g[u][i].to]>dis[u]+g[u][i].val){
dis[g[u][i].to]=dis[u]+g[u][i].val;
q.push({g[u][i].to,dis[g[u][i].to]});
}
}
}
}
int tag;
int main(){
m=read();
n=read();
aa.push_back({1,1,1});
for(int i=1,x,y,z;i<=n;i++){
x=read();
y=read();
z=read();
if(x==1&&y==1)s=i;
if(x==m&&y==m){
tag=1;
e=i;
}
aa.push_back({x,y,z});
}
for(int i=1;i<n;i++){
for(int j=i+1;j<=n;j++){
if(abs(aa[i].x-aa[j].x)+abs(aa[i].y-aa[j].y)==1)
{
g[i].push_back({j,abs(aa[i].color-aa[j].color)} );
g[j].push_back({i,abs(aa[i].color-aa[j].color)} );
}
if(abs(aa[i].x-aa[j].x)+abs(aa[i].y-aa[j].y)==2){
g[i].push_back({j,2+abs(aa[i].color-aa[j].color)} );
g[j].push_back({i,2+abs(aa[i].color-aa[j].color)} );
}
}
}
if(tag==0){
for(int i=1;i<=n;i++){
if(abs(aa[i].x-m)+abs(aa[i].y-m)==1){
g[i].push_back({n+1,2});
g[n+1].push_back({i,2});
}
}
n++;
e=n;
}
dij();
if(dis[e]>=inf){
cout<<-1;
}else{
cout<<dis[e];
}
return 0;
}
T3:
#include<bits/stdc++.h>
using namespace std;
int maxn=100004;
inline int lowbit(int x){
return x & -x;
}
int tree[100005];
int a[100005];
int te1[100005];
int te2[100005];
int n;
void update(int x,int y){
while(x<=maxn){
tree[x]+=y;
x+=lowbit(x);
}
}
int sum(int x){
int ans=0;
while(x){
ans+=tree[x];
x-=lowbit(x);
}
return ans;
}
int main(){
ios::sync_with_stdio(0);
long long ans=0;
int t;
cin>>t;
while(t--){
cin>>n;
for(int i=1;i<=n;i++){
cin>>a[i];
}
memset(tree,0,sizeof(tree));
for(int i=1;i<=n;i++){
update(a[i],1);
te1[i]=sum(a[i]-1);
}
memset(tree,0,sizeof(tree));
for(int i=n;i>=1;i--){
update(a[i],1);
te2[i]=sum(a[i]-1);
}
ans=0;
for(int i=2;i<=n;i++){
ans+=te1[i]*(n-i-te2[i])+(i-te1[i]-1)*te2[i];
}
cout<<ans<<'\n';
}
return 0;
}
T4：
#include<bits/stdc++.h>
using namespace std;
#define mod 10007
vector<int>g[200001];
int v[200001];
int n,ans,maxx;
void dos(){
for(int i=1;i<=n;i++){
int temp=0,a=0,b=0;
for(int j=0;j<g[i].size();j++){
int to=g[i][j];
if(v[to]>a){
b=a;
a=v[to];
}else if(v[to]>b){
b=v[to];
}
ans=(ans+temp*v[to])%mod;
temp=(temp+v[to])%mod;
}
maxx=max(maxx,a*b);
}
}
int main(){
ios::sync_with_stdio(0);
cin>>n;
for(int i=1,x,y;i<n;i++){
cin>>x>>y;
g[x].push_back(y);
g[y].push_back(x);
}
for(int i=1;i<=n;i++){
cin>>v[i];
}
dos();
cout<<maxx<<' '<<(ans*2)%mod;
return 0;
}