昆明站没参加，周一下午一起打的重现赛，比赛时间记错，到的时候队友已经过了两道水题了，然后就开了风车那题，思路讨论的很快，加上队友强大的代码功底，一个半小时的时候又过了一题，铜牌到手了。然后就是漫长的卡题…（简直就是济南站复刻），卡在K题（排序题），思路一开始就跑偏，结果就是在跑偏的路上越走越远。一个多小时的挣扎无果，去开新题，感觉一个比一个难，然后自闭。最后实在没事干，我就死磕K题，结果运气逆天被我找到了个规律（其实正解应该是推出来的），但不是很确定，和队友交流了一下，抱着破罐子破摔的态度实现了这个规律，交了一发，居然A了，然后看了一下终榜，去掉打星刚好银尾。

这次比赛打的还是挺魔幻的，还是老问题，前期很顺，后期疲软乏力，说明主敲手的代码功底够扎实，简单题题过的快，但是整体的思维能力还是很欠缺，稍难的题就会把我们卡死。还是得多打cf，多刷题拓展眼见。。。不过，值得高兴的是最终拿了个银，虽然是重现赛，有一定的外部因素的影响，也有一定的运气因素，但还是很鼓舞士气的，EC争取拿个铜，加油！沈阳争取拿个银，加油！

C. Cities（区间DP）

题意：

有n个城市，每个城市归某个议院管辖，每次可以选择相邻的几座归属于同一个议院的城市，将他们交给别的议院管辖，问最少的操作数使得最终全部城市归属一个议院。初始状态时，一个议院最多管辖15座城市。

分析：

首先，一开始就相邻且相同议院的城市可以缩成一座城市（可以一起改变），这样剩下的都是不同的城市，为了描述方便，下面将城市用点代替，归属的议院用字符代替，假设缩点后还剩n个点，最坏的情况需要n-1次操作（所有的点都不同），那么什么情况可以优化使得操作数减少呢？比如xxxabaxxx，我们肯定把 b 改成 a ，而不是分别把两个 a 改成b，所以当一段字符串的两端相同时可以进行优化。

我们用 dp[i][j] 表示下标为 i 到 j 的字符串最小操作数，有如下几种情况（a[ ]表示字符串数组）：

一般情况：
dp[i][j] = min(dp[i][j], min(dp[i+1][j] + 1, dp[i][j-1] + 1))
a[i] == a[j] 时：
dp[i][j] = min(dp[i][j], dp[i+1][j-1] + 1) ，即将 i+1 到 j-1 这一段变成一样后再将整体变成和a[i] 一样。
a[k] == a[j] i<= k <= j 时：
dp[i][j] = min(dp[i][j], dp[i][k-1] + dp[k+1][j] +1)，将k右边的统一变成和 a[j] 一样的颜色，k左边的全部变成任意一样的颜色，然后将k左边全部变成和k一样的颜色（+1）。
a[k] == a[j] == a[i] i<= k <= j 时：
dp[i][j] = min(dp[i][j], dp[i][k-1] + dp[k+1][j])，将k左边变成和 a[i] 一样的颜色，k右边变成和 a[j] 一样的颜色，由于a[i] == a[j] == a[k] 所以，不用+1。

还有注意点就是初始化 dp[i][j] = j-i，即最坏情况，然后要预处理出所有 k 的位置，即距离每个字符左边最近的相同的位置，然后用记忆化搜索去做即可。

代码：

#include <bits/stdc++.h>
#define LL long long
using namespace std;
const int maxn = 1e5 + 10;
const int inf = 0x3f3f3f3f;
const double PI = acos(-1.0);
typedef pair<int, int> PII;
int a[5100], dp[5100][5100];
int pre[5100], ne[5100], id[5100];
int n;
int dfs(int l, int r) {
    if (l == r) return 0;//无需操作，返回0
    if (dp[l][r] != inf) return dp[l][r];//记忆化
    int ans = r - l;//初始化
    ans = min(ans, min(dfs(l + 1, r) + 1, dfs(l, r - 1) + 1));//两种基本情况
    if (a[l] == a[r]) ans = min(ans, dfs(l + 1, r - 1) + 1);//左右两端相同的情况
    for (int i = pre[r]; i > l; i = pre[i]) {//考虑所有的a[k] == a[r]
        ans = min(ans, dfs(i + 1, r) + dfs(l, i - 1) + 1);
        if (a[l] ==  a[r]) ans = min(ans, dfs(i + 1, r) + dfs(l, i - 1));
    }
    //考虑所有的a[k] == a[l],其实这里没必要，只要考虑所有的a[k] == a[r]就足够了
    for (int i = ne[l]; i < r && i > 0; i = ne[i]) {
        ans = min(ans, dfs(i + 1, r) + dfs(l, i - 1) + 1);
        if (a[l] ==  a[r]) ans = min(ans, dfs(i + 1, r) + dfs(l, i - 1));
    }
    return dp[l][r] = ans;//记得记录dp[l][r]
}

int main(int argc, char const *argv[]) {
    int t;
    cin >> t;
    while (t--) {
        memset(dp, 0x3f, sizeof dp);
        memset(id, 0, sizeof id);
        cin >> n;
        for (int i = 1; i <= n; i++) {
            scanf("%d", &a[i]);
            if (a[i] == a[i - 1]) {// 缩点操作
                i--, n--;
                continue;
            }
            pre[i] = id[a[i]];//记录a[i]左边最近的值相同的位置
            id[a[i]] = i;
        }
        // for(int i = 1; i <= n; i++) cout << a[i];
        memset(id, 0, sizeof id);
        //记录a[i]右边最近的值相同的位置，其实没必要
        for(int i = n; i >= 1; i--) {
            ne[i] = id[a[i]];
            id[a[i]] = i;
        }
        cout << dfs(1, n) << '\n';
    }
    return 0;
}

G. Gift(背包DP)

题意：

有N个朋友，告诉你他们的生日日期，以及为每个人制作生日蛋糕需要的时间以及能获得的好感度，你有W元钱，有M件礼物你可以挑选，告诉你每件礼物的价钱和送出去可以获得的好感，一个朋友只能收获一个蛋糕或者一个礼物，每件礼物只能挑选一次，你从2021年的第一天开始计划，问你可以获得的最大好感度。

分析：

首先，礼物最多只有15个，可以穷举所有的情况，用 f[i] 表示送出去 i 件礼物可以获得的最大价值。然后我们可以发现不去考虑送礼物的情况下，就是一个01背包，那么我们可以用 dp[i][j][k] 表示考虑前 i 个人，剩下 j 个人没有做蛋糕，现在是第k天所能获得的最大好感度。那么最终答案就是 $max(dp[n][j][k] + f[j])_{0\leq j \leq M, 1 \leq k \leq 365}$ ,dp[i][j][j] 的状态转移如下：

第 i 个人不制作蛋糕：dp[i][j][k] = max(dp[i][j][k],[i - 1][j - 1][k])
第 i 个人不制作蛋糕：
dp[i][j][k] =max(dp[i][j][k],dp[i - 1][j][k - fri[i].cost] + fri[i].val)

需要注意的是，如果没做蛋糕的人超过了M个其实没啥区别了，所以状态转移的时候只要转移到M就够了，不然会T。每个朋友要按照生日的日期进行排序，要将生日为2月29日的人删去，因为题目要求当天送出蛋糕。

代码：

#include <bits/stdc++.h>
#define LL long long
using namespace std;
const int maxn = 1e5 + 10;
const int inf = 0x3f3f3f3f;
const double PI = acos(-1.0);
typedef pair<int, int> PII;
struct node {
    int data, cost, val;
    const bool operator<(const node &t) { return data < t.data; }
} fri[550];

int f[17], mon[20] = {0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31},s_mon[20];

int cal(int year, int x, int y) {//计算当前日期距离第一天的天数
    if (x == 2 && y == 29) return inf;
    return s_mon[x - 1] + y;
}

PII gift[20];
int dp[550][550][400];
int main(int argc, char const *argv[]) {
    for (int i = 1; i <= 12; i++) s_mon[i] = s_mon[i - 1] + mon[i];
    int t;
    cin >> t;
    while (t--) {
        int N, M, W, n = 0, x, y, z, u, v;
        cin >> N >> M >> W;
        for (int i = 0; i < N; i++) {
            scanf("%d-%d-%d %d %d", &x, &y, &z, &u, &v);
            int data = cal(x, y, z);
            if (data != inf) {
                fri[++n] = {data, u, v};
            }
        }
        sort(fri + 1, fri + 1 + n);
        for (int i = 0; i < M; i++)
            scanf("%d %d", &gift[i].first, &gift[i].second);
        for (int i = 0; i <= M; i++) f[i] = -inf;
        for (int i = 0; i < (1 << M); i++) {//枚举求所有送礼物的最优解
            int sum = 0, cost = 0, cnt = 0;
            for (int j = 0; j < M; j++) {
                if ((i >> j) & 1) {
                    cnt++;
                    cost += gift[j].first;
                    sum += gift[j].second;
                }
            }
            if (cost <= W) f[cnt] = max(f[cnt], sum);
        }
        for (int i = 1; i <= M; i++) f[i] = max(f[i - 1], f[i]);
        for (int i = 0; i <= n; i++) {//dp初始化用循环遍历，memset可能会T
            for (int j = 0; j <= M; j++) {
                for (int k = 0; k <= 365; k++) dp[i][j][k] = -inf;
            }
        }
        dp[0][0][0] = 0;
        for (int i = 1; i <= n; i++) {
            for (int j = 0; j <= min(i, M); j++) {//只转移到最多M人没做蛋糕
                for (int k = 0; k <= 365; k++) {
                    dp[i][j][k] = dp[i - 1][max(j - 1, 0)][k];
                    //只有在当前时间比朋友生日早，且制作蛋糕的时间比当前时间短的情况才可能制作蛋糕
                    if (k >= fri[i].cost && k <= fri[i].data) {
                        dp[i][j][k] = max(dp[i][j][k],dp[i - 1][j][k - fri[i].cost] + fri[i].val);
                    }
                }
            }
        }
        int ans = 0;
        for (int j = 0; j <= M; j++) {
            for (int k = 0; k <= 365; k++) ans = max(ans, dp[n][j][k] + f[j]);
        }
        cout << ans << endl;
    }
    return 0;
}

H. Hard Calculation(签到题)

题意：

输出举办第n次ICPC昆明站的年份。

分析：

有PTA内味儿了，难怪现场赛在“神秘手段”下可以10s过题（

代码：

#include <bits/stdc++.h>

using namespace std;

int main () {
    int n;
    cin >>n;
    cout << n +2020;
}

I. Mr. Main and Windmills(计算几何)

题意：

在一个二维平面，告诉你轨道的起点和终点，一列火车在上面行驶，规定在火车的某一侧有许多的风车，告诉你风车的坐标，以火车的视角来看，一开始的时候风车a可能在风车b的左边，随着火车的移动，风车a可能跑到了风车b的右边，这记为1次变换。有q次询问，每次问你第h个风车发生第k次变换的位置（h号风车与任意风车的左右位置发生变化都记为一次）。

思路：

队友过的（r佬yyds！）。

代码：

#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>

#define x first
#define y second
using namespace std;
typedef pair<double, double> PDD;
const int N = 1e4 + 10;
const double PI = acos(-1.0), eps = 1e-8;
struct Node {
    int id;
    double ang;
    bool operator<(const Node &b) const { return ang < b.ang; }
} v[N][N];
PDD q[N], st, ed;
int cnt[N], n, m;
bool flag;

int sign(double x) {
    if (fabs(x) < eps) return 0;
    if (x < 0) return -1;
    return 1;
}
int dcmp(double x, double y) {
    if (fabs(x - y) < eps) return 0;
    if (x < y) return -1;
    return 1;
}
PDD operator+(PDD a, PDD b) { return {a.x + b.x, a.y + b.y}; }
PDD operator-(PDD a, PDD b) { return {a.x - b.x, a.y - b.y}; }
PDD operator*(PDD a, double b) { return {a.x * b, a.y * b}; }
double operator*(PDD a, PDD b) { return a.x * b.y - a.y * b.x; }
double operator&(PDD a, PDD b) { return a.x * b.x + a.y * b.y; }
double get_dist(PDD a, PDD b) {
    double dx = a.x - b.x;
    double dy = a.y - b.y;
    return sqrt(dx * dx + dy * dy);
}
double get_len(PDD a) { return sqrt(a & a); }
bool on_right(PDD a, PDD b, PDD p) { return sign((p - a) * (b - a)) >= 0; }
PDD get_line_intersection(PDD p, PDD v, PDD q, PDD w) {
    PDD u = p - q;
    double t = (w * u) / (v * w);
    return p + v * t;
}
double get_angle(int id, int p) {
    PDD a, b;
    if (on_right(st, q[id], q[p])) {
        a = st - q[id];
        b = q[p] - q[id];
    } else {
        a = q[id] - st;
        b = q[p] - q[id];
    }
    return acos((a & b) / get_len(a) / get_len(b));
}
void get_change_point() {
    for (int id = 1; id <= n; id++) {
        for (int i = 1; i <= n; i++) {
            if (i == id) continue;
            if (on_right(st, q[id], q[i]) != on_right(ed, q[id], q[i]))
                v[id][++cnt[id]].id = i;
        }
    }
}
void get_point_angle() {
    for (int id = 1; id <= n; id++) {
        for (int i = 1; i <= cnt[id]; i++) {
            v[id][i].ang = get_angle(id, v[id][i].id);
        }
        sort(v[id] + 1, v[id] + cnt[id] + 1);
    }
}
int main() {
    cin >> n >> m;
    scanf("%lf%lf%lf%lf", &st.x, &st.y, &ed.x, &ed.y);
    for (int i = 1; i <= n; i++) scanf("%lf%lf", &q[i].x, &q[i].y);
    if (on_right(st, ed, q[1])) {
        swap(st, ed);
        flag = true;
    }
    get_change_point();
    get_point_angle();
    int h, k;
    while (m--) {
        scanf("%d%d", &h, &k);
        if (k > cnt[h]) {
            puts("-1");
        } else {
            if (flag) k = cnt[h] - k + 1;
            PDD o =
                get_line_intersection(st, ed - st, q[h], q[v[h][k].id] - q[h]);
            printf("%.10lf %.10lf\n", o.x, o.y);
        }
    }
    return 0;
}

J. Parallel Sort（思维）

题意：

给你一个1-n的随机排列（即1-n的数字每个出现且只出现一次），现在有一个操作：选取任意对数字，并将他们分别两两交换，要求选择的这k对数字中没有一个数字同时在两对数字中。问你最少的操作次数，并输出方案。

分析：

以7 5 3 1 2 6 8 4为例，我们首先设法将数字7归位，即与 a[7] = 8 互换，然后将 8 归位，即与 a[8] = 4 互换，一直执行下去，发现可以找到若干个链： 7 - 8 - 4 - 1， 5 - 2 （3和6已经归位）。我们发现类似 5 - 2 这样只有两个元素的链是可以通过一次互换完成归位操作的。再来看 7 - 8 - 4 - 1 这样的链，我们可以发现，7要到8的位置，8要到4的位置，4要到1的位置，1要到初始时7的位置，所以他们的位置是刚好错位的，所以问题就转变成了如何将所有元素向右挪一位（最后一位挪到第一位）。将问题抽象：即将 1,2,3,4,5...,N 变成 N,1,2,3,4,...,N-1 ,可以用两步完成这样的操作：

整体收尾交换，得到：N,N-1,N-2,...,3,2,1
忽略最后一个元素，将剩下的元素收尾交换，得到：N,1,2,3,...,N-3,N-2,N-1

如此便完成了整体向右移动一位的操作，且操作数固定为2，一定为最优解。综上可以整理出本题的解法：首先找出所有的链，判断是否有大于2个元素的链，如果没有则表示只要两两互换即可，操作数为1。如果存在，则用上述的方法，进行两次操作，注意题目要求输出的是下标。

题外话：对于序列 1,2,3,4,..N 也可以两步操作使得整体向左移动一位，只要在第一步的时候忽略第一个元素，其他操作不变。

代码：

#include <bits/stdc++.h>
#define LL long long
using namespace std;
const int maxn = 1e5 + 10;
const int inf = 0x3f3f3f3f;
const double PI = acos(-1.0);
typedef pair<int, int> PII;
int vis[maxn], a[maxn];
vector<vector<int>> cir;//记录所有的环（链）

void solve() {
    vector<PII> ans1, ans2;//ans1存第一步的方案，ans2存第二步的方案
    for (int i = 0; i < cir.size(); i++) {
        if (cir[i].size() == 2) {//将只需要一次交换的环在第二步集中交换
            ans2.push_back({cir[i][0], cir[i][1]});
            continue;
        }
        int L = 0, R = cir[i].size() - 1;
        while (L < R) {//第一步将除了最后一个元素的链首尾交换
            ans1.push_back({cir[i][L], cir[i][R]});
            L++;
            R--;
        }
    }

    for (int i = 0; i < cir.size(); i++) {
        if (cir[i].size() == 2) continue;
        int L = 1, R = cir[i].size() - 1;
        while (L < R) {
            ans2.push_back({cir[i][L], cir[i][R]});
            L++;
            R--;
        }
    }
    printf("%d", ans1.size());
    for (int i = 0; i < ans1.size(); i++) {
        printf(" %d %d", ans1[i].first, ans1[i].second);
    }
    puts("");
    printf("%d", ans2.size());
    for (int i = 0; i < ans2.size(); i++) {
        printf(" %d %d", ans2[i].first, ans2[i].second);
    }
}

int main(int argc, char const *argv[]) {
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
    int flag = 0;//判断是否有环，以及是否有大于2的环
    for (int i = 1; i <= n; i++) {
        if (vis[i] == 1) continue;//已经在某个环里了，跳过
        int id = i;//当前需要判断的元素的下标
        vector<int> temp;//存当前的环
        //找环操作，不好表达，模拟一下就知道了
        while (i != a[id]) {//每次交换都是放到第i个位置，所以只要判断当前的值是否为i即可
            temp.push_back(id);
            vis[id] = 1;
            id = a[id];
            if (a[id] == i) temp.push_back(id), vis[id] = 1;
        }
        if (temp.size() != 0) {
            if(flag == 0 ) flag = 1;
            cir.push_back(temp);
            if (temp.size() > 2) flag = 2;
        }
    }
    if (flag == 0) {
        puts("0");
    } else if (flag == 1) {
        puts("1");
        printf("%d", cir.size());
        for (int i = 0; i < cir.size(); i++) {
            printf(" %d %d", cir[i][0], cir[i][1]);
        }
        puts("");
    } else {//有大于2的环，需要两步
        puts("2");
        solve();
    }
    return 0;
}

L. Simone and graph coloring

记错时间，比赛来晚了二十分钟，刚踏进实验室，就听到队友：“oh，A了！”

#include <bits/stdc++.h>

using namespace std;
const int N = 1e6 + 10;
int a[N], dp[N], co[N], cnt;

int Find(int l, int r, int val) {
    int res = r + 1;
    while (l <= r) {
        int mid = l + r >> 1;
        if (dp[mid] < val) {
            res = mid;
            r = mid - 1;
        } else {
            l = mid + 1;
        }
    }
    return res;
}

int main() {
    int t, n;
    cin >> t;
    while (t --) {
        scanf("%d", &n);
        cnt = 0;
        for (int i = 1; i <= n; i++) {
            scanf("%d", &a[i]);
            int id = Find(1, cnt, a[i]);
            dp[id] = a[i];
            co[i] = id;
            if (id > cnt) cnt = id;
        }
        printf("%d\n", cnt);
        for (int i = 1; i <= n; i++) printf("%d%c", co[i], i == n ? '\n' : ' ');
    }
    return 0;
}

M. Stone Games(主席树)

题意：

抽象化后的题意是这样的，给你长度为n的一个序列，q次询问，每次问你序列中下标从L到R的所有数字任意组合，不能表示的最小数字。需要注意的是，每次询问的范围L，R不是直接给你而是通过上次询问的答案计算得到的，所以必须进行在线处理。

分析：

要用到权值线段树，忘的有点厉害，先挖个坑，找时间再填。

代码：

（队友赛后补题代码）

#include <bits/stdc++.h>

using namespace std;
typedef long long LL;
const int N = 1e6 + 10;
struct SegmentTree {
    int l, r;
    LL val;
} tr[N << 5];
vector<int> ls;
map<int, vector<int>> mp;
int a[N], root[N], idx;

int Find(LL val) {
    return lower_bound(ls.begin(), ls.end(), val) - ls.begin();
}

int build(int p, int l, int r) {
    p = ++idx;
    if (l == r) return p;
    int mid = l + r >> 1;
    tr[p].l = build(tr[p].l, l, mid);
    tr[p].r = build(tr[p].r, mid + 1, r);
    return p;
}

int Insert(int p, int q, int l, int r, int id) {
    p = ++idx;
    tr[p] = tr[q];
    if (l == r) {
        tr[p].val += ls[id];
    } else {
        int mid = l + r >> 1;
        if (id <= mid)
            tr[p].l = Insert(tr[p].l, tr[q].l, l, mid, id);
        else
            tr[p].r = Insert(tr[p].r, tr[q].r, mid + 1, r, id);
        tr[p].val = tr[tr[p].l].val + tr[tr[p].r].val;
    }
    return p;
}

LL query(int p, int q, int l, int r, int limit) {
    if (l >= limit) return 0;
    int mid = l + r >> 1;
    if (r < limit) {
        return tr[p].val - tr[q].val;
    } else if (mid < limit) {
        return tr[tr[p].l].val - tr[tr[q].l].val +
               query(tr[p].r, tr[q].r, mid + 1, r, limit);
    } else {
        return query(tr[p].l, tr[q].l, l, mid, limit);
    }
    return 0;
}

bool judge(LL val, int l, int r) {
    if (mp.count(val) == 0) return false;
    vector<int> &v = mp[val];
    l = lower_bound(v.begin(), v.end(), l) - v.begin();
    if (l < v.size() && v[l] <= r) return true;
    return false;
}

int main() {
    int n, q, l, r, ll, rr;
    LL ans = 0;
    cin >> n >> q;
    for (int i = 1; i <= n; i++) {
        scanf("%d", &a[i]);
        mp[a[i]].push_back(i);
        ls.push_back(a[i]);
    }
    sort(ls.begin(), ls.end());
    ls.erase(unique(ls.begin(), ls.end()), ls.end());
    root[0] = build(root[0], 0, ls.size() - 1);
    for (int i = 1; i <= n; i++) {
        root[i] = Insert(root[i], root[i - 1], 0, ls.size() - 1, Find(a[i]));
    }
    while (q--) {
        scanf("%d %d", &ll, &rr);
        l = min((LL)(ll + ans) % n + 1, (LL)(rr + ans) % n + 1);
        r = max((LL)(ll + ans) % n + 1, (LL)(rr + ans) % n + 1);
        LL f = 0;
        int last = Find(f + 1);
        while (last < ls.size() && f + 1 >= ls[last]) {
            last = Find(f + 2);
            f = query(root[r], root[l - 1], 0, ls.size() - 1, last);
        }
        ans = f + 1;
        printf("%lld\n", ans);
    }
    return 0;
}