A Prefix Sum Primes
显然，除了 2 以外的质数都是奇数，所以最优的排布方式应该是 21222222.... 然后 2 不够的时候再放 1
code:
#include <bits/stdc++.h>
#define N 200009
#define setIO(s) freopen(s".in","r",stdin)
using namespace std;
int vis[N],prime[N],cnt;
void init()
{
int i,j;
for(i=2;i<N;++i)
{
if(!vis[i]) prime[++cnt]=i;
for(j=1;j<=cnt&&i*prime[j]<N;++j)
{
vis[i*prime[j]]=1;
if(i%prime[j]==0)
break;
}
}
}
int main()
{
// setIO("input");
// init();
int n,a1=0,a2=0,i,j;
scanf("%d",&n);
for(i=1;i<=n;++i)
{
int x;
scanf("%d",&x);
if(x==1)
++a1;
else
++a2;
}
if(!a2)
{
for(i=1;i<=n;++i) printf("%d ",1);
}
else
{
printf("%d ",2),--a2;
if(a1) printf("%d ",1),--a1;
while(a2) printf("%d ",2),--a2;
while(a1) printf("%d ",1),--a1;
}
return 0;
}
B Three Religions
有一个朴素的dp : $f[i][a][b][c]$ 表示母串匹配到 $i$，三个子串分别匹配了长度为 $a,b,c$
然后我们发现我们可以将状态改为 $f[a][b][c]$ 表示三个子串匹配到 $a,b,c$ 时母串的最小位置，然后开一个 $next[pos][c]$ 来转移.
code:
#include <bits/stdc++.h>
#define ll long long
#define MAX 100300
#define setIO(s) freopen(s".in","r",stdin)
using namespace std;
int n,Q;
char s[MAX],a[4][MAX];
int nxt[MAX][26],lst[26],len[4],f[255][255][255];
void dp(int x,int y,int z)
{
if(!(x|y|z))
return;
f[x][y][z]=n+1;
if(x&&f[x-1][y][z]<=n)
f[x][y][z]=min(f[x][y][z],nxt[f[x-1][y][z]][a[1][x]-97]);
if(y&&f[x][y-1][z]<=n)
f[x][y][z]=min(f[x][y][z],nxt[f[x][y-1][z]][a[2][y]-97]);
if(z&&f[x][y][z-1]<=n)
f[x][y][z]=min(f[x][y][z],nxt[f[x][y][z-1]][a[3][z]-97]);
}
int main()
{
// setIO("input");
int i,j;
scanf("%d%d%s",&n,&Q,s+1);
for(i=0;i<26;++i) lst[i]=n+1;
for(i=n;i>=0;--i)
{
for(j=0;j<26;++j) nxt[i][j]=lst[j];
if(i) lst[s[i]-97]=i;
}
while(Q--)
{
int x;
char ch[2],ss[2];
scanf("%s%d",ch,&x);
if(ch[0]=='+')
{
scanf("%s",ss);
a[x][++len[x]]=ss[0];
if(x==1)
{
for(i=0;i<=len[2];++i)
for(j=0;j<=len[3];++j)
dp(len[1],i,j);
}
if(x==2)
{
for(i=0;i<=len[1];++i)
for(j=0;j<=len[3];++j)
dp(i,len[2],j);
}
if(x==3)
{
for(i=0;i<=len[1];++i)
for(j=0;j<=len[2];++j)
dp(i,j,len[3]);
}
}
else
--len[x];
if(f[len[1]][len[2]][len[3]]<=n)
printf("YES
");
else
printf("NO
");
}
return 0;
}
C Tree Generator™
将左括号看成 $1$，右括号看成 $-1$.
我们发现答案是最大的一个连续子段的后半部分减去前半部分的值.
然后这个东西用线段树维护就行.
code:
#include <bits/stdc++.h>
#define ll long long
#define setIO(s) freopen(s".in","r",stdin)
using namespace std;
#define N 200400
#define lson (now<<1)
#define rson (now<<1|1)
int n,Q;
char str[N];
struct node {
int pre[2],suf[2],ans,sum,tot;
}s[N<<2],L,R;
node operator+(node a,node b)
{
node c;
c.pre[0]=max(a.pre[0],a.sum+b.pre[0]);
c.pre[1]=max(a.pre[1],max(a.tot+b.pre[0],-a.sum+b.pre[1]));
c.suf[0]=max(b.suf[0],-b.sum+a.suf[0]);
c.suf[1]=max(b.suf[1],max(b.tot+a.suf[0],b.sum+a.suf[1]));
c.sum=a.sum+b.sum;
c.tot=max(a.tot+b.sum,-a.sum+b.tot);
c.ans=max(max(a.ans,b.ans),max(a.suf[0]+b.pre[1],a.suf[1]+b.pre[0]));
return c;
}
void modify(int now,int l,int r,int p)
{
if(l==r)
{
s[now]=(str[p]=='(')?L:R;
return;
}
int mid=(l+r)>>1;
if(p<=mid)
modify(lson,l,mid,p);
else
modify(rson,mid+1,r,p);
s[now]=s[lson]+s[rson];
}
int main()
{
// setIO("input");
int i,j;
L=(node){1,1,0,1,1,1,1};
R=(node){0,1,1,1,1,-1,1};
scanf("%d",&n);
n=((n-1)<<1);
scanf("%d",&Q);
scanf("%s",str+1);
for(i=1;i<=n;++i) modify(1,1,n,i);
printf("%d
",s[1].ans);
while(Q--)
{
int x,y;
scanf("%d%d",&x,&y);
swap(str[x],str[y]);
modify(1,1,n,x),modify(1,1,n,y);
printf("%d
",s[1].ans);
}
return 0;
}