今天又是没改完题的一天！！！
考场心态越来越好！！做题策略也有些改进，趁着自己昏昏欲睡的时候就不要想了，而是先把暴力打了！
第一题，一眼就切了，一下就过样例了，手造了一个一下就假了，完事一下就不会了...
第二题，一下就想到了最小割树，一度认为自己已经切掉了此题，然后发现只有40
第三题，一下就看到了是特判题，这次认为稳稳的切了，然而有两个impossible判错了，于是挂没了
T1 定位系统
目前只会50分，LCT上二分颓难了
总而言之，DP的思想对于这种题来说非常的重要，其实考场上意识到了和单链有关系，然而没有找到具体的关系！！
我们可以通过dp式子找到一定的关系，甚至可以推出来是一个定值！
于是这个题就可以这样一步一步的化简到非常好求的程度！！
50_code
#include<bits/stdc++.h>
using namespace std;
#define fo(i,x,y) for(int i=(x);i<=(y);i++)
#define fu(i,x,y) for(int i=(x);i>=(y);i--)
int read(){
int s=0,t=1;char ch=getchar();
while(!isdigit(ch)){if(ch=='-')t=-1;ch=getchar();}
while(isdigit(ch)){s=s*10+ch-'0';ch=getchar();}
return s*t;
}
const int N=5e5+5;
int n,q,ans;
int du[N];
struct D{int x,y;}d[N];
struct E{int to,nxt;}e[N*2];
int head[N],rp;
void add_edg(int x,int y){e[++rp].to=y;e[rp].nxt=head[x];head[x]=rp;}
int cnt[N],mxd[N];
void dfs_rt(int x,int f){
mxd[x]=du[x];cnt[x]=0;
for(int i=head[x];i;i=e[i].nxt){
int y=e[i].to;
if(y==f)continue;
dfs_rt(y,x);if(mxd[y]<=2)cnt[x]++;
mxd[x]=max(mxd[x],mxd[y]);
}
}
void dfs_dp(int x,int f){
for(int i=head[x];i;i=e[i].nxt){
int y=e[i].to;
if(y==f)continue;
if(mxd[y]<=2&&((du[x]==2&&cnt[x]==2)||(du[x]==1&&cnt[x]==0)))cnt[y]++;
if(mxd[y]>2&&((du[x]==2&&cnt[x]==1)||(du[x]==1&&cnt[x]==0)))cnt[y]++;
dfs_dp(y,x);
}
}
int ck(){
if(n==1)return 0;
bool flag=true;
fo(i,1,n)if(du[i]>2)flag=false;
if(flag)return 1;rp=ans=0;
memset(head,0,sizeof(int)*(n+1));
fo(i,1,n-1)add_edg(d[i].x,d[i].y),add_edg(d[i].y,d[i].x);
dfs_rt(1,0);dfs_dp(1,0);
fo(i,1,n)ans+=max(0,cnt[i]-1);//cerr<<i<<" "<<du[i]<<" "<<mxd[i]<<" "<<cnt[i]<<endl;
return ans;
}
signed main(){
freopen("location.in","r",stdin);
freopen("location.out","w",stdout);
n=read();
fo(i,1,n-1){
d[i].x=read();
d[i].y=read();
du[d[i].x]++;du[d[i].y]++;
}
q=read();printf("%d\n",ck());
while(q--){
int u=read(),v=read();
int x=read(),y=read();
du[u]--;du[v]--;du[x]++;du[y]++;
fo(i,1,n-1)if((d[i].x==u&&d[i].y==v)||(d[i].x==v&&d[i].y==u))d[i].x=x,d[i].y=y;
printf("%d\n",ck());
}
return 0;
}
T2 签到题
首先我发现了最大的可能的最大流是3,但是没有想到什么好办法
于是我们可以看题解！！！这个就是利用随机权值来判断两条边割掉之后是否可以使得图不联通
AC_code
#include<bits/stdc++.h>
using namespace std;
#define ull unsigned long long
#define fo(i,x,y) for(int i=(x);i<=(y);i++)
#define fu(i,x,y) for(int i=(x);i>=(y);i--)
int read(){
int s=0,t=1;char ch=getchar();
while(!isdigit(ch)){if(ch=='-')t=-1;ch=getchar();}
while(isdigit(ch)){s=s*10+ch-'0';ch=getchar();}
return s*t;
}
random_device you;
mt19937 pyt(you());
ull rd(){return 1ull*pyt()*pyt();}
const int N=1e6+5;
int n,m;ull ans;
struct E{int to,nxt;ull val;}e[N*6];
int head[N],rp=1,ban[N*6];
void add_edg(int x,int y){e[++rp].to=y;e[rp].nxt=head[x];head[x]=rp;}
int sz0[N];bool vis[N];
void dfs0(int x,int f){
sz0[x]=1;vis[x]=true;
for(int i=head[x];i;i=e[i].nxt){
int y=e[i].to;
if(y==f||vis[y])continue;
dfs0(y,x);sz0[x]+=sz0[y];
}
//cerr<<"dfs0"<<" "<<x<<" "<<sz0[x]<<endl;
}
int dfn[N],low[N],cnt;
int bl[N],cbl,sz1[N],brt[N],sta[N],top;
void tarjan(int x){
dfn[x]=low[x]=++cnt;sta[++top]=x;
for(int i=head[x];i;i=e[i].nxt){
if(ban[i])continue;
int y=e[i].to;ban[i]=ban[i^1]=true;
if(!dfn[y])tarjan(y),low[x]=min(low[x],low[y]);
else if(!bl[y])low[x]=min(low[x],dfn[y]);
}
if(low[x]==dfn[x]){
bl[x]=++cbl;sz1[cbl]=1;
while(sta[top]!=x)bl[sta[top--]]=cbl,sz1[cbl]++;
top--;brt[cbl]=x;
}
}
int fe[N],ji[N],cj,dep[N];
ull val[N];
void dfs_cl(int x,int f,int blg){
vis[x]=true;dep[x]=dep[f]+1;
for(int i=head[x];i;i=e[i].nxt){
int y=e[i].to;
if(bl[y]!=blg)continue;
ban[i]=ban[i^1]=false;
if(vis[y])continue;
dfs_cl(y,x,blg);
}
}
void dfs_fg(int x,int f,int blg){
ji[++cj]=x;dep[x]=dep[f]+1;vis[x]=true;
for(int i=head[x];i;i=e[i].nxt){
if(ban[i])continue;
int y=e[i].to;ban[i]=ban[i^1]=true;
if(y==f||bl[y]!=blg)continue;
if(vis[y]){
ull tmp=rd();
//cerr<<"FZ"<<" "<<x<<" "<<y<<endl;
e[fe[x]].val^=tmp;
e[fe[y]].val^=tmp;
continue;
}
fe[y]=i;dfs_fg(y,x,blg);
e[fe[x]].val^=e[i].val;
}
}
bool com(int x,int y){
if(e[fe[x]].val==e[fe[y]].val)return dep[x]<dep[y];
return e[fe[x]].val<e[fe[y]].val;
}
int fzb[N];
void dfs_fz(int x,int f,int blg){
vis[x]=true;dep[x]=dep[f]+1;
for(int i=head[x];i;i=e[i].nxt){
if(ban[i])continue;
int y=e[i].to;ban[i]=ban[i^1]=true;
if(y==f||bl[y]!=blg)continue;
if(vis[y]){fzb[y]--;fzb[x]++;continue;}
dfs_fz(y,x,blg);fzb[x]+=fzb[y];
}
if(fzb[x]<=1)val[x]^=rd();
}
void dfs_xf(int x,int f,int blg){
vis[x]=true;
for(int i=head[x];i;i=e[i].nxt){
if(ban[i])continue;
int y=e[i].to;ban[i]=ban[i^1]=true;
if(y==f||bl[y]!=blg)continue;
if(vis[y])continue;
val[y]^=val[x];dfs_xf(y,x,blg);
}
}
bool con(int x,int y){return val[x]<val[y];}
signed main(){
freopen("juice.in","r",stdin);
freopen("juice.out","w",stdout);
n=read();m=read();
fo(i,1,m){
int x=read(),y=read();
add_edg(x,y);add_edg(y,x);
}
//cout<<"SB"<<endl;
fo(i,1,n){
if(!sz0[i])dfs0(i,0);//cerr<<i<<" "<<sz0[i]<<endl;
else sz0[i]=0;
}
fo(i,1,n)vis[i]=false;
//cout<<"SB"<<endl;
fo(i,1,n)if(sz0[i]){
int now=cbl+1;
tarjan(i);//cerr<<cbl<<endl;
fo(j,now,cbl)ans+=1ull*sz1[j]*(sz0[i]-sz1[j]);//cout<<sz1[j]<<" "<<sz0[i]<<endl;
}
memset(ban,false,sizeof(ban));
cerr<<ans<<endl;
fo(i,1,cbl){cj=0;
dfs_fg(brt[i],0,i);sort(ji+1,ji+cj+1,com);
fo(j,1,cj)vis[ji[j]]=false;
dfs_cl(brt[i],0,i);fo(j,1,cj)vis[ji[j]]=false;
//cerr<<e[fe[2]].val<<" "<<e[fe[6]].val<<endl;
fo(j,2,cj)if(e[fe[ji[j]]].val==e[fe[ji[j-1]]].val){
ull tmp=rd();val[ji[j]]^=tmp;val[ji[j-1]]^=tmp;
//cerr<<"SB"<<" "<<ji[j]<<" "<<ji[j-1]<<endl;
}
dfs_fz(brt[i],0,i);fo(j,1,cj)vis[ji[j]]=false;
dfs_cl(brt[i],0,i);fo(j,1,cj)vis[ji[j]]=false;
dfs_xf(brt[i],0,i);fo(j,1,cj)vis[ji[j]]=false;
dfs_cl(brt[i],0,i);fo(j,1,cj)vis[ji[j]]=false;
sort(ji+1,ji+cj+1,con);int now=1;
ji[cj+1]=0;val[0]=0;
fo(j,2,cj+1){
//cerr<<ji[j-1]<<" ";
if(val[ji[j]]!=val[ji[j-1]]){
ans+=3ull*now*(now-1);
ans+=2ull*now*(cj-now);
now=0;//cerr<<endl;
}now++;
}
}
printf("%llu",ans/2);
}
T3 卷王
直接分1,2,3种情况特判就行了
AC_code
#include<bits/stdc++.h>
using namespace std;
#define fo(i,x,y) for(int i=(x);i<=(y);i++)
#define fu(i,x,y) for(int i=(x);i>=(y);i--)
int read(){
int s=0,t=1;char ch=getchar();
while(!isdigit(ch)){if(ch=='-')t=-1;ch=getchar();}
while(isdigit(ch)){s=s*10+ch-'0';ch=getchar();}
return s*t;
}
const int N=1e6+5;
int n,p[N];
int buc[N],sum;
void spj1(){
if(!buc[0]){
if(n==1)printf("Possible");
else printf("Impossible");
return ;
}
else {
if(n<4){printf("Impossible");return ;}
printf("Possible\n");
fo(i,2,n)printf("1 %d\n",i);
}
}
void spj2(){
int fi,se,las,sum;
fo(i,0,n)if(buc[i]){fi=i;break;}
fo(i,0,n)if(buc[i]&&i!=fi)se=i;
if(buc[0]){
if(buc[0]==1||p[se]){printf("Impossible");return ;}
if(buc[0]>=(n-1>>1)&&buc[se]<=2){printf("Impossible");return ;}
las=se;sum=0;printf("Possible\n");
fo(i,1,n)if(p[i]==0&&i!=se){
if(sum<min(buc[0],buc[se])-1)printf("%d %d\n",las,i),las=i,sum++;
else printf("%d %d\n",las,i);
}
sum=0;fo(i,1,n)if(p[i]==se){
if(sum<min(buc[0],buc[se]-1)-1)printf("%d %d\n",las,i),las=i,sum++;
else printf("%d %d\n",las,i);
}
return ;
}
else {
if(n==2){printf("Possible\n1 2\n");return ;}
if(n==3||p[se]==se||p[fi]==fi){printf("Impossible");return ;}
if(buc[fi]!=buc[se]&&min(buc[fi],buc[se])==2){printf("Impossible");return ;}
if(buc[fi]>buc[se])swap(fi,se);
printf("Possible\n");las=se;
fo(i,1,n)if(p[i]==fi&&i!=se){printf("%d %d\n",las,i);las=i;}
int beh;fo(i,1,n)if(p[i]==se&&i!=fi){beh=i;break;}sum=0;
fo(i,1,n)if(p[i]==se&&i!=fi&&sum<buc[fi]-1){printf("%d %d\n",las,i);las=i;sum++;}
printf("%d %d\n",las,fi);
fo(i,las+1,n)if(p[i]==se&&i!=fi){printf("%d %d\n",beh,i);}
}
}
void spj3(){
if(!buc[0]){printf("Impossible");return ;}
int fi,se,las,sum;
fo(i,1,n)if(buc[i]){fi=i;break;}
fo(i,1,n)if(buc[i]&&i!=fi)se=i;
if(p[fi]!=se||p[se]!=fi){printf("Impossible");return ;}
if(min(buc[fi],buc[se])<=2){printf("Impossible");return ;}
printf("Possible\n");//cerr<<buc[fi]<<" "<<buc[0]<<" "<<buc[se]<<endl;
if(buc[fi]>buc[se])swap(fi,se);
las=se;fo(i,1,n)if(p[i]==fi&&i!=se){printf("%d %d\n",las,i);las=i;}
int beh;fo(i,1,n)if(p[i]==se&&i!=fi){beh=i;break;}sum=0;
fo(i,1,n)if(p[i]==0){
if(p[las]==fi)printf("%d %d\n",las,i),las=i;
else printf("%d %d\n",las,i);
}
fo(i,1,n)if(p[i]==se&&i!=fi&&sum<buc[fi]-1){printf("%d %d\n",las,i);las=i;sum++;}
printf("%d %d\n",las,fi);
fo(i,las+1,n)if(p[i]==se&&i!=fi){printf("%d %d\n",beh,i);}
}
signed main(){
freopen("tree.in","r",stdin);
freopen("tree.out","w",stdout);
n=read();
fo(i,1,n){
p[i]=read();
if(p[i]==-1)p[i]=0;
buc[p[i]]++;
if(buc[p[i]]==1)sum++;
}
if(sum==1){spj1();return 0;}
if(sum==2){spj2();return 0;}
if(sum==3){spj3();return 0;}
printf("Impossible");
return 0;
}