题意
[CSP-S 2024] 擂台游戏（民间数据）
题目描述
小 S 想要举办一场擂台游戏，如果共有 \(2^k\) 名选手参加，那么游戏分为 \(k\) 轮进行：
- 第一轮编号为 \(1, 2\) 的选手进行一次对局，编号为 \(3, 4\) 的选手进行一次对局，以此类推，编号为 \(2^k - 1, 2^k\) 的选手进行一次对局。
- 第二轮在只保留第一轮的胜者的前提下，相邻的两位依次进行一场对局。
- 以此类推，第 \(k - 1\) 轮在只保留第 \(k - 2\) 轮的 \(4\) 位胜者的前提下，前两位、后两位分别进行对局，也就是所谓的半决赛。
- 第 \(k\) 轮即为半决赛两位胜者的决赛。
确定了游戏晋级的规则后，小 S 将比赛的规则设置为了擂台赛。具体而言，每位选手都有一个能力值 \(a_1, a_2, \dots , a_{2^k}\)，能力值为 \([0,2^{31}-1]\) 之内的整数。对于每场比赛，会先抽签决定一个数 \(0/1\)，我们将第 \(R\) 轮的第 \(G\) 场比赛抽到的数记为 \(d_{R,G}\)。抽到 \(0\) 则表示表示编号小的选手为擂主，抽到 \(1\) 则表示编号大的选手为擂主。擂主获胜当且仅当他的能力值 \(a\geq R\)。也就是说，游戏的胜负只取决于擂主的能力值与当前比赛是第几轮的大小关系，与另一位的能力值无关。
现在，小 S 先后陆续收到了 \(n\) 位选手的报名信息，他们分别告知了小 S 自己的能力值。小 S 会按照报名的先后顺序对选手进行编号为 \(1, 2, \dots, n\)。小 S 关心的是，补充尽量少的选手使总人数为 \(2\) 的整次幂，且所有选手进行一次完整的擂台游戏后，所有可能成为总冠军的选手的编号之和是多少。
形式化地，设 \(k\) 是最小的非负整数使得 \(2^k\geq n\)，那么应当补充 \((2^k-n)\) 名选手，且补充的选手的能力值可以任取 \([0,2^{31}-1]\) 之内的整数。如果补充的选手有可能取胜，也应当计入答案中。
当然小 S 觉得这个问题还是太简单了，所以他给了你 \(m\) 个询问 \(c_1,c_2,\dots,c_m\)。小 S 希望你帮忙对于每个 \(c_i\) 求出，在只收到前 \(c_i\) 位选手的报名信息时，这个问题的答案是多少。
CSP 石题基本上没有什么简化题意的空间了 , 想做题就得先做完这道阅读理解 .
题解
这道题的流程还是连续的同一思路不断优化的流程 , 所以从暴力开始说 .
前置
理解题目之后, 就可以提出一些概念和性质 .
发现题目事实上给出了一颗二叉树 , 每一个叶子节点代表一个选手 , 每一个非叶子节点有一个值 \(d\) 代表晋级情况由左儿子/右儿子决定.
在已知前 \(len\) 个人的报名情况时 , 称 \(1 \cdots len\) 部分的叶子节点是 " 确定 " 的 , \(len \cdots 2^k\) 部分的叶子节点是" 不确定 "的 .
对于非叶子节点 , 称能够确定下属子树唯一的可能晋级的人的节点为" 确定 "的 , 否则是不确定的 , 如果能到达这一节点的选手不包括任何确定的选手 , 称他为完全不确定.
1.左右儿子都确定的节点一定确定, 但是确定的节点并不必须要求右儿子确定
可以发现答案同样包含两部分 . 一部分来自确定部分 . 另一部分则来自不确定部分 .
2.确定部分不一定只有一个选手
证明: 假设一个右儿子既可以取一个足够强的确定选手, 也可能取一个不确定选手 . 它在向上贡献的时候存在一种情况 ,左右儿子的确定选手都有可能晋级.
3.不确定部分不一定包含所有不确定选手,但是一定是一个 \([r,2^k]\) 的形式.
证明: 当左边儿子确定能够晋级而右儿子是不确定选手时,这个不确定选手并不能晋级.
一旦有一个不确定选手能到达根节点,其右边的选手经过的与确定选手的比赛不会更多 , 因此也一定有可能晋级.
期望40做法
通过前面理解题意后的简单分析, 可以写出一个 \(O(Tnm)\) 的模拟 .
我们需要维护两个信息 : 哪些确定选手可以晋级 , 以及能够晋级的不确定选手的区间的左界 .
这些信息都可以直接记录在节点里并且合并 .
$\mathrm{Case\ 1} $ : 左右儿子都是确定的 , 直接按照题意确定哪个儿子可以晋级即可 .
$\mathrm{Case\ 2} $ : 左儿子确定 , 右儿子不确定 .
一种是左儿子确定能赢 , 那么贡献上去的点仍然是确定的 . 一种是左儿子确定输 , 那么贡献上去一定是不确定选手 . 如果右儿子决定 , 那么贡献上去左儿子和右边的确定点都有可能 .
\(\mathrm{Case \ 3}\) : 左右儿子都不确定 . 注意左儿子可能会带上来一些确定选手 . 和 $\mathrm{Case\ 2} $ 类似 .
注意一个节点中可能同时维护多个确定/选手 . 暴力处理会多一个 \(log\) , 可以在遍历过程顺便维护当前子树能到达树顶所需的最小能力值 \(lim\) . 同时注意如果一个确定点必然能贡献上去 , 它的兄弟子树内的节点就不可能到达树顶 , 可以视作 \(lim=INF\) . 每次贡献一个确定选手时直接判定它能否成为答案 . 这样在节点内只维护确定点 \(a_i\) 最大值就可以确定它的晋级情况了 .
通过讨论好每一种情况直接模拟就可以获得 \(40\) 分左右.
期望84做法
我们发现每一次整体遍历的时候对很多节点的处理都是重复的 . 所有的确定点和完全不确定点的处理其实是可以重复利用的 . 再进一步思考 , 尝试从左向右逐一插入选手 . 这样每一次可能对答案有影响的只有这个新选手的贡献过程 , 这样每一次贡献只需要跳 \(logn\) 个点 , 就可以在 \(O(nlogn\)) 的总时间回答所有询问.
其实可以发现整个过程类似于树形数据结构的 pushup ,而单点插入的时间复杂度是 \(O(log)\) 的 .
每次单点插入 , 我们需要做三件事 : 确定当前选手是否对答案有贡献 , 去除不再对答案有贡献的点 , 修改答案不确定部分的左界 .
过程类似于暴力 , 具体地 :
\(\mathrm{Task1}\) :确定当前选手是否对答案有贡献. 当前节点不能到达树顶有两种情况 , 一种是因为某一个确定点必然能贡献上去 , \(i\) 不可能贡献 , 另一种就是 \(a_i\) 不够大 .
注意到第一种情况下确定节点和不确定节点没有本质区别 . 我们可以直接利用我们维护的左界 \(r\) ,只有 \(i\le r\) 时 , 才可能贡献 .
第二种情况我们可以预处理出每一个节点到达树顶需要的最小能力值 \(lim_i\) ,只有 \(a_i\ge lim_i\) 时才可能贡献 . \(lim_i\) 的预处理和暴力里相似 , 直接整体 dfs 一遍即可 .
\(\mathrm{Task2}\) :从叶子向上跳父亲更新时,当前更新的节点\(now\) 作为右儿子时 ,左儿子一定确定 . 如果更新后可以确定左儿子不再贡献 , 就把左儿子从答案中去除即可 .
\(\mathrm{Task3}\) :当\(now\) 作为左儿子时,右儿子一定完全不确定 . 如果更新后可以确定右儿子不再贡献 , 就把右儿子管辖的区间从答案不确定部分中移除 .
注意每次 \(i=2^{k'}\) 时意味着下次更新后树高会加一层 . 因此需要单独对新树根再更新一次并且从新的根开始重新预处理后半部分的 \(lim_i\) .
预处理复杂度 \(O(Tn)\) , 单次更新复杂度 \(O(1)\) , 瓶颈在于跳父亲.
总时间复杂度 \(O(Tnlogn)\) .
正解
题目中最大给到了 \(T=256\) , 带 \(log\) 的情况下很难拿到最后几个点 .
考虑优化单次操作 , 发现其实很多时候更新时没有必要从底跑到顶 . 每次新插入只会影响那些它"能决定"的节点 .
具体讨论 : 设当前节点是\(now\) , 从下向上贡献过程中分两种情况:
$\mathrm{Case\ 1} $ : \(now\) 是左儿子 , 那么右儿子一定完全不确定 . 如果 \(now\) 是确定节点并确定能晋级 , 即右儿子不能晋级 , 需要更新答案不确定部分的左界 ; 其余情况父亲节点都会包含不确定选手 , 不可能再排除其他选手, 没有必要更新下去.
$\mathrm{Case\ 2} $ : \(now\) 是右儿子 , 那么左儿子一定完全确定 . 如果本来左儿子就确定能晋级,右儿子不能晋级 , 那么父亲是由前面的节点决定的 , 没有必要再向上更新.
其余情况下 , 如果 \(now\) 是确定节点 , 就可以判定左儿子确定的那个选手是否会被排除 .
如果 \(now\) 包含不确定选手 , 它一定能更新到父亲节点 , 不可能再排除其他选手, 没有必要更新下去.
综上 , 发现当且仅当 \(now\) 是确定节点时 , 才有可能对父亲节点以上的节点造成影响 . 同时 , 如果一个节点在本次更新先就已经成为了确定的 , 也没有必要继续向上更新 .
因此 , 只对能够"确定化"父亲的节点进行更新 . 每个节点只会被 "确定化" 一次 , 总复杂度 \(O(Tn)\) .
代码
#include<bits/stdc++.h>
#define file(x) freopen(#x ".in","r",stdin),freopen(#x ".out","w",stdout)
#define int long long
#define INF 0x3f3f3f3f
#define INF64 1e18
using namespace std;
constexpr int N=4e5+5;
int n,m,b[N],c[N],ask[N],k,ans[N];
inline int id(int r,int g){
return (1<<(k-r))-1+g;
}
struct node{
int l,r,d,to;
}a[N*2];
bitset<N> vis;
int now,res;
int r,lim[N];
void build(int x,int l,int r){
a[x].l=l;a[x].r=r;
a[x].d=-1;
if(l==r) return ;
int mid=l+r>>1;
build(x*2,l,mid);
build(x*2+1,mid+1,r);
}
void init(){
vis.reset();
for(int i=1;i<=id(0,n);i++) a[i].d=-1;
}
inline bool pushup(int x,int op,int dep){
if(a[x].d!=-1) return 0;
int ls=x*2,rs=x*2+1;
if(op==0){
if(a[x].to==0){
if(c[a[ls].d]>=dep){
a[x].d=a[ls].d;
r=max(r,a[x].r);
return 1;
}
if(c[a[ls].d]<dep){
if(vis[a[ls].d]) vis[a[ls].d]=0,res-=a[ls].d;
return 0;
}
}
if(a[x].to==1){
return 0;
}
}
if(op==1){
if(a[x].to==0){
if(c[a[ls].d]>=dep){
a[x].d=a[ls].d;
return 1;
}
if(c[a[ls].d]<dep){
a[x].d=a[rs].d;
return 1;
}
}
if(a[x].to==1){
if(c[a[rs].d]>=dep){
a[x].d=a[rs].d;
if(vis[a[ls].d]) vis[a[ls].d]=0,res-=a[ls].d;
return 1;
}
if(c[a[rs].d]<dep){
a[x].d=a[ls].d;
return 1;
}
}
}
return 0;
}
void getlim(int x,int lm,int dep,int tag){
if(dep==0){
lim[a[x].l]=lm;
return ;
}
if(a[x].to==0){
if(!tag) getlim(x*2,max(lm,dep),dep-1,0);
getlim(x*2+1,lm,dep-1,0);
}
if(a[x].to==1){
if(!tag) getlim(x*2,lm,dep-1,0);
getlim(x*2+1,max(lm,dep),dep-1,0);
}
}
inline void solve(){
init();
int know=0;r=1;ans[1]=1;res=1;vis[1]=1;a[id(0,1)].d=1;
for(int i=1;i<=n;i++){
int x=id(0,i),dep=0;
a[id(0,i)].d=i;
if(i>r&&c[i]>=lim[i]) vis[i]=1,res+=i;
r=max(i,r);
while(dep<know){
if(!pushup(x/2,x&1,dep+1)) break;
dep++;x/=2;
}
ans[i]=res;
int tmp=1<<know;
if(r<tmp) ans[i]+=(tmp-r)*(tmp+r+1)/2;
if(i!=n&&i==(1<<know)){
know++;
pushup(id(know,1),0,know);
getlim(id(know,1),0,know,1);
}
}
res=0;
for(int i=1;i<=m;i++) res^=(i*ans[ask[i]]);
cout<<res<<'\n';
}
signed main(){
//file(arena);
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
cin>>n>>m;
for(int i=1;i<=n;i++) cin>>b[i];
for(int i=1;i<=m;i++) cin>>ask[i];
k=ceil(log2(1.0*n));
for(int i=1;i<=k;i++){
string s;cin>>s;
for(int j=1;j<=(1<<(k-i));j++)
a[id(i,j)].to=s[j-1]-'0';
}
int t;cin>>t;
build(1,1,1<<k);
while(t--){
int tmp[4];for(int i=0;i<4;i++) cin>>tmp[i];
for(int i=1;i<=n;i++) c[i]=b[i]^tmp[i%4];
solve();
}
}
后记
对这次 CSP-S 的题不予置评 .
如果CCF认为出一道不需要任何前置算法 , 没有任何思维含量 , 通过大量讨论提高题目难度的套皮大模拟就可以和 [CSP-S2019]树上的数 同享 "好题"的称呼的话 , 那也只好顺从了.
说实话这场CSP的分数也不值得拿太较真的态度来对待了 . 毕竟从题目质量上就可以看出来 , 没人对CSP有过什么太多态度.
标签：晋级,int,题解,确定,节点,S2024,选手,儿子,CSP From： https://www.cnblogs.com/youlv/p/18514523