Codeforces Records

目前共做完了   2   轮 Codeforces Contests 和   1   套 Gym

Dec / 16 - Round # 761 (4/6)

Dec / 14 - Round # 760 (7/7)

Nov / 26 - Round #757 (3/6)

Nov / 23 - Global #17 (2/9)

Nov / 22 - Edu #117 (5/7)

Nov / 14 - Round #755 (2/7)

Nov / 12 - Round #754 (4/6)

Oct / 30 - Round #752 (5/8)

  • A(构造):插入最少的数使得 $a_i\le i$ 。显然插入 $1$ 就可以了,需要插入的最少个数是 $\max_{i=1}^n\max(0, a_i-i)$

  • B(构造):将数列分段使每段 LIS 长度异或和为 $0$ 。偶数长 $1$ 个数 $1$ 段,奇数长找长度为 $2$ 的块 LIS 为 $1$ 即可。

  • C(构造):若一个前缀可以删干净,则当前数可以在前方任意位置被删掉,暴力判断 10 个质数的范围即可。

  • D(构造):找到一个 $n$ 使得 $n\ \text{mod}\ x = y\ \text{mod}\ n$ ,其中 $x,y$ 为偶数。

    • 若 $x>y$ ,令 $n=x+y$
    • 若 $x=y$ ,令 $n=x$
    • 若 $x<y$ ,令 $n=\lfloor\frac{y}{x}\rfloor x+\frac{y\ \text{mod}\ x}{2}$ ,$x,y$ 为偶数保证 $y\ \text{mod}\ x$ 可以被 $2$ 整除
    • 推导的方法是设 $n=t_1x+k,y = t_2n+k$ ,整理后发现令 $t_2=1$ 即可
  • E(暴力):设 $f[i][j]$ 表示有多少个 $i$ 的后缀,使得最优解中 $a_i\to j$ ,这样每个位置只有 $\sqrt{a_i}$ 种可能的取值,暴力转移即可,每次的贡献是 $i\times f[i+1][j]\times (\lceil\frac{a_i}{a_i+1}\rceil - 1)$ ,清空数组的方法比较有技巧。其实子序列也可以做。

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    int a[N], f[2][N];

    vector<int> pos[2];

    inline void work() {
    int n = rd();
    int ans = 0;
    for (int i = 1; i <= n; ++i) a[i] = rd();
    int u = (n & 1), v = 1 - (n & 1);
    for (int i = n; i; --i, u ^= 1, v ^= 1) {
    f[u][a[i]] = 1;
    pos[u].push_back(a[i]);
    int lst = a[i];
    for (auto x : pos[v]) {
    int cnt = (a[i] + x - 1) / x;
    //前面的方案数为i, 后面的方案数为f[v][x]
    ans = (ans + 1ll * i * f[v][x] * (cnt - 1)) % mod;
    int tar = a[i] / cnt;
    f[u][tar] += f[v][x];
    if (lst != tar) {pos[u].push_back(tar); lst = tar;}
    }
    for (auto x : pos[v]) f[v][x] = 0;
    pos[v].clear();
    }
    printf("%d\n", ans);
    for (auto x : pos[0]) f[0][x] = 0;
    for (auto x : pos[1]) f[1][x] = 0;
    pos[0].clear(); pos[1].clear();
    }

Oct / 29 - Edu #116 (4/6)

Oct / 25 - Round #751 (3/8)

  • D(不是DAG):没注意到方案中一次跳跃可能会落到比出发点更低的地方。直接线段树优化建图是可以的。

Oct / 24 - Round #750 (7/8)

  • A (数据范围):因为 1,2,3 个数都大于 $0$ ,所以可以组合出 $[1,\sum a_i]$ 内所有整数,所以拆成两部分差不会超过 $1$
  • D (特殊情况):奇数构造时忘记考虑可能有相同的数字,用减法可能会产生 $0$ ,$n$ 为奇数的时候恰好是 $n$ 上界 $-1$ ,因此刚好剩出来一个 $10^4$ 的空间,直接用加法构造即可。
  • E (倒序转移):要求区间越往后,长度越短+值越大,不好扩展(无法继承上一状态),转化成从右往左选区间,长度越长+值越小,这样就可以继承之前的状态了。设 $f[i][j]$ 表示到第 $i$ 个为止,最后一段长度为 $j$ 的区间和的最大值。
  • F (维护技巧)

Oct / 17 - Round #749 (2/9)

Oct / 13 - Edu #115 (0/6)

Oct / 09 - Round #747 (0/6)

Oct / 03 - Round #746 (5/7)

  • B(分讨):交换距离不小于 $k$ ,则不可移动的范围为 $[n - x + 1, x]$ ,只需保证这些位置数字正确即可。

  • C(性质):注意到多个块是可以三个合并成一个的,因此任何解都等价于只划分成两个块或三个块。设所有 $a[i]$ 异或和为 $A$ ,若 $A=0$ 则可以划分为两个块。其余情况判断是否能划分成三个块,一遍 dfs 计数异或和为 $A$ 的块即可。

    1
    2
    3
    4
    5
    void dfs(int u, int fa) {
    for (int i = hd[u], v; i; i = e[i].nxt)
    if ((v = e[i].to) != fa) {dfs(v, u); a[u] ^= a[v];}
    if (a[u] == tar) {++cnt; a[u] = 0;}
    }
  • D(构造):寻找具有某个性质的路径可以考虑转化到欧拉序上二分。

  • E(性质):注意到任意奇数长度的区间,所有数字的与和 $\le$ 异或和,因为与和为 $1$ 的位置,异或和里也是奇数个 $1$ 。而偶数长度的区间,与和为 $1$ 的位置异或和必定为 $0$ ,因此只要判断区间所有数比与和最高位更高的部分异或和是不是 $0$ 即可,枚举与和最高位,按照异或差分的思路维护,注意区间偶数长度的要求,需要区分奇偶位置。

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    int a[N], lst[N][2], ans;

    memset(lst, 0xcf, sizeof(lst));
    for (int t = 20; t >= 0; --t) {
    lst[0][0] = 0;
    for (int i = 1, pre = 0; i <= n; ++i) {
    if (!(a[i] & (1 << t))) {
    pre = 0;
    while (!s.empty()) {
    int x = s.front(); s.pop();
    lst[x][0] = lst[x][1] = -1;
    }
    //注意区间从头开始的情况
    lst[0][i & 1] = i;
    lst[0][1 - (i & 1)] = -1;
    } else {
    pre ^= (a[i] >> (t + 1));
    int fl = (i & 1);
    if (lst[pre][fl] < 0) lst[pre][fl] = i;
    if (lst[pre][fl] >= 0) ans = max(ans, i - lst[pre][fl]);
    s.push(pre); //记录需要清空的位置
    }
    }
    while (!s.empty()) {
    int x = s.front(); s.pop();
    lst[x][0] = lst[x][1] = -1;
    }
    }

Feb / 12 - Round #701 (6/6)

  • Add and Divide

    首先最优解一定是 ++b 若干次(可能为 $0$ ),然后再一直做 a=a/b 直到符合条件。

    考虑最差的情况:$a=10^9,b=1$ ,至多只需 $1+\lceil \log_2{10^9}\rceil = 31$ 次,所以所有答案都 $\le 31$。

    因此枚举++b 的操作次数 $k\ (0\le k\le 31)$ ,然后暴力计算答案即可,复杂度 $\text O(t\log^2 a)$ 。

  • B. Replace and Keep Sorted

    考虑 $b_i\not =a_i$ ,那么考虑 $b_i$ 的取值范围:

    • 对于 $i=l$ 的情况, $1\le b_i<a_{i+1}$ ,与 $a_i$ 不同的方案有 $a_{i + 1} - 2$ 个。

    • 对于 $i=r$ 的情况, $a_{i-1}<b_i\le k$ ,与 $a_i$ 不同的方案有 $k - a_{i-1} - 1$ 个。

    • 对于 $l<i<r$ 的情况, $a_{i-1}<b_i<a_{i+1}$ ,与 $a_i$ 不同的方案有 $a_{i+1}-a_{i-1}-2$ 个。

    $i$ 不同的贡献是独立的,所以用前缀和优化一下第三部分的计算,各个位置的方案数求和即可。

  • C. Floor and Mod

    设 $\lfloor a/b\rfloor=a\ \text{mod}\ b=k$ ,根据整除理论,有 $a=k *b+k$ ,且 $k < b$ 。

    考虑枚举 $k$ ,去数可行的 $b$ ,那么限制条件有:$1\le b \le y\ ,\ 1\le k*b+b=a\le x$

    移项,得 $1\le b\le \min(y,\ x / k - 1)$ ,即 $k$ 的贡献为 $\min(y,\ x/k - 1)$ 。

    又由 $k\le b$ 得 $k ^2 < k * b+k = a\le x$ ,得 $k\le \sqrt x$ ,因此 $O(t\sqrt x)$ 枚举 $k$ 直接计算即可。


    比赛时用的另一种做法,复杂度也是 $\text O(t\sqrt x)$ :

    考虑枚举 $b$ ,由上知可行的 $a = k *(b+1)$ 且 $1\le k\le b-1$ 。

    考虑枚举 $b$ ,则贡献为 $\min(b-1,\lfloor x/(b + 1)\rfloor)$ ,具体的:

    • 当 $(b+1)(b-1)\le x$ 时,即 $b \le \sqrt{x + 1}$ 时,贡献为 $b-1$ ,可以等差数列求和。

    • 否则贡献取 $\lfloor x /(b + 1)\rfloor$ ,整除分块计算即可。

  • D. Multiples and Power Differences

    数据范围 $1\le a_{i,j}\le 16$ ,观察:

    • $\text{lcm}(1,2,\cdots,16)=720720\le 10^6 - 10^5$

    • $16^4 = 65536\le 10^5$

    将矩阵黑白染色,黑色变为 $720720$ , 白色变为 $720720+x^4$ 即可 ( $x$ 为原矩阵对应位置的数)

  • E. Move and Swap

    设 $f[u]$ 表示红点在 $u$ 时,$u$ 及其子树的最大得分。

    若红蓝不交换,假设红色在 $u$ ,则最优解本质上是 $u$ 儿子最大得分 + 同深度点与 $u$ 点权最大差值。

    若红蓝交换,则本质是任选同深度节点 $v$ 的最优儿子,及 $v$ 与 $u$ 点权差值。

    那么转移方程具体的(设 $d[u]$ 表示节点 $u$ 的深度):
    $$
    f[u] = \max \bigg \{ \max_{s\in son[u]} f[s] + \max_{d[v] = d[u]} | a_u - a_v |\ ,\ \max_{d[v]=d[u]}\bigg(|a_u-a_v| + \max_{s\in son[v]} f[s]\bigg)\bigg \}
    $$
    可以发现转移是从深到浅转移的。第一部分直接枚举儿子转移即可,第二部分维护:

    $$
    mxp[d] = \max_{d[v]=d}\bigg(a_v + \max_{s\in son[v]} f[s]\bigg)\ ,\ mxm[d] = \max_{d[v]=d}\bigg(-a_v + \max_{s\in son[v]} f[s]\bigg)
    $$

    则第二部分的转移就可以表示为 $f[u] = \max{mxp[d[u]] - a[u],mxm[d[u]]+a[u]}$ 。

  • F. Copy or Prefix Sum

    假设当前处理到第 $i$ 位,前 $i-1$ 位的和为 $S$ ,那么 $a_i=b_i$ 或者 $a_i=b_i-S$ 都是可以的。

    那么答案为什么不是 $2^n$ 呢?因为 $S=0$ 时会重复计数。

    设 $f_{i,S}$ 表示前 $i$ 位填完,前缀和为 $S$ 的方案数,那么转移为:

    • $a_i=b_i$ : $\forall S\ ,\ f_{i+1,S+b_i} += f_{i,S}$

    • $a_i = b_i -S$ : $\forall S\ ,\ f_{i+1,b_i}+=f_{i,S}$ ,即 $f_{i+1,b_i}=\sum_{\forall S} f_{i,S}$

    • $S=0$ 去重:$f_{i+1,b_i} -= f_{i,0}$

    综上,$i\to i+1$ 转移的过程即为:所有的 $f$ 整体向右偏移 $b_i$ ,然后对 $f_{b_i}$ 单独赋值。

    因此省略第一维,使用 map 维护第二维,用记录整体偏移量的方法优化。

    记录 $tot=\sum_{k=1}^ib_k\ ,\ ans=\sum_{\forall S} f_S$ ,递推即可,实现见 代码

Feb / 05 - Round #699 (4/6)

  • A. Space Navigation

    统计四个方向的移动分别有多少,只保留走向目标向量对应方向的移动,判断是否可达。

  • B. New Colony

    观察数据范围 $n,h_i\le 100$ 最多扔 $10^4$ 个石头就结束了,模拟 $\text O(n^2h)$ 即可。

  • C. Fence Painting

    首先如果最后一次涂色不在 $b_i$ 里,肯定无解。

    然后如果所有涂色不能满足将所有 $a_i$ 和 $b_i$ 不一样的位置覆盖为 $b_i$ ,则无解。

    剩下的情况必定有解,一种构造方法:

    对每种颜色 $c$ 预处理出来所有 $a_i$ 和 $b_i$ 不同且 $b_i=c$ 的位置集合 $S_c$ 。

    首先确定最后一次涂色的位置 $pos_m$ :

    • 若 $S_{c_m}$ 为空,则令 $pos_m$ 为任意一个 $b_i=c_m$ 的位置。

    • 若 $S_{c_m}$ 不为空,则让 $pos_m$ 为 $S_{c_m}$ 中的任意一个,并将该位置移出 $S_{c_m}$ 。

    然后时间倒序考虑,对于当前颜色 $c_j$ :

    • 若 $S_{c_j}$ 为空,那么让 $pos_j=pos_m$ ,因为第 $m$ 次操作是最后一次,所以肯定会覆盖。

    • 若 $S_{c_j}$ 不为空,则让 $pos_j$ 为 $S_{c_j}$ 中任意一个位置,然后将该位置移除 $S_{c_j}$ 即可。

  • D. AB Graph

    首先奇数长度一定有解,在两个点之间来回跑就可以了。

    考虑偶数长度,如果存在连接两个点的一组边类型相同,那么就一直在这两个点之间来回跑就可以了。

    剩余的情况就是每一组边都是一条 $A$ 一条 $B$ ,那么对于 $n\ge 3$ 时很容易证明:

    存在一个点 $x$ ,满足存在另两个点 $y,z$ ,边 $x\to y$ 和 $x\to z$ 的类型不同。

    反证法:假设对于任意的点,所有的出边类型相同,入边类型相同,且两种边类型不同。

    不妨设点 $x$ 的所有出边类型均为 $A$ ,也就是说对于其他任意的点的入边类型均为 $A$ (由假设性质)

    那么对于任意另外两个点 $y,z$ 之间的边的类型,存在矛盾:

    $z$ 的入边由上知类型为 $A$ ,则 $y\to z$ 是 $z$ 的入边,类型必须为 $A$。

    $y$ 的出边与入边类型相反,则 $y\to z$ 是 $y$ 的出边,类型必须为 $B$ 。

    因此只需要 $\text O(n)$ 枚举 $x$ ,$\text O(n)$ 扫描其他点,判断是否存在 $y,z$ 即可。

    对于 $m = 4k$ 的情况,构造解形如 $x\ y\ x\ y\cdots x\ y\ x\ z\ x\ \cdots z\ x\ z\ x$ 即可。

    对于 $m = 4k+2$ 的情况,构造解形如 $y\ x\ y\ x\ y\cdots x\ y\ x\ z\ x\ \cdots z\ x\ z\ x\ z$ 即可。


本博客所有文章除特别声明外,均采用 CC BY-SA 4.0 协议 ,转载请注明出处!