目录
写在前面
比赛地址：https://codeforces.com/contest/2026。
因为太困了决定睡大觉，于是赛时 unrated register 只写了 DE。
然而十一点半上床还是失眠到一点半睡的太搞了呃呃
A 签到
B 暴力
限定了只能操作白色格子，显然对于 \(n\) 为偶数只能直接操作，\(n\) 为奇数一定会多操作一个格子。
一个显然的结论是，对于 \(n\) 为奇数的情况，多操作的格子的位置一定为某个 \(a_i\) 前驱或后继（即 \(a_i + 1\) 或 \(a_i - 1\)）。
这等价于删去某个位置（即与多修改的格子匹配的位置）之后，求前面所有位置的差分，以及后面所有位置的差分的最大值。要是不注意数据范围的话可能就会去写这个 \(O(n)\) 的东西了。
然而 \(O(n^2)\) 可过，于是直接枚举修改位置即可。
//
/*
By:Luckyblock
*/
#include <bits/stdc++.h>
#define LL long long
const int kN = 2010;
//=============================================================
int n;
LL a[kN];
//=============================================================
//=============================================================
int main() {
// freopen("1.txt", "r", stdin);
std::ios::sync_with_stdio(0), std::cin.tie(0);
int T; std::cin >> T;
while (T --) {
std::cin >> n;
LL ans = 0;
for (int i = 1; i <= n; ++ i) std::cin >> a[i];
if (n % 2 == 0) {
for (int i = 2; i <= n; i += 2) ans = std::max(ans, a[i] - a[i - 1]);
} else {
ans = a[n];
std::set<LL> s;
for (int i = 1; i <= n; ++ i) s.insert(a[i] - 1), s.insert(a[i] + 1);
for (auto p: s) {
std::vector<LL> b;
for (int i = 1; i <= n; ++ i) if (a[i] < p) b.push_back(a[i]);
b.push_back(p);
for (int i = 1; i <= n; ++ i) if (a[i] > p) b.push_back(a[i]);
LL k = 0;
for (int i = 1; i <= n; i += 2) k = std::max(k, b[i] - b[i - 1]);
ans = std::min(ans, k);
}
}
std::cout << ans << "\n";
}
return 0;
}
C 反悔贪心
D 枚举，分块，推式子
经典题，写了一个类似分块的做法。
考虑按照 \(s(l, r)\) 的左端点 \(l\) 对构造的数列 \(b\) 分块，每次询问分别处理左右的散块和中间的整块。
对于中间的整块考虑预处理，记：\(\operatorname{sum}_i\) 表示 \(a\) 的前缀和，\(\operatorname{sum}'_i\) 表示 \(a\) 的二维前缀和，记 \(S_{i} = \sum_{i\le j\le n} s(i, j)\) 表示整块的和。\(S_1\) 即 \(\operatorname{sum}'_n\)，且显然可以递推：
\[S_i = S_{i - 1} - (n - i + 2)\times a_{i - 1} \]再对 \(S\) 做个前缀和即可快速询问整块的和。
对于左右散块推下式子，记当前位于块 \(\operatorname{id}\)，且 \(l, r\) 分别为该块的第 \(l', r'\) 个元素，则有：
\[\sum_{l'\le j\le r'} s(\operatorname{id}, j) = \operatorname{sum}'_{\operatorname{id} + r' - 1} - \operatorname{sum}'_{\operatorname{id} + l' - 2} - (r - l + 1)\times \operatorname{sum}_{\operatorname{id} - 1} \]每次找到端点所在块使用二分，总时间复杂度 \(O(n + q\log n)\) 级别。
//
/*
By:Luckyblock
*/
#include <bits/stdc++.h>
#define LL long long
const int kN = 3e5 + 10;
//=============================================================
int n, a[kN];
LL L[kN], R[kN], sum[kN], sumsum[kN];
LL S[kN], sumS[kN];
//=============================================================
int get(LL pos_) {
int ret = 1;
for (int l = 1, r = n; l <= r; ) {
int mid = (l + r) >> 1;
if (pos_ >= L[mid]) {
ret = mid;
l = mid + 1;
} else {
r = mid - 1;
}
}
return ret;
}
LL query(LL l_, LL r_) {
int bl = get(l_), br = get(r_);
LL ret = 0;
if (bl == br) {
int pl = l_ - L[bl] + 1, pr = r_ - L[bl] + 1, len = r_ - l_ + 1;
ret = sumsum[bl + pr - 1] - sumsum[bl + pl - 1 - 1] - len * sum[bl - 1];
} else {
ret = sumS[br - 1] - sumS[bl];
ret += query(l_, R[bl]) + query(L[br], r_);
}
return ret;
}
//=============================================================
int main() {
// freopen("1.txt", "r", stdin);
std::ios::sync_with_stdio(0), std::cin.tie(0);
std::cin >> n;
for (int i = 1; i <= n; ++ i) std::cin >> a[i];
for (int i = 1; i <= n; ++ i) sum[i] = sum[i - 1] + a[i];
for (int i = 1; i <= n + 1; ++ i) L[i] = R[i - 1] + 1, R[i] = R[i - 1] + (n - i + 1);
for (int i = 1; i <= n; ++ i) sumsum[i] = sumsum[i - 1] + sum[i];
S[1] = sumsum[n];
for (int i = 2; i <= n; ++ i) S[i] = S[i - 1] - (n - i + 2) * a[i - 1];
for (int i = 1; i <= n; ++ i) sumS[i] = sumS[i - 1] + S[i];
int q; std::cin >> q;
while (q --) {
LL l, r; std::cin >> l >> r;
std::cout << query(l, r) << "\n";
}
return 0;
}
E 网络流，最大权闭合子图
一眼最大权闭合子图板子，具体做法和证明见这题：P2762 太空飞行计划问题。
看不出来的鉴定为没写完网络流 24 题。
最搞的是调了二十分钟发现自己板子写错了哈哈。
//知识点：网络最大流，Dinic
/*
By:Luckyblock
*/
#include <bits/stdc++.h>
#define LL long long
const int kN = 1e5 + 10;
const int kM = 2e6 + 10;
const LL kInf = 1e18 + 2077;
//=============================================================
int n, m, k, S, T;
int nodenum, maxnodenum, edgenum = 1, v[kM], ne[kM], head[kN];
int cur[kN], dep[kN];
LL w[kM];
//=============================================================
void addedge(int u_, int v_, LL w_) {
v[++ edgenum] = v_;
w[edgenum] = w_;
ne[edgenum] = head[u_];
head[u_] = edgenum;
v[++ edgenum] = u_;
w[edgenum] = 0;
ne[edgenum] = head[v_];
head[v_] = edgenum;
}
void init() {
std::cin >> n;
edgenum = 1;
nodenum = n + 61;
maxnodenum = n + 100;
S = ++ nodenum, T = ++ nodenum;
for (int i = 1; i <= maxnodenum; ++ i) {
head[i] = 0;
}
for (int i = 0; i < 60; ++ i) addedge(n + i + 1, T, 1);
for (int i = 1; i <= n; ++ i) {
LL a; std::cin >> a;
addedge(S, i, 1);
for (LL j = 0; j < 60; ++ j) {
if (a >> j & 1ll) addedge(i, n + j + 1, kInf);
}
}
}
bool bfs() {
std::queue <int> q;
memset(dep, 0, (nodenum + 1) * sizeof (int));
dep[S] = 1; //注意初始化
q.push(S);
while (!q.empty()) {
int u_ = q.front(); q.pop();
for (int i = head[u_]; i > 1; i = ne[i]) {
int v_ = v[i];
LL w_ = w[i];
if (w_ > 0 && !dep[v_]) {
dep[v_] = dep[u_] + 1;
q.push(v_);
}
}
}
return dep[T];
}
LL dfs1(int u_, LL into_) {
if (u_ == T) return into_;
LL ret = 0;
for (int i = cur[u_]; i > 1 && into_; i = ne[i]) {
int v_ = v[i];
LL w_ = w[i];
if (w_ && dep[v_] == dep[u_] + 1) {
LL dist = dfs1(v_, std::min(into_, w_));
if (!dist) dep[v_] = kN;
into_ -= dist;
ret += dist;
w[i] -= dist, w[i ^ 1] += dist;
if (!into_) return ret;
}
}
if (!ret) dep[u_] = 0;
return ret;
}
LL dinic() {
LL ret = 0;
while (bfs()) {
memcpy(cur, head, (nodenum + 1) * sizeof (int));
ret += dfs1(S, kInf);
}
return ret;
}
//=============================================================
int main() {
// freopen("1.txt", "r", stdin);
std::ios::sync_with_stdio(0), std::cin.tie(0);
int T; std::cin >> T;
while (T --) {
init();
std::cout << n - dinic() << "\n";
}
return 0;
}
F
写在最后
zzz。
败犬女主真好看。
标签：std,Educational,Rated,int,LL,Codeforces,ret,kN,dep From： https://www.cnblogs.com/luckyblock/p/18512564