首页 > 代码库 > Codeforces

Codeforces

2024-08-11 16:44:18   221人阅读

 

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 }
C++

我们考虑一个宏是否是“安全”的，经过观察和一些实验，可以发现，只有以下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 }
C++

一段连续的字母必定对应原 串的某个字符， 原串的某个字符也必定对应可以得到的串中一段连续的字母。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 }
C++

可以用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 }
C++

需要高精度.

用F[i][s]表示考虑以i为根的子树，且i所属的连通块大小是s时的最大值

转移：对于i的每个孩子j，枚举k，用dp[j][k]∗dp[i][s]去更新dp[i][s+k]即可.

 

Codeforces


联系
我们