A
容易发现i,i+1至少有一个数出现，于是可以让尽量多的2和奇数出现
#include<bits/stdc++.h>
using namespace std;
int n,s1,s2;
int main()
{
scanf("%d",&n);
for(int i=,x;i<=n;i++)
{
scanf("%d",&x);
if(x==)s1++;else s2++;
}
if(s1==)
{
if(!s2)printf("");
else{
printf("2 1");
for(int i=;i<s2;i++)printf("");
}
}
else if(s1&)
{
for(int i=;i<=s1;i++)printf("1 ");
for(int i=;i<=s2;i++)printf("2 ");
}
else if(s1!=)
{
for(int i=;i<s1;i++)printf("1 ");
for(int i=;i<=s2;i++)printf("2 ");
if(s1)printf("");
}
else{
if(!s2)printf("1 1");
else{
printf("2 1 ");
for(int i=;i<s2;i++)printf("2 ");
printf("");
}
}
}
B
设f[i][j][k]表示第1个串匹配到i，第2个串匹配到j，第3个串匹配到k所用的最小长度，然后每次添加一个字符可以O(250^2)转移另外两维的状态即可。
复杂度：O(q250^2)，我比赛时写了个多余的二分变为O(q250^2*logn)，不过评测机快+复杂度不满，实测也能通过，手算在1e9以内就没改了
多个log的code
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+;
int n,q,la,lb,lc,p[N],sum[N][],f[][][];
char s[N],a[N],b[N],c[N];
int find(int v,int pos)
{
if(pos>n)return 1e9;
if(sum[n][v]-sum[pos-][v]==)return 1e9;
int L=pos,R=n,mid,ret=1e9;
while(L<=R)
{
mid=L+R>>;
if(sum[mid][v]-sum[pos-][v]==)L=mid+;
else R=mid-,ret=mid;
}
return ret;
}
void del1()
{
for(int i=;i<=lb;i++)
for(int j=;j<=lc;j++)
f[la][i][j]=1e9;
la--;
}
void del2()
{
for(int i=;i<=la;i++)
for(int j=;j<=lc;j++)
f[i][lb][j]=1e9;
lb--;
}
void del3()
{
for(int i=;i<=la;i++)
for(int j=;j<=lb;j++)
f[i][j][lc]=1e9;
lc--;
}
void add1()
{
la++;cin>>a[la];
p[n+]=1e9;
for(int i=n;i>=;i--)if(s[i]==a[la])p[i]=i;else p[i]=p[i+];
for(int i=;i<=lb;i++)
for(int j=;j<=lc;j++)
if(f[la-][i][j]<1e9)
f[la][i][j]=p[f[la-][i][j]+];
else f[la][i][j]=1e9;
for(int i=;i<=lb;i++)
for(int j=;j<=lc;j++)
if(f[la][i][j]<1e9)
{
int pos=i<lb?find(b[i+]-'a',f[la][i][j]+):1e9;
if(pos<1e9)f[la][i+][j]=min(f[la][i+][j],pos);
pos=j<lc?find(c[j+]-'a',f[la][i][j]+):1e9;
if(pos<1e9)f[la][i][j+]=min(f[la][i][j+],pos);
}
}
void add2()
{
lb++;cin>>b[lb];
p[n+]=1e9;
for(int i=n;i>=;i--)if(s[i]==b[lb])p[i]=i;else p[i]=p[i+];
for(int i=;i<=la;i++)
for(int j=;j<=lc;j++)
if(f[i][lb-][j]<1e9)
f[i][lb][j]=p[f[i][lb-][j]+];
else f[i][lb][j]=1e9;
for(int i=;i<=la;i++)
for(int j=;j<=lc;j++)
if(f[i][lb][j]<1e9)
{
int pos=i<la?find(a[i+]-'a',f[i][lb][j]+):1e9;
if(pos<1e9)f[i+][lb][j]=min(f[i+][lb][j],pos);
pos=j<lc?find(c[j+]-'a',f[i][lb][j]+):1e9;
if(pos<1e9)f[i][lb][j+]=min(f[i][lb][j+],pos);
}
}
void add3()
{
lc++;cin>>c[lc];
p[n+]=1e9;
for(int i=n;i>=;i--)if(s[i]==c[lc])p[i]=i;else p[i]=p[i+];
for(int i=;i<=la;i++)
for(int j=;j<=lb;j++)
if(f[i][j][lc-]<1e9)
f[i][j][lc]=p[f[i][j][lc-]+];
else f[i][j][lc]=1e9;
for(int i=;i<=la;i++)
for(int j=;j<=lb;j++)
if(f[i][j][lc]<1e9)
{
int pos=i<la?find(a[i+]-'a',f[i][j][lc]+):1e9;
if(pos<1e9)f[i+][j][lc]=min(f[i+][j][lc],pos);
pos=j<lb?find(b[j+]-'a',f[i][j][lc]+):1e9;
if(pos<1e9)f[i][j+][lc]=min(f[i][j+][lc],pos);
}
}
int main()
{
scanf("%d%d",&n,&q);
scanf("%s",s+);
for(int i=;i<=n;i++)
for(int j=;j<;j++)
sum[i][j]=sum[i-][j]+(j==s[i]-'a');
for(int i=;i<=;i++)
for(int j=;j<=;j++)
for(int k=;k<=;k++)
f[i][j][k]=1e9;
f[][][]=;
while(q--)
{
char ch;int x;
cin>>ch>>x;
if(ch=='+')
{
if(x==)add1();
else if(x==)add2();
else add3();
}
else if(x==)del1();
else if(x==)del2();
else del3();
if(f[la][lb][lc]==1e9)puts("NO");
else puts("YES");
}
}
C
一眼看还以为是动态DP，死都想不出方程，懵了。发现根本不是的，mdzz
据说是ZJOI2007捉迷藏的第二种做法？详见http://www.shuizilong.com/house/archives/bzoj-1095-zjoi2007hide-%E6%8D%89%E8%BF%B7%E8%97%8F/?tdsourcetag=s_pcqq_aiomsg
然后发现答案是将(视为1，)视为0后，求选择序列一段区间并将其分成两段后，后一段减去前一段的最大值即为直径，即求max{s[x3]-2s[x2]+s[x1]}，其x1<=x2<=x3，然后可以做线段树，维护5个变量，s[rt]表示节点区间和，tr[rt][0]表示区间答案，tr[rt][1/2]表示最大/小前缀和，tr[rt][3]表示取过x1次后-2s[x2]+s[x1]的最大值，tr[rt][4]表示取过x2后的答案，直接暴力统计在哪一段即可。
#include<bits/stdc++.h>
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
using namespace std;
const int N=2e5+;
int n,q,a[N],s[N<<],tr[N<<][];
char str[N];
void modify(int rt,int v){tr[rt][]=,s[rt]=tr[rt][]=tr[rt][]=v,tr[rt][]=tr[rt][]=-v;}
void pushup(int rt)
{
int lc=rt<<,rc=rt<<|;
s[rt]=s[lc]+s[rc];
tr[rt][]=max(max(tr[lc][],tr[rc][]),max(tr[lc][]+s[lc]+tr[rc][],tr[lc][]-s[lc]+tr[rc][]));
tr[rt][]=max(tr[lc][],s[lc]+tr[rc][]);
tr[rt][]=min(tr[lc][],s[lc]+tr[rc][]);
tr[rt][]=max(max(tr[lc][],tr[rc][]-s[lc]),tr[lc][]-*(tr[rc][]+s[lc]));
tr[rt][]=max(max(tr[lc][],tr[rc][]-s[lc]),tr[rc][]+s[lc]-*tr[lc][]);
}
void build(int l,int r,int rt)
{
if(l==r){if(l)modify(rt,a[l]);return;}
int mid=l+r>>;
build(lson),build(rson);
pushup(rt);
}
void update(int k,int v,int l,int r,int rt)
{
if(l==r){modify(rt,v);return;}
int mid=l+r>>;
if(k<=mid)update(k,v,lson);else update(k,v,rson);
pushup(rt);
}
int main()
{
scanf("%d%d",&n,&q),n=(n-)*;
scanf("%s",str+);
for(int i=;i<=n;i++)a[i]=str[i]=='('?:-;
build(,n,);
printf("%d\n",tr[][]);
while(q--)
{
int x,y;scanf("%d%d",&x,&y);
if(a[x]!=a[y])update(x,a[y],,n,),update(y,a[x],,n,),swap(a[x],a[y]);
printf("%d\n",tr[][]);
}
}
D
这题的思路也很神，首先看到n<=70，肯定不是什么常规做法……首先可以连长为A的边形成若干连通块，然后跑一遍最短路，记录连通块经过的状态，保证走长为B的边不经过相同的连通块，由于连通块大小为1的不需要记录，所以可以做到O(35n*2^35*logn)，这个显然会T飞掉，但是还有更多的连通块也不需要记录，因为它们不会通过走长为B的边绕回来，就是连通块大小为2、3的连通块，因为绕回来的长度最短为2B，而A<2B（大小为2的），2A<2B（大小为3的）。于是只需要记录>=4的连通块即可，复杂度O(17n*2^17logn)，显然不会TLE
#include<bits/stdc++.h>
using namespace std;
const int N=,M=;
struct node{int u,d,S;};
int n,m,cnt,tot,A,B,hd[N],v[],nxt[],w[],f[N],sz[N],bel[N],d[N][M];
bool vis[N][M];
bool operator<(node a,node b){return a.d>b.d;}
priority_queue<node>q;
void adde(int x,int y,int z){v[++cnt]=y,w[cnt]=z,nxt[cnt]=hd[x],hd[x]=cnt;}
int find(int x){return x==f[x]?x:f[x]=find(f[x]);}
void modify(int u,int dis,int S){if(d[u][S]>dis)d[u][S]=dis,q.push((node){u,dis,S});}
int main()
{
scanf("%d%d%d%d",&n,&m,&A,&B);
for(int i=;i<=n;i++)f[i]=i,sz[i]=,bel[i]=-;
for(int i=,x,y,z;i<=m;i++)
{
scanf("%d%d%d",&x,&y,&z),adde(x,y,z),adde(y,x,z);
if(z==A)
{
x=find(x),y=find(y);
if(x!=y)f[y]=x,sz[x]+=sz[y];
}
}
for(int i=;i<=n;i++)
if(bel[i]==-&&sz[find(i)]>)
{
for(int j=i;j<=n;j++)if(find(i)==find(j))bel[j]=tot;
++tot;
}
for(int i=;i<=n;i++)
for(int j=;j<(<<tot);j++)
d[i][j]=1e9;
modify(,,(~bel[])?<<bel[]:);
while(!q.empty())
{
int u=q.top().u,S=q.top().S;q.pop();
if(vis[u][S])continue;
vis[u][S]=;
for(int i=hd[u];i;i=nxt[i])
if(w[i]==A)modify(v[i],d[u][S]+w[i],S);
else if(find(u)!=find(v[i])&&(bel[v[i]]==-||!(S>>bel[v[i]]&)))
modify(v[i],d[u][S]+w[i],S|((~bel[v[i]])?<<bel[v[i]]:));
}
for(int i=,ret;i<=n;i++)
{
ret=1e9;
for(int j=;j<(<<tot);j++)ret=min(ret,d[i][j]);
printf("%d ",ret);
}
}
E
首先一看博弈论，也想不出什么重大结论，就猜是SG函数。然后结论是对所有sg=i的点，令s[k]为所有sg[i]=k的h[i]异或起来的值，若存在s[k]!=0则先手必胜，反之必败。
#include<bits/stdc++.h>
using namespace std;
const int N=2e5+;
int n,m,h[N],q[N],d[N],s[N],vis[N],sg[N];
vector<int>G[N];
int main()
{
scanf("%d%d",&n,&m);
for(int i=;i<=n;i++)scanf("%d",&h[i]);
for(int i=,x,y;i<=m;i++)scanf("%d%d",&x,&y),G[x].push_back(y),d[y]++;
int qs=,qe=;
for(int i=;i<=n;i++)if(!d[i])q[qe++]=i;
while(qs<qe)
{
int u=q[qs++];
for(int i=;i<G[u].size();i++)if(!--d[G[u][i]])q[qe++]=G[u][i];
}
for(int i=n;i;i--)
{
int u=q[i];
for(int j=;j<G[u].size();j++)vis[sg[G[u][j]]]=i;
while(vis[sg[u]]==i)sg[u]++;
s[sg[u]]^=h[u];
}
for(int i=n,u;~i;i--)
if(s[i])
{
for(int j=;j<=n;j++)if(sg[j]==i&&h[j]>(s[i]^h[j]))u=j;
h[u]^=s[i];
for(int j=;j<G[u].size();j++)h[G[u][j]]^=s[sg[G[u][j]]],s[sg[G[u][j]]]=;
puts("WIN");
for(int j=;j<=n;j++)printf("%d ",h[j]);
puts("");
return ;
}
puts("LOSE");
}
result：rank206 rating+=36，手速慢了，没上2200，水平低啊……