地址：https://atcoder.jp/contests/agc033/
D Complexity
dp[ i ][ j ][ k ][ l ] 表示左上角是 ( i , j ) 、右下角是 ( k , l ) 的矩阵的最小代价。
注意到答案是 log(n) + log(m) 级别的，因为每次从中间分， log 次之后就变成一行/列，log(n)+log(m)次就变成 1*1 的格子，代价是 0 。
所以把值和角标互换，dp[ i ][ j1 ][ j2 ][ k ] 表示左上角是 ( i , j1 ) 、右上角是 ( i , j2 ) 、用 k 的代价，往下最长能延伸到哪行。
转移的时候考虑横着切与竖着切。令 d = dp[ i ][ j1 ][ j2 ][ k ] ，首先有 d = dp [ dp[ i ][ j1 ][ j2 ][ k-1 ] ] [ j1 ][ j2 ][ k-1 ] ；
然后考虑 j3 满足 j1 <= j3 < j2 ，使得 [ j1 , j3 ] 和 [ j3+1 , j2 ] 就是分出的两部分；
如果 dp[ i ][ j1 ][ j3 ][ k-1 ] 和 dp[ i ][ j3+1 ][ j2 ][ k-1 ] 有一个是 < d 的，那么说明在这里切之后，两边有一个部分的代价 > k-1 ；
考虑二分找出最大的 min( dp[ i ][ j1 ][ j3 ][ k-1 ] , dp[ i ][ j3+1 ][ j2 ][ k-1 ] ) 。因为固定一条边之后，矩形越大，代价越大，所以根据两个值的大小关系来二分即可。
1#include<cstdio> 2#include<cstring> 3#include<algorithm> 4using namespace std; 5int Mx(int a,int b){return a>b?a:b;} 6int Mn(int a,int b){return a<b?a:b;} 7const int N=190; 8int n,m,sm[N][N],dp[2][N][N][N]; 9char ch[N][N]; 10bool chk(int x1,int y1,int x2,int y2) 11{ 12 int s=sm[x2][y2]-sm[x2][y1-1]-sm[x1-1][y2]+sm[x1-1][y1-1]; 13 return (!s)||s==(x2-x1+1)*(y2-y1+1); 14} 15int main() 16{ 17 scanf("%d%d",&n,&m); 18 for(int i=1;i<=n;i++) 19 scanf("%s",ch[i]+1); 20 for(int i=1;i<=n;i++) 21 for(int j=1;j<=m;j++)sm[i][j]=sm[i][j-1]+(ch[i][j]=='.'); 22 for(int i=1;i<=n;i++) 23 for(int j=1;j<=m;j++)sm[i][j]+=sm[i-1][j]; 24 for(int i=1;i<=n;i++) 25 for(int j1=1;j1<=m;j1++) 26 for(int j2=j1;j2<=m;j2++) 27 { 28 int l=i,r=n,ans=i-1; 29 while(l<=r) 30 { 31 int mid=l+r>>1; 32 if(chk(i,j1,mid,j2))ans=mid,l=mid+1; 33 else r=mid-1; 34 } 35 dp[0][i][j1][j2]=ans; 36 } 37 if(dp[0][1][1][m]==n){puts("0");return 0;} 38 bool u=1,v=0; 39 for(int t=1;t<=16;t++,swap(u,v)) 40 { 41 for(int i=1;i<=n;i++) 42 for(int j1=1;j1<=m;j1++) 43 for(int j2=j1;j2<=m;j2++) 44 { 45 int d=dp[v][dp[v][i][j1][j2]+1][j1][j2]; 46 if(dp[v][i][j1][j2]==n) 47 { dp[u][i][j1][j2]=n;continue;} 48 int l=j1,r=j2-1; 49 while(l<=r) 50 { 51 int mid=l+r>>1; 52 int t1=dp[v][i][j1][mid],t2=dp[v][i][mid+1][j2]; 53 d=Mx(d,Mn(t1,t2)); 54 if(t1>=t2)l=mid+1; else r=mid-1; 55 } 56 dp[u][i][j1][j2]=d; 57 } 58 if(dp[u][1][1][m]==n) 59 {printf("%d\n",t);return 0;} 60 } 61}
View Code
E Go around a Circle
题解：https://blog.csdn.net/yzyyylx/article/details/89839025
关键是把 “有一种颜色不能相邻” 和 “长度是奇数” 的限制用 “形如 RRR..RRB 的段” 的角度来看，通过 “ 长度/2 ” 来去掉第二个条件。
注意最后一个连续段如果是和第一个字符相同的字符，不会对长度造成限制。注意是全局的最后一个连续段，而不是该种字符的最后一段。
1#include<cstdio> 2#include<cstring> 3#include<algorithm> 4#define ll long long 5using namespace std; 6int Mn(int a,int b){return a<b?a:b;} 7const int N=2e5+5,mod=1e9+7; 8int upt(int x){while(x>=mod)x-=mod;while(x<0)x+=mod;return x;} 9 10int n,m,lm,dp[N],sm[N],ans,g[N]; 11char s[N]; 12void solve() 13{ 14 g[0]=sm[0]=1; 15 for(int i=1;i<=n;i++) 16 { 17 if(i>=2)g[i]=sm[i-2]; 18 sm[i]=upt(sm[i-1]+g[i]); 19 } 20 int ans=1;//ans=1 for all one color 21 for(int i=2;i<=n;i++) 22 ans=(ans+(ll)i*g[n-i])%mod; 23 printf("%d\n",ans); 24} 25int main() 26{ 27 scanf("%d%d",&n,&m); 28 scanf("%s",s+1); bool fg=0; 29 for(int i=1;i<=m;i++) 30 if(s[i]!=s[1]){fg=1;break;} 31 if(!fg){solve();return 0;} 32 if(n&1){puts("0");return 0;} 33 lm=n+1; 34 for(int i=1;i<=m;i++) 35 if(s[i]==s[1])//== not != 36 { 37 int j=i; 38 while(j+1<=m&&s[j+1]==s[j])j++; 39 swap(i,j); j=i-j+1; 40 if(i-j==0) lm=Mn(lm,j+((j&1)==0)); 41 else if((j&1)&&i!=m)lm=Mn(lm,j);//i!=m not lst 42 //else if((j&1)&&i!=lst)lm=Mn(lm,j); 43 } 44 n>>=1; lm=(lm+1)>>1; dp[0]=sm[0]=1; 45 for(int i=1;i<=n;i++) 46 { 47 dp[i]=sm[i-1]; if(i>lm)dp[i]=upt(dp[i]-sm[i-lm-1]); 48 sm[i]=upt(sm[i-1]+dp[i]); 49 } 50 int ans=0; 51 for(int i=1;i<=lm;i++)//lm not n 52 ans=(ans+(ll)i*2*dp[n-i])%mod; 53 printf("%d\n",ans); 54 return 0; 55}
View Code
F Adding Edges
题解代码看了这个：https://atcoder.jp/contests/agc033/submissions/5406519
但还是不太明白这道题是怎么回事……
算法流程大概是：
考虑把图上的边一条一条加进去，一边加一边让它尽量贴在树上；就是如果有边 ( a, b ) 和 ( a, c ) 且在树上有 a->b->c 的链（a,b,c可以不相邻），就把 ( a, c ) 的边改成 ( b, c ) 的边。
然后可以认为一个点沿图上的边、顺着树上的链能走到的点都是它可以连边的对象；走不到的就是不能连边的。
所以主要考虑怎么把第一行的那个操作实现。
考虑图中加入一条边 ( a, b ) ；把树上 a -> b 的路径找出来； a 和 b 都沿图上的边、顺着树上的链往对方走过去（别走得过了，可以先走 a ，然后 b 走的时候不要超过 a 的位置）；
如果 a 走到路径的另一端，或者 a 和 b 停下之后发现它们在图上已经有边了，就不管了；
否则就给图连上 ( a, b ) ；然后要考虑这条边是否导致一些边需要修改；需要修改的边一定有一个端点是 a 或者 b ，设一条边 ( a, x ) 要被删掉，需要满足树上有 a->b->x 的链（a,b,x可以不相邻），那么就要把 ( a, x ) 改成 ( b, x ) ；改的操作就是删边，然后递归这个“加边”操作来加入新边。
把一个点的出边用 set 存就能方便地删边了。
判断一个点 cr 在两个点 s , t 的路径上，可以通过判断 dis( s, t ) == dis( s, cr ) + dis( cr, t ) 。
尚不明白正确性或者复杂度……
1#include<cstdio> 2#include<cstring> 3#include<algorithm> 4#include<set> 5using namespace std; 6int rdn() 7{ 8 int ret=0;bool fx=1;char ch=getchar(); 9 while(ch>'9'||ch<'0'){if(ch=='-')fx=0;ch=getchar();} 10 while(ch>='0'&&ch<='9')ret=ret*10+ch-'0',ch=getchar(); 11 return fx?ret:-ret; 12} 13const int N=2005; 14int n,m,hd[N],xnt,to[N<<1],nxt[N<<1],fa[N][N],dis[N][N]; 15int p[N<<1],tot,ans; bool vis[N][N]; 16set<int> cd[N]; 17set<int>::iterator it; 18void add(int x,int y){to[++xnt]=y;nxt[xnt]=hd[x];hd[x]=xnt;} 19void ini_dfs(int cr,int rt,int lj) 20{ 21 dis[rt][cr]=lj; 22 for(int i=hd[cr],v;i;i=nxt[i]) 23 if(!fa[rt][v=to[i]]) 24 { fa[rt][v]=cr; ini_dfs(v,rt,lj+1);} 25} 26void fnd_path(int x,int y) 27{ 28 tot=0; p[++tot]=x; 29 while(x!=y){ x=fa[y][x]; p[++tot]=x;} 30} 31bool on_path(int cr,int s,int t) 32{return dis[s][t]==dis[s][cr]+dis[cr][t];} 33void solve(int x,int y) 34{ 35 fnd_path(x,y); int s=x,t=y,tmp=1; 36 for(int i=1;i<=tot;i++) if(vis[s][p[i]])s=p[i],tmp=i; 37 for(int i=tot;i>=tmp;i--) if(vis[t][p[i]])t=p[i];//>=tmp 38 if(s==y||vis[s][t])return; 39 int tp[N],tt=0;//here not use p[]!!! 40 for(it=cd[s].begin();it!=cd[s].end();it++) 41 if(on_path(t,(*it),s))tp[++tt]=(*it); 42 int bj=tt; 43 for(it=cd[t].begin();it!=cd[t].end();it++) 44 if(on_path(s,(*it),t))tp[++tt]=(*it); 45 vis[s][t]=vis[t][s]=1; 46 cd[s].insert(t); cd[t].insert(s); 47 for(int i=1;i<=bj;i++) 48 { 49 int v=tp[i]; vis[s][v]=vis[v][s]=0; 50 cd[s].erase(v); cd[v].erase(s); 51 solve(t,v); 52 } 53 for(int i=bj+1;i<=tt;i++) 54 { 55 int v=tp[i]; vis[t][v]=vis[v][t]=0; 56 cd[t].erase(v); cd[v].erase(t); 57 solve(s,v); 58 } 59} 60void dfs(int cr,int rt) 61{ 62 set<int>::iterator it2;//don't use it!!!!! 63 for(it2=cd[cr].begin();it2!=cd[cr].end();it2++) 64 if(on_path(cr,rt,(*it2))&&!vis[rt][*it2]) 65 vis[rt][*it2]=1,ans++,dfs((*it2),rt); 66} 67int main() 68{ 69 n=rdn();m=rdn(); 70 for(int i=1,u,v;i<n;i++) 71 { u=rdn();v=rdn();add(u,v);add(v,u);} 72 for(int i=1;i<=n;i++) 73 fa[i][i]=-1,ini_dfs(i,i,0); 74 for(int i=1,u,v;i<=m;i++) 75 { u=rdn();v=rdn();solve(u,v);} 76 memset(vis,0,sizeof vis); 77 for(int i=1;i<=n;i++) dfs(i,i); 78 printf("%d\n",ans/2); 79 return 0; 80}
View Code