Codeforces Round 894 (Div. 3)-526互联

A. \(n\) 个长为 \(m\) 的字符串，判断存在 \(i, j, k, l\) 有 \(1 \leq i < j < k < l \leq m\) ，满足这四列的字符串分别有 \(v, i, k, a\) 。

小细节的题。时间复杂度 \(O(n^2)\) 。

view

#include <bits/stdc++.h>

#define REP(i, A, N) for (int i = (int)A; i <= (int)N; i++)
#define PER(i, N, A) for (int i = (int)N; i >= (int)A; --i)

typedef long long ll;

const int MAXN = 200005;
char s[25][25];
int n, m;
bool check() {
    std::string v = "vika?"; // 逐个查找存储txt串标记指针
    int l = 0;
    REP(j, 1, m) {
        REP(i, 1, n) {
            if (s[i][j] == v[l]) {
                l++;
                break; // 查找到及时 break
            }
        }
    }
    return l == 4;
}

void solve() {
    std::cin >> n >> m;
    REP (i, 1, n) REP(j, 1, m) std::cin >> a[i][j];
    std::cout << (check() ? "YES" : "NO") << '\n';
} 
signed main() {
	std::ios::sync_with_stdio(false);
	std::cin.tie(0);
    #ifndef ONLINE_JUDGE
    freopen("IO/in", "r", stdin); freopen("IO/out", "w", stdout);
	#endif 

	int _ = 1; std::cin >> _;
    while (_--) { solve(); }
	return 0;
}

B. 有一个长为 \(m\) 的数组 \(a\) ，现在生成另一个数组 \(b\) 。已知：

\(b_1 = a_1\)
若 \(a_{i - 1} \leq a_{i}\) ，\(b\) \(push\) 一个 \(a_i\) 。

对于某个 \(b\) ，考虑一个可能的 \(a\)

\(a_1 = b_1\)
注意到非降子串，注意到数形结合。
观察到：一段长为 \(n\) 的非降 \(a\) 子串可生成由一段长为 \(n - 1\) 的非降 \(b\) 子串。
注意在同一平面对比两个数组的数形结合。
（待补图）
若 \(b_i \geq b_{i - 1}\) ，\(a\) \(push\) 一次 \(b_i\) ，否则 \(a\) \(push\) 两次 \(b_i\) 。

时间复杂度 \(O(n)\) 。

view

#include <bits/stdc++.h>

#define REP(i, A, N) for (int i = (int)A; i <= (int)N; i++)
#define PER(i, N, A) for (int i = (int)N; i >= (int)A; --i)

typedef long long ll;
typedef double db;
const double EPS=1e-8;
const int ZSX=998244353;

const int MAXN = 200005;

void solve() {
    int n;
    std::cin >> n;
    std::vector<int> b(n+1);
    REP(i, 1, n) std::cin >> b[i];
    std::vector<int> a(1, b[1]);
    REP(i, 2, n) {
        if (b[i] >= b[i - 1]) a.push_back(b[i]);
        else a.push_back(b[i]), a.push_back(b[i]);
    }
    int m = (int)a.size();
    std::cout << m << '\n';
    REP(i, 0, m - 1) {
        std::cout << a[i] << " \n"[i == m - 1];
    }
}
signed main() {
	std::cin.tie(0); std::cout.tie(0);
    std::ios::sync_with_stdio(false);
    #ifndef ONLINE_JUDGE
    freopen("IO/in", "r", stdin); freopen("IO/out", "w", stdout);
	#endif 

	int _ = 1;
    std::cin >> _;
    while (_--) {
        solve();
    }

	return 0;
}

C. 有一个长为 \(n\) 的数组 \(a\) 。\(a_1, a_2, \cdots, a_n\) 在 \(x\) 轴上作为高度生成图形，满足 \(a_i \geq a_{i - 1}\) 。这个图形经过 \(y = x\) 对称后是否不变。

注意到数形结合。不难发现仅 \(a_i \geq a_{i - 1}\) 的是图形经过 \(y = x\) 对称的必要条件。此题给出了条件降低难度。
在微积分或圆锥曲线以外的领域，一个图形无法通过一个多项式表示。此时需要从更 \(naive\) 的角度考虑图形对称问题。
考虑计算 \(y\) 轴上的贡献 \(b\) ，每次 \([1, a_i]\) 区间加 \(1\) 的贡献，这是一个经典的差分问题。扫描 \(y\) 轴，\(b = a\) 时图形关于 \(y = x\) 对称。数组越界一定不对称，可以特判避免。

时间复杂度 \(O(n)\) 。

view

#include <bits/stdc++.h>

#define REP(i, A, N) for (int i = (int)A; i <= (int)N; i++)
#define PER(i, N, A) for (int i = (int)N; i >= (int)A; --i)


typedef long long ll;
typedef unsigned long long ull;
typedef double db;
const double EPS=1e-8;

void solve() {
    int n;
    std::cin >> n;
    std::vector<ll> a(n+1), b(n + 2);
    bool ok = true;
    REP(i, 1, n) {
        std::cin >> a[i];
        if (a[i] > n)
            ok = false;
        else {
            b[1] += 1;
            b[ a[i] + 1 ] -= 1;
        }
    }
    REP(i, 1, n) b[i] += b[ i - 1 ];
    REP(i, 1, n) ok &= (b[i] == a[i]);
    std::cout << (ok ? "YES" : "NO") << '\n';
}

signed main() {
	std::cin.tie(0);
    std::ios::sync_with_stdio(false);
    #ifndef ONLINE_JUDGE
    freopen("IO/in", "r", stdin); freopen("IO/out", "w", stdout);
	#endif 
	int _ = 1; std::cin >> _;
    while (_--) { solve(); }

	return 0;
}

D. 一个大小为 \(n\) 的多重集合中任选两个数，有 \(m\) 种组合方案。给出 \(m\) ，求多重集合大小最小。

多重集合中每个元素都不一样时，可以获得最多方案数。于是可以二分到 \(x\) 满足 \(f(x+1) > m, f(x) \leq m\) 。
任意加入 \(m - f(x)\) 个各自不同且集合内已有的元素后，有 \(m\) 种组合方案。
- 证明：
  - 任意加入一个集合外的元素， \(f(x + 1) > m\) ，不合法。
  - 第一次任意加入一个集合内的元素 \(d\) ，方案数加一，即 \((d, d)\) 。重复加入不会更优
答案为 \(x + m - f(x)\) 。

时间复杂度 \(O(\log M)\) 。

view

#include <bits/stdc++.h>

#define REP(i, A, N) for (int i = (int)A; i <= (int)N; i++)
#define PER(i, N, A) for (int i = (int)N; i >= (int)A; --i)

typedef long long ll;
int n, m;
void solve() {
    ll n; std::cin >> n;
    ll L = 2, R = 2E9;
    while ( R - L > 1 ) {
        ll M = (R + L) >> 1;
        ll cost = M * (M - 1) / 2;
        if (cost > n) R = M;
        else L = M;
    }
    // L
    std::cout << L + ( n - L * (L - 1) / 2 ) << '\n';
}
signed main() {
	std::cin.tie(0);
    std::ios::sync_with_stdio(false);
    #ifndef ONLINE_JUDGE
    freopen("IO/in", "r", stdin); freopen("IO/out", "w", stdout);
	#endif 

	int _ = 1; std::cin >> _;
    while (_--) { solve(); }

	return 0;
}

E. 给一个长为 \(n\) 的数组 \(a\) 。选择第 \(i\) 个可以获得 \(a_i - d \cdot cnt\) 的贡献， \(cnt\) 为与上一次选择的位置的距离，第一个位置的 \(cnt\) 为 \(1\) 。如何选出至多 \(m\) 个，使得所得贡献最大。

转化： \(cnt\) 必须由一化二（经典拆分才能观察到性质），转化为 \(i_k - i_{k - 1}\) ，后可求解。当前选择第 \(k\) 次。
于是

\[\begin{aligned} cost &= (a_{i_1} - d(i_{1} - i_{0})) + (a_{i_2} - d(i_{2} - i_{1})) + \cdots + (a_{i_k} - d(i_{k} - i_{k-1})) \\ &= \sum_{j = 1}^{k} a_{i_j} - d \cdot i_k \end{aligned} \]

发现限制住 \(i_k\) 后 \(cost\) 具有单调性，故枚举 \(i_k\)。
维护前 \(k\) 个最大值的经典做法是小根堆维护。同时可以维护其和。
注意到此处是需要维护前不超过 \(k\) 个最大值，特殊在于
- 做法与维护前 \(k\) 个最值相差不大
- 不需要等于 \(k\) 时即可更新答案
- 如果可能更优，则允许不选。不选负数 \(\sum_{j = 1}^{k} a_{i_j}\) 更大，于是更优。

时间复杂度 \(O(n \log n)\) 。

view

#include <bits/stdc++.h>

#define REP(i, A, N) for (int i = (int)A; i <= (int)N; i++)
#define PER(i, N, A) for (int i = (int)N; i >= (int)A; --i)

typedef long long ll;

void solve() {
    int n, m, d;
    std::cin >> n >> m >> d;
    std::vector<int> a(n+1);
    std::priority_queue<int, std::vector<int>, std::greater<int> > q;
    ll ans = 0, sum = 0;
    REP(i, 1, n) {
        std::cin >> a[i];
        if (a[i] > 0) {
            q.push(a[i]);
            sum += a[i];
        }
        if (q.size() > m) {
            sum -= q.top();
            q.pop();
        }
        ans = std::max(ans, sum - 1LL * d * i);
    }
    std::cout << ans << '\n';
}
signed main() {
	std::cin.tie(0);
    std::ios::sync_with_stdio(false);
    #ifndef ONLINE_JUDGE
    freopen("IO/in", "r", stdin); freopen("IO/out", "w", stdout);
	#endif 

	int _ = 1; std::cin >> _;
    while (_--) { solve(); }

	return 0;
}

F. 有 \(n\) 个物品，权重分别为 \(s_1, s_2, \cdots, s_3\) 。每秒可以积累一个强度为 \(w\) 的 \(W\) 类魔法和一个强度为 \(f\) 的 \(F\) 类魔法。在某一秒可以一次性释放多个 \(W\) 类或 \(F\) 类魔法直接消灭多个物品，当花费该类魔法的强度之和大于这些物品的权重和。问最短需要多少时间消灭掉所有物品。

显然地让一部分重量为 \(v\) 的物品用 \(F\) 类魔法消灭，另一部分重量为 \(sum - v\) 的物品用 \(W\) 类魔法消灭。此时花费时间为 \(cost = max(\lceil \frac{v}{f} \rceil, \lceil \frac{sum - v}{w} \rceil)\) 。枚举 \(v\) 即可找到最小 \(cost\) 。
一堆物品的总重量确定，某个 \(v\) 是否是其中 \(n\) 个物品的和。当重量和不大，物品个数较多时，是一个时间复杂度 \(O(nV)\) 的 \(01\) 背包问题。

view

#include <bits/stdc++.h>

typedef long long ll;

void solve() {
	int w, f; std::cin >> w >> f;
	int n; std::cin >> n;
	std::vector<int> a(n+1);
	int sum = 0;
	for (int i = 1; i <= n; i++) {
		std::cin >> a[i];
		sum += a[i];	
	}
	std::vector<int> dp(sum+1);
	dp[0] = 1;
	for (int i = 1; i <= n; i++) {
		for (int j = sum; j >= a[i]; --j) {
			dp[j] |= dp[j - a[i]];
		}
	}
	int cost = 1 << 30;
	for (int i = sum; ~i; --i) if (dp[i]) {
		cost = std::min(cost, std::max((i + w - 1) / w, (sum - i + f - 1) / f));
	}
	std::cout << cost << '\n';
}

int main() {
	int _ = 1; std::cin >> _;
	while (_--) { solve(); }
}

G. 本场中质量最高且高得离谱的题。

一个数组 \(a\) 按以下程序操作

按非降排序并去重
当数组中只有一个元素时输出，终止程序
让数组中第 \(i\) 个数加上 \(n - i + 1\) ， \(n\) 是现在数组的长度，下标从 \(1\) 开始。
返回步骤 1

现在测试 \(q\) 次已给的数组 \(a\) ，每次测试分两步

将第 \(i\) 个数改为 \(x\) ，即 \(a_i = x\) 。
将 \(a\) 输入程序，输出执行结果。

此题的主要考点：去重有序数组的重要性质。

一个去重有序数组，加上 \({n, n - 1, \cdots, 1}\) 后。
1. 每个相邻数字的差分会减 \(1\) ，差分为 \(0\) 会被去重。设一开始最大的差分为 \(d\) ，于是总共会迭代 \(d\) 轮。
2. 某个数是被去重后他的数值依然存留。
3. 所有数增大，最大的数恒在第 \(n\) 个。设最大值一开始为 \(v\) ，每次程序迭代，\(a_n\) 恒为 \(++v\) 。
于是程序输出的答案可 \(O(1)\) 求解，为 \(v + d\) 。

此题的第二个考点：数据结构。
新问题，如何创造数据结构。支持单点修改，维护一个数组的最大值和最大差分。
这是两个都能用 \(multiset\) 维护的问题，因为要维护数组而不是下标，所以避免去重。

注意单点修改对数组差分的影响：

修改可以转化为删除、插入。
删除或插入一个元素，对一个数组的差分有会影响三次。

注意 \(multise\) 的 \(erase\) ：

\(erase(x)\) 会把重复 \(x\) 的迭代器都删掉
\(erase(find(x))\) 一个元素的迭代器只会删除一个 \(x\) 的迭代器。

注意 \(STL\) \(a\) 中判断一个元素的迭代器 \(it\) 是否在首位或末位：

若 \(it\) 在首位，则 \(it == a.begin()\) 。
若 \(it\) 在末位，则 \(next(it) == a.end()\) 。

接下来是默认已经初始化后的操作。

单点修改 \(a_i = x\)，维护最大值：
\(multiset\ c1\) 。
\(del(a_i)\) ，在 \(c1\) 中 \(find\) 到一个 \(a_i\) 的迭代器，将这个迭代器删除。
\(add(x)\) ，对 \(c1\) \(insert\) 一个 \(x\) 。
单点修改 \(a_i = x\) ，维护最大差分：（定义 \(d_i = a_{i + 1} - a_{i}\) ，数据结构中通常只维护 \(d_2\) 到 \(d_n\) 共 \(n - 1\) 个差分，因为 \(d_1\) 和 \(d_n\) 不代表元素相对关系，除非是数学类算贡献的题）
\(multiset\ c2\) ，且需借助到 \(c1\) 。

\(multiset\) 内的具体操作。

\(del(a_i)\) 。
1. 在 \(c1\) 中 \(find\) 到 \(a_i\) 的迭代器 \(t\) 。
2. 若 \(t\) 不在 \(c1\) 首位，\(c2\) \(erase(c2.find(*t - *prev(it)))\) 。
3. 若 \(t\) 不在 \(c1\) 末位，\(c2\) \(erase(c2.find(*next(t) - *t))\) 。
4. 若 \(t\) 既不在 \(c1\) 首位也不在 \(c1\) 末位， \(c2\) \(insert(*next(t) - *prev(t))\) 。
5. 在 \(c1\) 中 \(erase\) 迭代器 \(t\) 。
\(add(x)\) 。
1. 在 \(c1\) 中 \(insert\) 元素 \(x\) ，并返回迭代器 \(t\) 。
2. 若 \(t\) 不在 \(c1\) 首位，\(c2\) \(insert(*t - *prev(it))\) 。
3. 若 \(t\) 不在 \(c1\) 末位，\(c2\) \(insert(*next(t) - *t)\) 。
4. 若 \(t\) 既不在 \(c1\) 首位也不在 \(c1\) 末位， \(c2\) \(erase(c2.find(*next(t) - *prev(t)))\) 。

view

#include <bits/stdc++.h>

typedef long long ll;

void solve() {
	int n; std::cin >> n;
	std::vector<int> a(n+1);
	std::multiset<int> c1, c2{0};
	
	auto add = [&](int x) {
		auto t = c1.insert(x);
		if (t != c1.begin()) {
			c2.insert( *t - *std::prev(t) );
		}
		if (std::next(t) != c1.end()) {
			c2.insert( *std::next(t) - *t );
		}
		if (t != c1.begin() && std::next(t) != c1.end()) {
			c2.erase( c2.find( *std::next(t) - *std::prev(t) ) );
		}
	};
	
	auto del = [&](int x) {
		auto t = c1.find(x);
		if (t != c1.begin()) {
			c2.erase( c2.find( *t - *std::prev(t) ) );
		}
		if (std::next(t) != c1.end()) {
			c2.erase( c2.find( *std::next(t) - *t ) );
		}
		if (t != c1.begin() && std::next(t) != c1.end()) {
			c2.insert( *std::next(t) - *std::prev(t) );
		}
		c1.erase(t);
	};
	
	for (int i = 1; i <= n; i++) {
		std::cin >> a[i];
		add(a[i]);
	}
	int q; std::cin >> q;
	std::vector<int> ans(q+1);
	for (int i = 1; i <= q; i++) {
		int id, x; std::cin >> id >> x;
		del(a[id]);
		a[id] = x;
		add(x);
		ans[i] = *c1.rbegin() + *c2.rbegin();
	}
	for (int i = 1; i <= q; i++) {
		std::cout << ans[i] << " \n"[i==q];
	}
}

int main() {
	int _ = 1; std::cin >> _;
	while (_--) { solve(); }
}

codeforces round 894 div

codeforces abcdefg round 894

题解codeforces round 894

codeforces round 894

codeforces round 911 div

codeforces round 864 div

codeforces round 887 div

codeforces round 863 div

codeforces round 913 div

codeforces round 915 div