联合省选 2026 游记
wrkwrkwrk
·
·
生活·游记
前情提要：NOIP 288，JS 卡队线。
前面在核桃集训，模拟赛看着似乎还行，但是感觉自己好摆。
Day 0
从南京离开然后又到南京。转了一圈。
教练领过牌了，但是还是要试机的。
这里又不是没来过，所以随便写点东西就走了。
要开始了吗。
Day 1
8：15到达考场，8：29发密码。
T1咋是期望？？
特殊性质咋有个链，这个不是全0吗，还给样例就搞笑。
反正就是要求出每条边是轻边的概率就是了。但是记录的状态咋这么多啊。还得枚举啥的。
对着这个想了 1h，不会低于 n^2\log n 的缺1分治，那咋办，只能这么写了。咋样例 0.6s，那咋办，不会更好的。
于是开 T2。长度 15 题意检测，全 0 似乎是加点字符啥的。
反正计算答案是判断点当前的前缀能有多少的。等下这个不是字符串匹配吗？向后面加得维护个一直加个数啥的啊，感觉没法维护。
那往前加不是得维护个啥来着。AC自动机，状态数 n^2，那是 mn^2k 加个 bitset，这下能过 75 了。
想到这里已经是 10:30了，但是自己并没有想好咋写 AC 自动机维护的状态是啥。一开始甚至把每个前缀的最后一个字符取反去做。咋要输出方案。11:30 才写好。第一次写好长度比样例小？？在那里写checker啥的。n=3 挂了，发现这个插入问题去解决了。不知为何过样例就到 12:30 了。
然后当时认为这个不是 kmp 吗，那是不是状态少个 n 直接过了？但是并不是，但是还是写到 13:00 才发现问题。
那就紧急开 T3，n\leq 16 和 m=1 是读题检测。然后以为性质 B 只能是后缀一个不一样，写了当然全是 No。
最后把 T2 的长度上限开到了 1000 并特判 00 就结束了。
大概是 [64,100]+75+12。
出场发现大家 T2 全过了。
赛后发现有人 n^3 把 qoj 过了，那没事了。
咋有人 T2 写乱搞的。
看起来明天的目标是稳住就行。
Day2
还是 8:29 发密码。
6，2026:interaction! 来了。
本来以为全是交互形式，后来发现 T3 并不是。
先是 T1 了，咋返回任意一个就行啊。
checker判断每个mex的极大区间就是了。
30min后想起排列区间mex等于外界min啊，那没事了。直接判断前后缀找到 0 就行了。写完过大样例。但是咋就一组样例？Day2一般很难，但是时间还有很多，写个拍子先。咋挂了？问了个 (n,n-1) l>r 了？改好了，拍 10^5 \times 100 个 n\in [2,100] 的数据没挂就是了。似乎没拍 n=3\times 10^4 来着，不管了，反正数组全开的 vector(n)。
开 T2。反转一个团？那咋做。思考个 k=3 先。咋啥也不会，包括暴力？
30min 后没思路只好读那个题面很长的 T3。似乎是比较子树啥的。准备写点东西发现每个点维护的咋是递归子树里面每个点的信息？？那咋弄啊。（并没有发现只看邻接儿子和原题意等价。）
那回去 T2 呗。暴力似乎是维护个线性基啥的，那先维护下。等下非自由元个数似乎很少？那暴力就有了，维护正交线性基的一个 dp 啥的。然后写出这个的答案，这个是 n\leq 18 的第一问，4 pts。在写下能把 n\leq 8 的答案维护出来，但是先不管了。
不对，还有 1.5h，T3还啥也没写呢。菊花，然后 $r=1$，然后想了下 $r=2$，但是不会，根据数据随机写了个是不是相邻最长链直接返回，但是那个样例 WA 一行。
然后感觉就算好好写暴力也是至少 $n^3$ 以上的，那还是直接写个模拟题意的暴力吧。于是写出了如下内容：
```
struct p{
mutable vector<p>ids;
void sc()const{
sort(ids.begin(),ids.end());
reverse(ids.begin(),ids.end());
}
bool operator<(p b)const{
sc();b.sc();
for(int i=0;i<min(ids.size(),b.ids.size());i++){
if(ids[i]<b.ids[i])return 1;
if(b.ids[i]<ids[i])return 0;
}
return ids.size()<b.ids.size();
}
bool operator==(p b)const{
sc();b.sc();
return ids==b.ids;
}
void clear()const{
ids.clear();
}
};
p s[100005];
void fd2(p&r,int now,int fa){
r.ids.push_back(s[now]);
for(auto x:g[now])if(x!=fa){
fd2(r,x,now);
}
}
void forcedfs(int now,int fa){
s[now].clear();
for(auto x:g[now])if(x!=fa){
forcedfs(x,now);
fd2(s[now],x,now);
}
s[now].sc();
}
```
题意写的递归比较就递归比较，甚至比较先排序，排序里面也有比较……感觉复杂度完蛋了，虽然样例跑的飞快。（赛后 AI 声称这个最坏是 $\Omega((n!)^2)$的，不过这个树随机就是了。）
最后把 T2 $n\leq 8$ 构造（其实是 $dp$ 记录方案）写完就~~结束~~进入延时 15min，但是除了检查啥也没干。
$100+22+16$。不说 $r=2$ 的分是因为样例没过来着。但是数据过了。
咋 T3 大家全是 44 啊。不过 T2 似乎算不会这个题中暴力满的。
有人 T1 因为 $a_{n-1/0}=0$ 导致询问不合法挂 $80\sim 90$ 不好评价。
赛后觉得全是暴力啊，有个口述分数统计，等下，卡线了？
# Day 3+
出分发现没挂分，甚至还多了 $8pts$。
总分 $[100+75+12]+[100+22+24]=333$，发现 $|\Sigma|=1$。