noip2020 模拟赛

记录考试总结

2020.09.05

比赛入口

---

比赛时一开始把T1做了，用了个错算法，但是我当时不知道。随后想了一会儿做了T2。最后半个小时一对拍就发现T1用了个错的dp方法，于是赶紧写了个60pts暴力交上去。
然而，T2由于把题目理解错了，只计算了 $\sum_{i=1}^{n}p_i$ ，导致100pts$\to$20pts。

最终得分：80

---

Solution：

1. 无线网路发射器选址

经典的求最大矩形问题：悬线法。

记
$h_{i, j}$ 为以 $(i,j)$ 为起点，向上的最长空线段（即悬线）长度。
$l_{i,j}$ 为 $(i,j)$ 向左最多拓展到的点
$r_{i,j}$ 为 $(i,j)$ 向右最多拓展到的点
$s_{i,j}$ 为悬线最多向左移动到的列编号
$t_{i,j}$ 为悬线最多向右移动到的列编号

则有

$$ans=max \left(h_{i,j}\times(t_{i,j}-s_{i,j}+1)\right)\quad(1\le i\le n,1\le j\le m)$$

递推式

$$s_{i,j}=max(s_{i-1,j},l_{i,j})$$

$$t_{i,j}=min(t_{i-1,j},r_{i,j})$$

code

2. 联合权值

树形dp

求联合联通块（即下图左边图形）的数量，要求每一条直线在树上都是一条链。

考虑分开考虑

设

形式	意义
$cnt_i$	节点 $i$ 的儿子数量
$son_{i,j}$	节点 $i$ 的第j个儿子，简写为 $son_j$
$subtree_i$	节点 $i$ 的子树
$f_i$	以 $i$ 为深度较小的端点的链的数量，即上图编号1
$g_i$	以 $i$ 为顶点的两条链的方案数，即上图编号2
$h_{i,j}$	以 $i$ 为顶点的两条链，且其中一条链经过 $i$ 的第 $j$ 个儿子的方案数。故有 $g_i=(\sum_{j=1}^{cnt_i}h_{i,j}) / 2$
$w_i$	节点 $i$ 的子树内所有点的 $g$ 值和，即 $\sum_{j\in subtree_i}g_j$
$p_i$	以节点 $i$ 为“根”的上图编号3的图形的数量

可以发现，答案为：

$$ans=\sum_{i=1}^{n}\sum_{j\in subtree_i}p_j$$

依次递推，求得答案。

$$f_i=\sum_{j=1}^{cnt_i}f_{son_{j}}+1$$

$$h_{i,j}=f_{son_{j}}\times \left( (\sum_{k=1}^{cnt_i}f_{son_k})-f_{son_j}\right)$$

$$g_i=\frac{\sum_{j=1}^{cnt_i}\ h_{i,j}}{2}$$

$$w_i=\sum_{j\in subtree_i}g_j$$

$$p_i=\sum_{j=1}^{cnt_i}\left((g_i-h_{i,j})\times w_{son_j}\right)$$

复杂度 $O(n^2)$

code

---

2020.09.06

入口 contest_show.php?cid=682

这一天的比赛还算顺利，T1、T3写出来了，T2写了个 $O(n^2)$ 暴力水了50pts。

---

Solution

T1

题意：有 $n$ 个相同的弹珠， $k$ 个相同的盒子。现在随机的将每个弹珠扔进盒子中，使得最终每个盒子非空，求出一共有多少种不同方案，对 $998244353$ 取模。

不难想到一个略暴力的dp方法：设 $f(i,j)$ 表示将 $j$ 个弹珠放到 $i$ 个盒子（每个盒子可以放的数量 $x$ 满足 $0\le x\le j$ ，且 $x_1\le x_2\le\ ...\ \le x_{i-1}\le x_i$）的方案数。

这里我们设第一个盒子里面放了 $k$ 个弹珠，则剩下的 $i-1$ 个盒子里面每个盒子至少要放 $k$ 个弹珠才能满足 $x_1\le x_2\le\ ...\ \le x_{i-1}\le x_i$。此时剩下 $i-1$ 个盒子和 $j-ki$ 个弹珠，方案数为 $f(i-1, j-ki)$ 。
因此有状态转移方程：

$$f(i,j)=\sum_{k=0}^{\left\lfloor\ j/i\ \right\rfloor}f(i-1,j-ki)$$

特别地，$f_{0,0}=1$ 。答案为 $f(k,n-k)$

这个算法的复杂度为 $O(n^3)$ 。

考虑优化：
观察一下状态转移的来源：

以 $f(2,7)$ 为例：

f(1, 7) -> f(2, 7)
f(1, 5) -> f(2, 7)
f(1, 3) -> f(2, 7)
f(1, 1) -> f(2, 7)

可以发现，第二维 $j-ki$ 对 $i$ 取模是一个固定的值，且等于 $j\bmod i$ 。不妨令 $j-ki=p$ ，方便表示。在上面的例子中，$p\equiv j\pmod{i}$ 。且取值范围 $j\bmod i\le k\le j$ ，所以 $k$ 构成一个序列： $j\bmod i$，$(j\bmod i)+i$ ，$(j\bmod i)+2i$ ，… ，$(j\bmod i)+\lfloor\frac{j}{i}\rfloor i$ 。

设 $g(p,k)$ 表示第一项为 $p$ 的序列的第 $0...k$ 个元素之和。
则 $f(i,j)=g(j\bmod i,\lfloor\frac{j}{i}\rfloor)$ 。

考虑 $f(i,j)$ 对 $g$ 数组的影响。

令 $p=j\bmod (i+1)$ ， $q=\left\lfloor\dfrac{j}{i+1}\right\rfloor$ 。

则 $g(p,q)=\begin{cases}f(i,j)&\quad(q=0)\\g(p,q-1)+f(i,j)&\quad(q\ge 1)\end{cases}$
实际编写过程中要使用滚动数组，防止 $g$ 数组被覆盖。

实际上把 $f(i,j)$ 代入到上式中可以化简递推式，去掉一个数组 可是我懒得搞 。

code

---

T2

给出一棵树，有边权，求该树中某路径长度$k$ 使得 $k>=S$且$k<=E$

一道很经典的点分治

可以每次以现在森林中每棵树的重心心作为根计算答案，一条路径的长度只有经过节点 $root$ 和不经过 $root$ 两种情况，其中不经过 $root$ 的方案可通过递归 $root$ 的子树来求答案。

那么每次设 $root$ 的子树每个节点的 $d(v)$ 表示节点 $v$ 到 $root$ 的距离。

易知经过 $root$ 的路径一定为 $d(u)$ 或$d(v)$ 组成，那么考虑给该子树的所有节点编号按 $d(v)$ 进行排序，每次选取两个节点求他们的 $d(u)+d(v)$ 值即为路径答案。

将子树存储在数组 $a$ 中，大小为 $cnt$
设 $l=1$，$r = cnt$

如果当前$d(a_l)+d(a_r)>E$ 那么说明 $r$ 的下标取太大了，将 $r$ 赋值为 $r-1$
如果当前$d(a_l)+d(a_r)<S$ 那么说明左端点为 $l$ 的情况已经考虑完了，将 $l$ 赋值为 $l+1$

倘若找到符合条件的 $l$ 和 $r$ 满足 $S\le d(a_l)+d(a_r)\le E$，仍需考虑一个问题：如果 $a_l$ 和 $a_r$ 在同一棵子树内，那么它们之间的路径不经过节点 $root$ ,考虑如何解决这个问题：

如果 $S\le d(a_l)+d(a_{r-1}) \le E$，那么考虑 $r$ 自减可能会找到一种情况使得 $a_l$ 和 $a_r$ 不在同一棵子树内，就会找到一组解

否则 $a_l$ 肯定找不到一组解使得$S\le d(a_l)+d(a_{r}) \le E$，$a_l$ 就一定无法对答案造成影响，将 $l$ 赋值为 $l+1$ 继续找解。

复杂度$O(nlog^2n)$
code

---

T3

要求在 $[1,n]$ 范围内有多少无序数对满足$gcd(a,b)=a \ xor\ b$

1. 引理1

若 $gcd(a,b)=a\ xor\ b$

则 $gcd(a,b)\ xor\ gcd(a,b)\ xor\ a=a\ xor\ b\ xor\ a\ xor\ gcd(a,b) $

那么 $a=gcd(a,b)\ xor\ b$

2. 引理2

易知 $gcd(a,b) \times k=a-b$

因此得到 $gcd(a,b) <= a-b$

3. 引理3

观察 $a-b$ 和 $a\ xor\ b$

对于两个数的第 $k$ 位
| -----------: | -----------: | -----------: | -----------: | -----------: |
| num1 | 0 | 0 | 1 | 1 |
| num2 | 0 | 1 | 0 | 1 |
| xor | 0 | 1 | 1 | 0 |
| 减法 | 0 | -1 | 1 | 0 |

对比表格会发现

$a-b<=a\ xor\ b$

根据已求证的引理2和引理3得到

$$gcd(a,b)<=a-b<=a\ xor\ b$$

又由题目条件：$gcd(a,b)=a\ xor\ b$
不难得到$gcd(a,b)=a-b=a\ xor\ b$
那么只需枚举 $a-b$ 的值，并且 $gcd(a,b)=a-b$ ，那么两个数 $a$ 和 $b$ 可表示为：$a=k \times i,b=(k+1) \times i$

每次得到两个数 $a$ 和 $b$ 时，还需检验第三个条件 $a-b=a\ xor\ b$ 即可
code

---

2020.09.19

contest_show.php?cid=691

---

Review

在手推样例之前，不要试图以任何方式写代码。

T1是一个比较有意思的题目，但是我一开始把 “小 $\small\mathtt{T}$ 的乐谱与乐谱 $\small\mathtt{P}$ 的最长公共子序列长度为 $\small\mathtt{E}$” 理解成了 “小 $\small\mathtt{T}$ 的乐谱与乐谱 $\small\mathtt{P}$ 的最长公共连续子序列长度为 $\small\mathtt{E}$”，而且只看了样例的最后一行就开始敲代码。
一个小时之后，等我把 $\small\mathtt{hash}$ 调完，输入样例的那一刻，结果发现样例第一组数据不是连续的！人都傻了。
幸好这个 $\small\mathtt{dp}$ 不是很难，冷静之后，搞了几十分钟后还是写了出来，但是就失去了想剩下两题正解的时间。

T2是所谓莫队算法，很久以前学的，好像忘了，需要在接下来的一个星期之内重新学一下。

T3也是一个 $\small\mathtt{dp}$，但是需要一些数学处理。

---

Solution

1.Piano

这里记录两种方法

先是题解做法：

“保证小 T 的乐谱中每个音符都不会重复出现。”
注意到这个条件,我们可以把 $\small\mathtt{LCS}$ 问题转换成 $\small\mathtt{LIS}$(最长上升子序列)问题。
数据是随机的,所以先将乐谱 A 中的字符串哈希,转成数值,
(总共只有 $5\times7\times10^6$ 种哈希值,所以哈希值之间没有冲突。)
然后通过哈希值判断,将乐谱 B 中无效的音符去除。
记 $C_i$ 为标号序列, 若 $A_i$ = $B_j$ ,那么 $C_j$ = $i$
接下来对序列 $C$ 做 $\small\mathtt{LIS}$ 就可以啦~!
时间复杂度: $O\left( S + RL(logL+logS) \right)$

然后是我的考场做法：

设 $f(i, j)$ 表示 $A_{1\to i}$ 与 $B_{1\to j}$ 的 $\small\mathtt{LCS}$ 且满足 $A_i$ = $B_j$， $pos(x)$ 满足 $B_i=A_{pos(i)}$

则有状态转移方程

$$f(pos(p),p)=\max\left(\left(\max_{i,j=1}^{i<pos(p),j<p}f(i,j) \right)+ 1, \max_{i,j=1}^{i\le pos(p),j<p}f(i,j)\right)$$

$$f(pos(p),p)=m$$

理解：$f(i,j)$ 满足 $A_i$ 与 $B_j$ 匹配，又因为 $A_{pos(p)}$ 与 $B_{p}$ 匹配，所以 $f(pos(p),p)=f(i,j)+1$
为什么 $i$ 与 $pos(p)$ 不能取等号呢？由于可能有多个 $p_1$，$p_2$ （$p_1 < p_2$）对应同一个 $pos(p)$，那这时 $f(pos(p), p_2)\not=f(pos(p), p_1)+1$ ，因为$A_{pos(p)}$ 不能使用两次。但是 $f(pos(p),p_2)$ 可以等于 $f(pos(p),p1)$ ，相当于 $A_{pos}$ 只与 $B_{p_1}$ 匹配，不与 $B_{p_2}$ 匹配。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

const int MAXN = 1e5 + 10;

struct Pos_val_pair {
    int val, pos;
    const bool operator < (const Pos_val_pair &pvp) {
        if (val != pvp.val) return val < pvp.val;
        return pos < pvp.pos;
    }
}x[MAXN];

struct Binary_indexed_tree {
    int size = MAXN, c[MAXN + 10];
    void add(int x, int v) { for (; x < size; x += (x & (-x))) c[x] = max(c[x], v); }
    int query(int x) { int v = 0; for (; x; x -= (x & (-x))) { v = max(v, c[x]); } return v; }
    void clear() { memset(c, 0, sizeof(c)); }
}bit;

int a[MAXN], b[MAXN << 1];
int n, q, m;

int idx(char str[]) {
    int l = strlen(str), p = l;
    for (int i = l - 1; i >= 0; i--) {
        if (str[i] == '{' || str[i] == '(' || str[i] == '[') {
            p = i;
        }
    }
    int res = 0;
    for (int i = 1; i <= p - 1; i++) {
        if (str[i] == '.') continue;
        res = res * 10 + str[i] - '0';
    }
    res += (str[0] - 'A' + 1) * 10000000;
    return res;
}

int main() {
    freopen("Piano.in", "r", stdin);
    freopen("Piano.out", "w", stdout);
    scanf("%d%d", &n, &q);
    char str[30];
    for (int i = 1; i <= n; i++) {
        scanf("%s", str);
        a[i] = idx(str);
        x[i].val = a[i];
        x[i].pos = i;
    }
    sort(x + 1, x + n + 1);
    for (int t = 1; t <= q; t++) {
        bit.clear();
        scanf("%d", &m);
        for (int i = 1; i <= m; i++) {
            scanf("%s", str);
            b[i] = idx(str);
        }
        int ans = 0;
        for (int i = 1; i <= m; i++) {
            Pos_val_pair p; p.pos = 0, p.val = b[i];
            int pos = lower_bound(x + 1, x + n + 1, p) - x;
            if (x[pos].val != b[i]) continue;
            int f = bit.query(x[pos].pos - 1) + 1;
            f = max(f, bit.query(x[pos].pos));
            ans = max(ans, f);
            bit.add(x[pos].pos, f);
        }
        printf("%.6lf\n", (double)ans / m);
    }
    return 0;
}

2.Movie

离线处理。
莫队算法+线段树
莫队算法:参考 莫涛的论文《Hose 解题报告》
直接分块解决
考虑两个任意位置的区间 $[L1,R1]$ 与 $[L2,R2]$,
已经维护好了前者的信息, 要得 到后者的信息,
只需要插入或删除 $(L1,L2]$ 与 $(R1,R2]$ 中的数。
具体来说,
若 $L1 < L2$，则删除 $[L1, L2)$ 内的数,
若 $L1 > L2$，则插入 $[L2 , L1)$ 内的数。
若 $R1 < R2$，则插入 $(R1,R2]$ 内的数,
若 $R1 > R2$，则删除 (R2,R1] 内的数。
无论是哪种情况，所需的操作数总是 $|L1−L2| + |R1−R2|$。
将序列分成 $\sqrt M$ 块,以 $L$ 所在块为第一关键字, $R$ 为第二关键字排序。
然后按排序之后的顺序处理序列。
所以时间复杂度为 $O((M +Q)\sqrt M )$
(线段树维护最长连续区间是经典算法就不多说了。)
时间复杂度: $O(( M +Q)\sqrt M \log_2 N )$

3.Gift

咕咕咕

---

2020.10.18

T1:约瑟夫问题

设 $f(n,k)$ 表示 $n$ 个人，每 $m$ 个人删掉的答案

对于 $f(n,k)$ 而言，在一圈内可以删掉 $\left\lfloor \dfrac{n}{k} \right\rfloor $个，剩 $n-\left\lfloor \dfrac{n}{k} \right\rfloor$ 个人，此时在 $\left\lfloor \dfrac{n}{k} \right\rfloor \cdot k$ 个人的位置，即 $n - n \mod k$。于是我们继续递归处理，但是要还原相对位置，从 $n-(n\ mod\ k)$ 还原到 $0$ 的位置，位置 $res$ 减去 $\left\lfloor \dfrac{n}{k} \right\rfloor$。同时还要考虑每 $k-1$ 个人就要补上一个之前删掉的人，下标加上 $\left\lfloor \dfrac{res}{k-1} \right\rfloor$。

int josephus(int n, int k) {
  if (n == 1) return 0;
  if (k == 1) return n - 1;
  if (k > n) return (josephus(n - 1, k) + k) % n;  // 线性算法
  int res = josephus(n - n / k, k);
  res -= n % k;
  if (res < 0)
    res += n;  // mod n
  else
    res += res / (k - 1);  // 还原位置
  return res;
}

---

T2:

trick:

$$\sum_{1\le j<k\le n}(a_jb_k-a_kb_j)^2=\left(\sum_{k=1}^n{a_k}^2\right)\left(\sum_{k=1}^n{b_k}^2\right)-\left(\sum_{k=1}^na_kb_k\right)^2$$

用 BIT 维护。

Provement:

$$\sum_{1\le j<k\le n}(a_jb_k-a_kb_j)^2\qquad(1)$$

观察一下，发现 $j$ 与 $k$ 相等时，$(a_jb_k-a_kb_j)^2$的值是零，所以 $(1)$ 乘二的结果就是

$$\sum_{1\le j,k\le n}(a_jb_k-a_kb_j)^2\qquad(2)$$

考虑化简

$$\begin{aligned}\sum_{1\le j<k\le n}(a_jb_k-a_kb_j)^2&=\dfrac{1}{2}\left(\sum_{1\le j,k\le n}(a_jb_k-a_kb_j)^2\right)\\&=\frac 12\left(\sum_{1\le j,k\le n}{a_j}^2{b_k}^2+\sum_{1\le j,k\le n}{a_k}^2{b_j}^2-2\sum_{1\le j,k\le n}a_jb_ka_kb_j\right)\\&=\frac 12\left(2\sum_{1\le j,k\le n}{a_j}^2{b_k}^2-2\sum_{1\le j,k\le n}a_jb_ka_kb_j\right)\\&=\sum_{1\le j,k\le n}{a_j}^2{b_k}^2-\sum_{1\le j,k\le n}a_jb_ka_kb_j\\&=\left(\sum_{j=1}^n{a_j}^2\right)\left(\sum_{k=1}^n{b_k}^2\right)-\left(\sum_{j=1}^na_jb_j\right)\left(\sum_{k=1}^na_kb_k\right)\\&=\left(\sum_{k=1}^n{a_k}^2\right)\left(\sum_{k=1}^n{b_k}^2\right)-\left(\sum_{k=1}^na_kb_k\right)^2\end{aligned}$$

QED.

---

T3:

期望题，咕咕~

---

2020.10.24

试卷上写不要文件，测的时候又要，真的坑

---

总结：考试时大部分时间在划水，如果多点时间推，T1 没准就推出来了

---

T1

暴力

T2

打表

T3

没看

T4

放弃

---

result: 50pts

---

2020.11.28

color

想了好久，没想出来，就写一个自以为正确的构造，跑了。
结果只有 10 pts

发现只有 2 是偶质数，$\bmod 4$ 构造颜色，刚好能干掉限制条件

很多次没考虑到跟取模有关的构造方法了。

array

想出来了贪心考虑给定最小值的情况，但是需要改变式子形态：将填满的位置而不是最小值分离出来，才能推出正解。

直接二分斜率乱搞能得 95 pts

query

考虑把路径拆成两条链。

把一条链上的式子写出了，将与某个特定变量有关的全部移到式子的一边，方便处理。

$dep(u) = dep(v)+v$

查询 u 至 lca 上的点每个点 x ，满足 $dep(x)+x=dep(u)$ ，于是可以用主席树维护一下每个点到根节点路径上的所有点的 $dep+id$ 值（预处理）。
从 lca 至 v 的点 x ，满足 $dep(x)+dep(u)-2\times dep(lca)=x$ 维护 $id-dep$。

查询时在两颗主席树上查 $dep(u)$ 和 $dep(u)-2\times dep(lca)$

network

gugugu~~