Codeforces 7E
1 #include <iostream> 2 #include <cstring> 3 #include <cstdio> 4 #include <algorithm> 5 #include <map> 6 using namespace std; 7 map<string,int> Map; 8 int KASE; 9 string Str,t; 10 char Tmp[110]; 11 inline int Get(int l,int r) 12 { 13 int L,R,B=0; 14 for (int i=r-1;i>=l;i--) 15 { 16 B+=(t[i]==‘(‘)-(t[i]==‘)‘); 17 if (!B && (t[i]==‘+‘ || t[i]==‘-‘)) 18 { 19 L=Get(l,i),R=Get(i+1,r); 20 return L && R && (t[i]==‘+‘ || R>1); 21 } 22 } 23 for (int i=r-1;i>=l;i--) 24 { 25 B+=(t[i]==‘(‘)-(t[i]==‘)‘); 26 if (!B && (t[i]==‘*‘ || t[i]==‘/‘)) 27 { 28 L=Get(l,i),R=Get(i+1,r); 29 return L>1 && R>1 && (t[i]==‘*‘ || R==3)?2:0; 30 } 31 } 32 if (t[l]==‘(‘) return Get(l+1,r-1)?3:0; 33 string x=t.substr(l,r-l); 34 return Map.count(x)?Map[x]:3; 35 } 36 inline int Work() 37 { 38 gets(Tmp); 39 int Len=strlen(Tmp); t=""; 40 for (int i=0;i<Len;i++) if (Tmp[i]!=‘ ‘) t+=Tmp[i]; 41 return Get(0,t.size()); 42 } 43 int main() 44 { 45 scanf("%d",&KASE); 46 for (int Kase=1;Kase<=KASE;Kase++) 47 { 48 scanf(" #%*s"),cin>> Str; 49 Map[Str]=Work(); 50 } 51 puts(Work()?"OK":"Suspicious"); 52 return 0; 53 }
我们考虑一个宏是否是“安全”的，经过观察和一些实验，可以发现，只有以下4种状态：
• 状态1(s1)： 这个宏完全安全，以任何方式使用该宏都没问题。
• 状态2(s2)： 这个宏不安全，只要表达式中出现该宏，都会导致表达式不安全。
• 状态3(s3)： 这个宏部分安全，仅当这个宏与’*’,’/’连接时，或出现在’-’后面时，才会使 表达式不安全。
• 状态4(s4)： 这个宏部分安全，仅当这个宏出现在’/’后面时，才会使表达式不安全。
有了这4个状态，我们只需推出状态之间的转移即可。
• 如果表达式没有使用任何运算符或括号或宏（也就是s仅仅是个单独的变量），那么安 全级别显然是s1
• 如果表达式s是(t)的形式（被一对括号括起来的表达式t），那么如果t的状态不是s2， 则s的状态是s1，否则s的状态是s2
• 我们找到表达式s中，最后一次运算的符号，设其为op，设其两侧表达式分别为t1和t2。 我们进行以下分类讨论：
– 显然，如果t1或t2的安全状态是s2，则s的状态也是s2;
– 如果op是’+’，那么s的状态是s3; – 如果op是’-’，那么，如t2状态是s3，则s状态是s2，否则s状态是s3
– 如果op是’*’，那么，如t1或t2状态是s3，则s状态是s2，否则s状态是s4
– 如果op是’/’，那么，如t1或t2状态是s3，或t2状态是s4，则s状态是s2，否则s状态是s4
于是，此题得到了解决。 时间复杂度O(n∗len2)，如果愿意追求更好的复杂度，可以建 出表达式树，从而做到O(N ∗len)
Codeforces 17C
1 #include <iostream> 2 #include <cstring> 3 #include <cstdio> 4 #include <algorithm> 5 using namespace std; 6 int F[154][54][54][54],Pos[200]; 7 int Next[160][4],n,Ans=0; 8 char Str[200]; 9 const int Mod=51123987; 10 inline int Abs(int x) {return x>0?x:-x;} 11 int main() 12 { 13 scanf("%d",&n); int m=n/3+1; 14 scanf("%s",Str+1); 15 for (int i=n;i>=1;i--) 16 { 17 Pos[Str[i]]=i; 18 for (int j=1;j<=3;j++) Next[i][j]=Pos[j+‘a‘-1]; 19 } 20 F[1][0][0][0]=1; 21 for (int i=1;i<=n;i++) 22 { 23 for (int a=0;a<=m;a++) 24 for (int b=0;b<=m;b++) 25 for (int c=0;c<=m;c++) 26 { 27 if (!F[i][a][b][c]) continue; 28 if (a+b+c==n && Abs(a-b)<=1 && Abs(a-c)<=1 && Abs(b-c)<=1) Ans=(Ans+F[i][a][b][c])%Mod; 29 F[Next[i][1]][a+1][b][c]=(F[Next[i][1]][a+1][b][c]+F[i][a][b][c])%Mod; 30 F[Next[i][2]][a][b+1][c]=(F[Next[i][2]][a][b+1][c]+F[i][a][b][c])%Mod; 31 F[Next[i][3]][a][b][c+1]=(F[Next[i][3]][a][b][c+1]+F[i][a][b][c])%Mod; 32 } 33 } 34 printf("%d\n",Ans); 35 return 0; 36 }
一段连续的字母必定对应原 串的某个字符， 原串的某个字符也必定对应可以得到的串中一段连续的字母。Dp就可以了。
Codeforces 17E
1 #include <cstdio> 2 #define LL long long 3 using namespace std; 4 const LL Maxn=4000010; 5 const LL Mod=51123987; 6 char Str[Maxn],S[Maxn]; 7 LL P[Maxn],n,a[Maxn],b[Maxn],Ans=0; 8 inline LL Min(LL x,LL y) {return x>y?y:x;} 9 inline void Manacher() 10 { 11 Str[0]=‘$‘; Str[1]=‘#‘; Str[(n<<1)+2]=‘^‘; 12 for (LL i=1;i<=n;i++) Str[i<<1]=S[i],Str[i<<1|1]=‘#‘; 13 LL Mx=0,Id=0; n=n<<1|1; 14 for (LL i=1;i<=n;i++) 15 { 16 if (i<Mx) P[i]=Min(Mx-i,P[2*Id-i]); else P[i]=1; 17 while (Str[i-P[i]]==Str[i+P[i]]) P[i]++; 18 if (P[i]+i>Mx) Mx=P[i]+i,Id=i; 19 } 20 } 21 int main() 22 { 23 scanf("%I64d",&n); LL nn=n; 24 scanf("%s",S+1); 25 Manacher(); 26 for (LL i=1;i<=n+1;i++) a[(i-P[i])/2+1]++,a[i/2+1]--,b[(i+1)/2]++,b[(i+P[i])/2]--,Ans+=P[i]/2; 27 for (LL i=1;i<=n;i++) a[i]+=a[i-1],b[i]+=b[i-1]; 28 Ans%=Mod; Ans=(Ans*(Ans-1))/2%Mod; 29 for (LL i=1;i<=nn;i++) (b[i]+=b[i-1])%Mod,Ans=(Ans-a[i]*b[i-1])%Mod; 30 printf("%I64d\n",(Ans+Mod)%Mod); 31 return 0; 32 }
可以用Manacher算出每个字符为中心的回文串的最大长度。相交的对数=总的对数-不相交的对数， 那窝萌统计不想交的对数。
sum[i]表示右边界小于等于i的回文串个数，cnt[i]表示左边界等于i的回文串个数。那么就是∑sum[i]*cnt[i+1]
那么如何统计cnt[i]呢，求出Manacher求出P[i]以后，从左边界加一右边界减一从左往右加即可.
sum[i]就是再次从往右加即可.
Codeforce 23E
1 #include <iostream> 2 #include <cstring> 3 #include <cstdio> 4 #include <algorithm> 5 using namespace std; 6 const int Maxn=710; 7 struct EDGE{int to,next;}edge[Maxn<<2]; 8 int head[Maxn],n,u,v,F[Maxn][Maxn],cnt,Size[Maxn]; 9 inline int Max(int x,int y) {return x>y?x:y;} 10 inline void Add(int u,int v) 11 {edge[cnt].to=v;edge[cnt].next=head[u];head[u]=cnt++;} 12 void Dfs(int u,int fa) 13 { 14 Size[u]=1; 15 for (int i=1;i<=n;i++) F[u][i]=1; 16 for (int i=head[u];i!=-1;i=edge[i].next) 17 { 18 if (edge[i].to==fa) continue; 19 Dfs(edge[i].to,u); 20 for (int j=Size[u];j;j--) 21 { 22 for (int k=1;k<=Size[edge[i].to];k++) 23 { 24 int x=F[u][j]*F[edge[i].to][k]; 25 F[u][j+k]=Max(F[u][j+k],x); 26 } 27 F[u][j]=F[u][j]*F[edge[i].to][0]; 28 } 29 Size[u]+=Size[edge[i].to]; 30 } 31 for (int i=1;i<=Size[u];i++) 32 { 33 int x=F[u][i]*i; 34 F[u][0]=Max(F[u][0],x); 35 } 36 } 37 int main() 38 { 39 scanf("%d",&n); 40 memset(head,-1,sizeof(head)); 41 for (int i=1;i<n;i++) 42 { 43 scanf("%d%d",&u,&v); 44 Add(u,v),Add(v,u); 45 } 46 Dfs(1,0); 47 printf("%d\n",F[1][0]); 48 return 0; 49 }
需要高精度.
用F[i][s]表示考虑以i为根的子树，且i所属的连通块大小是s时的最大值
转移：对于i的每个孩子j，枚举k，用dp[j][k]∗dp[i][s]去更新dp[i][s+k]即可.
原文：http://www.cnblogs.com/yyjxx2010xyu/p/5831206.html
