A、Alice and Bob

题目大意

存在两堆石子，石子个数分别是 $n$ 和 $m$ ，数量级在 $5*10^3$ ，现在每个人轮流进行挑选，必须任选一堆拿走 $k>0$ 个石子，再从另外一堆拿走 $s*k$ 个石子 $s\ge0$ ，也就是第二次选的可以拿走 $0$ 个石子。 $Alice$ 先手， $Bob$ 后手，第一个无法操作的人就输了，询问比赛谁胜利了。

Solution

考点：博弈

首先我们来考虑用 $f[i][j]$ 代表第一堆有 $i$ 个石子，第二堆有 $j$ 个石子的先手必胜 $(true)$ 还是必败态 $(false)$ 。

初始化 $f[0][0] = false,f[1...n][0]=f[0][1...n]=true$ 。

接下来暴力枚举第一堆石子，第二堆石子，如果某个点是现在必败态，说明把它加上若干个符合要求的左右石子数一定是必胜态。

但是这样一看复杂度有 $O(n^3\log n)$ ，我们再仔细观察，假设对于两个局面 $(i,p),(i,q)$ 都是必败态，并且假设 $p>q$ ，那么我们就可以在 $(i,p)$ 局面的时候拿掉 $(0,p-q)$ 个石子，让局面变成 $(i,q)$ 这时候又是变成必胜态，前后矛盾，表明对于第一堆有 $i$ 个石子的时候，第二堆石子只有一种情况是必败态。这样我们复杂度就到了 $O(n^2\log n)$ 。

不过这个题还是很玄学，官方的题解说近似的复杂度是 $O(n)$ …用 $bitset$ 代替 $bool$ 数组时间可以来到 $300ms$ 左右。

#include <bits/stdc++.h>
using namespace std;
#define js ios::sync_with_stdio(false);cin.tie(0); cout.tie(0)
#define all(__vv__) (__vv__).begin(), (__vv__).end()
#define endl "\n"
#define pai pair<int, int>
#define ms(__x__,__val__) memset(__x__, __val__, sizeof(__x__))
#define rep(i, sta, en) for(int i=sta; i<=en; ++i)
#define repp(i, sta, en) for(int i=sta; i>=en; --i)
#define debug(x) cout << #x << ":" << x << '\n'
typedef tuple<int, int> tup;
typedef long long ll; typedef unsigned long long ull; typedef long double ld;
inline ll read() { ll s = 0, w = 1; char ch = getchar(); for (; !isdigit(ch); ch = getchar()) if (ch == '-') w = -1; for (; isdigit(ch); ch = getchar())    s = (s << 1) + (s << 3) + (ch ^ 48); return s * w; }
inline void print(ll x, int op = 10) { if (!x) { putchar('0'); if (op)    putchar(op); return; }    char F[40]; ll tmp = x > 0 ? x : -x;    if (x < 0)putchar('-');    int cnt = 0;    while (tmp > 0) { F[cnt++] = tmp % 10 + '0';        tmp /= 10; }    while (cnt > 0)putchar(F[--cnt]);    if (op)    putchar(op); }
inline ll gcd(ll x, ll y) { return y ? gcd(y, x % y) : x; }
ll qpow(ll a, ll b) { ll ans = 1;    while (b) { if (b & 1)    ans *= a;        b >>= 1;        a *= a; }    return ans; }    ll qpow(ll a, ll b, ll mod) { ll ans = 1; while (b) { if (b & 1)(ans *= a) %= mod; b >>= 1; (a *= a) %= mod; }return ans % mod; }
const int dir[][2] = { {0,1},{1,0},{0,-1},{-1,0},{1,1},{1,-1},{-1,1},{-1,-1} };
const int MOD = 1e9 + 7;
const int INF = 0x3f3f3f3f;
const ll INF64 = 0x3f3f3f3f3f3f3f3f;

const int N = 5e3 + 1;
struct Node {
    ll val;
    int id;
    bool operator < (const Node& opt) const {
        return val < opt.val;
    }
};
ll n, m;
bitset<N> f[N];

void init() {
    f[0][0] = 0;
    rep(i, 1, N - 1)
        f[i][0] = f[0][i] = 1;
    for (int i = 0; i < N; ++i) {
        for (int j = 0; j < N; ++j) {
            if (!f[i][j]) {
                for (int a = 1; i + a < N; ++a) {
                    for (int b = 0; b + j < N; b += a) {
                        f[i + a][j + b] = 1;
                    }
                }
                for (int a = 1; j + a < N; ++a) {
                    for (int b = 0; b + i < N; b += a) {
                        f[i + b][j + a] = 1;
                    }
                }
                break;
            }
        }
    }
}

int solve() {
    n = read(), m = read();


    return f[n][m];
}

int main() {
    init();
    int T = read();    rep(_, 1, T)
    {
        //solve();
        cout << (solve() ? "Alice" : "Bob") << endl;
    }
    return 0;
}

B、Ball Dropping

题目大意

下面的图像给出 $a,b,h,r$ ，要你判断这个小球是否会穿过漏斗，如果不穿过输出圆心距离漏洞底部的高度。

Solution

考点：计算几何

首先考虑何时会穿过漏斗，当且仅当 $2*r\ge b$ 的时候。
其他时候算出漏斗右上角角度 $\theta$ ，借用半径 $r$ 和 $\displaystyle\frac{b}{2}$ 就可以算到小三角形的底，接着 $\tan$ 就行了，借用一下官方题解的图片。

图片说明

int solve() {
    double r, a, b, h;
    cin >> r >> a >> b >> h;
    if (r * 2 <= b) {
        cout << "Drop" << endl;
    }
    else {
        double sita = atan(h / ((a - b) / 2));
        double L = r / sin(sita) - b / 2;
        double res = L * tan(sita);
        cout << "Stuck" << endl;
        printf("%.6f\n", res);
    }

    return 1;
}

C、Determine the Photo Position

题目大意

给出一个 $n*n$ 的 $01$ 矩阵，你要用 $1*m$ 的矩阵填充 $0$ 的位置，询问你有多少种填充方案。

$1\le n,m\le 2000$

Solution

签到题，模拟连续 $0$ 的数量即可。

char s[N], t[N];

int solve() {
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    cin >> n >> m;
    vector<string> a(n);
    for (int i = 0; i < n; ++i)
        cin >> a[i];
    string b;
    cin >> b;
    int res = 0;
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            int cnt = 0;
            int k = j;
            while (k < n && a[i][k] == '0')    ++k;
            res += max(0ll, k - j - m + 1);
            j = k;
        }
    }
    print(res);
    return 1;
}

F、Find 3-friendly Integers

题目大意

定义一个数是 $3-friendly$ ，当且仅当这个数的某个子串 $x\mod 3\equiv 0$ 。求 $[l,r]$ 中是 $3-friendly$ 的个数。

Solution

考点：~~数位dp~~思维题

首先我们知道某个数是 $3$ 的倍数，可以对他若干项累加求和 $\mod 3$ ，然后我们还知道 $(a+b+c)\mod 3\equiv a\mod 3+b\mod 3+c\mod 3$ 。

那么我们思考大于等于 $100$ 的数，他们一定存在某 $3$ 位 $\mod 3$ 后不为 $0$ 。但是在发现这些 $111,112,121...222$ 一系列组合下来一定存在某个子串累加求和 $\mod 3\equiv0$ ，那么我们就任意了，直接暴力处理前 $100$ 个数即可。

bool check(int x) {
    int p[3];
    p[0] = x % 10;
    if (p[0] % 3 == 0)    return 1;
    x /= 10;
    if (!x)    return 0;
    p[1] = x % 10;
    if (p[1] % 3 == 0)    return 1;
    if ((p[0] + p[1]) % 3 == 0)    return 1;
    x /= 10;
    if (!x)    return 0;
    p[2] = x;
    if (p[2] % 3 == 0)    return 1;
    if ((p[0] + p[2]) % 3 == 0 || (p[1] + p[2]) % 3 == 0 || (p[0] + p[1] + p[2]) % 3 == 0)
        return 1;
    return 0;
}

int solve() {
    ll l = read(), r = read();
    if (r <= 100) {

        int x = 0;
        for (int i = l; i <= r; ++i) {
            x += check(i);
        }
        print(x);

    }
    else {
        ll res = r - l + 1;
        for (ll i = l; i <= 100; ++i) {
            res -= !check(i);
        }
        print(res);
    }

    return 1;
}

G、Game of Swapping Numbers

题目大意

给定等长度序列 $A,B$ ，你必须交换 $k(0\le k\le 10^8)$ 次 $A$ 序列中的两个不同的数，输出最终 $\sum\limits_{i=1}^n|A_i-B_i|$ 最大是多少。

$2\le n\le 5*10^5, -10^8\le A_i,B_i\le 10^8$

Solution

考点：贪心

我们假设序列 $A=\{0,2,5\},B=\{1,3,4\}$ ，那么我们在绝对值求和就代表着要向 $A,B$ 集合分配正负号，并且保证最终两个集合一起计算的时候正负号数量相等，单个集合内正负号数量可以不同。

那么对于上面我们的最优分配策略就是 $A=\{-0,-2,+5\},B=\{-1,+3,+4\}$ ，可以看出最优解就是前 $n$ 大放正号，前 $n$ 小放负号。

我们还可以发现对于 $n>2$ 的时候来说， $k>$ 最优解的最少次数和 $k=$ 最优解的最少次数是一致的，因为这时候 $A$ 中一定存在最少 $2$ 个相同的符号，我们只需要交换这两个相同的符号磨平次数即可， $n=2$ 的时候判断 $k$ 的奇偶性即可。

接下来就要来看如何构建尽可能优的解，首先我们可以拿到初始的正号集合与负号集合，我们每次交换 $A$ 中两个数，就可以调整 $2$ 个数的符号把一个正号变成负号，把一个负号变成正号，那么很显然要让答案最优，一定是先把最大的负号和最小的正号做一次符号互换，知道处理完全部的数或者 $k$ 用尽。

int a[N], b[N];
int maxi[N], mini[N];

int solve() {
    n = read(), k = read();
    rep(i, 1, n)    a[i] = read();
    rep(i, 1, n)    b[i] = read();
    if (n == 2) {
        if (k & 1)    print(abs(a[1] - b[2]) + abs(a[2] - b[1]));
        else    print(abs(a[1] - b[1]) + abs(a[2] - b[2]));
    }
    else {
        ll sum = 0;
        for (int i = 1; i <= n; ++i) {
            maxi[i] = max(a[i], b[i]);
            mini[i] = min(a[i], b[i]);
            sum += abs(a[i] - b[i]);
        }
        sort(maxi + 1, maxi + 1 + n); // 正号集合 小的开始挑
        sort(mini + 1, mini + 1 + n, greater<int>()); // 负号集合 大的开始挑
        for (int i = 1; i <= n && i <= k; ++i) {
            if (mini[i] > maxi[i]) {
                sum += 2 * (mini[i] - maxi[i]);
            }
            else break;
        }
        print(sum);
    }

    return 1;
}

H、Hash Function

题目大意

给出一个长度为 $n(1\le n\le 5e5)$ 互不相同的序列，你要选择一个 $Seed$ 让 $n$ 个数在模 $Seed$ 的前提下互不相同，求最小的 $Seed$ 。

Solution

考点：多项式乘法，卷积 $FFT$

参考题解

首先考虑一个简化问题，给出一个序列 $a_1,a_2...a_n$ ，一个序列 $b_1,b_2...b_n$ 如果你可以选择任意两个数 $a_i+b_j$ 我要你判断这个数是否存在，你能如何处理，首先不考虑开桶的 $O(n)$ 做法，我们要求 $O(n\log n)$ 处理，很明显我们写出这个序列的生成函数。

$P_1=x^{a_1}+x^{a_2}...+x^{a_n}$

$P_2=x^{b_1}+x^{b_2}...+x^{b_n}$

很显然我们对着 $a,b$ 卷积之后就可以得到全部的 $x^{a_i+b_j}$ 前面的系数，也就可以判断出来这个数是否存在。

那么回到这个问题，我要选择一个 $Seed$ 让全部的数都不发生哈希冲突，也就是没有下面的几个式子。

$a_i\mod Seed= a_j\mod Seed$

$a_i\mod Seed- a_j\mod Seed=0$

$(a_i- a_j)\mod Seed=0$

那么问题就变成了我要找到一个 $Seed$ 让他不是任意一个 $a_i-a_j$ 的约数。

上面我们知道如何快速的求解 $a_i+b_j$ 的系数，这里做减法的话也是同理，用一个偏移量 $P$ 把负数转成正数即可。

接下来对着 $a_i$ 和 $P-a_i$ 做一次 $FFT$ ，然后再去枚举最小的因子即可。

#include <bits/stdc++.h>
using namespace std;
#define all(__vv__) (__vv__).begin(), (__vv__).end()
#define endl "\n"
#define pai pair<int, int>
#define ms(__x__,__val__) memset(__x__, __val__, sizeof(__x__))
#define debug(x) cout << #x << ":" << x << '\n'
typedef tuple<int, int> tup;
typedef long long ll; typedef unsigned long long ull; typedef long double ld;
inline ll read() { ll s = 0, w = 1; char ch = getchar(); for (; !isdigit(ch); ch = getchar()) if (ch == '-') w = -1; for (; isdigit(ch); ch = getchar())    s = (s << 1) + (s << 3) + (ch ^ 48); return s * w; }
inline void print(ll x, int op = 10) { if (!x) { putchar('0'); if (op)    putchar(op); return; }    char F[40]; ll tmp = x > 0 ? x : -x;    if (x < 0)putchar('-');    int cnt = 0;    while (tmp > 0) { F[cnt++] = tmp % 10 + '0';        tmp /= 10; }    while (cnt > 0)putchar(F[--cnt]);    if (op)    putchar(op); }
inline ll gcd(ll x, ll y) { return y ? gcd(y, x % y) : x; }
ll qpow(ll a, ll b) { ll ans = 1;    while (b) { if (b & 1)    ans *= a;        b >>= 1;        a *= a; }    return ans; }    ll qpow(ll a, ll b, ll mod) { ll ans = 1; while (b) { if (b & 1)(ans *= a) %= mod; b >>= 1; (a *= a) %= mod; }return ans % mod; }
const int dir[][2] = { {0,1},{1,0},{0,-1},{-1,0},{1,1},{1,-1},{-1,1},{-1,-1} };
const int MOD = 1e9 + 7;
const int INF = 0x3f3f3f3f;
const ll INF64 = 0x3f3f3f3f3f3f3f3f;

const int N = (2097152) + 7; // 2^21
ll n, m;

const double PI = acos(-1);

struct cp {
    double r, i; cp(double _r = 0, double _i = 0) { r = _r, i = _i; }
    cp operator+(const cp& x)const { return cp(r + x.r, i + x.i); }
    cp operator-(const cp& x)const { return cp(r - x.r, i - x.i); }
    cp operator*(const cp& x)const { return cp(r * x.r - i * x.i, r * x.i + i * x.r); }
    cp conj() { return cp(r, -i); }
}a[N], b[N];

int c[N], rev[N], limit;
double p1[N], p2[N];


const int P = 500001;

void FFT(cp* a, int inv) {
    for (int i = 0; i < limit; ++i) {
        if (i < rev[i])swap(a[i], a[rev[i]]);
    }
    for (int mid = 1; mid < limit; mid <<= 1) {
        cp w1(cos(PI / mid), inv * sin(PI / mid));
        for (int i = 0; i < limit; i += mid * 2) {
            cp wk(1, 0);
            for (int j = 0; j < mid; ++j, wk = wk * w1) {
                cp x = a[i + j], y = wk * a[i + j + mid];
                a[i + j] = x + y, a[i + j + mid] = x - y;
            }
        }
    }
    if (inv == -1) {
        for (int i = 0; i < limit; ++i)
            c[i] = a[i].r / limit + 0.5;
    }
}

bool vis[N];

bool check(int x) {
    for (int i = x; i <= P; i += x) {
        if (vis[i])    return 0;
    }
    return 1;
}

int solve() {
    n = read();
    for (int i = 1; i <= n; ++i) {
        int x = read();
        a[x].r = 1;
        b[P - x].r = 1;
    }
    int bit = 0;
    while (1 << bit < P * 2)    ++bit;
    limit = 1 << bit;

    for (int i = 0; i < limit; ++i)    rev[i] = (rev[i >> 1] >> 1) | ((i & 1) << (bit - 1));
    FFT(a, 1); FFT(b, 1);
    for (int i = 0; i < limit; ++i)    a[i] = a[i] * b[i];
    FFT(a, -1);

    for (int i = 0; i < limit; ++i) {
        if (c[i] > 0)    vis[abs(i - P)] = 1;
    }

    for (int i = n; i < P + 1; ++i) {
        if (check(i))    return print(i), 1;
    }

    return 1;
}

int main() {
    //int T = read();    rep(_, 1, T)
    {
        solve();
        //cout << (solve() ? "YES" : "NO") << endl;
    }
    return 0;
}

I、Increasing Subsequence

题目大意

给出一个长度为 $n(1\le n\le 5000)$ 的排列 $p_i$ ，两名玩家轮流选数，如果某名玩家选了 $p_i$ 这个数那么后手只能选择某个 $j$ ，并且满足 $j>i,p_j>p_i$ 。问这局游戏的期望局数。

Solution

考点：期望 $dp$

参考题解)

我们定义 $f[i][j]$ 是上一次选了 $i$ 这个数，下次选了 $j$ 这个数的期望。

那么状态转移方程就是： $\displaystyle f[i][j]=\frac{\sum\limits_{k=j+1}^{n} (f[j][k]+1)}{cnt}$ ，其中合法的转移叠加， $cnt$ 是合法的转移次数， $+1$ 代表着多执行的一步操作。

那么我们得到状态转移方程之后，倒序的枚举上一次选择的 $i$ 这个数，然后从后往前遍历 $p_j$ 。

如果 $p_j>i$ 说明 $f[i][p_j]$ 是一个合理转移累计和；

如果 $p_j<i$ 说明 $f[p_j][i]$ 应该被计算一次答案了。

最终我们的答案就是 $\displaystyle \frac{\sum\limits_{i=1}^n f[0][i]}{n}$ ，涉及的除法就用逆元计算，可以用线性逆元预处理。

const int MOD = 998244353;
const int N = 5e3 + 7;
ll n, m;
ll p[N], inv[N];

ll f[N][N]; // f[i][j] 上次选了i，下次选j的期望

int solve() {
    n = read();
    inv[0] = inv[1] = 1;
    for (int i = 2; i <= n; ++i)
        inv[i] = (MOD - MOD / i) * inv[MOD % i] % MOD;

    for (int i = 1; i <= n; ++i)    p[i] = read();

    for (int i = n; i >= 1; --i) { // 上一次选的是i
        ll sum = 0, cnt = 0; // sum后面可选的全部期望之和，cnt后面可选的次数
        for (int j = n; j >= 0; --j) {
            if (p[j] > i) {
                ++cnt;
                sum += f[i][p[j]];
                sum %= MOD;
            }
            else if (p[j] < i) {
                f[p[j]][i] = 1;
                f[p[j]][i] += sum * inv[cnt] % MOD;
                f[p[j]][i] %= MOD;
            }
        }
    }

    ll res = 0;
    for (int i = 1; i <= n; ++i)
        res = (res + f[0][i]) % MOD;
    print(res * inv[n] % MOD);

    return 1;
}

J、Journey among Railway Stations

题目大意

你有一个 $n(1\le n\le 10^6)$ 个点的火车路线，每个火车站开放的时间是 $[u_i,v_i]$ ，从第 $i$ 号火车站去往第 $i+1$ 号火车站时间是 $d_i$ 。

题目有 $3$ 种操作，可以修改某个点的 $[u_i,v_i]$ ，或者修改 $d_i$ ，第三种操作就是询问你从 $i$ 号点的 $x$ 时刻出发能否通过最后一个火车站。火车站通过的标准是你可以提前到来等待，但是不允许迟到。

Solution

考点：数据结构（线段树）

这题我觉得官方题解写的挺好的我就贴一下他们的题解，以及我自己的代码了，不过我至今不知道为什么我的代码用参数控制 $(rt,l,r)$ 线段树编号，控制的左边界，控制的右边界，就永远只能过 $28\%$ 左右，把 $(l,r)$ 放进线段树的 $struct$ 里面控制就可以 $AC...$ 可能是这题空间给的不够导致回溯的时候爆栈了？

图片说明
AC代码

WA掉的

#include <bits/stdc++.h>
using namespace std;
#define js ios::sync_with_stdio(false);cin.tie(0); cout.tie(0)
#define all(__vv__) (__vv__).begin(), (__vv__).end()
#define endl "\n"
#define pai pair<ll, ll>
#define ms(__x__,__val__) memset(__x__, __val__, sizeof(__x__))
#define rep(i, sta, en) for(int i=sta; i<=en; ++i)
#define repp(i, sta, en) for(int i=sta; i>=en; --i)
#define debug(x) cout << #x << ":" << x << '\n'
typedef long long ll; typedef unsigned long long ull; typedef long double ld;
inline ll read() { ll s = 0, w = 1; char ch = getchar(); for (; !isdigit(ch); ch = getchar()) if (ch == '-') w = -1; for (; isdigit(ch); ch = getchar())    s = (s << 1) + (s << 3) + (ch ^ 48); return s * w; }
inline void print(ll x, int op = 10) { if (!x) { putchar('0'); if (op)    putchar(op); return; }    char F[40]; ll tmp = x > 0 ? x : -x;    if (x < 0)putchar('-');    int cnt = 0;    while (tmp > 0) { F[cnt++] = tmp % 10 + '0';        tmp /= 10; }    while (cnt > 0)putchar(F[--cnt]);    if (op)    putchar(op); }
inline ll gcd(ll x, ll y) { return y ? gcd(y, x % y) : x; }
ll qpow(ll a, ll b) { ll ans = 1;    while (b) { if (b & 1)    ans *= a;        b >>= 1;        a *= a; }    return ans; }    ll qpow(ll a, ll b, ll mod) { ll ans = 1; while (b) { if (b & 1)(ans *= a) %= mod; b >>= 1; (a *= a) %= mod; }return ans % mod; }
const int dir[][2] = { {0,1},{1,0},{0,-1},{-1,0},{1,1},{1,-1},{-1,1},{-1,-1} };
const int MOD = 1e9 + 7;
const int INF = 0x3f3f3f3f;
const ll INF64 = 0x3f3f3f3f3f3f3f3f;
const int N = 1e6 + 7;

ll u[N], v[N], d[N], suf[N];

struct node {
    int l, r, mid;
    ll uma, vmi, lazy;
    bool ok;
}tree[N << 2];

#define ls x<<1
#define rs x<<1|1
#define MID (L+R>>1)

void merge(node& x, node lson, node rson) {
    x.uma = max(lson.uma, rson.uma);
    x.vmi = min(lson.vmi, rson.vmi);
    x.ok = (lson.ok && rson.ok && lson.uma <= rson.vmi);
}

void build(int x, int l, int r, int L, int R) {
    tree[x] = { l,r,(l + r) >> 1,0,0,0,0 };
    if (l == r) {
        tree[x].uma = u[l];
        tree[x].vmi = v[l];
        tree[x].ok = 1;
        tree[x].lazy = 0;
        return;
    }
    int mid = tree[x].mid;
    assert(l == L);
    assert(r == R);
    assert(MID == mid);
    build(ls, l, mid, L, MID);
    build(rs, mid + 1, r, MID + 1, R);
    merge(tree[x], tree[ls], tree[rs]);
}

void solve(int x, ll k) {
    tree[x].uma += k;
    tree[x].vmi += k;
    tree[x].lazy += k;
}

void pd(int x) {
    if (tree[x].lazy) {
        solve(ls, tree[x].lazy);
        solve(rs, tree[x].lazy);
        tree[x].lazy = 0;
    }
}

void modify(int x, int l, int r, ll k, int id) {
    if (l <= tree[x].l && tree[x].r <= r) {
        if (id == 1) solve(x, k);
        else if (id == 2) tree[x].uma += k;
        else if (id == 3) tree[x].vmi += k;
        return;
    }
    pd(x);
    int mid = tree[x].mid;
    if (l <= mid) modify(ls, l, r, k, id);
    if (r > mid) modify(rs, l, r, k, id);
    merge(tree[x], tree[ls], tree[rs]);
}

node query(int x, int l, int r) {
    if (l <= tree[x].l && tree[x].r <= r) {
        return tree[x];
    }
    int mid = tree[x].mid;
    pd(x);
    node ans = { 0,0,0,0,0,0,0 };
    if (r <= mid) ans = query(ls, l, r);
    else if (l > mid) ans = query(rs, l, r);
    else merge(ans, query(ls, l, mid), query(rs, mid + 1, r));
    return ans;
}

void solve() {
    int n = read();
    rep(i, 1, n)    u[i] = read();
    rep(i, 1, n)    v[i] = read();
    rep(i, 1, n - 1)    d[i] = read();
    suf[n] = 0;
    repp(i, n - 1, 1)    suf[i] = suf[i + 1] + d[i];
    rep(i, 1, n)    u[i] += suf[i], v[i] += suf[i];

    build(1, 1, n, 1, n);
    int Q = read(), op, l, r, pos, w;
    while (Q--) {
        op = read();
        if (op == 0) {
            l = read(), r = read();
            if (query(1, l, r).ok) {
                puts("Yes");
            }
            else {
                puts("No");
            }
        }
        else if (op == 1) {
            pos = read(), w = read();
            modify(1, 1, pos, w - d[pos], 1); // 差分修改
            d[pos] = w;
        }
        else if (op == 2) {
            pos = read(), l = read(), r = read();
            modify(1, pos, pos, suf[pos] - u[pos] + l, 2);
            modify(1, pos, pos, suf[pos] - v[pos] + r, 3);
            u[pos] = suf[pos] + l;
            v[pos] = suf[pos] + r;
        }
    }
}

signed main() {
    int T = read();    rep(_, 1, T)
    {
        solve();
    }
    return 0;
}

K、Knowledge Test about Match

题目大意

随机生成一个权值范围为 $0\to n-1$ 的序列，你要用 $0\to n-1$ 去和它匹配，匹配函数是 $sqrt$ 。要求平均情况下和标准值偏差不能超过 $4\%$ 。

Solution

这题没啥考点…看到随机生成几个字就可以赛后补题开始乱搞了。

~~所以这题题解是来水的的~~

const int N = 1e3 + 7;
ll n, m;
int p[N];
double sqr[N];

int solve() {
    n = read();
    rep(i, 0, n - 1)    p[i] = read();
    sort(p, p + n);

    int t = 5;
    while (t--) {
        for (int i = 0; i < n; ++i) {
            for (int j = i + 1; j < n; ++j) {
                if (sqr[abs(i - p[i])] + sqr[abs(j - p[j])] > sqr[abs(i - p[j])] + sqr[abs(j - p[i])]) {
                    swap(p[i], p[j]);
                }
            }
        }
    }
    rep(i, 0, n - 1)    print(p[i], " \n"[i + 1 == n]);
    return 1;
}

int main() {
    rep(i, 1, N - 1)    sqr[i] = sqrt(i);
    int T = read();    rep(_, 1, T)
    {
        solve();
        //cout << (solve() ? "YES" : "NO") << endl;
    }
    return 0;
}

2021牛客暑期多校训练营1

A、Alice and Bob

题目大意

Solution

B、Ball Dropping

题目大意

Solution

C、Determine the Photo Position

题目大意

Solution

F、Find 3-friendly Integers

题目大意

Solution

G、Game of Swapping Numbers

题目大意

Solution

H、Hash Function

题目大意

Solution

I、Increasing Subsequence

题目大意

Solution

J、Journey among Railway Stations

题目大意

Solution

K、Knowledge Test about Match

题目大意

Solution