SWERC 2021-2022

Links

和袁妹妹打的一场acm。感觉由于是 7点开始，有点疲劳了，我自己状态不是很好，爬了。。。。。

赛时只做对了6道，实际上可以做出8，9道以上，两道是DS，而且我思路都不是很对。而且还是较为简单的“送分题”，DS真的应该多加练习。

只说我做的吧。。

D 题。

题意是每次你可以插入或删除 \(\text{aa,bb,cc,abab,bcbc}\) ，问你能不能将 \(A\) 串变为 \(B\) 串。

\(n\) 竟然只开到了 \(100\) 让我以为是dp什么的。。

但是存在 \(\text{a}\to\text{aabcb}\to \text{bcb}\) 这种，不是很能dp。

仔细考虑一下发现这样一种变换 \(\mathrm{ab\to ababba\to ba}\) 所以暗示了我们本质是在交换。

只不过 \(\text{a,b,c}\) 不对称。所以变成 \(\text{b}\) 随便动 ，\(\text{a,c}\) 不能交叉动。

所以剩下的也很简单了，先把连着的消没，然后把 \(\text{b}\) 放到一起，删掉。

看剩下的两个只包含 \(\text{a,c}\) 的串是否相同。

---

F 题。

题意是你从 \(i\) 走到 \(j\) 的充要条件是 \(|i-j|\leq \min(p_i,p_j)\) 。问 \(i\to j\) 最短路。

性质想错了。。口胡了。。

实际上正解就是 bfs。

只需要满足 \(j\in[i,i-p_i],j+p_j\leq i\) 很简单的线段树二分即可解决。

线段树二分新写法get： 你把区间列出来，然后一个一个判断，如果存在答案，那就正常dfs他.

口胡.jpg

//[x,y] first <=w
int tot=0,d[100];
inline void divi(int p,int l,int r,int x,int y){
    if(x<=l&&r<=y){
        d[++tot]=p;return ;
    }
    int mid=l+r>>1;
    if(x<=mid) divi(p<<1,l,mid,x,y);
    if(y>mid) divi(p<<1|1,mid+1,r,x,y);
}
inline int solve(int p,int l,int r,int w){
    if(l==r) return l;int mid=l+r>>1;
    if(t[p<<1]<=w) return solve(p<<1,l,mid,w);
    return solve(p<<1|1,mid+1,r,w);
}
inline int solve(int x,int y,int w){
    tot=0;divi(1,1,n,x,y);
    for(int i=1,p=d[i];i<=tot;i++,p=d[i]){
        if(t[p]<=w) return solve(p,l[p],r[p],w);
    }
    return inf;
}

我觉得，，挺好写的，因为 divi 就是在找区间。

这个题赛后一遍过了，爽歪歪。、

---

I 枚举当前能覆盖道的最后一个。然后二分。

不知道加强版是神木。

L 题。优化simple的 \(O(n^2)\) dp。

发现有绝对值小等。

\(|A|\leq B \Longleftrightarrow A\leq B,-A\leq B\) 然后等价二位数点。cdq,BIT什么的就好了。、

总结，这次和上次 GR 都看出来了我时间一晚脑子就不好使，必须要利用上午时间，十一点前的时间、。

G 题。。赛后竟然觉得很简单。。

结论容易猜到，实际上我们能感觉到应该是，一堆点都能到 \(u\) ，然后 \(u\) 能到达剩下的点这样最优。

然后有这样的性质 \(u\) 就无可厚非是重心了。

具体证明结论就是说

1. 首先不存在内向根（除非叶子），原因是你可以任选一个子树，把所有边反向，然后新增贡献显然。
2. 外向根同理
3. 想了一下感觉充要了？？不知道题解在说什么。。。。。。

然后考虑为啥这样的 \(u\) 是重心。这个我胡的感觉不太对（猜的结论相当于）。实际上感觉有点显然，如果\(u\) 是这样的点，且不是重心，那么向重心方向的边，也一定指向中心方向，然后这个点就可以看作没用了，听显然了。

如果是重心我们需要分配子树大小 \(s\) ，使得最接近 \(n-1/2\) 。

这里题解给出了一种 \(O(\frac{n\sqrt n}{w})\) 的做法。

\(O(\frac{n\sqrt n}{w} \log n)\) 可以用二进制分组背包来做。。。。。。

但实际上，考虑如果我们要选 \(k\) 个大小位 \(w\) 的物品，可以按 \(k\) 奇偶分类，如果 \(k\) 是奇数，那么看作 \(1\) 个 \(w\) 和 \((k-1)/2\) 个 \(2w\) 。

偶数就是 \(k/2\) 个 \(2w\) ，那么对于 小于 \(\sqrt n\) 的我们这么做，每一个只会被更新 \(O(1)\) 次。

剩下的都是 \(w>\sqrt n\) 的，也是 根号个了。复杂度得到了。