Codeforces Round ＃784 (Div. 4)

A Division?

题意: 分段输出$rating$值所对应级别

void solve() {
    
	int n; cin >> n;
	int x = -1;
	if(n >= 1900) x = 1;
	else if(n >= 1600) x = 2;
	else if(n >= 1400) x = 3;
	else if(n <= 1399) x = 4;
	cout << "Division " << x << endl;
}

---

B Triple

题意: 给定数组中某数出现 $>=$ 3次就输出该数，否则输出$-1$

map<int, int> s;
 
void solve() {
    
	s.clear();
	int n; cin >> n;
	
	int o = 0;
	int res = 0;
	for (int i=  0; i < n; i++) {
    
		int x; cin >> x;
		s[x] ++;
		if(s[x] >= 3) o = 1, res = x;
	}
	if(o) cout << res << endl;
	else cout << -1 << endl;
}

---

C Odd/Even Increments

题意: 要么对所有奇位，要么对所有偶位操作一次，问是否最后数组奇偶性能一致。

操作： $+1或+0$

void solve() {
    
	int n; cin >> n;
	vector<int> v;
	v.resize(n);
	for (int i = 0; i < n; i++) cin >> v[i];
	
	int x = (v[0] & 1);
	for (int i = 2; i < n; i += 2) {
    
		int j = (v[i] & 1);
		if(x != j) {
    
			cout << "NO" << endl;
			return ;
		}
	}
	
	int y = (v[1] & 1);
	for (int i = 3; i < n; i += 2) {
    
		int j = (v[i] & 1);
		if(y != j) {
    
			cout << "NO" << endl;
			return ;
		}
	}
	cout << "YES" << endl;
}

---

D Colorful Stamp

题意: 长度为n的字符串，RB印章，判断该字符串是否合法。印章可以旋转，RB，BR，并且印会覆盖上一次，印的时候印章的R和B都要在字符串内部。

思路: 以W字符分隔出每一段RB序列。不符合的情况：长度为1，或者全R，或者全B。其它情况都可以满足，可证。

bool func(string s) {
    
	if(s == "") return true;
	if(s.sz == 1) return false;
	if(s.find("R") == -1 || s.find("B") == -1) return false;
	return true;
}
 
void solve() {
    
	int n = 1; cin >> n;
	string s; cin >> s;
	string t = "";
 
	for (int i = 0; i < s.sz; i++) {
    
		if(s[i] == 'W') {
    
			if(!func(t)) {
    
				cout << "NO" << endl;
				return ;
			}
			t = "";
			continue;
		}
		t += s[i];
	}
	if(!func(t)) {
    
		cout << "NO" << endl;
		return ;
	}
	cout << "YES" << endl;
}

---

E 2-Letter Strings

题意: 求这样的$(i,j)$数对的个数，满足$i<j并且S_i与S_j仅有一个字符不同$。暴力求解。

代码一：

int st[30][30];
 
void solve() {
    
	memset(st, 0, sizeof st);
	int res = 0;
	int n; cin >> n;
	for (int i = 0; i < n; i++) {
    
		string s; cin >> s;
		int a = s[0] - 'a', b = s[1] - 'a';
		for (int j = 0; j < 26; j++) {
    
			if(j != a) res += st[j][b];
			if(j != b) res += st[a][j];
		}
		st[a][b]++;
	}
	cout << res << endl;
}
 

代码二：

map<string, int> mp;
 
void solve() {
    
	mp.clear();
	int n; cin >> n;
	int ans = 0;
	for (int i = 0; i < n; i++) {
    
		string s; cin >> s;
		string t = s;
		for (int j = 0; j < 26; j++) {
    
			if(s[0] != j + 'a') {
    
				t[0] = j + 'a';
				ans += mp[t];
				t = s;
			}
			if(s[1] != j + 'a') {
    
				t[1] = j + 'a';
				ans += mp[t];
				t = s;
			}
		}
		mp[s] ++;
	}
	cout << ans << endl;
}

---

F Eating Candies

题意: 左右找到不相交的前后缀值相同，求最大的这种情况下，加起一共多少位数。

int a[N], b[N];
 
void solve() {
    
	int n = 1; cin >> n;
	for (int i = 0; i <= n; i++) a[i] = b[i] = 0;
	for (int i = 1; i <= n; i++) cin >> a[i], b[i] = a[i];
	for (int i = 1; i <= n; i++) a[i] += a[i - 1];
	for (int i = n - 1; i >= 1; i--) b[i] += b[i + 1];
	for (int i = 1; i <= n / 2; i++) swap(b[i], b[n - i + 1]);
	
	int res = 0;
	
	for (int i = 1; i <= n; i++) {
    
		int d = lower_bound(b + 1, b + 1 + n, a[i]) - b;
		if(n - d < i) break;
		if(d <= n && b[d] == a[i]) {
    
			res = i + d;
		}
	}
	cout << res << endl;
}

---

G Fall Down

题意: *向下下落，模拟就行

void solve() {
    
	cin >> n >> m;
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= m; j++) 
			cin >> cc[i][j];
	int k = 1022;
	while (k--)
	{
    
		for (int i = n - 1; i >= 1; i--)
		{
    
			for (int j = 1; j <= m; j++)
			{
    
				if (cc[i][j] == '*' && cc[i + 1][j] == '.')
					cc[i][j] = '.', cc[i + 1][j] = '*';
			}
		}
	}
	for (int i = 1; i <= n; i++)
	{
    
		for (int j = 1; j <= m; j++) cout << cc[i][j];
		cout << endl;
	}
	cout << endl;
}

---

H Maximal AND

题意: k次操作，每次操作可选择数组中一个数在任意位（$<=30$）置1，求最后数组所有元素相与的最大值。

思路: 贪心， 从高位开始，在第$i$位能填满1就消耗k去填。

int n, m;
int a[N];
int s[35];
 
void solve() {
    
	cin >> n >> m;
	memset(s, 0, sizeof s);
	for (int i = 1; i <= n; i++) {
    
		cin >> a[i];
		for (int j = 30; j >= 0; j--) {
    
			if(a[i] >> j & 1) s[j]++;
		}
	}
	for (int i = 30; i >= 0; i--) {
    
		if(m + s[i] >= n) {
    
			for (int j = 1; j <= n; j++) a[j] |= (1ll << i);
			m -= n - s[i];
			// Dbug(m);
		}
	}
	int res = 0;
	for (int i = 0; i <= 30; i++) res |= (1ll << i); 
	// for (int i = 1; i <= n; i++) {cout << a[i] << ' '; }
	// cout << endl;
	for (int i = 1; i <= n; i++) res &= a[i];
	cout << res << endl;
}

---