Codeforces Round #827 (Div. 4) A - G

A.Sum

void solve() {
    int a[3] = {};
    cin >> a[0] >> a[1] >> a[2];
    sort(a, a + 3);
    if (a[2] == a[0] + a[1]) cout << "YES\n";
    else cout << "NO\n";
}

B.Increasing

判断是否有一个数出现了两次。

void solve() {
    map<int, int> mp;
    int n; cin >> n;
    bool ok = true;
    while (n --) {
    	int x; cin >> x;
    	if (mp[x] == 1) {
    		ok = false;
    	}
    	mp[x] = 1;
    }
    cout << (ok ? "YES\n" : "NO\n");
}

C.Stripes

如果有一行全部为R，则最后涂色的是R；
如果有一列全部为B，则最后涂色的是B。

void solve() {
    char g[10][10];
    for (int i = 0;i < 8;i++) cin >> g[i];

    for (int i = 0;i < 8;i++) {
    	bool ok = true;
    	for (int j = 0;j < 8;j++) {
    		if (g[i][j] != 'R') ok = false;
    	}
    	if (ok) {
    		cout << g[i][0] << endl;
    		return;
    	}
    	ok = true;
    	for (int j = 0;j < 8;j++) {
    		if (g[j][i] != 'B') ok = false;
    	}
    	if (ok) {
    		cout << g[0][i] << endl;
    		return;
    	}
    }
}

D.Coprime

出现过的不同的数最多有一千个，记录每个数出现的最大的位置。
将出现过的数和这个数出现的最大的位置丢进数组，暴力判断即可。

void solve() {
    int n; cin >> n;
    map<int, int> mp;
    for (int i = 1;i <= n;i++) {
    	int x; cin >> x;
    	mp[x] = max(mp[x], i);
    }

    vector<pair<int, int>> a;
    for (auto [k, v] : mp) {
        a.push_back({k, v});
    }
    int ans = -1;
    for (int i = 0;i < sz(a);i++) {
    	for (int j = 0;j < sz(a);j++) {
    		if (gcd(a[i].first, a[j].first) == 1) ans = max(ans, a[i].second + a[j].second);
    	}
    }
    cout << ans << endl;
}

E.Scuza

预处理前缀最大值和前缀和。
对于每次询问，在前缀最大值数组中，二分找到\(x\)的\(upper\ bound\)，能达到的高度为\(pre[upper\ bound - 1]\)。

void solve() {
    int n, k; cin >> n >> k;
    vector<ll> a(n + 1), mx(n + 1), pre(n + 1);
    for (int i = 1;i <= n;i++) {
    	cin >> a[i];
    	mx[i] = max(mx[i - 1], a[i]);
    	pre[i] = a[i] + pre[i - 1];
    }

    while (k --) {
    	int x; cin >> x;
    	int l = 1, r = n;
        if (x == 0) r = 0;
    	while (l < r) {
    		int mid = (l + r) >> 1;
    		if (mx[mid] > x) r = mid;
    		else l = mid + 1;
    	}
        if (mx[r] > x) r --;
    	cout << pre[r] << ' ';
    }
    cout << endl;
}

F.Smaller

可以知道\(a\)一定出现在字符串\(S\)和\(T\)中。
由于我们可以任意重排字符串\(S\)和\(T\)，如果有其他的字母出现在\(T\)中，当\(T\)第一个字符不为\(a\)，而\(S\)第一个字符为\(a\)时，使得\(S<T\)；
如果没有其他的字母出现在\(T\)中：
1.S中仅有字符\(a\)，则当\(lenth(S) < lenth(T)\) 时满足\(S < T\)。
2.S中含有其他字符，则一定有\(S > T\)。

void solve() {
    int n; cin >> n;
    vector<ll> cnt1(30), cnt2(30);
    cnt1[0] = cnt2[0] = 1;
    for (int i = 0;i < n;i++) {
    	int d, k; string x;
    	vector<ll> cnt(30);
    	cin >> d >> k >> x;
    	for (auto c : x) cnt[c - 'a'] += k;
    	if (d == 1) {
    		for (int j = 0;j < 26;j++) cnt1[j] += cnt[j];
    	}
    	else {
    		for (int j = 0;j < 26;j++) cnt2[j] += cnt[j];
    	}

    	bool ok = false;
    	bool res1 = false, res2 = false;
    	for (int j = 25;j > 0;j--) {
    		if (cnt2[j] > 0) res2 = true;
    		if (cnt1[j] > 0) res1 = true;
    	}
    	if (res2) ok = true;
    	else if (!res1 && cnt1[0] < cnt2[0]) ok = true;
    	cout << (ok ? "YES\n" : "NO\n");
    }
}

G.Orray

要使得前缀\(or\)和字典序最大，第一个数一定为最大的数。
\(int\)类型的数二进制位占32bit，因此\(or\)前缀和最多增大30次左右，所以我们每次暴力找到使\(or\)前缀和增量最大的数即可。

void solve() {
    int n; cin >> n;
    vector<int> a(n), vis(n);
    for (int i = 0;i < n;i++) cin >> a[i];
    sort(a.rbegin(), a.rend());
	int pre = a[0]; vis[0] = 1;

	vector<int> res;
	res.push_back(a[0]);
	while (true) {
		int pos = -1, last = pre;
		for (int i = 0;i < n;i++) {
			if (vis[i]) continue;
			if ((pre | a[i]) > last) {
				last =  pre | a[i];
				pos = i;
			}
		}
		if (pos != -1) {
			res.push_back(a[pos]);
			vis[pos] = 1;
			pre |= a[pos];
		}
		else break;
	}

	for (auto v : res) cout << v << ' ';
	for (int i = 0; i< n;i++) if (!vis[i]) cout << a[i] << ' ';
	cout << endl;
}