哎，今天第一次打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=,f=;char ch=getchar();
while(ch<''||ch>''){if(ch=='-') f=-;ch=getchar();}
while(ch>=''&&ch<=''){x=x*+ch-''; ch=getchar();}
return x*f;
} char s2[MAXN+];
char s[MAXN+];
int n,m;
int a[MAXN+];
int p[MAXN+]; bool check(int x)
{
int j=;
for(int i=;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+);
scanf("%s",s2+);
n=strlen(s+);m=strlen(s2+);
for(int i=;i<=n;i++)
{
a[i]=read();
p[a[i]]=i;
}
int l=,r=n,mid,ans;
while(l<=r)
{
mid=(l+r)>>;
if(check(mid)) ans=mid,l=mid+;
else r=mid-;
}
cout<<ans;
return ;
}
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=,f=;char ch=getchar();
while(ch<''||ch>''){if(ch=='-') f=-;ch=getchar();}
while(ch>=''&&ch<=''){x=x*+ch-''; ch=getchar();}
return x*f;
}
string st,st2,name;
map<string,int> mp;
char s[];
int mark[][];
int x[][],x2[][];
int n,m,ans[];
char op[];
int f[]; int check(int j,int def)
{
int x1,y1,tot=;
for(int i=;i<=n;i++)
{
if(mark[i][]==ID) x1=x[i][j];
else if(mark[i][]==-) x1=def;
else x1=f[mark[i][]];
if(mark[i][]==ID)y1=x2[i][j];
else if(mark[i][]==-) y1=def;
else y1=f[mark[i][]];
// 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=;i<=n;i++)
{
int nown=;
cin>>name;mp[name]=i;
scanf("%s",s);cin>>st;
if(getchar()!='\n')
{
scanf("%s",s);
cin>>st2;
if(st2=="?") mark[i][]=-;
else if(st2[]>=''&&st2[]<='')
{ mark[i][]=ID;for(int j=;j<m;j++) x2[i][j]=st2[j]-'';}
else mark[i][]=mp[st2];
op[i]=s[];
}
else mark[i][]=ID,op[i]='O';
if(st=="?") mark[i][]=-;
else if(st[]>=''&&st[]<='')
{ mark[i][]=ID;for(int j=;j<m;j++) x[i][j]=st[j]-'';}
else mark[i][]=mp[st]; }
for(int i=;i<m;i++)
{
int x=check(i,);int y=check(i,);
if(x>y) printf("");
else if(x==y) printf("");
else printf(""),ans[i]=;
}
puts("");
for(int i=;i<m;i++)printf("%d",ans[i]);
return ;
}
C.给定一棵trie树，你可以删掉其中一个深度的点，求重建的trie树最少有多少个点以及最少时删掉哪一个深度。
题解：如图：
我们可以发现，删掉一个深度之后减少的点的数量不仅仅是这个深度的节点的数量，还包括这个 深度的爸爸相同(1)的点 (2,3) 的相同字母(c) 的边指向的点(5,4)
这个例子中4和5可以合成一个点，实际上减少的部分还包括了4和5的相同字母的边指向的点，以此类推。
所以我们可以考虑在dfs的时候直接暴力算每个点的可合并孙子的个数，并且加入对应深度的答案当中，然后递归下去做。
具体实现见代码（向cf的一些dalao学习的）
复杂度是ditoly帮我证明的，这样做的复杂度，因为是两两合并，应该会严格小于启发式合并的复杂度，所以复杂度大概是26*n*logn
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<queue>
#include<cstring>
#include<map>
#define MAXN 600000
using namespace std;
inline int read()
{
int x=,f=;char ch=getchar();
while(ch<''||ch>''){if(ch=='-') f=-;ch=getchar();}
while(ch>=''&&ch<=''){x=x*+ch-''; ch=getchar();}
return x*f;
} int n,m;
int c[MAXN+][];
char ch;
int sum[MAXN+]; int newnode(int x)
{
for(int i=;i<;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=;i<;i++)merge(c[x][i],c[y][i],dep);
} void dfs(int x,int dep)
{
sum[dep-]++;int nown=;m=n+;
for(int i=;i<;i++,nown=)
for(int j=;j<;j++)
if(c[c[x][j]][i])
merge(nown,c[c[x][j]][i],dep);
for(int i=;i<;i++) if(c[x][i]) dfs(c[x][i],dep+);
} int main()
{
n=read();
for(int i=;i<n;i++)
{
int u=read(),v=read();scanf("%c",&ch);
c[u][ch-'a']=v;
}
dfs(,);int ans=;
for(int i=;i<=n;i++) if(sum[i]>sum[ans]) ans=i;
printf("%d\n%d",n-sum[ans],ans);
return ;
}
D.Parquet Re-laying
有两个n*m并由1*2的小矩形构成的图，每次可以把两个构成2*2的小矩形的块旋转一下（横的变成竖的，竖的变成横的）
要从第一个图变到第二个图，求一种方案。n,m<=50
很显然，不管图是什么样，都能转到全是横的 或者全是竖的 的情况，所以这道题其实没有无解...
所以把两个图都转成全是横的或者全是竖的情况，倒着输出第二个就没了.....
#include<iostream>
#include<cstdio>
using namespace std;
int read()
{
int x=,f=;char ch=getchar();
while(ch<''||ch>''){if(ch=='-') f=-;ch=getchar();}
while(ch>=''&&ch<=''){x=x*+ch-''; ch=getchar();}
return x*f;
} char s[][],s2[][],ch;
int n,m,cnt=;
struct ANS{
int x,y;
}A[]; bool check(char a[][])
{
for(int i=;i<=n;i++)
for(int j=;j<=m;j++)
if(a[i][j]==ch) return ;
return ;
} void solve(char a[][])
{
while()
{
bool ok=;
for(;ok;)
{
ok=;
for(int i=;i<n;i++)
for(int j=;j<m;j++)
if(a[i][j]=='L'&&a[i+][j]=='L')
{
ok=;A[++cnt]=(ANS){i,j};
a[i][j]='U';a[i+][j]='D';
a[i][j+]='U';a[i+][j+]='D';
}
}
if(check(a)) break;
for(ok=;ok;)
{
ok=;
for(int i=;i<n;i++)
for(int j=;j<m;j++)
if(a[i][j]=='U'&&a[i][j+]=='U')
{
ok=;A[++cnt]=(ANS){i,j};
a[i][j]='L';a[i+][j]='L';
a[i][j+]='R';a[i+][j+]='R';
}
}
if(check(a)) break;
}
} int main()
{
n=read();m=read();ch=n&?'U':'L';
for(int i=;i<=n;i++)scanf("%s",s[i]+);
for(int i=;i<=n;i++)scanf("%s",s2[i]+);
solve(s);int pre=cnt;
solve(s2);
cout<<cnt<<endl;
for(int i=;i<=pre;i++) printf("%d %d\n",A[i].x,A[i].y);
for(int i=cnt;i>pre;i--) printf("%d %d\n",A[i].x,A[i].y);
return ;
}
E.Selling Numbers
做题背景：今天（第二天，周一）下午和ditoly大佬切完了前四题之后准备看一看第五题，看了一下，发现好像比cd都可做？好像是个数位dp，但是不知道怎么做。
然后就去standing里面，发现只有30个左右的人过了，就开始一个个翻代码（没几个能看的），能看也看的懵逼，就得出了一个结论：它们都在排序。
然后就懵懵地去上体育课，想着想着，发现排序后进位连续，这样就可以表示状态了，于是就没了。
题目大意：给定n个最多1000位的十进制数，你可以选择一个数（有些位数是确定的），并把剩余的数都加上它，求贡献最大值。
贡献计算：每个数字都有一定的贡献值，每个数的贡献是它的所有数字的贡献值之和。
n<=1000
题解：很显然我们能够得到几个结论:
每一位分开计算->如果不考虑进位就是一道贪心->进位的处理是题目难点
怎么处理进位呢？我们发现 对于一个数的任意两位，假设是ab 和cd
如果a>c 那么a>=c+1,如果第二个数进位了，第一个也会进位
如果a==c，那么b>=d时也有同样的结论
所以我们可以把每一位都分别以这一位的数为第一关键字，后缀为第二关键字做一遍计数排序，
这样就能保证进位的部分肯定是连续的一段。
那么我们就可以用数位dp来计算结果了。
用f[i][j]表示后i位数字，第i位的前j个有进位的时候的最大答案。
先枚举数位，再枚举这一位选的数字，按照上一位的大小顺序，让它们一个个进位，同步更新答案。
f[i][j]=max(f[i-1][k]+合并的答案）并且第i位的数字加上上一位的k个进位，再加上这一位的选择的数字有j个进位
复杂度 10*n^2 (10*1000*1000)
然后代码丑
#include<iostream>
#include<cstdio>
#include<cstring>
#define INF 2000000000
using namespace std;
int read()
{
int x=,f=;char ch=getchar();
while(ch<''||ch>''){if(ch=='-')f=-;ch=getchar();}
while(ch>=''&&ch<=''){x=x*+ch-'';ch=getchar();}
return x*f;
}
int a[];
int n,m,len2;
int len[];
int b[];
char s[],s2[];
int x[][];
int f[][];
int sa[][];
int rk[][];
int v[];
void sort()
{
for(int i=;i<=n;i++) rk[][i]=INF;
for(int i=;i<=n;i++) sa[][i]=i;
for(int i=;i<=m;i++)
{
memset(v,,sizeof(v));
for(int j=;j<=n;j++) v[x[j][i]]++;
for(int j=;j>=;j--) v[j]+=v[j+];
for(int j=n;j;j--) rk[i][sa[i-][j]]=v[x[sa[i-][j]][i]]--;
for(int j=;j<=n;j++) sa[i][rk[i][j]]=j;
}
} int work(int k,int ad,int&tot)
{
int en=n,fn=,i;
for(register int ii=;ii<=n;ii++)
{
i=sa[k][ii];b[i]=;
int xx=x[i][k]+ad;
if(en==n&&xx<) en=ii-;
if(k>len2&&len[i]<k&&xx==) continue;
fn+=a[xx%];tot+=(xx>=);b[i]=xx;
}
if(f[k-][]>=) f[k][en]=max(f[k][en],f[k-][]+fn);
return fn;
} void ins(int i,int j,int ad,int&num,int&into)
{
int xx=x[j][i]+ad;
num=num-a[xx%]+a[(xx+)%];
if(i>len2&&i>len[j]&&b[j]==)
num+=a[xx%];
into+=(xx==);
} int main()
{
m=;
scanf("%s",s+);len2=strlen(s+);
for(int i=len2,j=;i;i--,j++) s2[j]=s[i];
for(int i=len2+;i<=m;i++) s2[i]='';
n=read();
for(int i=;i<=n;i++)
{
scanf("%s",s+);len[i]=strlen(s+);
for(int j=len[i],k=;j;j--,k++)
x[i][k]=s[j]-'';
}
for(int i=;i<;i++) a[i]=read();
sort();
for(int i=;i<=m;i++)
for(int j=;j<=n;j++) f[i][j]=-INF;
f[][]=;
for(register int i=;i<=m;i++)
{
if(s2[i]=='?')
{
for(register int th=;th<;th++)
{
if(th==&&i==len2) continue;
int into=;
int num=work(i,th,into);
for(register int j=;j<=n;j++)
{
ins(i,sa[i-][j],th,num,into);
if(f[i-][j]>=)
{
f[i][into]=max(f[i][into],f[i-][j]+num);
}
}
}
}
else
{
int th=s2[i]-'';
int into=;
int num=work(i,th,into);
for(register int j=;j<=n;j++)
{
ins(i,sa[i-][j],th,num,into);
if(f[i-][j]>=)
f[i][into]=max(f[i][into],f[i-][j]+num);
}
}
}
int ans=;
for(register int i=;i<=n;i++) ans=max(ans,f[m][i]+i*a[]);
printf("%d",ans);
return ;
}