T1string
T1开的不错，看到这个题很激动，类似与HEOI2016排序，好像还要更简单一些，于是迅速冲了个桶排。因为洛谷上排序那道题是用桶排水的，所以我觉得没必要打线段树了，极端大数据20秒冲过，心想还行，起码80左右。
其实想的都挺美好哈哈，种种原因之下吧，桶排竟然跟垃圾快排拿一个分。。。。好吧，还是疏忽了。
线段树就是很基础的板子，记录区间覆盖，及时up down ，最后递归输出就好。唯一的细节是注意好update时每个字母对应的区间端点不要搞错了，别的废话就不多说了。
code
#include<bits/stdc++.h>
#define re register
using namespace std;
char a[100010];
int f[27],n,m;
struct zxb
{int l,r,ji;}tree[400010];
namespace AYX
{ inline void pushup(int x){if(tree[x<<1].ji==tree[x<<1|1].ji)tree[x].ji=tree[x<<1].ji;}
inline void pushdown(int x){if(tree[x].ji)tree[x<<1].ji=tree[x<<1|1].ji=tree[x].ji;tree[x].ji=0;}
inline void build(int x,int l,int r)
{ if(l==r)
{ tree[x].ji=a[l]-'a'+1;
return;
}
int mid=(l+r)>>1;
build(x<<1,l,mid);
build(x<<1|1,mid+1,r);
pushup(x);
}
inline void query(int x,int l,int r,int L,int R)
{ if(l>=L and r<=R and tree[x].ji)
{f[tree[x].ji]+=r-l+1;return;}
pushdown(x);
int mid=(l+r)>>1;
if(mid>=L)query(x<<1,l,mid,L,R);
if(mid<R)query(x<<1|1,mid+1,r,L,R);
}
inline void update(int x,int l,int r,int L,int R,int j)
{ if(l>=L and r<=R){tree[x].ji=j;return;}
pushdown(x);
int mid=(l+r)>>1;
if(mid<R)update(x<<1|1,mid+1,r,L,R,j);
if(mid>=L)update(x<<1,l,mid,L,R,j);
}
inline void p(int x,int l,int r)
{ if(tree[x].ji){for(int i=l;i<=r;++i)putchar(tree[x].ji+'a'-1);return;}
int mid=(l+r)>>1;
p(x<<1,l,mid);
p(x<<1|1,mid+1,r);
}
inline short main()
{ //freopen("c.in","r",stdin);
scanf("%d%d",&n,&m);
scanf("%s",a+1);
build(1,1,n);
while(m--)
{ int l,r,opt,sum=0;
scanf("%d%d%d",&l,&r,&opt);
memset(f,0,sizeof(f));
query(1,1,n,l,r);sum=l;
if(opt==1)
{
for(int i=1;i<=26;++i)
if(f[i])update(1,1,n,sum,sum+f[i]-1,i),sum+=f[i];
}
else
{ for(int i=26;i;--i)
if(f[i])update(1,1,n,sum,sum+f[i]-1,i),sum+=f[i];
}
}
p(1,1,n);
}
}
signed main()
{return AYX::main();}
T2matrix
一道计数DP，不得不说，出题人的思路太妙了。
矩阵放数，有限制，那就来枚举限制。本体一个很棘手的问题是l和r区间有重合，根本没法搞，这也启示我们要在对应区间上做文章。先从一边开始，我在第i列，而有j列填了右区间。这样的状态有三种转移，一是向后走但不填数，直接加上就好（f[i+1][j]+=f[i][j])二是在填一个属于右区间的数，f[i+1][j+1]=f[i][j]* (r[i+1]-j);这个很容易理解，前面已经填了j个，我新增的这一个就是端点位于i左侧除去填过的j个后的任意一个。三是要满足i自身以内左端点要搞完，要填的数就是l[i]-l[i-1] 而总共有i-j-l[i-1]个位置，要乘上组合数A。
三个方程一出，此题解决了80%。最后还要注意jc啦inv啦都要去线性递推，直接莽qpow的话会TLE.
code
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int mod=998244353;
int n,m,ll[100001],rr[100001],l[100001],r[100001],f[3001][3001],inv[10001],jc[10001];
namespace AYX
{ inline int qpow(int a,int b)
{ int base=1;
while(b)
{ if(b&1)base=base*a%mod;
a=a*a%mod;
b>>=1;
}
return base;
}
inline short main()
{ scanf("%lld%lld",&n,&m);
for(int i=1;i<=n;++i)scanf("%lld%lld",&ll[i],&rr[i]),++l[ll[i]],++r[rr[i]];
for(int i=1;i<=m;++i)l[i]+=l[i-1],r[i]+=r[i-1];
jc[0]=inv[0]=inv[1]=1;
for(int i=1;i<=m;++i)(jc[i]=jc[i-1]*i)%=mod,inv[i]=qpow(i,mod-2);
for(int i=1;i<=m;++i)(inv[i]*=inv[i-1])%=mod;
f[0][0]=1;
for(int i=0;i<=m;++i)
for(int j=0;j<=i;++j)
{ if(i)(f[i][j]*=((jc[i-j-l[i-1]]*inv[i-j-l[i]])%mod))%=mod;
(f[i+1][j]+=f[i][j])%=mod;
(f[i+1][j+1]+=f[i][j]*(r[i+1]-j)%mod)%=mod;
}
printf("%lld\n",f[m][n]);
}
}
signed main()
{return AYX::main();}
T3 big
一堆数异或，还有个足够聪明的人来卡你，这题真的很干。暴力求出前缀后缀，40pts是没问题的。暴力分给的不少。
与异或相关，明显是要使01trie。其实这道题很烦的就是那个式子(2x/2n+2*x)%(2n)，我们仔细分析，2x/2n是在干吗？乘以2是左移了一位，再除以2n，是在取二进制第n位，后面的%2^n是再截取n-1位。所以相当于整体左移，再把最高位干到最后，这个东西好像叫循环左移。
对手可以在任何情况下搞这莫一下，那我们先要求出改之后序列异或和是神魔样子。首先明确x循环左移后仍然互不相同，覆盖整个区间，所以没有必要讨论x。我们需要的是在不同位置考虑异或序列的值。对于异或，位与位之间相对独立，我们异或了所有数后左移和每个数左移后在异或是一样的，所以可以前缀和搞序列，然后扔进trie树里。
进树之后，只有一个儿子就向他跑，加上贡献，若有俩儿子就没有贡献，两个都跑，因为不论你选那一个，对手都可以选择另一个对应的断点操作，从而把你干废。
最后跑出一条路径后就update，直到跑完。
code
#include<bits/stdc++.h>
#define f() cout<<"fuck"<<endl
using namespace std;
int n,m,res,tot,a[300100],trie[4000100][2],ans[4000001],sum[1000001],mod;
namespace AYX
{ inline void add(int x)
{ int now=0;
for(int i=1;i<=n;++i)
{ int p=(x>>(n-i))&1;
if(!trie[now][p])trie[now][p]=++tot;
now=trie[now][p];
}
}
inline void dfs(int x,int dep,int sss)
{ if(dep<0)
{ans[++ans[0]]=sss;return;}
if(trie[x][0] and trie[x][1])
{ dfs(trie[x][0],dep-1,sss);
dfs(trie[x][1],dep-1,sss);
}
if(trie[x][0] and !trie[x][1])
{ sss^=(1<<dep);
dfs(trie[x][0],dep-1,sss);
}
if(trie[x][1] and !trie[x][0])
{ sss^=(1<<dep);
dfs(trie[x][1],dep-1,sss);
}
}
inline short main()
{ scanf("%d%d",&n,&m);mod=(1<<n);
for(int i=1;i<=m;++i)scanf("%d",&a[i]);
sum[m]=a[m];
for(int i=m-1;i>=1;--i)sum[i]=a[i]^sum[i+1];
for(int i=0;i<=m;++i)
{ res^=((a[i]*2/mod+a[i]*2)%mod);
add(res^sum[i+1]);
}
dfs(0,n-1,0);
sort(ans+1,ans+1+ans[0]);
int maxn=ans[ans[0]],ji=0;
for(int i=ans[0];i;--i)
if(ans[i]==maxn)++ji;
else break;
printf("%d\n%d\n",maxn,ji);
return 0;
}
}
signed main()
{return AYX::main();}
T4 所驼门王的宝藏
tarjan大水题，然而我不会。。。板子早忘得差不多了，今天终于复习了一下。
本题就是建边麻烦，O(n)的话是构造出几个假点，代表一行或一列，然后就用门都连这个点，建图就完成了。
剩下的就是套路缩点+DAG+DP，这是纯板子。
code
#include<bits/stdc++.h>
using namespace std;
int n,r,c,hd[10000001],head[10000001],to[10000001],toto[10000001],nxt[10000001],ext[10000001],dp[10000001],f[10000001],id[10000001],dfn[10000001],low[10000010],xx[10010000],yy[10000100],du[10000010],tot,cnt,lll,ppp,zhan[10000010],top,cnt1,hh[10000001];
int dx[10]={-1,-1,-1,0,0,1,1,1},dy[10]={-1,0,1,-1,1,-1,1,0};
map <pair<int ,int >,int >cao;
namespace AYX
{ inline void tarjan(int x)
{ low[x]=dfn[x]=++ppp;
zhan[++top]=x;
for(int i=head[x];i;i=nxt[i])
{ int v=toto[i];
if(!dfn[v])
{ tarjan(v);
low[x]=min(low[v],low[x]);
}
else if(!id[v])low[x]=min(low[x],dfn[v]);
}
if(dfn[x]==low[x])
{ id[x]=++tot;
hh[id[x]]=f[x];
while(zhan[top]!=x)
{ id[zhan[top]]=id[x];
hh[id[x]]+=f[zhan[top]];
--top;
}
top--;
}
}
inline void add(int u,int v)
{ toto[++cnt]=v;
nxt[cnt]=head[u];
head[u]=cnt;
}
inline void addaa(int u,int v)
{ to[++cnt1]=v;
ext[cnt1]=hd[u];
hd[u]=cnt1;
}
inline short main()
{ scanf("%d%d%d",&n,&r,&c);
for(int i=1;i<=n;++i)
{ f[r+c+i]=1;
int x,y,z;
scanf("%d%d%d",&x,&y,&z);
add(x,r+c+i);add(y+r,r+c+i);
if(z==1)add(r+c+i,x);
if(z==2)add(r+c+i,y+r);
if(z==3)xx[i]=x,yy[i]=y;
cao[make_pair(x,y)]=i;
}
for(int i=1;i<=n;++i)
if(xx[i])for(int j=0;j<8;++j)if(cao[make_pair(xx[i]+dx[j],yy[i]+dy[j])])add(r+c+i,cao[make_pair(xx[i]+dx[j],yy[i]+dy[j])]+c+r);
for(int i=1;i<=n+r+c;++i)if(!dfn[i])tarjan(i);
for(int i=1;i<=n+r+c;++i)
for(int j=head[i];j;j=nxt[j])
{ int v=toto[j];
if(id[i]!=id[v])
{ addaa(id[i],id[v]);
++du[id[v]];
}
}
queue<int >q;
for(int i=1;i<=tot;++i)if(!du[i])q.push(i),dp[i]=hh[i];
while(!q.empty())
{ int x=q.front();q.pop();
for(int i=hd[x];i;i=ext[i])
{ int v=to[i];
dp[v]=max(dp[v],dp[x]+hh[v]);
--du[v];
if(!du[v])q.push(v);
}
}
int ans=0;
for(int i=1;i<=tot;++i)
ans=max(ans,dp[i]);
printf("%d\n",ans);
return 0;
}
}
signed main()
{return AYX::main();}