26沈阳icpc

B. 出 Bug 的绘画软件I

题意简述

画布由若干有序图层组成，每层是 \(n\times m\) 的像素网格。像素值 \(0\) 表示透明，\(1\sim nm\) 表示不同颜色。某位置的合成可见值为所有图层中最上层非透明像素的值；若所有图层在该位置都透明，则可见值为 \(0\)。

初始没有图层。可以任意次执行： - 免费在最上方新建图层，初始化为全为颜色 \(c\) 的常量层（\(1\le c\le nm\)），或全透明层； - 花费 \(a\) 将任意图层中任意单个像素涂成颜色 \(c\)； - 花费 \(b\) 将任意图层中任意单个像素变为透明。

给定目标可见矩阵 \(p_{i,j}\)，求使最终合成图像等于目标图像的最小总花费。

数据范围

\(1\le T\le 10^5\)，\(1\le n,m\le 500\)，\(1\le a,b\le 10^6\)，\(0\le p_{i,j}\le nm\)，且所有测试用例的 \(\sum nm\le 10^6\)。

题解

贪心 对于每种颜色，要么在透明图层上只用画笔工具，要么在纯色图层上只用橡皮工具。图层摆放为：顶层为透明，下面为若干纯色。

设某种非透明色颜色数为 \(c\)，则使用画笔代价为 \(ac\)，使用橡皮代价为 \(bc(k-1)\)，\(k\) 为纯色图层从上到下的序号。透明色 \(c_0\) 单独考虑，代价为 \(c_0l\)，\(l\) 为纯色图层个数。

问题转化为，给颜色数组 \(c\) 分配代价，使得代价最小。假设 \(4b\) 刚好大于 \(a\)，查看代价数组：

a a a a a a a a 0
0 a a a a a a a c0
0 b a a a a a a 2c0
0 b 2b a a a a a 3c0
0 b 2b 3b a a a a 4c0
0 b 2b 3b a a a 4b 5c0
0 b 2b 3b a a 4b 5b 6c0
...

显然，出现 \(4b\) 及以上的代价是不优秀的，所以代价数组前缀为 \(bk\)，后缀为 \(a\)。颜色数组乘代价数组，倒序之积最小，枚举代价数组分界点计算代价即可。

A. 平方王国

题意简述

在 Square Kingdom 中有 \(n\) 个居民，编号为 \(1\) 到 \(n\)。第 \(i\) 个居民的石柱高度为 \((i+b/a)^2\)。任意两个居民之间建一条梯子，梯子长度为两根石柱高度差的绝对值。共有 \(\frac{n(n-1)}2\) 条梯子。

给定 \(n,k,a,b\)，求所有梯子按长度升序排列（含重复）后的第 \(k\) 条梯子的长度。该长度可以表示为最简分数 \(\frac{p}{q}\)，输出 \(p\) 和 \(q\)。

数据范围

\(2\le n\le 10^{12}\)，\(1\le k\le \min\left(\frac{n(n-1)}2,10^{12}\right)\)，\(1\le a\le 10^6\)，\(0\le b\le 10^{12}\)。

输出两个整数 \(p,q\)，满足 \(p\ge 0\)，\(q\ge 1\)，且 \(\gcd(p,q)=1\)。

题解

二分 二分答案 考虑二分答案： \[ (i+b/a)^2-(j+b/a)^2=(i+j+2b/a)(i-j)\le mid/a \] 设 \(i-j=d\)，则上式为 \(i\le(mid-2bd+ad^2)/2ad\)，与此同时 \(i\in[1+d,n]\)。而 \(d\) 枚举上界是 \(O(\sqrt k)\)。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef __int128_t l128;
#define PII pair<ll, ll>
const ll N = 0, inf = 1e17;

ll n, k, a, b;

l128 mygcd(l128 a, l128 b) { return b ? mygcd(b, a % b) : a; }

l128 check(l128 x) {
    l128 res = 0;
    for (l128 i = 1; i <= 2e6; i++) {
        l128 r = min((l128)n, (x - 2 * b * i + a * i * i) / 2 / a / i);
        l128 l = 1 + i;
        res += max(r - l + 1, (l128)0);
    }
    return res;
}

void solve() {
    cin >> n >> k >> a >> b;
    l128 g = mygcd(a, b);
    a /= g, b /= g;
    l128 l = 1, r = 5e18, ans = 0;
    while (l <= r) {
        l128 mid = (l + r) / 2;
        if (check(mid) < k) {
            l = mid + 1;
        } else {
            r = mid - 1;
            ans = mid;
        }
    }
    g = mygcd(ans, a);
    ans /= g, a /= g;
    cout << (ll)ans << " " << (ll)a << endl;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    ll T = 1;
    // cin >> T;
    while (T--) {
        solve();
    }
    return 0;
}

K. 接力跳

题意简述

有 \(n\) 只青蛙，编号 \(1\sim n\)，初始位置 \(P_i\) 两两不同。从青蛙 \(s\) 开始被刺激。当青蛙 \(i\) 被刺激时，它可以选择：

• 选择另一只青蛙 \(j\)（\(j\ne i\)），立即跳到当前位置关于青蛙 \(j\) 当前所在点的反射点，即新位置为 \(2P_j-P_i\)；随后青蛙 \(j\) 成为下一个且唯一被刺激的青蛙；
• 或停在原地，此时所有跳跃结束。

一只青蛙可能被多次刺激。最终所有青蛙到达位置 \(Q_i\)，且 \(Q_i\) 两两不同。设最后被刺激并选择停下的青蛙编号为 \(t\)，求 \(t\)。

数据范围

\(2\le n\le 10^5\)，\(1\le s\le n\)，坐标范围 \(-10^9\le px_i,py_i,qx_i,qy_i\le 10^9\)。所有初始位置 \(P_i\) 两两不同，所有最终位置 \(Q_i\) 也两两不同。保证对应一个刺激次数不超过 \(2\times 10^5\) 的合法过程。

题解

思维题 构造不变量。假设当前被刺激的是青蛙 \(i\)，它选择跳向青蛙 \(j\)。跳跃前，青蛙 \(i\) 的位置为 \(R_i\)，青蛙 \(j\) 的位置为 \(R_j\)。

根据中心对称的定义，跳跃后青蛙 \(i\) 的新位置是

\[ R_i'=2R_j-R_i \]

与此同时，下一只被刺激的青蛙变成了 \(j\)。记跳跃前所有青蛙的位置之和为

\[ S=\sum_{k=1}^{n}R_k \]

跳跃后只有青蛙 \(i\) 的位置发生变化，因此

\[ \begin{aligned} S'&=S-R_i+R_i'\\ &=S-R_i+(2R_j-R_i)\\ &=S+2R_j-2R_i \end{aligned} \]

设 \[ \boxed{\Phi=\sum_{k=1}^{n}R_k-2R_x} \]

跳跃后的不变量为 \[ \begin{aligned} \Phi'&=S'-2R_j\\ &=S+2R_j-2R_i-2R_j\\ &=S-2R_i\\ &=\Phi \end{aligned} \]

因此

\[ \boxed{\Phi'=\Phi} \]

无论发生多少次跳跃，这个不变量始终保持不变。

F. 友谊地久天长

题意简述

给定一个简单连通无向图，有 \(n\) 个顶点、\(m\) 条边，Alice 和 Bob 分别从两个不同顶点 \(x,y\) 出发。需要为每条无向边确定方向，将其变为有向图。之后两人按轮同时移动：若当前顶点有出边，则各自任意选择一条出边走；若没有出边，则停在原地。要求无论他们每轮如何选择，在任何一轮结束时都不会位于同一顶点。若存在这样的定向，输出 Yes 并给出 \(m\) 条有向边；否则输出 No。

数据范围

\(1\le T\le 1000\)，\(2\le n\le 300\)，\(n-1\le m\le \frac{n(n-1)}2\)，\(1\le x,y\le n\)，\(x\ne y\)。图连通，无自环、无重边。\(n>30\) 的测试用例至多一个。