Bronze

B1

import sys
sys.stdin = open('herding.in', 'r')
sys.stdout = open('herding.out', 'w')
x, y, z = sorted(map(int, raw_input().split()))
z -= y + 1
y -= x + 1
if y == 0 and z == 0:
    print 0
elif y == 1 or z == 1:
    print 1
else:
    print 2
print max(y, z)

B2

import sys
sys.stdin = open('revegetate.in', 'r')
sys.stdout = open('revegetate.out', 'w')
n, m = map(int, raw_input().split())
a = [[] for i in range(n + 1)]
for i in range(m):
    x, y = map(int, raw_input().split())
    a[x].append(y)
    a[y].append(x)
c = [0 for i in range(n + 1)]
s = ''
for i in range(1, n + 1):
    t = set(range(1, 5))
    for j in a[i]:
        if j < i and c[j] in t:
            t.remove(c[j])
    c[i] = list(t)[0]
    s += str(c[i])
print s

B3

import sys
sys.stdin = open('traffic.in', 'r')
sys.stdout = open('traffic.out', 'w')
n = input()
a = []
for i in range(n):
    x, y, z = raw_input().split()
    y = int(y)
    z = int(z)
    a.append((x, y, z))

l, h = 0, 1000000
for x, y, z in a[::-1]:
    if x == 'none':
        l = max(l, y)
        h = min(h, z)
    elif x == 'on':
        l -= z
        h -= y
    elif x == 'off':
        l += y
        h += z
l = max(l, 0)
print l, h
l, h = 0, 1000000
for x, y, z in a:
    if x == 'none':
        l = max(l, y)
        h = min(h, z)
    elif x == 'on':
        l += y
        h += z
    elif x == 'off':
        l -= z
        h -= y
l = max(l, 0)
print l, h

Silver

S1

#include <bits/stdc++.h>
using namespace std;
int n, a[100020];
int work() {
    if (a[n - 1] == a[0] + n - 1) {
        return 0;
    }
    if (a[n - 2] == a[0] + n - 2 || a[n - 1] == a[1] + n - 2) {
        if (a[n - 1] == a[0] + n) {
            return 1;
        } else {
            return 2;
        }
    }
    int z1 = n;
    for (int i = 0; i < n; i++) {
        int p = a[i] + n - 1;
        int t = upper_bound(a, a + n, p) - a;
        z1 = min(z1, n - (t - i));
    }
    for (int i = 0; i < n; i++) {
        int p = a[i] - n + 1;
        int t = lower_bound(a, a + n, p) - a - 1;
        z1 = min(z1, n - (i - t));
    }
    return z1;
}
int main() {
    freopen("herding.in", "r", stdin);
    freopen("herding.out", "w", stdout);
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }
    sort(a, a + n);
    int z2 = max(a[n - 1] - a[1], a[n - 2] - a[0]) - n + 2;
    cout << work() << endl;
    cout << z2 << endl;
}

S2

#include <bits/stdc++.h>
using namespace std;
int n, k;
int a[1020][1020];
int main() {
    freopen("paintbarn.in", "r", stdin);
    freopen("paintbarn.out", "w", stdout);
    cin >> n >> k;
    for (int i = 0; i < n; i++) {
        int x1, y1, x2, y2;
        cin >> x1 >> y1 >> x2 >> y2;
        x1++;
        y1++;
        x2++;
        y2++;
        a[x1][y1]++;
        a[x1][y2]--;
        a[x2][y1]--;
        a[x2][y2]++;
    }
    for (int i = 1; i <= 1010; i++) {
        for (int j = 1; j <= 1010; j++) {
            a[i][j] += a[i][j - 1];
        }
    }
    for (int i = 1; i <= 1010; i++) {
        for (int j = 1; j <= 1010; j++) {
            a[i][j] += a[i - 1][j];
        }
    }
    int cnt = 0;
    for (int i = 1; i <= 1010; i++) {
        for (int j = 1; j <= 1010; j++) {
            if (a[i][j] == k) {
                cnt++;
            }
        }
    }
    cout << cnt << endl;
    return 0;
}

S3

#include <bits/stdc++.h>
using namespace std;
int n, m;
int f[200020];
int F(int x) {
    return f[x] != x ? f[x] = F(f[x]) : x;
}
void U(int x, int y) {
    f[F(x)] = F(y);
}
int main() {
    freopen("revegetate.in", "r", stdin);
    freopen("revegetate.out", "w", stdout);
    cin >> n >> m;
    for (int i = 0; i <= 2 * n; i++) {
        f[i] = i;
    }
    for (int i = 0; i < m; i++) {
        int x, y;
        char o;
        cin >> o >> x >> y;
        if (o == 'S') {
            U(x, y);
            U(x + n, y + n);
        } else {
            U(x + n, y);
            U(x, y + n);
        }
    }
    for (int i = 1; i <= n; i++) {
        if (F(i) == F(i + n)) {
            printf("0\n");
            return 0;
        }
    }
    int cnt = 0;
    for (int i = 1; i <= 2 * n; i++) {
        if (F(i) == i) {
            cnt++;
        }
    }
    cnt /= 2;
    printf("1");
    for (int i = 0; i < cnt; i++) {
        printf("0");
    }
    printf("\n");
    return 0;
}

Gold

G1

DFS序 + 树状数组

x到y路径上所有点的异或，就是
x到根节点所有点的异或 ^ y到根节点所有点的异或 ^ LCA(x, y)的点权。

#include <bits/stdc++.h>
using namespace std;
int n, q;
vector<int> a[100020];
int f[100020][20];
int d[100020];
int c[200020];
int w[100020];
int L[100020];
int R[100020];
int ss;
void change(int x, int y) {
    for (int i = x; i <= 2 * n; i += i & -i) {
        c[i] ^= y;
    }
}
int query(int x) {
    int re = 0;
    for (int i = x; i > 0; i -= i & -i) {
        re ^= c[i];
    }
    return re;
}
void dfs(int x, int y) {
    f[x][0] = y;
    d[x] = d[y] + 1;
    for (int i = 1; i < 20; i++) {
        f[x][i] = f[f[x][i - 1]][i - 1];
    }
    ss++;
    L[x] = ss;
    for (int i: a[x]) {
        if (i != y) {
            dfs(i, x);
        }
    }
    ss++;
    R[x] = ss;
}
int lca(int x, int y) {
    if (d[x] < d[y]) {
        swap(x, y);
    }
    int dd = d[x] - d[y];
    for (int i = 0; i < 20; i++) {
        if (dd >> i & 1) {
            x = f[x][i];
        }
    }
    if (x == y) {
        return x;
    }
    for (int i = 20 - 1; i >= 0; i--) {
        if (f[x][i] != f[y][i]) {
            x = f[x][i];
            y = f[y][i];
        }
    }
    return f[x][0];
}
int main() {
    freopen("cowland.in", "r", stdin);
    freopen("cowland.out", "w", stdout);
    cin >> n >> q;
    for (int i = 1; i <= n; i++) {
        cin >> w[i];
    }
    for (int i = 1; i < n; i++) {
        int x, y;
        cin >> x >> y;
        a[x].push_back(y);
        a[y].push_back(x);
    }
    dfs(1, 0);
    for (int i = 1; i <= n; i++) {
        change(L[i], w[i]);
        change(R[i], w[i]);
    }
    for (int i = 0; i < q; i++) {
        int o, x, y;
        cin >> o >> x >> y;
        if (o == 1) {
            change(L[x], w[x] ^ y);
            change(R[x], w[x] ^ y);
            w[x] = y;
        } else {
            cout << (query(L[x]) ^ query(L[y]) ^ w[lca(x, y)]) << endl;
        }
    }
    return 0;
}

G2

二分，贪心。

#include <bits/stdc++.h>
using namespace std;
int n, a[100020];
vector<int> b[100020];
bool ok(int M) {
    int cnt = 0;
    int st = 0;
    for (int i = 0; i < M; i++) {
        b[i].clear();
    }
    int last = 0;
    for (int i = 1; i <= M; i++) {
        if (a[i] < last) {
            return false;
        }
        if (st == cnt) {
            b[cnt].push_back(a[i]);
            cnt++;
        } else if (a[i] > b[cnt - 1][0]) {
            b[cnt].push_back(a[i]);
            cnt++;
        } else {
            int left = st - 1;
            int right = cnt;
            while (left < right - 1) {
                int mid = (left + right) / 2;
                if (a[i] < b[mid][0]) {
                    right = mid;
                } else {
                    left = mid;
                }
            }
            if (a[i] < b[right].back()) {
                b[right].push_back(a[i]);
            } else {
                st = right;
                while (a[i] > b[right].back()) {
                    last = b[right].back();
                    b[right].pop_back();
                }
                b[right].push_back(a[i]);
            }
        }
//      for (int j = st; j <= cnt; j++) {
//          for (int k: b[j]) {
//              cout << k << ' ';
//          }
//          cout << endl;
//      }
    }
    return true;
}
int main() {
    freopen("dishes.in", "r", stdin);
    freopen("dishes.out", "w", stdout);
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }
    int L = 0;
    int R = n + 1;
    while (L < R - 1) {
        int M = (L + R) / 2;
        if (ok(M)) {
            L = M;
        } else {
            R = M;
        }
    }
    cout << L << endl;
    return 0;
}

G3

注意选择的2个矩形不能有任何重叠的部分。
这样预处理出来前后几行的结果，前后几列的结果。枚举分割线即可。

#include <bits/stdc++.h>
using namespace std;
const int L = 200;
int n, k;
int a[220][220];
int b[220][220];
int c[220][220];
int cL[220];
int cR[220];
int rT[220];
int rB[220];
void gao(int a[220][220]) {
    for (int i = 1; i <= L; i++) {
        for (int j = 1; j <= L; j++) {
            a[i][j] += a[i][j - 1];
        }
    }
    for (int i = 1; i <= L; i++) {
        for (int j = 1; j <= L; j++) {
            a[i][j] += a[i - 1][j];
        }
    }
}
int main() {
    freopen("paintbarn.in", "r", stdin);
    freopen("paintbarn.out", "w", stdout);
    cin >> n >> k;
    for (int i = 0; i < n; i++) {
        int x1, y1, x2, y2;
        cin >> x1 >> y1 >> x2 >> y2;
        x1++;
        y1++;
        x2++;
        y2++;
        a[x1][y1]++;
        a[x1][y2]--;
        a[x2][y1]--;
        a[x2][y2]++;
    }
    gao(a);
    int cnt = 0;
    for (int i = 1; i <= L; i++) {
        for (int j = 1; j <= L; j++) {
            if (a[i][j] == k) {
                b[i][j] = 1;
            }
            if (a[i][j] == k - 1) {
                c[i][j] = 1;
            }
        }
    }
    gao(b);
    gao(c);
    int ans = 0;
    for (int i1 = 0; i1 < L; i1++) {
        for (int i2 = i1 + 1; i2 <= L; i2++) {
            int tmp = 0;
            for (int j = 1; j <= L; j++) {
                int dd = 0;
                dd -= (b[i2][j] - b[i1][j]) - (b[i2][j - 1] - b[i1][j - 1]);
                dd += (c[i2][j] - c[i1][j]) - (c[i2][j - 1] - c[i1][j - 1]);
                tmp += dd;
                tmp = max(tmp, 0);
                cL[j] = max(cL[j], tmp);
            }
        }
    }
    for (int i1 = 0; i1 < L; i1++) {
        for (int i2 = i1 + 1; i2 <= L; i2++) {
            int tmp = 0;
            for (int j = L; j >= 1; j--) {
                int dd = 0;
                dd -= (b[i2][j] - b[i1][j]) - (b[i2][j - 1] - b[i1][j - 1]);
                dd += (c[i2][j] - c[i1][j]) - (c[i2][j - 1] - c[i1][j - 1]);
                tmp += dd;
                tmp = max(tmp, 0);
                cR[j] = max(cR[j], tmp);
            }
        }
    }
    for (int j1 = 0; j1 < L; j1++) {
        for (int j2 = j1 + 1; j2 <= L; j2++) {
            int tmp = 0;
            for (int i = 1; i <= L; i++) {
                int dd = 0;
                dd -= (b[i][j2] - b[i][j1]) - (b[i - 1][j2] - b[i - 1][j1]);
                dd += (c[i][j2] - c[i][j1]) - (c[i - 1][j2] - c[i - 1][j1]);
                tmp += dd;
                tmp = max(tmp, 0);
                rT[i] = max(rT[i], tmp);
            }
        }
    }
    for (int j1 = 0; j1 < L; j1++) {
        for (int j2 = j1 + 1; j2 <= L; j2++) {
            int tmp = 0;
            for (int i = L; i >= 1; i--) {
                int dd = 0;
                dd -= (b[i][j2] - b[i][j1]) - (b[i - 1][j2] - b[i - 1][j1]);
                dd += (c[i][j2] - c[i][j1]) - (c[i - 1][j2] - c[i - 1][j1]);
                tmp += dd;
                tmp = max(tmp, 0);
                rB[i] = max(rB[i], tmp);
            }
        }
    }
    int maxcL = 0;
    int maxrT = 0;
    for (int i = 1; i <= L + 1; i++) {
        maxcL = max(maxcL, cL[i-1]);
        maxrT = max(maxrT, rT[i-1]);
        ans = max(ans, maxcL + cR[i]);
        ans = max(ans, maxrT + rB[i]);
    }
    ans += b[L][L];
    cout << ans << endl;
    return 0;
}

Platinum

P1

注意到如果起点相同，那么随着终点向右移动，最优解是单峰的。

并且随着左端点从左向右移动，右端点的最优解是单调的。

所以就是双指针法。

注意到一个区间的答案是
(1-p1)(1-p2)..(1-pn) * (p1/(1-p1) + p2/(1-p2) + … + pn/(1-pn))

分别维护前后2部分，这样就可以支持在末尾追加一个概率，和删掉第一个概率。

疑似需要处理精度爆炸的问题（疑似需要取对数）

如果左端点是i，右端点的最优位置是best[i] （如果有多个最优位置，认为是最左的）
那么best[i]数组是单调增加的。

#include <bits/stdc++.h>
using namespace std;
int n;
long double p[1000020];
int main() {
    freopen("cowdate.in", "r", stdin);
    freopen("cowdate.out", "w", stdout);
    long double ans = 0;
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> p[i];
        p[i] /= 1e6;
        ans = max(ans, (long double)p[i]);
    }
    if (n <= 4000) {
        ans = 0;
        for (int i = 1; i <= n; i++) {
            long double f = 0;
            long double g = 0;
            for (int j = i; j <= n; j++) {
                f += log(1 - p[j]);
                g += p[j] / (1 - p[j]);
                ans = max(ans, exp(f) * g);
            }
        }
        printf("%d\n", (int)(1000000 * ans + 1e-6));
        return 0;
    }
    long double f = 0;
    long double g = 0;
    int j = 1;
    for (int i = 1; i <= n; i++) {
        while (j <= n && exp(f) * g < exp(f + log(1 - p[j])) * (g + p[j] / (1 - p[j]))) {
            f += log(1 - p[j]);
            g += p[j] / (1 - p[j]);
            ans = max(ans, exp(f) * g);
            j++;
        }
        f -= log(1 - p[i]);
        g -= p[i] / (1 - p[i]);
    }
    printf("%d\n", (int)(1000000 * ans + 0.13));
}

P2

首先不考虑y算一个全部的答案。

然后减去考虑y不合法的。

这是一个背包，对于每棵树需要预处理出来所有路径的长度。

(每个树选一个路径，加上(n-m) * x) < y 问方案数

然后最后还要乘上一个环排列（不同子树的顺序不定）

再除以2（顺时针和逆时针算作相同）

#include <bits/stdc++.h>
using namespace std;
const int mod = 1000000007;
vector<pair<int, int> > a[2520];
long long ans = 0;
long long cnt = 1;
long long sum;
int sz;
bool v[2520];
long long inv[2520];
long long f[2520];
long long g[2520];
int n, m, x, y;
int dfs(int x, int y) {
    v[x] = true;
    int re = 1;
    for (pair<int, int> i: a[x]) {
        if (i.first != y) {
            int tmp = dfs(i.first, x);
            re += tmp;
            sum += (long long)i.second * tmp * (sz - tmp);
        }
    }
    return re;
}
map<int, int> c;
map<int, int> gao(int x, int y) {
    v[x] = true;
    map<int, int> re;
    re[0] = 1;
    for (pair<int, int> i: a[x]) {
        if (i.first != y) {
            map<int, int> tmp = gao(i.first, x);
            for (pair<int, int> j: re) {
                for (pair<int, int> k: tmp) {
                    c[j.first + i.second + k.first] += j.second * k.second * 2;
                }
            }
            for (pair<int, int> k: tmp) {
                re[i.second + k.first] += k.second;
            }
        }
    }
    return re;
}
int main() {
    freopen("mooriokart.in", "r", stdin);
    freopen("mooriokart.out", "w", stdout);
    cin >> n >> m >> x >> y;
    inv[1] = 1;
    for (int i = 2; i <= n; i++) {
        inv[i] = inv[mod % i] * (mod - mod / i) % mod;
    }
    if ((n - m) * x <= y) {
        f[(n - m) * x] = 1;
    }

    for (int i = 0; i < m; i++) {
        int x, y, z;
        cin >> x >> y >> z;
        a[x].push_back(make_pair(y, z));
        a[y].push_back(make_pair(x, z));
    }

    memset(v, 0, sizeof v);
    for (int i = 1; i <= n; i++) {
        if (!v[i]) {
            sz = dfs(i, 0);
            cnt = cnt * sz % mod * (sz - 1) % mod;
        }
    }

    memset(v, 0, sizeof v);
    for (int i = 1; i <= n; i++) {
        if (!v[i]) {
            sz = dfs(i, 0);
            sum = 0;
            dfs(i, 0);
            ans = (ans + cnt * inv[sz] % mod * inv[sz-1] % mod * sum % mod) % mod;
        }
    }

    ans *= 2;

    ans = (ans + cnt * (n - m) * x) % mod;

    memset(v, 0, sizeof v);
    for (int i = 1; i <= n; i++) {
        if (!v[i]) {
            c.clear();
            gao(i, 0);
            memset(g, 0, sizeof g);
//          for (pair<int, int> i: c) {
//              cout << i.first << ' ' << i.second << endl;
//          }
//          cout << endl;
            for (pair<int, int> i: c) {
                for (int j = i.first; j <= y; j++) {
                    g[j] = (g[j] + f[j - i.first] * i.second) % mod;
                }
            }
            swap(f, g);
        }
    }
//  for (int i = 0; i <= y; i++) {
//      cout << i << ' ' << f[i] << endl;
//  }
    for (int i = 0; i < y; i++) {
        ans = (ans - (long long)i * f[i] % mod + mod) % mod;
    }

    for (int i = 1; i < n - m; i++) {
        ans = ans * i % mod;
    }

    if (ans & 1) {
        ans += mod;
    }
    ans /= 2;
    cout << ans << endl;
    return 0;
}

P3

输入(0, 0)到(T, T)矩形内的n个点。

从(0, 0)到(T, T)只能向正方向走，希望经过最多的点（最长上升子序列）

如果从(x1, y1)走到(x2, y2)那么代价是(x2-x1) * (y2-y1)

问所有经过最多点的路径，权值最小的是多大？

T <= 1e6
n <= 2e5
n个点中，任意2个点，不会在同一行或同一列。

首先说说题目中的哪些条件有用，哪些没用吧。
T的范围基本没用。
任意2个点，不会在同一行或同一列，可以去掉，但是实现起来会麻烦很多。
最关键的是经过最多点的路径。

直接暴力是n^2的

然后假设求出了最长不下降子序列
每个点在最长不下降子序列中的位置是确定的。
动态规划中只需要考虑相邻两个位置之间的关系即可。

这个事情用暴力来做还是n^2的
怎么做更快呢？线段树分治

对于相邻两个位置i-1和i
假设i-1位置上的任意一个点，可以到i位置上的任意一个点，那么有一个非常简单的反向单调性。
（越靠右下的点，越会选到左上的点）

但是实际上，对于第i位置的点，不是i-1位置上的任意一个点都可以（可行的是一个区间）
这个区间是不包含的（这个条件没用）
对于第i-1层的点建一个线段树。

可以用这个线段树上的一些节点，拼出 可以转移到某点的区间。
这样对于线段树上每个节点，可以转移到一些点。
这个问题就转化为了
「假设i-1位置上的任意一个点，可以到i位置上的任意一个点，那么有一个非常简单的反向单调性。」

总时间复杂度大概是$O(n \log^2 n)$。

#include <bits/stdc++.h>
using namespace std;
int n;
pair<int, int> points[1000020];
int lastmin[1000020];
long long t;
vector<pair<int, int> > group[200020];
vector<long long> dp[200020];
vector<int> querys[800020];

void build(int x, int l, int r) {
    querys[x].clear();
    if (l == r) {
        return;
    }
    int mid = (l + r) / 2;
    build(x * 2, l, mid);
    build(x * 2 + 1, mid + 1, r);
}

void change(int x, int l, int r, int L, int R, int v) {
    if (L <= l && r <= R) {
        querys[x].push_back(v);
        return;
    }
    if (R < l || r < L) {
        return;
    }
    int mid = (l + r) / 2;
    change(x * 2, l, mid, L, R, v);
    change(x * 2 + 1, mid + 1, r, L, R, v);
}

void solve(const vector<int> &querys, int l, int r, int L, int R, int index) {
    if (l > r) {
        return;
    }
    int mid = (l + r) / 2;
    int j = querys[mid];
    long long best = 1e18;
    int pos = -1;
    for (int k = L; k <= R; k++) {
        int dx = (group[index][j].first - group[index - 1][k].first);
        int dy = (group[index][j].second - group[index - 1][k].second);
        if (dx > 0 && dy > 0) {
            long long tmp = dp[index - 1][k] + (long long)dx * dy;
            if (best > tmp) {
                best = tmp;
                pos = k;
            }
        }
    }
    assert(pos != -1);
    dp[index][j] = min(dp[index][j], best);
    solve(querys, l, mid - 1, pos, R, index);
    solve(querys, mid + 1, r, L, pos, index);
}

void query(int x, int l, int r, int index) {
    /*
    if (index == 2) {
        cerr << "tree " << x << ' ' << l << ' ' << r <<  ": ";
        for (int i: querys[x]) {
            cerr << i << ' ';
        }
        cerr << endl;
    }
    */
    solve(querys[x], 0, querys[x].size() - 1, l, r, index);
    if (l == r) {
        return;
    }
    int mid = (l + r) / 2;
    query(x * 2, l, mid, index);
    query(x * 2 + 1, mid + 1, r, index);
}

int main() {
    freopen("mowing.in", "r", stdin);
    freopen("mowing.out", "w", stdout);
    cin >> n >> t;
    for (int i = 1; i <= n; i++) {
        cin >> points[i].first >> points[i].second;
    }
    points[n + 1] = make_pair(t, t);
    sort(points, points + n + 2);
    for (int i = 0; i < n + 2; i++) {
        lastmin[i] = 1e9;
    }
    int length = 0;
    for (int i = 0; i < n + 2; i++) {
        int L = -1;
        int R = n + 2;
        while (L < R - 1) {
            int M = (L + R) / 2;
            if (lastmin[M] < points[i].second) {
                L = M;
            } else {
                R = M;
            }
        }
        lastmin[R] = points[i].second;
        group[R].push_back(points[i]);
        length = max(length, R);
    }
    dp[0].resize(1);
    dp[0][0] = 0;
    for (int i = 1; i <= length; i++) {
        dp[i].resize(group[i].size());
        build(1, 0, dp[i-1].size() - 1);
        for (int j = 0; j < group[i].size(); j++) {
            dp[i][j] = 1e18;
            int st = -1, ed = -1;
            {
                int L = -1, R = group[i-1].size();
                while (L < R - 1) {
                    int M = (L + R) / 2;
                    if (group[i-1][M].second > group[i][j].second) {
                        L = M;
                    } else {
                        R = M;
                    }
                }
                st = R;
            }
            {
                int L = -1, R = group[i-1].size();
                while (L < R - 1) {
                    int M = (L + R) / 2;
                    if (group[i-1][M].first > group[i][j].first) {
                        R = M;
                    } else {
                        L = M;
                    }
                }
                ed = L;
            }
            change(1, 0, group[i-1].size() - 1, st, ed, j);
        }
        query(1, 0, group[i-1].size() - 1, i);
        /*
        cerr << i << ": ";
        for (int j = 0; j < group[i].size(); j++) {
            cerr << dp[i][j] << ' ';
        }
        cerr << endl;
//      */
    }
    cout << dp[length][0] << endl;
    return 0;
}