这场是真的搞人心态…居然卡在B题，最后一分钟才过B2，人麻了

不过这次的题目质量还是挺高的，蛮有意思的一场div2

本场传送门

A

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=2e5+10;
int main(){
    int T;scanf("%d",&T);
    while(T--){
        int n;scanf("%d",&n);
		int p=0;
		for(int i=0;i<=n;i++){
			if((1<<i)>n){
				p=i-1;break;
			}
		}
		printf("%d\n",(1<<p)-1);
    }


    return 0;
}

B1&B2

yysy，如果不是这个B1题提示先考虑回文串，这道题绝对是E题难度…

先考虑B1这种特殊情况，假设初始是回文的01串要如何解决呢?

容易想到naive的贪心做法，即Alice能不花钱就不花钱，这样一来只需要考虑奇数，模4为0，模4为2的情况就行了。然后马上交一发————WA！

仔细思考后发现，贪心并不是最优的。比如，如果当n满足 n%2=0n\%2=0，且当BOB可以选择不花钱的时候，他其实可以选择继续花钱，这样能保证序列是对称的，从而让Alice在她的下一次操作必须选择花钱。这样一来，BOB在最后还剩两个0的时候再能不花钱就不花钱，这样就赢了Alice（如果按照贪心的方法，n为偶数并不能保证BOB一定会赢）。

剩下的对细节的讨论这里就不展开叙述了，直接上代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=2e5+10;
int n;
char s[maxn];
int main(){
    int T;scanf("%d",&T);
    while(T--){
        scanf("%d%s",&n,s);
		int cnt=0;
		for(int i=0;i<n;i++){
			if(s[i]=='0')cnt++;
		}
		if(cnt==1)printf("BOB\n");
		else if(cnt==3)printf("ALICE\n");
		else if(cnt%2){
			cnt--;
			if(cnt%2)printf("BOB\n");
			else printf("ALICE\n");
		}
		else {
			printf("BOB\n");
		}
    }
 
 
    return 0;
}

解决了特殊情况，开始考虑一般形式的求解

可以发现，如果BOB花钱把0变成1，应该要尽量将串变成回文才行，不然永远都是BOB花钱。

假设该串变成了回文串，Alice可以是先手，也可以在上一次操作中花一块钱让自己变成后手。

两种方案中对Alice更优的解即是答案

有趣的是，这道题的正解先用n2n^2的DP预处理，然后再O(1)O(1)查询。这样确实是直观多了，也不容易错。其实开始的时候我也是打算写记忆化搜索的，但是看到多组数据能达到1000之多，1e9的时间复杂度可能会超时就放弃了，忘了可以先预处理了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=2e5+10;
int n;
char s[maxn];
int a,b;
int main(){
    int T;scanf("%d",&T);
    while(T--){
        scanf("%d%s",&n,s);
		int cnt=0,flag=0;
		a=b=0;
		for(int i=0;i<n;i++){
			if(s[i]=='0')cnt++;
		}
		for(int i=0;i<n;i++){
			if(s[i]!=s[n-1-i])flag++;
			if(i==(n-1)/2)break;
		}
		cnt-=flag;
		if(cnt){
			if(cnt==1)b++;
			else if(cnt==3)a++;
			else if(cnt%2){
				cnt--;
				if(cnt%2)b++;
				else a++;
			}
			else b+=2;					
		}
		a+=flag;
		if(flag==0){
			if(a>b)printf("ALICE\n");
			else if(a<b)printf("BOB\n");
			else printf("DRAW\n");			
		}
		else {
			if(a>b)printf("ALICE\n");
			else {
				a-=flag;
				swap(a,b);
				b++;
				a+=flag-1;
				if(a>b)printf("ALICE\n");
				else if(a<b)printf("BOB\n");
				else printf("DRAW\n");					
			}
				
		}
    }
 
 
    return 0;
}

C

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=2e5+10;
map<int,int>mp;
int n,a[maxn],cnt;
int l[maxn],r[maxn],pos[maxn];
ll sum0[maxn],sum1[maxn];
int main(){
	int T;scanf("%d",&T);
	while(T--){
		scanf("%d",&n);cnt=0;
		for(int i=1;i<=n;i++)l[i]=0,r[i]=n,sum0[i]=0,sum1[i]=0;
		mp.clear();
		for(int i=1;i<=n;i++){
			scanf("%d",&a[i]);
			if(!mp.count(a[i])){
				mp[a[i]]=++cnt;
				pos[cnt]=i;
			}
			else l[i]=pos[mp[a[i]]],pos[mp[a[i]]]=i,r[l[i]]=i-1;
		}
		ll ans=0;
		for(int i=1;i<=n;i++){
			if(!l[i])continue;
			sum0[i]=l[i]+sum0[l[i]];
			sum1[i]=sum1[l[i]]+sum0[i];
			ans+=sum1[i]*(r[i]-i+1);
		}
		printf("%lld\n",ans);		
	}


    return 0;
}

D

分两种情况讨论，即MEX=0（不经过根节点）和MEX>0（必定经过根节点）

第一种情况很好求，接下来考虑第二种

对于MEX=i，直接求解十分复杂，于是转换思路

容易知道AnsMEX=i=AnsMEX≥i−AnsMEX>iAns_{MEX=i}=Ans_{MEX\geq i}-Ans_{MEX>i}

这样一来就简单多了，直接求路径中包含序列0,1,2,..,i−1,i0,1,2,..,i-1,i的(u,v)(u,v)总数就行了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=2e5+10;
int n,l,r,sonl;
vector<int>e[maxn];
ll sz[maxn],ans[maxn],sum;
ll vis[maxn];
int fa[maxn][20],dep[maxn];
void dfs1(int u,int p){
	sz[u]=1;
	fa[u][0]=p;
	for(auto v:e[u]){
		if(v==p)continue;
		dep[v]=dep[u]+1;
		dfs1(v,u);
		sz[u]+=sz[v];
	}
}
bool find(int top,int x){
	for(int i=19;i>=0;i--){
		if(fa[x][i]!=-1&&dep[fa[x][i]]>=dep[top])
			x=fa[x][i];
	}
	if(x==top)return true;
	else return false;
}
int main(){
    int T;scanf("%d",&T);
    while(T--){
		scanf("%d",&n);
		for(int i=0;i<n;i++){
			e[i].clear();
			ans[i]=0;vis[i]=0;
			for(int j=0;j<20;j++)fa[i][j]=-1;
		}
		for(int i=1;i<n;i++){
			int u,v;
			scanf("%d%d",&u,&v);
			e[u].push_back(v);
			e[v].push_back(u);
		}
		sum=1LL*n*(n-1)/2;
		dep[0]=1;
		dfs1(0,-1);
		for(int j=1;j<20;j++){
			for(int i=0;i<n;i++){
				if(fa[i][j-1]!=-1)
				fa[i][j]=fa[fa[i][j-1]][j-1];
			}
			
		}
		for(auto x:e[0]){
			ans[0]+=(sz[x]-1)*sz[x]/2;
		}
		sum-=ans[0];
		l=r=0;vis[0]=1;
		for(int i=1;i<n;i++){
			if(!sum)break;
			if(vis[i])continue;
			if(find(l,i)){
				for(int j=i;j!=l;j=fa[j][0]){
					vis[j]=1;
					if(dep[j]==2)sonl=j;
				}
				l=i;
			}
			else if(find(r,i)&&!find(sonl,i)){
				for(int j=i;j!=r;j=fa[j][0]){
					vis[j]=1;
				}
				r=i;
			}
			else ans[i]=sum,sum=0;
			if(sum){
				ll temp;
				if(!r)temp=sz[l]*(sz[r]-sz[sonl]);
				else temp=sz[l]*sz[r];
				ans[i]=sum-temp;
				sum=temp;			
			}

		}
		ans[n]=sum;
		for(int i=0;i<=n;i++){
			printf("%lld ",ans[i]);
		}
		printf("\n");

    }


    return 0;
}

E

容易推得一个复杂度为 O(kn2)O(kn^2) 的DP

dp[i][j]=min⁡k<j(dp[i−1][k]+c[k+1][j])d p[i][j]=\min _{k<j}(d p[i-1][k]+c[k+1][j])

要求数组 c[][]c[][] 的值，考虑对原问题进行转化，注意到题目中的

cost⁡(t)=∑x∈set⁡(t)last⁡(x)−first⁡(x)\operatorname{cost}(t)=\sum_{x \in \operatorname{set}(t)} \operatorname{last}(x)-\operatorname{first}(x)

设在序列t中，元素x总共出现了k次，则上式可以变成

cost⁡(t)=∑x∈set⁡(t)∑j=2kpos⁡(xj)−pos(xj−1)\operatorname{cost}(t)=\sum_{x \in \operatorname{set}(t)} \sum_{j=2}^{k} \operatorname{pos}\left(x_{j}\right)-pos\left(x_{j-1}\right)

则 c[i][j]c[i][j] 即为在区间[i,j][i,j]中，所有元素与上一个与其相同且同在该区间的元素之间的间隔之和。

注意到，加入第 ii 个元素，即等价于 dp[j][k]+=i−last_position_of(a[i]),j<last_position_of(a[i])dp[j][k]+=i-last\_position\_of(a[i]),j<last\_position\_of(a[i])由此，我们转化思路，把每个间隔都单独拿出来考虑进行更新，这样就能用线段树进行优化，变成 O(knlogn)O(knlogn)。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=4e4+10;
int n,k,now;
int a[maxn],lst[maxn],le[maxn];
int dp[maxn][105];
struct Tree{
	int val,tag;
}t[maxn<<2];
void push_up(int rt){
	t[rt].val=min(t[rt<<1].val,t[rt<<1|1].val);
}
void push_down(int rt){
	t[rt<<1].tag+=t[rt].tag;
	t[rt<<1|1].tag+=t[rt].tag;
	t[rt<<1].val+=t[rt].tag;
	t[rt<<1|1].val+=t[rt].tag;
	t[rt].tag=0;
}
void build(int rt,int l,int r){
	if(l==r){
		t[rt].val=dp[l][now-1];
		t[rt].tag=0;
		return ;
	}
	int mid=l+r>>1;
	t[rt].tag=0,t[rt].val=0;
	build(rt<<1,l,mid);
	build(rt<<1|1,mid+1,r);
	push_up(rt);
}
void update(int rt,int l,int r,int xl,int xr,int add){
	if(xl==l&&xr==r){
		t[rt].val+=add;
		t[rt].tag+=add;
		return;
	}
	int mid=l+r>>1;
	push_down(rt);
	if(xl<=mid)update(rt<<1,l,mid,xl,min(mid,xr),add);
	if(xr>mid)update(rt<<1|1,mid+1,r,max(mid+1,xl),xr,add);
	push_up(rt);
}
int query(int rt,int l,int r,int xl,int xr){
	if(xl==l&&xr==r){
		return t[rt].val;
	}
	int ans=1e9,mid=l+r>>1;
	push_down(rt);
	if(xl<=mid)ans=min(ans,query(rt<<1,l,mid,xl,min(mid,xr)));
	if(xr>mid)ans=min(ans,query(rt<<1|1,mid+1,r,max(mid+1,xl),xr));
	return ans;
}
int main(){
    int T=1;
    while(T--){
        scanf("%d%d",&n,&k);
		for(int i=1;i<=n;i++)scanf("%d",&a[i]);
		for(int i=1;i<=n;i++){
			le[i]=lst[a[i]];
			lst[a[i]]=i;
		}
		for(int i=1;i<=n;i++)
			dp[i][1]=dp[i-1][1]+(le[i]?i-le[i]:0);
		for(now=2;now<=k;now++){
			build(1,now-1,n);
			for(int j=now;j<=n;j++){
				if(le[j]>=now){
					update(1,now-1,n,now-1,le[j]-1,j-le[j]);
				}
				dp[j][now]=query(1,now-1,n,now-1,j);
			}
		}
		printf("%d\n",dp[n][k]);
    }


    return 0;
}