CCPC 2024 女赛 做题记录

· · 个人记录

\text{CCPC}\ 2024\ 女生赛\ \\做题记录

A. 盒子

给你一个长方体，若干组询问给定某个点是否在长方体内。

我一开始认为要做 6 个带符号的点到平面的距离。发现困难。后来发现直接把每个维度分开来判断就可以了。一交发现 \text{\color{red}WA} 了，原来是输入没有保证给定某一位上下界的顺序，需要自己手动判断。直到 \text{2h} 时才切掉这题。战犯级操作。

C.CCPC

给定字符串，任意重排它。求最多的 \text{CCPC} 子串的个数。

一开始没注意前后两个 \text{C} 可以连接在一起，吃了一发罚时。后来考虑到了就做出来了。就是 \min\{\frac {num_c-1} {2}\ ,num_p\}。也是战犯级操作。

F.完全平方数

给你 \{a_n\} ，你需要得到 \{d_n\} ，满足后者每一项都是前者对应项的因子，且后者每一项乘起来都是完全平方数。求所有的后者的乘积的开方和。n,a_i\leq10^6。

考虑到每一个质因子的贡献都是独立的，可以考虑拆开来算。

计算每个质因子在某一位有几个，一共有几个。那么就可以做一个 dp 。

已经得到了每个质因子的 ```dp``` 数组，统计答案。 #### G. 递增序列 > 给定一个长度为 $n$ 的非负整数序列 $a$ 和一个定值 $k$ 。 试求出有多少个整数 $x$，满足 $x ∈ [0, k]$，且 $a1 ⊕ x, a2 ⊕ x, . . . , an ⊕ x$ 是单调不降序列。 其中 $⊕$ 表示异或运算。 > > $n\leq2\times 10^5,a_i\leq10^{18}

摸一下，可以感悟出：规定 x 的其中一些位置必须选某个数，求 k 以内这样的 x 的数量。

可以拆位，有 \log 个物品，每个物品的代价是 2^w ，你可以选或者不选，求代价不超过 k' 的方案的个数。

每个高位的物品可以换取所有低位的物品，那么对每个 1 的位置分段就可以计算了。

非常神异的是到目前全队都没写出来（队友对我转化题意表示疑惑，目测不是同一个思路），不知道我的思路对了没有。

H. 平方根

给你一个 01 串，它的价值是每一段连续 1 的个数开根号求和，你可以把任意的 1 变成 0 ，求你能得到的最大价值。n\leq10^6。

对 1 的连续段长度分成奇偶两个情况讨论，容易发现规律。奇数就是分出尽量多的单独 1，偶数就是在奇数的基础上，要求有两个 1 连续。这样构造可以达到最大。

I.字符串复制

一个长度为 n 的字符串，复制最开始的字符串 m 次得到新字符串，求新串本质不同子串数量。n\leq5\times 10^3,m\leq10^9 ，要求 \mod 998244353 。

容易发现，第 3 次复制开始之后的字符串跟之前的除了中间原串的数量之外的部分是同构的。那么暴力复制就可以求得答案，直接乘上 m-2 ，加回 2 次的数量就好。小于边界次数的复制直接处理。没什么难度但是很少人过，很神奇。

J. 最大公因数的平方和

给你排列 a,b ，多次询问

\displaystyle \sum_{i=l}^r\sum_{j=L}^R \gcd(a_i,b_j)^2 \mod 2^{32}

简单莫反一下，得到那个式子的基本单位就是 \displaystyle\sum_{d=1}^nd^2\sum_{T=1}^n\mu(\frac T d)\sum_{i=1}^n[T|a _i]\sum_{j=1}^n[T|b_j] 。疑似要用神秘数据结构，不会做了。

M. 覆盖一棵树

给定一个 n 个节点的树，你可以使用若干个长度任意的线段覆盖树的所有边，要求: 每条边恰好被覆盖一次, 每个线段必须从叶子节点开始，到它的一个祖先节点。

求最长覆盖边的最小值。

n\leq2\times10^5

每次从最浅的叶子开始尽量长的往上面覆盖，直到不能覆盖为止就行了。