Codeforces 7E
#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <map>
using namespace std;
map<string,int> Map;
int KASE;
string Str,t;
char Tmp[];
inline int Get(int l,int r)
{
int L,R,B=;
for (int i=r-;i>=l;i--)
{
B+=(t[i]=='(')-(t[i]==')');
if (!B && (t[i]=='+' || t[i]=='-'))
{
L=Get(l,i),R=Get(i+,r);
return L && R && (t[i]=='+' || R>);
}
}
for (int i=r-;i>=l;i--)
{
B+=(t[i]=='(')-(t[i]==')');
if (!B && (t[i]=='*' || t[i]=='/'))
{
L=Get(l,i),R=Get(i+,r);
return L> && R> && (t[i]=='*' || R==)?:;
}
}
if (t[l]=='(') return Get(l+,r-)?:;
string x=t.substr(l,r-l);
return Map.count(x)?Map[x]:;
}
inline int Work()
{
gets(Tmp);
int Len=strlen(Tmp); t="";
for (int i=;i<Len;i++) if (Tmp[i]!=' ') t+=Tmp[i];
return Get(,t.size());
}
int main()
{
scanf("%d",&KASE);
for (int Kase=;Kase<=KASE;Kase++)
{
scanf(" #%*s"),cin>> Str;
Map[Str]=Work();
}
puts(Work()?"OK":"Suspicious");
return ;
}
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
#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
using namespace std;
int F[][][][],Pos[];
int Next[][],n,Ans=;
char Str[];
const int Mod=;
inline int Abs(int x) {return x>?x:-x;}
int main()
{
scanf("%d",&n); int m=n/+;
scanf("%s",Str+);
for (int i=n;i>=;i--)
{
Pos[Str[i]]=i;
for (int j=;j<=;j++) Next[i][j]=Pos[j+'a'-];
}
F[][][][]=;
for (int i=;i<=n;i++)
{
for (int a=;a<=m;a++)
for (int b=;b<=m;b++)
for (int c=;c<=m;c++)
{
if (!F[i][a][b][c]) continue;
if (a+b+c==n && Abs(a-b)<= && Abs(a-c)<= && Abs(b-c)<=) Ans=(Ans+F[i][a][b][c])%Mod;
F[Next[i][]][a+][b][c]=(F[Next[i][]][a+][b][c]+F[i][a][b][c])%Mod;
F[Next[i][]][a][b+][c]=(F[Next[i][]][a][b+][c]+F[i][a][b][c])%Mod;
F[Next[i][]][a][b][c+]=(F[Next[i][]][a][b][c+]+F[i][a][b][c])%Mod;
}
}
printf("%d\n",Ans);
return ;
}
C++
一段连续的字母必定对应原 串的某个字符， 原串的某个字符也必定对应可以得到的串中一段连续的字母。Dp就可以了。
Codeforces 17E
#include <cstdio>
#define LL long long
using namespace std;
const LL Maxn=;
const LL Mod=;
char Str[Maxn],S[Maxn];
LL P[Maxn],n,a[Maxn],b[Maxn],Ans=;
inline LL Min(LL x,LL y) {return x>y?y:x;}
inline void Manacher()
{
Str[]='$'; Str[]='#'; Str[(n<<)+]='^';
for (LL i=;i<=n;i++) Str[i<<]=S[i],Str[i<<|]='#';
LL Mx=,Id=; n=n<<|;
for (LL i=;i<=n;i++)
{
if (i<Mx) P[i]=Min(Mx-i,P[*Id-i]); else P[i]=;
while (Str[i-P[i]]==Str[i+P[i]]) P[i]++;
if (P[i]+i>Mx) Mx=P[i]+i,Id=i;
}
}
int main()
{
scanf("%I64d",&n); LL nn=n;
scanf("%s",S+);
Manacher();
for (LL i=;i<=n+;i++) a[(i-P[i])/+]++,a[i/+]--,b[(i+)/]++,b[(i+P[i])/]--,Ans+=P[i]/;
for (LL i=;i<=n;i++) a[i]+=a[i-],b[i]+=b[i-];
Ans%=Mod; Ans=(Ans*(Ans-))/%Mod;
for (LL i=;i<=nn;i++) (b[i]+=b[i-])%Mod,Ans=(Ans-a[i]*b[i-])%Mod;
printf("%I64d\n",(Ans+Mod)%Mod);
return ;
}
C++
可以用Manacher算出每个字符为中心的回文串的最大长度。相交的对数=总的对数-不相交的对数， 那窝萌统计不想交的对数。
sum[i]表示右边界小于等于i的回文串个数，cnt[i]表示左边界等于i的回文串个数。那么就是∑sum[i]*cnt[i+1]
那么如何统计cnt[i]呢，求出Manacher求出P[i]以后，从左边界加一右边界减一从左往右加即可.
sum[i]就是再次从往右加即可.
Codeforce 23E
#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
using namespace std;
const int Maxn=;
struct EDGE{int to,next;}edge[Maxn<<];
int head[Maxn],n,u,v,F[Maxn][Maxn],cnt,Size[Maxn];
inline int Max(int x,int y) {return x>y?x:y;}
inline void Add(int u,int v)
{edge[cnt].to=v;edge[cnt].next=head[u];head[u]=cnt++;}
void Dfs(int u,int fa)
{
Size[u]=;
for (int i=;i<=n;i++) F[u][i]=;
for (int i=head[u];i!=-;i=edge[i].next)
{
if (edge[i].to==fa) continue;
Dfs(edge[i].to,u);
for (int j=Size[u];j;j--)
{
for (int k=;k<=Size[edge[i].to];k++)
{
int x=F[u][j]*F[edge[i].to][k];
F[u][j+k]=Max(F[u][j+k],x);
}
F[u][j]=F[u][j]*F[edge[i].to][];
}
Size[u]+=Size[edge[i].to];
}
for (int i=;i<=Size[u];i++)
{
int x=F[u][i]*i;
F[u][]=Max(F[u][],x);
}
}
int main()
{
scanf("%d",&n);
memset(head,-,sizeof(head));
for (int i=;i<n;i++)
{
scanf("%d%d",&u,&v);
Add(u,v),Add(v,u);
}
Dfs(,);
printf("%d\n",F[][]);
return ;
}
C++
需要高精度.
用F[i][s]表示考虑以i为根的子树，且i所属的连通块大小是s时的最大值
转移：对于i的每个孩子j，枚举k，用dp[j][k]∗dp[i][s]去更新dp[i][s+k]即可.