题目链接：https://codeforces.com/contest/1343
A - Candies
随便做做。
B - Balanced Array
随便做做。
C - Alternating Subsequence
贪心，每段连续的正数和负数选最大的。
int n;
ll a[200005];
void TestCase() {
scanf("%d", &n);
for(int i = 1; i <= n; ++i)
scanf("%lld", &a[i]);
for(int l = 1, r; l <= n; l = r + 1) {
ll maxval = -LINF;
for(r = l; r + 1 <= n && ((a[l] < 0 && a[r + 1] < 0) || (a[l] > 0 && a[r + 1] > 0)); ++r)
maxval = max(maxval, a[r]);
maxval = max(maxval, a[r]);
for(int i = l; i <= r; ++i)
a[i] = maxval;
}
ll sum0 = 0, sum1 = 0;
int len0 = 0, len1 = 0;
int cur0 = 0, cur1 = 1;
for(int i = 1; i <= n; ++i) {
if(a[i] > 0) {
if(cur0 == 0) {
++len0;
sum0 += a[i];
cur0 = 1;
}
if(cur1 == 0) {
++len1;
sum1 += a[i];
cur1 = 1;
}
} else {
if(cur0 == 1) {
++len0;
sum0 += a[i];
cur0 = 0;
}
if(cur1 == 1) {
++len1;
sum1 += a[i];
cur1 = 0;
}
}
}
if(len0 > len1)
printf("%lld
", sum0);
else if(len0 < len1)
printf("%lld
", sum1);
else
printf("%lld
", max(sum0, sum1));
return;
}
D - Constant Palindrome Sum
题意：如题目的名字，给一个 (n) 个数字的数组，要保持对称位置的和恒为常数，但是每个数的范围都必须是 ([1,k]) ，求最少要修改多少次，每次修改可以选一个数改为 ([1,k]) 。
题解：数据结构选手总是强行套数据结构上去。
先想一个朴素的解法，枚举这个常数 (x in [2,2k]) ，然后每次扫一遍数组检测最少需要修改多少次，注意到若某个数对 ((a,b)) （这里 (aleq b) ）的和不足 (x) ，则应该贪心把小的那个加到至多 (k) ，反之要把大的那个数减到至多 (1) 。
那么这个朴素的解法复杂度是 (O(nk)) ，枚举 (x) 的过程无法二分优化，因为不满足单调性。但是注意到枚举 (x) 的过程可以迭代，每次把数对从“大于 (x) 的数据结构”搬到“小于 (x) 的数据结构”。那么这个过程需要用一种这样的数据结构来维护：
1、“小于 (x) 的数据结构”可以插入元素
2、“小于 (x) 的数据结构”需要贪心把 (a) 提升到 (k) ，所以要数 (k-aleq x-(a+b)) 的数量，也就是查询 (xgeq k+b) 的数量，换言之这个数据结构应该存 (k+b) ，然后支持查询 (x) 的名次。（其实这里可以把 (k) 移项过去节省空间）
1、“大于 (x) 的数据结构”可以删除元素。
2、“大于 (x) 的数据结构”需要贪心把 (b) 减少到 (1) ，所以要数 (b-1leq (a+b)-x) 的数量，也就是查询 (xleq a+1) 的数量，换言之这个数据结构应该存 (a+1) ，然后支持查询 (x) 的名次。
那么这种数据结构就是各种名次树，选择最快的“名次树”——权值线段树，然后改一改接口就可以做。
struct SegmentTree {
#define ls (o<<1)
#define rs (o<<1|1)
static const int MAXN = 400000;
int cnt[(MAXN << 2) + 5];
void PushUp(int o) {
cnt[o] = cnt[ls] + cnt[rs];
}
void Build(int o, int l, int r) {
if(l == r)
cnt[o] = 0;
else {
int m = l + r >> 1;
Build(ls, l, m);
Build(rs, m + 1, r);
PushUp(o);
}
}
//修改值为p的元素的个数，增量为v，且不能为负
void Update(int o, int l, int r, int p, int v) {
if(l == r) {
cnt[o] += v;
if(cnt[o] < 0)
cnt[o] = 0;
return;
} else {
int m = l + r >> 1;
if(p <= m)
Update(ls, l, m, p, v);
if(p >= m + 1)
Update(rs, m + 1, r, p, v);
PushUp(o);
}
}
//查询<=x的元素的个数
int GetRank(int o, int l, int r, int x) {
if(r <= x) {
return cnt[o];
} else {
int m = l + r >> 1;
if(x <= m)
return GetRank(ls, l, m, x);
else
return cnt[ls] + GetRank(rs, m + 1, r, x);
}
}
//查询最小的x，使得<=x的元素个数>=rk（第rk小）
int GetValue(int o, int l, int r, int rk) {
if(l == r) {
return l;
} else {
int m = l + r >> 1;
if(cnt[ls] >= rk)
return GetValue(ls, l, m, rk);
else
return GetValue(rs, m + 1, r, rk - cnt[ls]);
}
}
#undef ls
#undef rs
} set1, set2;
int n, k;
int a[200005];
pii p[200005];
void TestCase() {
scanf("%d%d", &n, &k);
for(int i = 1; i <= n; ++i)
scanf("%d", &a[i]);
for(int i = 1; i <= n / 2; ++i)
p[i] = make_pair(a[i] + a[n - i + 1], min(a[i], a[n - i + 1]));
sort(p + 1, p + 1 + n / 2);
set1.Build(1, 1, 2 * k);
set2.Build(1, 1, 2 * k);
int cntset1 = 0;
int cntset2 = 0;
for(int i = 1; i <= n / 2; ++i) {
set2.Update(1, 1, 2 * k, p[i].second, 1);
++cntset2;
}
int j = 1;
int ans = 2 * n;
for(int x = 2; x <= 2 * k; ++x) {
int l = j, r = j - 1;
while(r + 1 <= n / 2 && p[r + 1].first == x)
++r;
j = r + 1;
for(int i = l; i <= r; ++i) {
set2.Update(1, 1, 2 * k, p[i].second, -1);
--cntset2;
}
int tmp1 = set1.GetRank(1, 1, 2 * k, x - 1);
tmp1 = (cntset1 - tmp1) + tmp1 * 2;
int tmp2 = set2.GetRank(1, 1, 2 * k, x - 1);
tmp2 = tmp2 + (cntset2 - tmp2) * 2;
ans = min(ans, tmp1 + tmp2);
for(int i = l; i <= r; ++i) {
set1.Update(1, 1, 2 * k, p[i].first - p[i].second + k, 1);
++cntset1;
}
}
printf("%d
", ans);
return;
}
但是仔细一想，查询的 (x) 也满足单调性，这样甚至可以不需要任何数据结构。
E - Weights Distributing
题意：给一个 (n) 个点 (m) 条边的无向图，给一个 (m) 个数字的权重列表，给每条边分配合适的权重，使得 (a) 点到 (b) 点然后再从 (b) 点到 (c) 点的最短路权重之和最小。
题解：感觉应该是加入一个 (x) 点，分解成一条链： (a ightarrow x ightarrow b ightarrow x ightarrow c) ，然后把最短的边都分配给 ((x,b)) 之间的路径，再把次短的边分配给 ((x,a)) 之间的路径和 ((x,c)) 之间的路径，容易知道这里的“路径”就应该是原图中权重为1时的最短路。那么枚举 (x) 求出最短路就是答案，枚举的时候考虑反过来从 (a,b,c) 开始的最短路即可。
const int MAXN = 200000;
int n, m, a, b, c;
int p[MAXN + 5];
ll prefixp[MAXN + 5];
int disA[MAXN + 5];
int disB[MAXN + 5];
int disC[MAXN + 5];
vector<int> G[MAXN + 5];
bool vis[MAXN + 5];
queue<int>Q;
void BFS(int s, int *dis) {
while(!Q.empty())
Q.pop();
memset(vis, 0, sizeof(vis[0]) * (n + 1));
memset(dis, INF, sizeof(dis[0]) * (n + 1));
dis[s] = 0;
vis[s] = 1;
Q.push(s);
while(!Q.empty()) {
int u = Q.front();
Q.pop();
for(auto &v : G[u]) {
if(!vis[v]) {
dis[v] = dis[u] + 1;
vis[v] = 1;
Q.push(v);
}
}
}
return;
}
void TestCase() {
scanf("%d%d%d%d%d", &n, &m, &a, &b, &c);
for(int i = 1; i <= m; ++i)
scanf("%d", &p[i]);
sort(p + 1, p + 1 + m);
for(int i = 1; i <= m; ++i)
prefixp[i] = prefixp[i - 1] + 1ll * p[i];
for(int i = 1; i <= m; ++i) {
int u, v;
scanf("%d%d", &u, &v);
G[u].push_back(v);
G[v].push_back(u);
}
BFS(a, disA);
BFS(b, disB);
BFS(c, disC);
ll ans = LINF;
for(int i = 1; i <= n; ++i) {
ll tmp = LINF;
if(disA[i] + disB[i] + disC[i] <= m)
tmp = prefixp[disB[i]] + prefixp[disA[i] + disB[i] + disC[i]];
ans = min(ans, tmp);
}
printf("%lld
", ans);
for(int i = 1; i <= n; ++i)
G[i].clear();
return;
}
需要注意的是，若距离总和超过边的总数，则说明枚举的路径中有反复被走的边，那么这种情况会被枚举到正确的中转点 (x) 的情况覆盖掉。
*F - Restore the Permutation by Sorted Segments
看了一下题解，有点懂大概的意思了。
题意：给 (n-1) 段序列，这些序列的右端点分别是 ([2,n]) ，长度至少为 (2) ，他们是从原序列中取出然后sort得到的，顺序是随便给的。复原其中一种复合要求的原序列。
题解：只出现一次的那个数字，要么只有1个要么有2个。若只有1个，则只能出现在 (n) 位置。否则要把两种分别试一下。