Bronze

B1 / 843

还是$3$个变量，模拟交换，用数组计数即可。

import sys
sys.stdin = open('shell.in', 'r')
sys.stdout = open('shell.out', 'w')
n = input()
a = [0, 1, 2, 3]
c = [0, 0, 0, 0]
for i in range(n):
    x, y, z = map(int, raw_input().split())
    a[x], a[y] = a[y], a[x]
    c[a[z]] += 1
print max(c)

B2 / 844

未被操作的部分必须是一个单调增加的后缀。

import sys
sys.stdin = open('sleepy.in', 'r')
sys.stdout = open('sleepy.out', 'w')
n = input()
a = map(int, raw_input().split())
for i in range(n)[::-1]:
    if i == 0 or a[i-1] > a[i]:
        print i
        break

B3 / 845

枚举两个不同的集合，集合求交，然后用交集大小更新答案。

import sys
sys.stdin = open('guess.in', 'r')
sys.stdout = open('guess.out', 'w')
n = input()
a = []
for i in range(n):
    a.append(set(raw_input().split()[2:]))
z = 0
for i in range(n):
    for j in range(i):
        z = max(z, len(a[i] & a[j]))
print z + 1

Silver

S1 / 846

统计每个点度数，最大的度数+1就是答案。
比上个月简单好多。

#include <bits/stdc++.h>
using namespace std;
int n, x, y;
int c[100020];
int main() {
    freopen("planting.in", "r", stdin);
    freopen("planting.out", "w", stdout);
    scanf("%d", &n);
    for (int i = 1; i < n; i++) {
        scanf("%d%d", &x, &y);
        c[x]++;
        c[y]++;
    }
    int cnt = 0;
    for (int i = 0; i < n; i++) {
        cnt = max(cnt, c[i] + 1);
    }
    printf("%d\n", cnt);
    return 0;
}

S2 / 847

https://www.luogu.org/problemnew/show/P1451 计算每个区域面积和周长
直接DFS

#include <bits/stdc++.h>
using namespace std;
char s[1002][1002];
bool v[1002][1002];
int dx[] = {0, 0, -1, 1};
int dy[] = {-1, 1, 0, 0};
int n, area, perimeter;
pair<int, int> ans;
bool in(int x, int y) {
    return 0 <= x && x < n && 0 <= y && y < n;
}

void dfs(int x, int y) {
    if (v[x][y]) {
        return;
    }
    v[x][y] = true;
    area++;
    for (int i = 0; i < 4; i++) {
        int nx = x + dx[i];
        int ny = y + dy[i];
        if (in(nx, ny) && s[nx][ny] == '#') {
            dfs(nx, ny);
        } else {
            perimeter++;
        }
    }
}

int main() {
    freopen("perimeter.in", "r", stdin);
    freopen("perimeter.out", "w", stdout);
    scanf("%d", &n);
    for (int i = 0; i < n; i++) {
        scanf("%s", s[i]);
    }
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (s[i][j] == '#' && !v[i][j]) {
                area = 0;
                perimeter = 0;
                dfs(i, j);
                ans = max(ans, make_pair(area, -perimeter));
            }
        }
    }
    printf("%d %d\n", ans.first, -ans.second);
    return 0;
}

S3 / 848

将每个(x, y)变成区间(x-y, x+y)
然后问题变成了选最多的区间，使得不出现包含的情况。
https://www.luogu.org/problemnew/show/P1803 如果不能选相互包含的区间（选取的多个区间要么相离要么相交），最多选多少个？
按左端点从小到大排序，如果左端点相同，右端点从大到小排序。
这样对于两个区间i和j，如果i < j 且 r[i] >= r[j]那么区间i包含区间j。
贪心选择即可。

#include <bits/stdc++.h>
using namespace std;
int n, x, y;
pair<int, int> a[100020];
int main() {
    freopen("mountains.in", "r", stdin);
    freopen("mountains.out", "w", stdout);
    scanf("%d", &n);
    for (int i = 0; i < n; i++) {
        scanf("%d%d", &x, &y);
        a[i].first = x - y;
        a[i].second = -x - y;
    }
    sort(a, a + n);
    int cnt = 0, l = -2e9;
    for (int i = 0; i < n; i++) {
        if (l < -a[i].second) {
            l = -a[i].second;
            cnt++;
        }
    }
    printf("%d\n", cnt);
    return 0;
}

Gold

G1 / 849

背包，先求出以每个韵结尾的句子数。
最后对于每个大写字母计数，

#include <bits/stdc++.h>
using namespace std;
int n, m, l, p = 1000000007;
int f[5020];
int s[5020];
int c[5020];
int v[26];
int z[5020];
int pw(int x, int y) {
    int re = 1;
    for (; y > 0; y >>= 1) {
        if (y & 1) {
            re = (long long)re * x % p;
        }
        x = (long long)x * x % p;
    }
    return re;
}
int main() {
    freopen("poetry.in", "r", stdin);
    freopen("poetry.out", "w", stdout);
    scanf("%d%d%d", &n, &m, &l);
    for (int i = 0; i < n; i++) {
        scanf("%d%d", &s[i], &c[i]);
    }
    f[0] = 1;
    for (int i = 1; i <= l; i++) {
        for (int j = 0; j < n; j++) {
            if (i >= s[j]) {
                f[i] = (f[i] + f[i - s[j]]) % p;
            }
        }
    }
    for (int i = 0; i < n; i++) {
        z[c[i]] = (z[c[i]] + f[l - s[i]]) % p;
    }
    for (int i = 0; i < m; i++) {
        char ch;
        scanf(" %c", &ch);
        v[ch - 'A']++;
    }
    int ans = 1;
    for (int i = 0; i < 26; i++) {
        if (v[i] == 0) {
            continue;
        }
        int tmp = 0;
        for (int j = 1; j <= n; j++) {
            tmp = (tmp + pw(z[j], v[i])) % p;
        }
        ans = (long long)ans * tmp % p;
    }
    printf("%d\n", ans);
    return 0;
}

G2 / 850

树状数组。

#include <bits/stdc++.h>
using namespace std;
int n;
int c[1000020];
int a[1000020];
int z[1000020];
int v[1000020];
void change(int x, int y) {
    for (int i = x; i <= 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;
}
int main() {
    freopen("sleepy.in", "r", stdin);
    freopen("sleepy.out", "w", stdout);
    scanf("%d", &n);
    for (int i = 0; i < n; i++) {
        scanf("%d", &a[i]);
        change(a[i], 1);
    }
    int ans = -1;
    for (int i = n - 1; i >= 0; i--) {
        if (i == 0 || a[i - 1] > a[i]) {
            ans = i;
            break;
        }
    }
    printf("%d\n", ans);
    for (int i = ans - 1; i >= 0; i--) {
        change(a[i], -1);
        z[i] = query(a[i]) + ans - 1 - i;
    }
    if (ans == 0) {
        printf("\n");
    } else {
        for (int i = 0; i < ans; i++) {
            printf("%d%c", z[i], i == ans - 1 ? '\n' : ' ');
        }
    }
    return 0;
}

G3 / 851

裸最短路数，用dijkstra更新的时候，不仅要记录最短路，还要记录每个点是被哪个点更新的。

#include <bits/stdc++.h>
using namespace std;
vector<pair<int, int> > a[10020];
int n, m, t;
int c[10020];
int d[10020];
int f[10020];
set<pair<int, int> > s;
vector<int> q;
int main() {
    freopen("shortcut.in", "r", stdin);
    freopen("shortcut.out", "w", stdout);
    scanf("%d%d%d", &n, &m, &t);
    for (int i = 1; i <= n; i++) {
        scanf("%d", &c[i]);
    }
    for (int i = 0; i < m; i++) {
        int x, y, z;
        scanf("%d%d%d", &x, &y, &z);
        a[x].push_back(make_pair(y, z));
        a[y].push_back(make_pair(x, z));
    }
    memset(d, 0x3f, sizeof d);
    d[1] = 0;
    s.insert(make_pair(d[1], 1));
    while (s.size()) {
        int u = s.begin() -> second;
        q.push_back(u);
        s.erase(s.begin());
        for (int i = 0; i < a[u].size(); i++) {
            if (d[a[u][i].first] > d[u] + a[u][i].second) {
                s.erase(make_pair(d[a[u][i].first], a[u][i].first));
                d[a[u][i].first] = d[u] + a[u][i].second;
                f[a[u][i].first] = u;
                s.insert(make_pair(d[a[u][i].first], a[u][i].first));
            } else if (d[a[u][i].first] == d[u] + a[u][i].second) {
                f[a[u][i].first] = min(f[a[u][i].first], u);
            }
        }
    }
    long long ans = 0;
    for (int i = q.size() - 1; i > 0; i--) {
        ans = max(ans, (long long)c[q[i]] * (d[q[i]] - t));
        c[f[q[i]]] += c[q[i]];
    }
    printf("%lld\n", ans);
    return 0;
}

Platinum

P1 / 852

很容易得到一个时间复杂度为nk的动态规划

    for (int i = 1; i <= n; i++) {
        f[i] = f[i - 1] + 1;
        for (int j = max(i - m, 0); j < i; j++) {
            if (i - 2 * s[i] > j - 2 * s[j]) {
                f[i] = min(f[i], f[j]);
            } else {
                f[i] = min(f[i], f[j] + 1);
            }
        }
    }

先用 max(i – m, 0) 到 i-1 的每个j 的f[j] + 1更新f[i]
这个是区间最值，可以用线段树或者单调队列解决
然后考虑满足i – 2 * s[i] > j – 2 * s[j] 的 f[j]来更新f[i] （这里不+1，所以更优）
所以说每次得到一个f[i]，就把他放在i – 2 * s[i]的位置上，然后变成了询问小于i – 2 * s[i]的位置上，最小值是多少的问题。
这里注意一个位置上可能被加多个值
并且加上的值还必须支持删除（i – j > m的话就要把j删掉了）
所以用线段树，每个叶子节点维护一个set即可。

#include <bits/stdc++.h>
using namespace std;
int n, m;
char c[300020];
int f[300020];
int s[300020];
int qq[300020], bb, ff;
multiset<int> ms[600020];
int mn[2400020];
int inf = 1e9;
void build(int x, int L, int R) {
    if (L == R - 1) {
        mn[x] = inf;
        return;
    }
    int M = (L + R) / 2;
    build(x * 2, L, M);
    build(x * 2 + 1, M, R);
    mn[x] = min(mn[x * 2], mn[x * 2 + 1]);
}
int query(int x, int L, int R, int l, int r) {
    if (r <= L || R <= l) {
        return inf;
    }
    if (l <= L && R <= r) {
        return mn[x];
    }
    int M = (L + R) / 2;
    return min(query(x * 2, L, M, l, r), query(x * 2 + 1, M, R, l, r));
}
void insert(int x, int L, int R, int p, int v) {
    if (L == R - 1) {
        ms[L].insert(v);
        mn[x] = *ms[L].begin();
        return;
    }
    int M = (L + R) / 2;
    if (p < M) {
        insert(x * 2, L, M, p, v);
    } else {
        insert(x * 2 + 1, M, R, p, v);
    }
    mn[x] = min(mn[x * 2], mn[x * 2 + 1]);
}
void erase(int x, int L, int R, int p, int v) {
    if (L == R - 1) {
        multiset<int>::iterator it = ms[L].find(v);
        assert(it != ms[L].end());
        ms[L].erase(it);
        if (ms[L].size() > 0) {
            mn[x] = *ms[L].begin();
        } else {
            mn[x] = inf;
        }
        return;
    }
    int M = (L + R) / 2;
    if (p < M) {
        erase(x * 2, L, M, p, v);
    } else {
        erase(x * 2 + 1, M, R, p, v);
    }
    mn[x] = min(mn[x * 2], mn[x * 2 + 1]);
}
int main() {
    freopen("redistricting.in", "r", stdin);
    freopen("redistricting.out", "w", stdout);
    scanf("%d%d", &n, &m);
    scanf("%s", c);
    for (int i = 0; i < n; i++) {
        s[i + 1] = s[i] + (c[i] == 'G');
    }
    qq[ff++] = 0;
    build(1, 0, 2 * n + 1);
    insert(1, 0, 2 * n + 1, n, 0);
    for (int i = 1; i <= n; i++) {
        while (qq[bb] < i - m) {
            bb++;
        }
        {
            int u = i - m - 1;
            if (u >= 0) {
                erase(1, 0, 2 * n + 1, n + u - 2 * s[u], f[u]);
            }
        }
        assert(bb < ff);
        f[i] = f[qq[bb]] + 1;
        int tmp = query(1, 0, 2 * n + 1, 0, n + i - 2 * s[i]);
        f[i] = min(f[i], tmp);
        insert(1, 0, 2 * n + 1, n + i - 2 * s[i], f[i]);
        while (bb < ff && f[qq[ff - 1]] >= f[i]) {
            ff--;
        }
        qq[ff++] = i;
/*
        for (int j = max(i - m, 0); j < i; j++) {
            if (i - 2 * s[i] > j - 2 * s[j]) {
                f[i] = min(f[i], f[j]);
            } else {
                f[i] = min(f[i], f[j] + 1);
            }
        }
*/
//      cerr << i << ' ' << f[i] << endl;
    }
    printf("%d\n", f[n]);
    return 0;
}

P2 / 853

全部的路径数 – 没有公共点（显然不会有公共边）的路径对数 – 只有公共点而没有公共边的路径对数

全部的路径数 = C(m, 2) m为非树边的个数

没有公共点（显然不会有公共边）的路径对数
考虑较深的路径的lca的父亲方向的边，我们希望每一对路径都在这个位置被统计到。
所以需要处理对于每个点，有多少个点以他为LCA。
每个点对应的子树，内部有多少条路径
子树内部的路径有两种含义，
第一种是指路径完全在子树内部（路径的LCA在子树内部）
第二种是指路径一个端点在子树内部，一个端点在子树外部。
答案 += 以当前点为LCA的路径数 * (m – 路径完全在子树内部的个数 – 路径一个端点在子树内部的个数)
(m – 路径完全在子树内部的个数 – 路径一个端点在子树内部的个数) 相当于是不在子树内部的路径个数

但是这样会有一个问题，如果一对路径，分属不同子树，那么答案中他们会被统计两次，需要把这种情况减掉。
这个减去的过程会在所有点的LCA处被减去。

只有公共点而没有公共边的路径对数，考虑一条路径和一个点的关系有哪些
可能是完全无关，路径不通过这个点（这不需要考虑）
可能是通过这个点，和这个点相邻的两条边有交集。
可能是这个点是端点之一，和这个点相邻的一条边有交集。

然后需要考虑 有多少对边集（边集大小<=2），交集为空。
做法非常经典：
交集为空的边集对数 = C(交集包含空集的集合数, 2) – C(交集包含大小为1的集合数, 2) + C(交集包含大小为2的集合数, 2)
大小为1的集合 和 大小为2的集合 均需要枚举所有可能性。

大小为0的集合 即枚举所有点，对于每个点计算有多少条路径经过他。
大小为1的集合 即枚举所有边，对于每条边计算有多少条路径经过他。

以上两个问题几乎一样，但是注意每条边应该在孩子节点和父亲节点各被计算一遍。

大小为2的集合，即枚举所有相邻的两条边，对于每组计算有多少条路径经过他。
但是这样会超时，需要想一些其他的办法。

考虑一个点，大小为2的集合有这么几种可能
1. 从一个孩子来，到另一个孩子去（那么说明自己是LCA，这样的话每条路径求LCA的时候，求出来最接近LCA的2个点即可）
2. 从一个孩子来，到父亲节点去（因为每个点的孩子数不太多，直接枚举计算即可）

#include <bits/stdc++.h>
using namespace std;
int n, m;
vector<int> a[200020];
int f[200020][18]; // father
int d[200020]; //depth
long long b[200020]; // 有多少条路径过自己父亲这条边
long long r[200020]; // 当前点有多少个lca
long long c[200020]; // 子树内有多少个lca
long long e[200020]; // 有多少个路径，以x的父亲节点为lca
long long ans;
map<pair<int, int>, int> g[200020];
void dfs(int x, int y) {
    f[x][0] = y;
    d[x] = d[y] + 1;
    for (int i = 1; i < 18; i++) {
        f[x][i] = f[f[x][i - 1]][i - 1];
    }
    for (int i: a[x]) {
        if (i != y) {
            dfs(i, x);
        }
    }
}

void dfs2(int x, int y) {
    long long u = c[x];
    r[x] = c[x];
    long long s1 = 0;
    long long s2 = 0;
    for (int i: a[x]) {
        if (i != y) {
            dfs2(i, x);
            c[x] += c[i];
            b[x] += b[i];
            s1 += c[i];
            s2 += c[i] * c[i];
            ans -= (b[i] - e[i]) * (b[i] - e[i] - 1) / 2;
        }
    }
    ans -= u * (m - c[x] - b[x]);
// 有一些会被减两次
    ans += (s1 * s1 - s2) / 2;
// 加回来


    ans -= (b[x] + r[x]) * (b[x] + r[x] - 1) / 2;
//  cerr << (b[x] + r[x]) * (b[x] + r[x] - 1) / 2 << endl;
// 减去交集为0的对数（过点x的）

    ans += (b[x]) * (b[x] - 1) / 2 * 2;
//  cerr << (b[x]) * (b[x] - 1) / 2 << endl;
// 加上交集为1的对数（过点x父亲那条边的）

// 减去交集为2的，LCA是当前点。
    for (pair<pair<int, int>, int> i: g[x]) {
        ans -= (long long)i.second * (i.second - 1) / 2;
//      cerr << (long long)i.second * (i.second - 1) / 2 << endl;
    }
// 接下来需要考虑的路径就是自己孩子到自己父亲节点这种路径了
// 简单来说这就是b[i] ?但是有一些路径以自己结束啊，再开一个数组吧。
}

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 < 18; i++) {
        if (dd >> i & 1) {
            x = f[x][i];
        }
    }
    if (x == y) {
        return x;
    }
    for (int i = 17; i >= 0; i--) {
        if (f[x][i] != f[y][i]) {
            x = f[x][i];
            y = f[y][i];
        }
    }
    return f[x][0];
}

/*
对于每个点，每条路径是一个大小为2的集合
问有多少对集合没有交集
交集为0的对数 - 交集为1的对数 + 交集为2的对数
*/

int main() {
    freopen("exercise.in", "r", stdin);
    freopen("exercise.out", "w", stdout);
    scanf("%d%d", &n, &m);
    for (int i = 1; i < n; i++) {
        int x, y;
        scanf("%d%d", &x, &y);
        a[x].push_back(y);
        a[y].push_back(x);
    }
    dfs(1, 0);
    m -= n - 1;
    for (int i = 0; i < m; i++) {
        int x, y, nx, ny;
        scanf("%d%d", &x, &y);
        nx = x;
        ny = y;
        int l = lca(x, y);
        b[x]++;
        b[y]++;
        b[l] -= 2;
        c[l]++;
        for (int i = 17; i >= 0; i--) {
            if (d[f[nx][i]] > d[l]) {
                nx = f[nx][i];
            }
            if (d[f[ny][i]] > d[l]) {
                ny = f[ny][i];
            }
        }
        if (nx > ny) {
            swap(nx, ny);
        }
        if (nx != l) {
            e[nx]++;
        }
        if (ny != l) {
            e[ny]++;
        }
        if (nx != l && ny != l) {
            g[l][make_pair(nx, ny)]++;
        }
    }
    ans = (long long)m * (m - 1) / 2;
/*
全部 m*(m-1)/2
减去 不想交的
*/
    dfs2(1, 0);
/*
到这里，答案应该是点相交的无序对数量
还需要减去，只相交在点上的，也就是 -(交集为0的对数 - 交集为1的对数 + 交集为2的对数)
*/
    printf("%lld\n", ans);
    return 0;
}

P3 / 854

对于相邻的2个数字，如果c[i] < c[i + 1]
那么显然a[i] = c[i]

如果c[i] > c[i + 1]
那么显然a[i + k] = c[i + 1]

考虑这样的数据

7 3
1 2 2 2 3
可以画出7个位置
1 _ _ 2 _ _ _
其中
第2, 3, 4个位置，要求每个长度为3的区间的最小值都是2
第5, 6, 7个位置，要求每个长度为3的区间的最小值都是3

7 3
1 2 2 2 1
可以画出7个位置
1 _ _ _ _ _ 1
其中
第2, 3, 4, 5, 6个位置，要求每个长度为3的区间的最小值都是2

7 3
3 2 2 2 3
可以画出7个位置
_ _ _ 2 _ _ _
其中
第1, 2, 3个位置，要求每个长度为3的区间的最小值都是3
第5, 6, 7个位置，要求每个长度为3的区间的最小值都是3

10 3
3 2 2 2 2 2 2 3
_ _ _ 2 _ _ 2 _ _ _
其中
第1, 2, 3个位置，要求每个长度为3的区间的最小值都是3
第8, 9, 10个位置，要求每个长度为3的区间的最小值都是3
第4, 5, 6, 7个位置，要求每个长度为3的区间的最小值都是2

发现问题转化为了，对于一个长度为$n$的数组，要求每个长度为$m$的区间，最小值都是$M – r$。
其中$M$是能填的数字的上界。
（第一个和最后一个数字必须是M – r，并不影响答案，直接让n -= 1即可）
设f[i]为第i个数字为M – r的方案数

f[0] = 1 (什么都没有)
f[1] = 1 (只填了一个M – r)
f[i] = sum(i – j <= m, f[j] * r ** (i – j – 1))
第i个位置和第j个位置都必须是$M – r$，期间有$i – j – 1$个位置可以自由决定填$M – r + 1$到$M$共$r$个数字。
这个dp显然可以用前缀和优化。

把原题可以划分成若干段这样的DP，然后就可以AC了。

#include <bits/stdc++.h>
using namespace std;
int p = 1000000007;
int M = 1e9;
int n, m, ans;
int c[200020];
vector<pair<int, int> > b;
long long f[200020];
int F(int n, int m, int r) {
    if (n == -1) {
        return 1;
    }
    if (n < 0) {
        return 0;
    }
    for (int i = 0; i < n + 2; i++) {
        f[i] = 0;
    }
    f[0] = 1;
    long long u = f[0];
    long long v = 1;
    for (int i = 0; i < m; i++) {
        v = v * r % p;
    }
    for (int i = 1; i < n + 2; i++) {
        f[i] = u;
        u = (u * r + f[i]) % p;
        if (i - m >= 0) {
            u = (u - f[i - m] * v) % p;
        }
        if (u < 0) {
            u += p;
        }
    }
    return f[n + 1];
}

int main() {
    freopen("tracking2.in", "r", stdin);
    freopen("tracking2.out", "w", stdout);
//  scanf("%d%d%d", &n, &m, &M);
    scanf("%d%d", &n, &m);
    for (int i = 0; i <= n - m; i++) {
        scanf("%d", &c[i]);
    }
    b.push_back(make_pair(0, 1));
    for (int i = 0, j; i <= n - m; i = j) {
        j = i;
        while (j <= n - m && c[j] == c[i]) {
            j++;
        }
        b.push_back(make_pair(c[i], j - i));
    }
    b.push_back(make_pair(0, 1));
    ans = 1;
    for (int i = 1; i < b.size() - 1; i++) {
        if (b[i - 1].first < b[i].first && b[i].first > b[i + 1].first) {
            ans = (long long)ans * F(b[i].second + m - 1, m, M - b[i].first) % p;
        } else if (b[i - 1].first > b[i].first && b[i].first < b[i + 1].first) {
            ans = (long long)ans * F(b[i].second - m - 1, m, M - b[i].first) % p;
        } else {
            ans = (long long)ans * F(b[i].second - 1, m, M - b[i].first) % p;
        }
    }
    cout << ans << endl;
    return 0;
}