Codeforces Round #833 (Div. 2)

C 题挂 \(4\) 发赛后再挂 \(4\) 发 AB 耻辱跑路。

A. The Ultimate Square

有 \(n\) 个木块，第 \(i\) 块长 \(\lceil\frac {i} {2}\rceil\) 宽 \(1\)， 则用这些木块拼成的最大的正方形边长为多少。

见样例知结论。

若 \(n\bmod 2 = 1\)， 则长 \(1\sim \lceil\frac {n}{2}\rceil-1\) 的木块有 \(2\) 个，长 \(\lceil\frac {n}{2}\rceil\) 的木块有 \(1\) 个。
我们则可以单独放 \(\lceil\frac{n}{2}\rceil\) 的木块，对于剩下的木块首尾配对就可以组成边长 \(\lceil\frac{n}{2}\rceil\) 的木块。

若 \(n\bmod 2 = 0\)，则长 \(1\sim \frac{n}{2}\) 的都有 \(2\) 个。
便可以选一个长 \(\frac{n}{2}\) 的丢掉另一个，剩下的首尾配对，边长为 \(\frac{n}{2}\)。

// Problem: The Ultimate Square
// Contest: Codeforces
// URL: http://m3.codeforces.com/contest/1748/problem/A
// Memory Limit: 256 MB
// Time Limit: 1000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h> 
using namespace std;
int main () {
	ios :: sync_with_stdio (false);
	cin .tie (0);
	cout .tie (0);
	int t;
	cin >> t;
	while (t --) {
		int n;
		cin >> n;
		cout << (n + 1) / 2 << endl;
	}
	return 0;
}

B. Diverse Substrings

定义“好”的序列为出现的最多的元素的数量 \(\le\) 出现的元素种类数量，给你一个序列，你需要回答序列中有多少子序列是“好”的序列，元素 \(=0\sim 9\)。

很妙的一道题。

一开始不难想到 \(n^2\) 的枚举起点依次后推终点的暴力。

我们选择筛掉无用的。我们发现元素种类最多也只有 \(10\) 种，则每种元素最多出现次数也只有 \(10\) 种，则合法的序列长度最长也只有 \(100\)，便可以筛去长度 \(>100\) 的序列。

时间复杂度 \(O(w^2n)\)，\(w\) 为元素数量，这里为 \(10\)。

// LUOGU_RID: 94000172
// Problem: B. Diverse Substrings
// Contest: Codeforces - Codeforces Round #833 (Div. 2)
// URL: https://codeforc.es/contest/1748/problem/B
// Memory Limit: 256 MB
// Time Limit: 1000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>
using namespace std;
const int N = 100100, T = 10;
int a [N];
int cnt [T];
int main () {
	int t;
	scanf ("%d", &t);
	while (t --) {
		int n;
		scanf ("%d", &n);
		for (int i = 1; i <= n; i ++) {
			scanf ("%1d", & a[i]);
		}
		int ans = 0;
		for (int i = 1; i <= min (100, n); i ++) {//这里采用的枚举长度
			for (int j = 0; j < T; j ++) {
				cnt [j] = 0;
			}
			int scnt = 0;
			for (int j = 1; j <= i; j ++) {
				cnt [a [j]] ++;
				if (cnt [a [j]] == 1) {
					scnt ++;
				}
			}
			for (int j = i; j <= n; j ++) {
				int Max = 0;
				for (int k = 0; k < T; k ++) {
					Max = max (Max, cnt [k]);
				}	
				if (Max <= scnt) {
					ans ++;
				}
				cnt [a [j - i + 1]] --;
				if (!cnt [a [j - i + 1]]) {
					scnt --;
				}
				cnt [a [j + 1]] ++;
				if (cnt [a [j + 1]] == 1) {
					scnt ++;
				}
			}
		}
		printf ("%d\n", ans);
	}
	return 0;
}

C. Zero-Sum Prefixes

先咕到晚上吧。