Codeforces Round 894 (Div. 3)

标签：std 894 int REP Codeforces long c2 Div c1

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(); }
}

标签：std,894,int,REP,Codeforces,long,c2,Div,c1
From： https://www.cnblogs.com/zsxuan/p/17658683.html

相关文章

赞助商

阅读排行