Codeforces Round#704 Div2 题解(A,B,C,D,E)

FST ROUND ！!1

A Three swimmers:

直接整除一下向上取整就好了：

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int N = 2e5 + 10;

ll p,a,b,c;

int main() {

	ios::sync_with_stdio(false);

	cin.tie(0),cout.tie(0);

	int times;

	cin >> times;

	while(times--) {

		cin >> p >> a >> b >> c;

		cout << min((p + a - 1) / a * a - p,min((p + b - 1) / b * b - p,(p + c - 1) / c * c - p)) << '\n';

	}

	return 0;

}

B Card Deck:

(本人 CF 打得很少但感觉一般都是这种通过性质条件贪心的题)

保证了原数列是一个排列 $1 \le a_i \le n$，而每一位差异的系数等于 $n$。

所以每次找剩余部分的最大值即可。

本人懒得写数据结构，写了个堆和删除堆（太久没写过在赛场上差点没写出来 /kk）

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int N = 1e5 + 10;

priority_queue<pair<int,int> > p;

priority_queue<pair<int,int> > del;

int a[N];

int b[N],cnt = 0;

int n,m;

int times;

int main() {

	ios::sync_with_stdio(false);

	cin.tie(0),cout.tie(0);

	cin >> times;

	while(times--) {

		cin >> n ;

		for(int i = 1;i <= n;i++) {

			cin >> a[i];

			p.push(make_pair(a[i],i));

		}

		int poi = n;

		cnt = 0;

		while(p.empty() == false) {

			while(p.empty() == false && del.empty() == false && p.top() == del.top()) {

				p.pop(),del.pop();

			}

			if(p.empty()) break;

			int u = p.top().second;

			for(int i = u;i <= poi;i++) {

				b[++cnt] = a[i];

				del.push(make_pair(a[i],i));

			}

			poi = u - 1;

		}

		for(int i = 1;i <= n;i++) {

			cout << b[i] << ' ';

		}

		cout << '\n';

	}

	return 0;

}

C Maximum width:

比较显然的一个贪心，因为每一个 $s$ 中必会存在 $t$ 所以对于 $t$ 每一位可以得到一个合法取值的最小/大值（正反扫一遍）。

对于相邻的两个数 $i,i + 1$，以 $i$ 为分界分开，$i$ 及 $i$ 以前的都取最小情况，$i + 1$ 及其以后都取最大情况，便可以保证合法性。

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int N = 2e5 + 10;

int n,m;

char s[N],t[N];

int poi = 0;

int Er[N],La[N];

int main() {

	ios::sync_with_stdio(false);

	cin.tie(0),cout.tie(0);

	cin >> n >> m;

	cin >> (s + 1);

	cin >> (t + 1);

	poi = 1;

	for(int i = 1;i <= n;i++) {

		if(s[i] == t[poi]) {

			Er[poi] = i;

			poi++;

		}

		if(poi > m) break;

	}

	poi = m;

	for(int i = n;i >= 1;i--) {

		if(s[i] == t[poi]) {

			La[poi] = i;

			poi--;

		}

		if(!poi) break;

	}

	int ans = 0;

	for(int i = 1;i < m;i++) {

		ans = max(ans,abs(Er[i] - La[i + 1]));

	}

	cout << ans << '\n';

	return 0;

}

D Genius's Gambit:

魔鬼题，机房仅有一人没有被 $\texttt{FST}$。

注意到类似于这样的一种情况，相减后总是会贡献出 $len$ 长度的 $1$：(以下为两个长度为 $len + 1$ 的字符串)

$\texttt{1111...1100...0000}$

$\texttt{1011...1100...0001}$

所以我们一开始令第一个串类似于这样的结构：

$\texttt{1111...1100...0000}$

这样只需找到这个序列的第 $i$ 位交换到第 $i + k$ 位即可得到第二个串。(满足 $a[i] = 1,a[i + k] = 0$)

但是此题边界条件很多：

首先考虑构造的时候条件：满足 $k \ge a + b - 1$ 时无解。

当 $a = 0$ 时，当且仅当 $k = 0$ 有解。

当 $b = 1$ 时，当且仅当 $k = 0$ 有解。

但还有一个特例 :

$a = 0,b = 1,k = 0.$

这一个特例并不满足 $k \le a + b - 2$ 但确实有解。

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

char ans[300000];

int main() {

	ios::sync_with_stdio(false);

	cin.tie(0),cout.tie(0);

	int a,b,k;

	cin >> a >> b >> k;

	if(!a) {

		if(!k) {

			cout << "Yes" << '\n';

			for(int i = 1;i <= b;i++) {

				cout << "1" ;

			}

			cout << '\n';

			for(int i = 1;i <= b;i++) {

				cout << "1" ;

			}

		} else {

			cout << "No" << '\n';

		}

		return 0;

	}

	if(b == 1) {

		if(!k) {

			cout << "Yes" << '\n';

			cout << '1' ;

			for(int i = 1;i <= a + b - 1;i++) {

				cout << '0';

			}

			cout << '\n';cout << '1' ;

			for(int i = 1;i <= a + b - 1;i++) {

				cout << '0';

			}

			cout << '\n';

		} else {

			cout << "No";

			return 0;

		}

		return 0;

	}

	if(k >= a + b - 1) {

		cout << "No" << '\n';

		return 0;

	}

	cout << "Yes" << '\n';

	for(int i = 1;i <= b;i++) ans[i] = '1';

	for(int i = b + 1;i <= a + b;i++) ans[i] = '0';

	for(int i = 1;i <= a + b;i++) cout << ans[i];cout << '\n';

	for(int i = 2;i <= a + b;i++) {

		if(ans[i] == '1' && ans[i + k] == '0') {

			swap(ans[i],ans[i + k]);

			break;

		}

	}

	for(int i = 1;i <= a + b;i++) {

		cout << ans[i];

	}

	return 0;

}

E Almost Fault-Tolerant Database:

因为要构造一串序列要满足与任意序列的不同处不超过 $2$ ，不如就直接取第一个序列然后加之修改。

考虑第一个序列和其余序列可能存在的情况：

和一个串的不同处 $>4$ ，这时无论如何都是无解。
和每一个串的不同处 $ \le 2$ ，这时这一个序列就可以是答案。
存在一些序列不同处 $=3,4$ ，考虑如何处理使不同处减小到 $2$ 以下。

首先不难发现，如果只有一对不同串不同处大于 $2$，我们可以去枚举造成不同的位置，对其进行更改，使现在不同处 $\le 2$，然后去检查修改后的串是否满足整个序列不同处 $\le 2$。

如果此时只有三个串不同处大于 $2$，我们可以任意选择一个串进行修改，因为每次修改都是枚举完了所有不同处的情况的，如果此时修改后检查不合法，那么枚举另一个串修改了检查时也会不合法。

所以一开始选取一个与第一个串不同处最多的串，然后枚举修改的位置即可。

注意到有可能修改会修改成为其余序列的值，所以将其中一个设定为 $-1$ 处理，表示这个位置可以被修改。

最终实现的复杂度为 $O(nm)$ ,常数不大。

CODE

巴特西