首页 > 代码库 > Codeforces
Codeforces
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]即可.
Codeforces