APIO2022
前言
\[\boxed{\large \color{blue}{\huge\mathcal{A}} \text{sia-} \color{red}{\huge\mathcal{P}} \text{acific } \color{yellow}{\huge\mathcal{I}} \text{nformatics } \color{green}{\huge\mathcal{O}}\text{lympiad} } \]5.18
写完了网络流打算之后用网络流骗分。
写了两道 APIO 历年，发现好难，不想写了。
5.23
把 dev 的缺省源删了，多练练头文件，不让考试时挂在这里。
发了练习用的网站，发现 2/3 是交互题/ll。
对了，才知道 Batch 就是一般意义上的“传统题”，而 Communication 好像是交互题。
人傻了 APIO 的题这么难，2019~21 我分别抄题解做了 2,1,1 道题（甚至 2021 的那道还没过）。
5.25
学了一下 ，感觉好奇妙，不知道考场上用不用得到。
官方发的练习题做了 1,2 不会 3。
洛谷上帖子说这三道评分约蓝红蓝或绿红绿，wtcl。
T1
点击展开
Trans
下标从 \(0\) 开始。
有一个机器，输入一个长度为 \(n\) 的序列 \(\{a\}\)，返回 \(\{b\}\) 序列，\(b_i=a_{p_i}\ \text{xor} \ x\)，其中 \(\{p\}\) 为机器内置的 \(n\) 排列（\(0\) 到 \(n-1\)），\(x\) 为机器内定的值。你只能向机器中输入一次一个序列 \(\{a\}\)，其中值域 \([0,n+2]\)，然后得到返回 \(\{b\}\)，请猜出 \(\{p\}\)。
\(3\le n\le 128,0\le x\le 255\)
Sol
以下的 \(/\) 均代表除法+下取整。
首先我们认同，如果猜的数列 \(\{a\}\) 值互不相同，且我们求出了 \(x\) 的值，那 \(\{p\}\) 就迎刃而解了。
分类讨论。设 \(k\) 使得 \(2^k-1\le n,2^{k+1}-1>n\)。
\[\large{n<2^{k+1}-2} \]我们只要询问 \(\{1,2,3,\dots,2^k-1,2^k,\dots,n\}\) 即可。
我们发现将这些数 \(/ 2^k\) 后会有两种值 \(0,1\)，值的个数分别为 \(2^k-1,n-2^k+1\)。
由于 \(2^k-1>n-2^k+1\)，我们对于 \(\{b\}\) 统计同样的东西（\(/ 2^k\)），多的那类就对应 \([1,2^k-1]\) 这部分。
多的那部分值就是 \(x/2^k\)，我们直接将 \((x/2^k)\times 2^k\) 异或掉 \(\{b\}\)，接下来只有 \(x\bmod 2^k\) 的部分了。
由于 \([0,2^k-1]\) 异或一个 \(<2^k\) 的 \(x\) 后还是 \([0,2^k-1]\) 这些数，我们开桶查询 \(\{b\}\) 中 \([0,2^k-1]\) 少了哪个数，就对应着原来 \(\{a\}\) 中 \([1,2^k-1]\) 缺失的 \(0\)，所以 \(x\bmod 2^k\) 就是那个缺失的数。
\[\large{n=2^{k+1}-2} \]类似上一种情况的做法，但是 \(2^k-1=n-2^k+1\)，无法像上一种这样做。
我们发现 \(n+2=2^{k+1}\) 正好是 \(2\) 的幂，这说明要用。
我们询问 \(\{a\}=\{1,2,3,\dots,2^k-1,2^k,\dots,n-2,n-1,2^{k+1}\}\)。
由于 \(\{a\}\) 中只有 \(2^{k+1}/2^{k+1}=1\)，所以我们能快速定位到原 \(2^{k+1}\) 在 \(\{b\}\) 中的位置，记为 \(pos\)。
然后 \(x=b_{pos}\ \text{xor} \ 2^{k+1}\) 就结束了。
Detail
注意分类讨论中第二类不能 \(\{a\}=\{\color{red}{0},1,2,\dots,2^k-1,2^k,\dots,n-3,\color{red}{n-2},2^{k+1}\}\)。
因为当 \(n=6\) 时（其实就是小数据部分的锅），\((n-2)-(2^k-1)=1\)，这时 \(2^{k+1}\) 和 \(2^k(=n-2)\) 就无法区分了。
Code
点击查看代码
#include
#include"machine.h"
using namespace std;
#define For(i,j,k) for(int i=j;i<=k;i++)
#define pb emplace_back
#define sec second
#define fir first
map mp;
bool vis[1000];
vector guess_permutation(int n){
vector que,res;
int a=0;
while((1<<(a+1))-1<=n) a++;
if((1<<(a+1))-2==n){
For(i,0,n-2) que.pb(i);
que.pb((1<<(a+1)));
res=use_machine(que);
mp.clear();
For(i,0,n-1) mp[res[i]>>(a+1)]++;
int mn=0,cnt=n+1;
for(auto i:mp){
if(i.sec>(a+1))!=mn) pos++;
x=res[pos]^(1<<(a+1));
For(i,0,n-1) res[i]^=x;
res[pos]=n-1;
return res;
}
For(i,1,n) que.pb(i);
res=use_machine(que);
mp.clear();
For(i,0,n-1) mp[res[i]>>a]++;
int mx=0,cnt=0;
for(auto i:mp){
if(i.sec>cnt){
mx=i.fir;
cnt=i.sec;
}
}
mx<<=a;
For(i,0,n-1) res[i]^=mx;
For(i,0,(1< T2
就是前缀和板子，不再赘述。
5.26
重修了一下分数规划。
出发！！！
路上很不顺。
然后到处堵车（查核酸+下雨）。
我们 1:30 才到，这边午餐供应 1 点结束，我、xay、yjj、yzc、zty、wn、xyr AA 点了KFC吃。
一车大佬一起讨论 practice T3 终于会了。
感觉集体降智。——yjj
T3
点击展开
Trans
有人给了你 \(n\le 4e4\) 个点，每个点的两个坐标为整数 \(\in[0,5e8)\)，然后让你 encode 成一个长度为 \(3n\) 的整数序列，每一个值域 \([0,2e9]\)。
之后这个人会把这个序列打乱还给你，让你还原出最初的 \(n\) 个点的坐标，注意 \(n\) 个点之间的顺序无关紧要。
Sol
我们大体的思路为：\(n\) 个值存 \(X\) 坐标（末尾两个二进制位存 10，然后 \(4\times 5e8\) 正好 \(2e9\)），同理 \(n\) 个存 \(Y\)（末尾 11），然后存一个 \(n\) 的排列 \(\{p\}\)，使得 \(X\) 坐标第 \(i\) 小的对应 \(Y\) 坐标第 \(p_i\) 小的构成一个点。
前面的 \(X,Y\) 存起来没有问题，但是最后排列的值域会达到 \(2\times 4e4\times 4e4=3.2e9>2e9\)（末尾标识符 0，\(i\) 下标，\(p_i\) 的值）。
我们发现我们其实浪费了信息资源，因为这样 \(3.2e9\) 我们甚至可以存一个 \(n\) 长度值域 \([1,n]\) 的整数序列了，所以有排列的性质我们没有用到。
对了！
\[0+1+2+\dots+(n-1)=\frac{n(n-1)}{2}<1e9 \]所以再加上占位符也不超过 \(2e9\)。
所以我们对 \(\{p\}\) 求一个前缀和 \(\{q\}\)，这样 \(\{q\}\) 一定是单调不减的。
所以我们直接存 \(\{q\}\) 加占位符即可，最后将乱序的 \(\{q\}\) 排序后差分即得到 \(\{p\}\)，问题就迎刃而解。
Code
点击查看代码
#include
#include"treasure.h"
using namespace std;
#define vi vector
#define For(i,j,k) for(int i=j;i<=k;i++)
#define Rof(i,j,k) for(int i=j;i>=k;i--)
#define pb emplace_back
#define mkp make_pair
#define fir first
#define sec second
struct node{int x,y,rk;};
bool cmp (node x,node y){return x.x v;
n=X.size();
For(i,0,n-1) v.pb((node){X[i],Y[i],0});
sort(v.begin(),v.end(),cmp2);
For(i,0,n-1) v[i].rk=i;
sort(v.begin(),v.end(),cmp);
For(i,0,n-1) p.pb(v[i].rk);
For(i,0,n-1) res.pb(1+4*X[i]);
For(i,0,n-1) res.pb(3+4*Y[i]);
For(i,1,n-1) p[i]+=p[i-1];
For(i,0,n-1) res.pb(2*p[i]);
return res;
}
vi decode(vi w){
n=w.size()/3;
vi X,Y,res,p;
for(int i:w){
if(i&1){
if(i&2) Y.pb(i>>2);
else X.pb(i>>2);
}else{
p.pb(i>>1);
}
}
sort(X.begin(),X.end());
sort(Y.begin(),Y.end());
sort(p.begin(),p.end());
Rof(i,n-1,1) p[i]-=p[i-1];
For(i,0,n-1){
res.pb(X[i]);
res.pb(Y[p[i]]);
}
return res;
}
然后 APIO 主办方还发了衣服、袋子和牌子，感觉好好主要是颜色鲜艳。
宾馆和 zqs 住。
一直摸鱼，打雀魂，iwanna。
晚饭就挺好吃的，还有兰州拉面，但是全装在一盘了，味道混了。
然后做核酸：6:30 的时候超多人，7:10 的时候完全没人，直接做好。
然后问了门卫大叔，说小卖部在大门出门右左转 10m。
宾馆内有自助售货机卖的是老坛酸菜牛肉main。
然后 wyl 拉我们去玩狼人杀，然后我把wsy zqs wds拉过去了。
一开始他们三个蒙在鼓里。
然后就活起来了。
有一局我是预言家，然后直接选警长我一个新手能这样一定是真预言家。然后就一路开挂，直到被刀了最后输了。
再一局就我、wsy、zqs三个新手是狼，然后二中一般不相信我们是狼，而且wds是干扰选项，就开挂胜利。
22:45 了，不早了睡了，明天早上还有课。
晚上和zqs在谈政策聊太久了也有可能是出门玩太激动了，导致 0:30 才睡。
5.27
早上 6:45 的闹钟把我吵醒。
早饭海星，培根鸡蛋薯条西柚汁真解油。
7:00 开吃吃完 7:23，这时二中一堆人才过来，但是好像自助餐被吃得不多了。
上午 3.5h 的课好无聊啊我打游戏+睡觉。
本来台下安静的，但是 djq 不会控场，后面大家吵起来了 a bit。
旁边一位看起来文静的教练也是进行的一个骂，然后主动和我说：
djq 讲的，会的人听得懂，不会的人还是听不懂。
其实我觉得 djq 讲得确实不算差，但是口音比较 naive，而且设备的问题不会用 PPT、记事本，然后讲各种计数+卷积+多项式exp/ln，听得云里雾里。
为啥我对多项式一窍不通啊——我 & 5ab
然后 djq 感觉就是纯理论人，不太会啥电脑软件。
于是不用 PPT，直接手写 latex 在记事本上给我们看。
体会一下，一整节课都是这样的东西：
评价：
好吧，上午就这样浑浑噩噩过去了。
看了一眼之后的讲义，比 djq 的友好太多了，心里有了安慰。
ez 的说下午的集合幂级数就集体不去了，因为lj讲过。
然后吃了午饭做了核酸，还算快。
由于明天比赛大概率会饿，我去小卖部买了点旺仔QQ糖（和wsy wds zqy分了吃）充饥的东西。
然后我发现没有房卡上不去了，我想着先蹭到 6 楼再上 8 楼，谁想到我个笨蛋连个楼梯都找不到，只能回 1 楼叫 wsy 把我带上来。
所有人都知道了，但是不知道去哪里：
下午讲 FWT，还好大致懂了但是代码绝对不会写。
不过讲例题的时候还是云里雾里的，咱就是说不要把自己定义的记号和一般化的记号搞混啊。
一天下来被多项式折磨死。
做多项式题就像嗑药——pinkrabbit
啥多项式 exp ln inv pow 都不会。
我是不会说下午的课 wsy wds 在麦块屠龙的。
xmc 的赞赏：
摸鱼的时候看房卡，发现：
@侃哥侃英语 人 类 低 质 量 翻 译 鉴 赏（9）
晚饭吃了真假羊肉串：
我、wyl、wwc、wxw、wn、xay、yzc、xyr、zty、tyq 几个甚至偷闲玩了一局狼人杀，可刺激了。
当时十一人局，我及wwc、yzc、xyr是狼，然后预言家、女巫、骑士、守卫、警长。
一开始 wwc 当警长被 xay 骑士戳死了 qwq。
然后因为 yzc新手一直笑场外，xyr 当时力挺 wwc，然后两晚死三狼。
就剩我了，还有 6 个好人。
然后我就一点一点攻于心计挑拨离间，他们也看我小白，
晚上开幕式，信息量巨大。
开局先随机抽了几个幸运儿上台演讲。
然后放了一个关于准备工作和入场的 VCR有 wyl 入住做核酸的三个角度特写/ww。
甚至还有舞蹈和萨克斯才艺晚会。
之后让本校（南京外国语学校）的孙悠然女同学大佬演讲。
最后就是重（物理）头戏——dzd（杜子德）教授。
简介
1984年至1996年，于中科院计算所从事研究工作；
1996年9月至2004年3月，任中国计算机学会专职副秘书长；
1998年5月，创建中国计算机学会青年计算机科技论坛 YOCSEF；
1998年起，负责全国青少年信息学奥林匹克竞赛 NOI，任竞赛委员会主席。成功策划和组织由中国主办的2000国际信息学奥林匹克竞赛(IOI 2000)，任执行委员会主席；
2004年4月至2021年3月，任中国计算机学会秘书长；
2005年被选举为首任IOI主席；
2006年被中科院计算所聘为研究员；
2021年3月起任香港中文大学（深圳）校长顾问；
2021年9月起任深圳市人工智能与机器人研究院执行院长。
然后由于话筒不好+本身特有的口音，非常滑稽。
qwqwqwq
当然听得清楚的话也非凡：
指代码中存在暴戾性语言选手禁赛一年
开幕式时正好领了密码条。
关于密码条没有密码这回事。
我爸发了去年初二选手大佬们的成绩，ssfd。
wyl 传来话：lj 让我们认真对待，好好考。