这场是真的搞人心态…居然卡在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=AnsMEXiAnsMEX>iAns_{MEX=i}=Ans_{MEX\geq i}-Ans_{MEX>i}

这样一来就简单多了,直接求路径中包含序列0,1,2,..,i1,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]=mink<j(dp[i1][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)=xset(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)=xset(t)j=2kpos(xj)pos(xj1)\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]+=ilast_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;
}