哎，今天第一次打div1 感觉头脑很不清醒。。。
看到第一题就蒙了，想了好久，怎么乱dp，倒过来插之类的...突然发现不就是一道sb二分吗.....sb二分看了二十分钟........
然后第二题看了一下，感觉太码农了不可做，然后就cd逛一逛。
突然觉得c可做，就做了一下，交上去wa了，发现有情况没考虑。
这下又滚回了b，结果又没写完......
gg 2040 -83 ->1957
-----------------------------------------------我似分割线啊
A.String Game
题意：有一个n个字符组成的字符串，并给定它的一个子串。调皮的小孩一个人会按照时间顺序每一秒删掉其中一个字符，求一个最迟的时间，使得给定的串仍然是剩下的字符串的子串。n<=200000
题解：别想太多，直接二分答案，On 来check一下。
复杂度nlogn
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #include<queue> #define ll long longh #define INF 2000000000 #define MAXN 200000 using namespace std; int read() { int x=0,f=1;char ch=getchar(); while(ch<‘0‘||ch>‘9‘){if(ch==‘-‘) f=-1;ch=getchar();} while(ch>=‘0‘&&ch<=‘9‘){x=x*10+ch-‘0‘; ch=getchar();} return x*f; } char s2[MAXN+5]; char s[MAXN+5]; int n,m; int a[MAXN+5]; int p[MAXN+5]; bool check(int x) { int j=1; for(int i=1;i<=n&&j<=m;i++) if(p[i]>x&&s[i]==s2[j]) ++j; if(j>m) return true; return false; } int main() { scanf("%s",s+1); scanf("%s",s2+1); n=strlen(s+1);m=strlen(s2+1); for(int i=1;i<=n;i++) { a[i]=read(); p[a[i]]=i; } int l=0,r=n,mid,ans; while(l<=r) { mid=(l+r)>>1; if(check(mid)) ans=mid,l=mid+1; else r=mid-1; } cout<<ans; return 0; }
B.Bitwise Formula
题意：给定n个变量的定义，每个变量都是m位的二进制数，你可以选择一个数，这些变量在定义的时候可能会用到之前的变量和你选择的数，最后的贡献为所有的变量大小之和。你要分别在贡献最大和最小的情况下，选择最小的数字。
n<=5000 m<=1000
题解：贪心。对每一位分别check()，枚举那一位选择1或者0，算一下这一位上的贡献，确定取值即可。复杂度nm
我的代码丑
#include<iostream> #include<cstdio> #include<algorithm> #include<queue> #include<cstring> #include<map> #define ID 20170226 #define ll long long using namespace std; inline int read() { int x=0,f=1;char ch=getchar(); while(ch<‘0‘||ch>‘9‘){if(ch==‘-‘) f=-1;ch=getchar();} while(ch>=‘0‘&&ch<=‘9‘){x=x*10+ch-‘0‘; ch=getchar();} return x*f; } string st,st2,name; map<string,int> mp; char s[10000]; int mark[5005][3]; int x[5005][1005],x2[5005][1005]; int n,m,ans[5005]; char op[5005]; int f[5005]; int check(int j,int def) { int x1,y1,tot=0; for(int i=1;i<=n;i++) { if(mark[i][1]==ID) x1=x[i][j]; else if(mark[i][1]==-1) x1=def; else x1=f[mark[i][1]]; if(mark[i][2]==ID)y1=x2[i][j]; else if(mark[i][2]==-1) y1=def; else y1=f[mark[i][2]]; // cout<<i<<" "<<j<<" "<<x1<<" "<<y1<<endl; if(op[i]==‘O‘) x1=x1|y1; if(op[i]==‘A‘) x1=x1&y1; if(op[i]==‘X‘) x1=x1^y1; f[i]=x1;tot+=x1; } return tot; } int main() { n=read();m=read(); for(int i=1;i<=n;i++) { int nown=0; cin>>name;mp[name]=i; scanf("%s",s);cin>>st; if(getchar()!=‘\n‘) { scanf("%s",s); cin>>st2; if(st2=="?") mark[i][2]=-1; else if(st2[0]>=‘0‘&&st2[0]<=‘9‘) { mark[i][2]=ID;for(int j=0;j<m;j++) x2[i][j]=st2[j]-‘0‘;} else mark[i][2]=mp[st2]; op[i]=s[0]; } else mark[i][2]=ID,op[i]=‘O‘; if(st=="?") mark[i][1]=-1; else if(st[0]>=‘0‘&&st[0]<=‘9‘) { mark[i][1]=ID;for(int j=0;j<m;j++) x[i][j]=st[j]-‘0‘;} else mark[i][1]=mp[st]; } for(int i=0;i<m;i++) { int x=check(i,0);int y=check(i,1); if(x>y) printf("1"); else if(x==y) printf("0"); else printf("0"),ans[i]=1; } puts(""); for(int i=0;i<m;i++)printf("%d",ans[i]); return 0; }
C.给定一棵trie树，你可以删掉其中一个深度的点，求重建的trie树最少有多少个点以及最少时删掉哪一个深度。
题解：如图：
我们可以发现，删掉一个深度之后减少的点的数量不仅仅是这个深度的节点的数量，还包括这个 深度的爸爸相同(1)的点 (2,3) 的相同字母(c) 的边指向的点(5,4)
这个例子中4和5可以合成一个点，实际上减少的部分还包括了4和5的相同字母的边指向的点，以此类推。
所以我们可以考虑在dfs的时候直接暴力算每个点的可合并孙子的个数，并且加入对应深度的答案当中，然后递归下去做。
具体实现见代码（向cf的一些dalao学习的）
#include<iostream> #include<cstdio> #include<algorithm> #include<queue> #include<cstring> #include<map> #define MAXN 600000 using namespace std; inline int read() { int x=0,f=1;char ch=getchar(); while(ch<‘0‘||ch>‘9‘){if(ch==‘-‘) f=-1;ch=getchar();} while(ch>=‘0‘&&ch<=‘9‘){x=x*10+ch-‘0‘; ch=getchar();} return x*f; } int n,m; int c[MAXN+5][26]; char ch; int sum[MAXN+5]; int newnode(int x) { for(int i=0;i<26;i++) c[m][i]=c[x][i]; return m++; } void merge(int&x,int y,int dep) { if(!x||!y){x+=y;return;} x=newnode(x);++sum[dep]; for(int i=0;i<26;i++)merge(c[x][i],c[y][i],dep); } void dfs(int x,int dep) { sum[dep-1]++;int nown=0;m=n+1; for(int i=0;i<26;i++,nown=0) for(int j=0;j<26;j++) if(c[c[x][j]][i]) merge(nown,c[c[x][j]][i],dep); for(int i=0;i<26;i++) if(c[x][i]) dfs(c[x][i],dep+1); } int main() { n=read(); for(int i=1;i<n;i++) { int u=read(),v=read();scanf("%c",&ch); c[u][ch-‘a‘]=v; } dfs(1,1);int ans=1; for(int i=1;i<=n;i++) if(sum[i]>sum[ans]) ans=i; printf("%d\n%d",n-sum[ans],ans); return 0; }
D.还不会，挖个坑
Codeforces Round#402(Div.1)掉分记
原文：http://www.cnblogs.com/FallDream/p/codeforces402.html