昆明站没参加，周一下午一起打的重现赛，比赛时间记错，到的时候队友已经过了两道水题了，然后就开了风车那题，思路讨论的很快，加上队友强大的代码功底，一个半小时的时候又过了一题，铜牌到手了。然后就是漫长的卡题…（简直就是济南站复刻），卡在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 的位置，即距离每个字符左边最近的相同的位置，然后用记忆化搜索去做即可。
代码：
代码语言：javascript复制#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])_{0leq 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日的人删去，因为题目要求当天送出蛋糕。
代码：
代码语言：javascript复制#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过题（
代码：
代码语言：javascript复制#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！）。
代码：
代码语言：javascript复制#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 %.10lfn", 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 也可以两步操作使得整体向左移动一位，只要在第一步的时候忽略第一个元素，其他操作不变。
代码：
代码语言：javascript复制#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了！”
代码语言：javascript复制#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("%dn", 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不是直接给你而是通过上次询问的答案计算得到的，所以必须进行在线处理。
分析：
要用到权值线段树，忘的有点厉害，先挖个坑，找时间再填。
代码：
（队友赛后补题代码）
代码语言：javascript复制#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("%lldn", ans);
}
return 0;
}
