2022 东北四省赛 vp 记录

link: 牛客

vp time: 250502 12:00-17:00

team: std::future

members: LittleYoo, Broken_Eclipse, f2021ljh

accepted: LEIKBCG

penalty: 1193

ranking: 26/238 (10.92%)

problem difficulty: LEIKBGCDFJAMH

L. Polygon（签到题）

给定 $n$ 条边的长度，判断能否构成一个简单多边形。

多边形不等式：每条边小于其他所有边之和。

故判断最大的边是否满足即可。

E. Plus（结论题）

给定 $n$ ，求所有 $p,q$ 满足 $1\le p\le q\le n$ ， $p,q$ 均为素数，且 $p^q+q^p$ 为素数。

$1\le n\le10^{18}$ 。

如果 $p,q$ 均为奇数或均为 $2$ ，则 $p^q+q^p$ 一定为偶数，故不为素数。

因此，满足条件的 $p,q$ 只有 $p=2$ ， $q\ge3$ 且为素数，且 $2^q+q^2$ 为素数。

进一步发现， $2^q\equiv(-1)^q\equiv-1\pmod3$ ，又因为 $q$ 为奇素数，若 $q>3$ 则有 $3\nmid q$ 且 $q\equiv2\pmod3$ ，故 $q^2\equiv1\pmod3$ ，因此 $2^q+q^2\equiv0\pmod3$ 。

综上， $p=2,q=3$ 为唯一的解。

I. Generator（期望 DP，Euler 常数）

给定一个正整数 $N$ （ $1\le N\le10^9$ ），每次操作在 $[1,N]$ 内均匀随机生成一个整数，并将 $N$ 变成这个整数。

求将 $N$ 变成 $1$ 的期望操作次数。误差不超过 $10^{-6}$ 即可。

设 $f(N)$ 为将 $N$ 变成 $1$ 的期望操作次数。当 $n\ge2$ 时，有

f(n)=\frac{0+f(2)+\dots+f(n)}n+1,

移项得

(n-1)f(n)=f(2)+\dots+f(n-1)+n,

同理有

f(n-1)=\frac{0+f(2)+\dots+f(n-1)}{n-1}+1,

即

(n-1)f(n-1)=f(2)+\dots+f(n-1)+(n-1),

相减得

f(n)-f(n-1)=\frac1{n-1}.

根据题意，初值 $f(1)=1$ 。故

\begin{aligned} f(n)&=(f(n)+f(n-1))+(f(n-1)+f(n-2))+\dots+(f(2)-f(1))+f(1)\\ &=\frac1{n-1}+\frac1{n-2}+\dots+\frac12+1+1\\ &=1+\sum_{i=1}^{n-1}\frac1i. \end{aligned}

当 $n\le K$ 时，可 $O(n)$ 计算。

当 $n>K$ 时，可以证明 $\sum_1^n1/i$ 与 $\ln n$ 的差是收敛的。

证明（梅加强）：由 $e=\lim_{n\to\infty}(1+1/n)^n$ ，且数列 $a_n=(1+1/n)^n$ 递增， $b_n=(1+1/n)^{n+1}$ 递减，且 $a_n,b_n$ 收敛于 $e$ ，有不等式
$\left(1+\frac1k\right)^k<e<\left(1+\frac1k\right)^{k+1},$
两边取对数得
$k\ln\left(1+\frac1k\right)<1<(k+1)\ln\left(1+\frac1k\right),$
即
$\frac1{k+1}<\ln\left(1+\frac1k\right)<\frac1k.$
对于 $k=1,2,\cdots,n$ ，将上述不等式相加，得
$\frac12+\dots+\frac1n+\frac1{n+1}<\ln(n+1)<1+\frac12+\dots+\frac1n.$
令 $c_n=1+1/2+\dots+1/n-\ln n$ ，则由右端不等式知 $c_n>\ln(1+1/n)>0$ ，且有
$c_{n+1}-c_n=\frac1{n+1}-\ln\left(1+\frac1n\right)<0,$
故由单调有界准则知， $c_n$ 收敛，其极限记为 $\gamma$ ，称为 Euler 常数，计算表明
$\gamma=0.5772156649\cdots.$

可打表计算 $\gamma$ 的近似值，然后用 $1+1/2+\dots+1/n\approx\gamma+\ln n$ 近似。

取 $K=10^7$ 即可。

#include <bits/stdc++.h>
#define f(x, y, z) for (int x = (y); x <= (z); ++x)
using namespace std;
typedef double db;
int const K = 1e7;
db const _gamma = 0.577215665402;
int n;
db ans = 1;

signed main() {

    cin >> n;
    if (n <= K) {
        f(i, 1, n - 1) ans += 1.0 / i;
    } else {
        ans += _gamma + log(n - 1);
    }
    cout << fixed << setprecision(10) << ans << '\n';

    // int const N = 1e9;
    // db sum = 0;
    // f(i, 1, N) sum += 1.0 / i;
    // db err = sum - log(N);
    // cout << fixed << setprecision(12) << err << '\n';

    return 0;
}

由于要求的精度不高，在 $k$ 很大的情况下，可以将 $\frac1k+\frac1{k+1}+\dots+\frac1{k+w-1}$ 近似为 $\frac wk$ ，这样复杂度是 $O(K+(N-K)/w)\approx O(N/w)$ ，取 $w=4$ 即可通过。

#include <cstdio>
#include <algorithm>
#define ll long long
#define Reg register
using namespace std;
const int maxn = 210000;
int n;
double ans;
int main() {
    scanf("%d", &n);
    if (n == 1) ans = 1;
    else if (n == 2) ans = 2;
    else {
        ans = 2;
        int up = n - 1;
        double a = 0, b = 0;
        if (up <= 100000000 - 1) {
            for (Reg int i = 2; i <= up; ++i) ans += 1.0 / i;
        }
        else {
            int maxx = 100000000 - 1;
            for (Reg int i = 2; i <= maxx; ++i) ans += 1.0 / i;
            for (Reg int i = maxx + 1; i <= up; i += 4) ans += 4.0 / i;
        }
    }
    printf("%.10lf\n", ans);

    return 0;
}

由于 $N\le10^9$ ，也可采用分段打表的方式。（我不会）

K. Maze（BFS）

给定一个 $n\times n$ 的网格，有一些网格是障碍。现在要从 $(1,1)$ 走到 $(n,n)$ ，要求：

每次可以向上下左右走一步；

不能经过障碍；

沿同一方向连续走不超过 $m$ 步。

求最少步数。如果不能到达，输出 $-1$ 。

数据组数 $T\le50$ 。 $2\le n\le100$ ， $1\le m\le100$ 。保证 $n>40$ 的数据组数不超过 $10$ 。

记状态 $(i,j,k,dir)$ 为当前在 $(i,j)$ 网格，且在 $dir$ 方向上已经连续移动了 $k$ 次，其中 $dir\in\{0,1,2,3\}$ ，分别表示上下左右。

设 $d(i,j,k,dir)$ 为该状态下的最少步数，直接进行 BFS 即可，松弛操作类似最短路。

#include <bits/stdc++.h>
#define f(x, y, z) for (int x = (y); x <= (z); ++x)
using namespace std;
int const INF = 0x3f3f3f3f;
int const N = 110;
int const dx[4] = {-1, 1, 0, 0};
int const dy[4] = {0, 0, -1, 1};
int tt, n, m, d[N][N][N][4];
char g[N][N];

struct Node {
    int x, y, k, dir;
};

void bfs() {
    memset(d, 0x3f, sizeof d);
    queue<Node> q;
    q.push({1, 1, 0, 0});
    d[1][1][0][0] = 0;
    while (!q.empty()) {
        auto [x, y, k, dir] = q.front();
        q.pop();
        f(i, 0, 3) {
            if (i == dir && k == m) continue;
            int xx = x + dx[i], yy = y + dy[i];
            if (xx < 1 || xx > n || yy < 1 || yy > n || g[xx - 1][yy - 1] == '*') continue;
            int nxk = (i == dir ? k + 1 : 1);
            int cur = d[x][y][k][dir], &nxt = d[xx][yy][nxk][i];
            if (cur + 1 < nxt) {
                nxt = cur + 1;
                q.push({xx, yy, nxk, i});
            }
        }
    }
    int ans = INF;
    f(i, 0, 4) f(j, 0, m) ans = min(ans, d[n][n][j][i]);
    if (ans == INF) cout << "-1\n";
    else cout << ans << '\n';
    return;
}

void solve() {
    cin >> n >> m;
    f(i, 0, n - 1) cin >> g[i];
    bfs();
    return;
}

signed main() {
    cin.tie(0)->sync_with_stdio(false);

    cin >> tt;
    while (tt--) solve();

    return 0;
}

B. Capital Program（树的中心，贪心）

给定一棵 $n$ 个节点的树，边权为 $1$ 。

要求在树中选定一个大小为 $k$ 的连通块，使得连通块外所有点到连通块的距离的最大值最小。

输出这个最小值。

$5\le n\le100000$ ， $1\le k\le n$ 。

如果 $k=1$ ，则一定要选树的中心（直径的任意一个中点）作为首都。

以中心为根，向下选 $k$ 个点，根据贪心的思想，不断选与当前首都有连边的点中，子树深度最深的那个。

因此求出中心，以中心为根进行 DFS，求出每个节点的子树深度。

可以发现，选定的节点的子树深度一定是单调不增的。因此直接将子树深度按降序排序，那么第 $k$ 个即为最后一个选择的节点，故第 $\boldsymbol{k+1}$ 个为其他节点到连通块的最远距离。

时间 $O(n\log n)$ 。

如何求树的中心？

下面用类似拓扑排序的方法找到树的中心，即：开始时将叶子节点放进队列，从树中删去队首并出队的同时，向队列中不断加入新的叶子，最后一个入队的即为中心。

#include <bits/stdc++.h>
#define f(x, y, z) for (int x = (y); x <= (z); ++x)
#define pb push_back
using namespace std;
typedef pair<int, int> pii;
int const N = 1e5 + 10;
int n, k;
vector<int> g[N];

bitset<N> used;
int deg[N];
int getCenter() {
    queue<int> q;
    f(i, 1, n) {
        if ((deg[i] = g[i].size()) == 1) {
            q.push(i);
            used[i] = 1;
        }
    }
    int u;
    while (!q.empty()) {
        u = q.front();
        q.pop();
        for (int v: g[u]) {
            if (!used[v] && (--deg[v] == 1)) {
                q.push(v);
                used[v] = 1;
            }
        }
    }
    return u;
}

int dep[N];
void dfs2(int u, int fa) {
    for (int v: g[u]) if (v ^ fa) {
        dfs2(v, u);
        dep[u] = max(dep[u], dep[v]);
    }
    ++dep[u];
    return;
}

signed main() {
    cin.tie(0)->sync_with_stdio(false);

    cin >> n >> k;
    f(i, 2, n) {
        int u, v;
        cin >> u >> v;
        g[u].pb(v), g[v].pb(u);
    }

    int cen = getCenter();
    dfs2(cen, 0);

    sort(dep + 1, dep + n + 1, greater<int>());
    cout << dep[k + 1] << '\n';

    return 0;
}

或者可以用换根 DP 的方式求中心，即求到其他点的最大距离最小的点。

int dup[N], ddn[N], ddn2[N], msn[N], msn2[N];
void dfs(int u, int fa) {
    for (int v: g[u]) if (v ^ fa) {
        dfs(v, u);
        if (ddn[v] + 1 >= ddn[u]) {
            ddn2[u] = ddn[u], msn2[u] = msn[u];
            ddn[u] = ddn[v] + 1, msn[u] = v;
        } else if (ddn[v] + 1 > ddn2[u]) {
            ddn2[u] = ddn[v] + 1, msn2[u] = v;
        }
    }
    return;
}

void dfs1(int u, int fa) {
    for (int v: g[u]) if (v ^ fa) {
        if (msn[u] == v) dup[v] = 1 + max(dup[u], ddn2[u]);
        else dup[v] = 1 + max(dup[u], ddn[u]);
        dfs1(v, u);
    }
    return;
}

int getCenter() {
    dfs(1, 0);
    dfs1(1, 0);
    int res = 1, mn = ddn[1];
    f(i, 2, n) {
        int cur = max(ddn[i], dup[i]);
        if (cur < mn) {
            mn = cur, res = i;
        }
    }
    return res;
}

C. Segment Tree（思维题；贪心；DP）

下面用 $q$ 代替算法伪代码中的 $k$ 。

对于长度为 $q$ 的正整数序列 $P_0,P_1,\cdots,P_{q-1}$ ，其中 $P_i\in[1,m]$ ，执行上述算法，将序列插入动态开点线段树。

问如何构造序列 $P$ ，使得节点数 $cnt$ 取到最大值？输出这个最大值。

数据组数 $1\le T\le5\cdot10^5$ ， $1\le m,q\le10^9$ 。

设 $k=\lfloor\log_2m\rfloor,l=\lfloor\log_2q\rfloor$ 。

一棵线段树的形状一定是一个深度为 $k$ 的满二叉树，在其基础上选择 $m-2^k$ 个叶子，延伸出一层的左右儿子。

为了使选择的路径中包含尽可能多的未创建过的节点，应该左、右子树交替选择。

……（推出一个神必式子）

答案为

ans=-1+2^{l+1}+q(k-l)+\min\{m-2^k,q\}+\max\{0,q-2^k\}.

G. Hot Water Pipe（队列，暴力）

有一根热水管，由 $n$ 节组成，编号为 $1$ 到 $n$ ，每节容量为 $1$ 单位体积。

第 $i$ 节水管内的热水的初始温度为 $a_i$ ，且每分钟会下降 $1$ 单位温度。

任一节水管中的热水温度一旦小于 $T_{min}$ ，就会瞬间被加热至 $T_{max}$ ，加热时间可忽略不计。

使用热水时，从第 $n$ 节水管中取出 $1$ 单位体积热水，同时前 $n-1$ 节水管中的热水向后平移一节（温度不变），并在第一节水管中注入温度为 $T_{max}$ 的热水。

有 $m$ 次取水操作，每次操作在上次操作的第 $t$ 分钟后，且使用了 $k$ 单位体积的热水。

输出每次取出的热水温度的总和。

$1\le n,m\le10^6$ ， $1\le T_{min}\le a_i\le T_{max}\le10^6$ ， $1\le t,k\le10^6$ 。

注意到，热水的温度是周期性变化的，所以如果知道初始温度和经过的时间，就可以知道最终的温度。

另外，每次取水操作中，新加入的 $k$ 体积水的温度，无论何时总是相同的。

取水操作与加水操作的规则，符合队列的性质，故用队列来维护，元素为加水的体积和时间。

可以发现，在若干次取水操作之后，再取出的水，一定是后加入的水，而任意后加入的水的加入时间都是已知的，从而可以求出答案。

因此直接暴力模拟取水和加水的过程。

队列中同时最多有 $n$ 个元素，每次弹出至多 $k$ 个元素，加入 $1$ 个元素，由势能分析知，时间复杂度是 $O(n)$ 的。

#include <bits/stdc++.h>
#define f(x, y, z) for (int x = (y); x <= (z); ++x)
#define g(x, y, z) for (int x = (y); x >= (z); --x)
#define fi first
#define se second
#define mp make_pair
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
int const N = 1e6 + 10;
int n, m, tmin, tmax, dt, a[N];
queue<pii> q;

int get_t(ll tim, int t0) {
    int t = t0 - tim % dt;
    return t < tmin ? t + dt : t;
}

int get_t0(ll tim) {
    return tmin - 1 + tim % dt;
}

signed main() {
    cin.tie(0)->sync_with_stdio(false);

    cin >> n >> m >> tmin >> tmax;
    dt = tmax - tmin + 1;
    f(i, 1, n) cin >> a[i];
    g(i, n, 1) q.push(mp(a[i], 1));
    ll tim = 0;
    while (m--) {
        int t, k;
        ll tot = 0;
        cin >> t >> k;
        int kk = k;
        tim += t;
        while (!q.empty() && q.front().se <= k) {
            k -= q.front().se;
            tot += get_t(tim, q.front().fi) * 1ll * q.front().se;
            q.pop();
        }
        if (q.empty() && k) {
            tot += 1ll * k * tmax;
        } else if (q.front().se > k) {
            q.front().se -= k;
            tot += get_t(tim, q.front().fi) * 1ll * k;
        }
        q.push(mp(get_t0(tim), min(kk, n)));
        cout << tot << '\n';
    }

    return 0;
}

*D. Game（博弈，结论）

有 $n$ 堆石子，第 $i$ 堆石子有 $a_i$ 颗。Alice 和 Bob 轮流执行以下操作：

选择一堆非空的石子。

将若干颗石子从这堆中拿出，可以拿走全部，但不能不拿。

对这堆中剩余的每个石子，可以选择不动，也可以选择放到另一堆非空的石子中。

$Q$ 次询问，每次询问给定 $l,r$ ，问用 $a_l,\cdots,a_r$ 进行游戏，谁有必胜策略？

$1\le n,Q\le10^5$ ， $1\le a_i\le10^5$ 。

下面证明：如果所有石堆的石子数的出现次数都为偶数，则先手必败，否则先手必胜。

如果所有石堆的石子数的出现次数都为偶数，那么将所有石堆分成完全相同的两组，后手可以选择在另一组跟随先手的一切操作，最后清空的一定是后手，故后手必胜。
如果存在一堆石子，石子数的出现次数为奇数：不妨设 $0<a_1\le a_2\le\dots\le a_n$ 。
- 若 $n=2k+1$ ，则将 $a_n$ 取走，同时对于所有 $1\le i\le k$ ，在 $a_{2i-1}$ 上放 $a_{2i}-a_{2i-1}$ 个石子，由于
  $\sum_{i=1}^ka_{2i}-a_{2i-1}\le\sum_{i=1}^{2k+1}a_i-a_{i-1}<a_{2k+1},$
  这样做是可行的，得到的序列为 $(a_2,a_2,a_4,a_4,\cdots,a_{2k},a_{2k})$ ，故出现次数均为偶数。
- 若 $n=2k$ ，则从 $a_n$ 中取走 $a_n-a_1$ 个石子，同时对于所有 $1\le i\le k$ ，在 $a_{2i-1}$ 上放 $a_{2i+1}-a_{2i}$ 个石子，类似地，可以证明，这样做是可行的，得到的序列为 $(a_1,a_3,a_3,a_5,a_5,\cdots,a_{2k-1},a_{2k-1},a_1)$ ，故出现次数均为偶数。

对于静态询问区间内每个数的出现次数，可以用莫队实现。时间复杂度 $O(Q\sqrt n)$ 。

然而我们不需要求出每个数的具体出现次数，只需要求是否有数字出现过奇数次。因此可以用 异或哈希 的 trick 来做：给每个数随机赋一个 64 位权值，求异或和，如果为零，则所有数出现的次数都是偶数，否则存在至少一个数出现了奇数次。