A
大模拟。还是博弈题。
你说得对，但是《巫师 \(3\)：狂猎》是由 \(\rm CDPR\) 自主研发的一款全新开放世界卡牌游戏。游戏发生在一个“天球交汇”后的幻想世界，在这里，通过青草试炼的人将成为「猎魔人」，导引魔法之力。你将扮演一位名为「杰洛特」的猎魔人在自由的旅行中邂逅性格各异、能力独特的同伴们，和他们一起击败强敌，找回失散的亲人——同时，逐步发掘「昆特牌」的真相。
B
定义一段区间 \([l,r]\) 的权值为这段数的极差。
对于 \(k\in[1,n]\)，求出将 \(\{a_n\}\) 划分为 \(k\) 段的最大总权值。
\(1\le n\le 5000\)，\(1\le a_i\le 10^4\).
记 \(f_{i,j,0/1,0/1}\) 表示前 \(i\) 个数字划分为 \(j\) 段，当前区间是否选了最大值、最小值。
时间复杂度 \(O(n^2)\).
结果要么就是有人去写了单调栈或者四边形不等式。我还想了一会 dp 凸优化，显然完全做不了。
#include<bits/stdc++.h>
#define N 5010
using namespace std;
int read(){
int x=0,w=1;char ch=getchar();
while(!isdigit(ch)){if(ch=='-')w=-1;ch=getchar();}
while(isdigit(ch))x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
return x*w;
}
int n,a[N],f[2][N][4];
int max3(int x,int y,int z){
return max(max(x,y),z);
}
int max4(int a,int b,int c,int d){
return max(max(a,b),max(c,d));
}
int main(){
n=read();
for(int i=1;i<=n;i++)a[i]=read();
memset(f,-0x3f,sizeof(f)),f[0][0][3]=0;
int o=0;
for(int i=1;i<=n;i++){
o^=1;
for(int j=1;j<=n;j++){
f[o][j][0]=max(f[o^1][j-1][3],f[o^1][j][0]);
f[o][j][1]=max3(f[o^1][j-1][3]+a[i],f[o^1][j][0]+a[i],f[o^1][j][1]);
f[o][j][2]=max3(f[o^1][j-1][3]-a[i],f[o^1][j][2],f[o^1][j][0]-a[i]);
f[o][j][3]=max4(f[o^1][j-1][3],f[o^1][j][3],f[o^1][j][1]-a[i],f[o^1][j][2]+a[i]);
}
}
for(int i=1;i<=n;i++)
printf("%d\n",f[o][i][3]);
return 0;
}
C
若 \(|i-a_i|=|j-a_j|\) 则数 \(i\) 和 \(j\) 可以匹配。问 \(n\) 个数（\(n\) 为偶数）能否完美匹配,并给出方案。
\(T\le 10\)，\(\sum n\le 10^6\)，\(|a_i|\le 10^9\).
SPJ 又炸一回，总司令赢麻了。
容易想到 \(i+a_i=j+a_j\) 或者 \(i-a_i=j-a_j\).
在二分图上让左侧的 \(i-a_i\) 向 右侧的 \(i+a_i\) 连边。
也就是每条边选择让它的一个端点异或 \(1\)，要求最后均为 \(0\).
对于每个连通块随便找一棵生成树，自底向上贪心构造。
不是很想写。
D
一开始有 \(n\) 个数 \(\{a_n\}\)，第 \(i\) 个数属于集合 \(i\)，你需要支持如下操作：
-
合并两个数 \(x,y\) 所在的集合
-
对 \(x\) 所在集合中的数全体加 \(1\)
-
对 \(a_x\) 这个数加上 \(k\)
每次操作后询问 \(x\) 所在的集合中的数的异或和是否为 \(0\).
\(n,q\le 3\times 10^5\)，任意数任意时刻不超过 \(10^9\).
十一点出去装水，nosicuL 跟我说这题不就是我前几天问他那个 P6623 [省选联考 2020 A 卷] 树 吗！怎么半天都没看出来是原题。
给我看人麻了，没圣遗物就懒得敲了开始打摆。
建一棵 trie 树即可。
合并的话启发式一下就好。
整体 \(+1\) 在 trie 树里不断交换左右儿子递归左儿子下去即可。
单点改就是删个数再加回去。
时间复杂度 \(O(n\log V)\).
然而逆天数据又有问题。怪不得我 40 的暴力分怎么变成 20 了。
#include<bits/stdc++.h>
#define N 300010
#define L 30
#define M N*31
#define sit set<int>::iterator
using namespace std;
int read(){
int x=0,w=1;char ch=getchar();
while(!isdigit(ch)){if(ch=='-')w=-1;ch=getchar();}
while(isdigit(ch))x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
return x*w;
}
#define lc ch[u][0]
#define rc ch[u][1]
int ch[M][2],w[M],xorv[M],tot;
int newnode(){
int u=++tot;
lc=rc=w[u]=xorv[u]=0;
return u;
}
void maintain(int u){
w[u]=xorv[u]=0;
if(lc)w[u]+=w[lc],xorv[u]^=xorv[lc]<<1;
if(rc)w[u]+=w[rc],xorv[u]^=xorv[rc]<<1|(w[rc]&1);
}
void insert(int &u,int k,int dep,int flag){
if(!u)u=newnode();
if(dep>L){w[u]+=flag;return;}
insert(ch[u][k&1],k>>1,dep+1,flag),maintain(u);
}
int merge(int u,int v){
if(!u||!v)return u|v;
w[u]+=w[v],xorv[u]^=xorv[v];
lc=merge(lc,ch[v][0]),rc=merge(rc,ch[v][1]);
return u;
}
void add(int u){
swap(lc,rc);
if(lc)add(lc);
maintain(u);
}
int n,q,a[N],rt[N];
int fa[N],dlt[N];set<int>s[N];
int find(int x){
return x==fa[x]?x:fa[x]=find(fa[x]);
}
int main(){
n=read(),q=read();
for(int i=1;i<=n;i++){
a[i]=read(),insert(rt[i],a[i],0,1);
fa[i]=i,dlt[i]=0,s[i].insert(i);
}
for(int opt,x,y,k;q;q--){
opt=read();
if(opt==1){
x=find(read()),y=find(read());
if(x==y)continue;
bool swp=false;
if(w[rt[x]]<w[rt[y]])swap(x,y),swp=true;
for(sit it=s[y].begin();it!=s[y].end();it++)
s[x].insert(*it),a[*it]+=dlt[y]-dlt[x];
fa[y]=x,rt[x]=merge(rt[x],rt[y]);
}
if(opt==2){
x=find(read());
add(rt[x]),dlt[x]++;
}
if(opt==3){
x=read(),k=read();
int fx=find(x);
insert(rt[fx],a[x]+dlt[fx],0,-1);
a[x]+=k,insert(rt[fx],a[x]+dlt[fx],0,1);
}
puts(xorv[rt[find(x)]]?"Yes":"No");
}
return 0;
}