A题卡壳了，往离线倒着加那方面想了会儿，后来才发现方向错了，二十多分钟才过掉，过了B后做D，想法好像有点问题，最后只过两题，掉分了，差一点回紫。
AC:AB Rank:173 Rating:2227-23->2204
A.String Game
题目大意：给出字符串A和B，保证B是A的子序列，给出一个长度为A串长度的排列，问按排列的顺序删掉A串中字符，最多删几个使得B任然是A的子序列。（A串长度<=200,000）
思路：发现答案满足单调性，二分删几个，O(n)check一下B还是不是A的子序列，复杂度O(nlogn)。
#include<cstdio> inline int read() { int x;char c; while((c=getchar())<‘0‘||c>‘9‘); for(x=c-‘0‘;(c=getchar())>=‘0‘&&c<=‘9‘;)x=(x<<3)+(x<<1)+c-‘0‘; return x; } #define MN 200000 char a[MN+5],b[MN+5],s[MN+5]; int p[MN+5]; bool check(int x) { int i,j; for(i=0;a[i];++i)s[i]=a[i]; for(i=0;i<x;++i)s[p[i]-1]=‘ ‘; for(i=j=0;s[i]&&b[j];++i)if(s[i]==b[j])++j; return !b[j]; } int main() { int i,l=0,r,mid,ans; scanf("%s%s",a,b); for(r=0;a[r];++r)p[r]=read(); while(l<=r) { mid=l+r>>1; if(check(mid))ans=mid,l=mid+1; else r=mid-1; } printf("%d",ans); }
B.Bitwise Formula
题目大意：给出n条语句和语句中数字的二进制串长m，每条语句会新定义一个变量，并给它赋值，赋值语句有两种，一种给出一个长为m的二进制常量，另一种给出两个出现过的变量或"?"，以及一个位运算符（AND、OR、XOR）。所有"?"可以用同一个长为m的二进制串代替，问这个串最小为多少时，所有变量的和最大/最小。（N<=5000，M<=1000）
思路：二进制的每一位独立，分别枚举取0取1就可以了，复杂度O(nm)。
#include<cstdio> #include<iostream> #include<algorithm> #include<map> using namespace std; inline int read() { int x;char c; while((c=getchar())<‘0‘||c>‘9‘); for(x=c-‘0‘;(c=getchar())>=‘0‘&&c<=‘9‘;)x=(x<<3)+(x<<1)+c-‘0‘; return x; } #define MN 5000 #define MM 1000 map<string,int> mp; int n,a[MN+5][MM+5],cnt; int t[MN+5],ta[MN+5],tb[MN+5]; int aa[MM+5],bb[MM+5]; int f[MN+5]; int check(int p,int k) { int i,s=0; for(i=1;i<=n;++i) { if(!t[i])f[i]=a[i][p]; if(t[i]==1)f[i]=(ta[i]?f[ta[i]]:k)&(tb[i]?f[tb[i]]:k); if(t[i]==2)f[i]=(ta[i]?f[ta[i]]:k)|(tb[i]?f[tb[i]]:k); if(t[i]==3)f[i]=(ta[i]?f[ta[i]]:k)^(tb[i]?f[tb[i]]:k); s+=f[i]; } return s; } int main() { int m,i,j,x,y;string s; n=read();m=read(); for(i=1;i<=n;++i) { cin>>s;mp[s]=++cnt;cin>>s; cin>>s; if(s[0]==‘0‘||s[0]==‘1‘) { for(j=0;j<m;++j)a[i][j]=s[j]-‘0‘; continue; } ta[i]=s[0]==‘?‘?0:mp[s]; cin>>s; if(s[0]==‘A‘)t[i]=1; if(s[0]==‘O‘)t[i]=2; if(s[0]==‘X‘)t[i]=3; cin>>s; tb[i]=s[0]==‘?‘?0:mp[s]; } for(i=0;i<m;++i) { x=check(i,0);y=check(i,1); aa[i]=y<x;bb[i]=y>x; } for(i=0;i<m;++i)printf("%d",aa[i]);puts(""); for(i=0;i<m;++i)printf("%d",bb[i]); }
Codeforces Round #402 (Div. 1)
原文：http://www.cnblogs.com/ditoly/p/CF402.html