Codeforces Round ＃784 (Div. 4)

A Division?

The question : Segmented output $rating$ Level corresponding to value

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

The question : A number in a given array appears $>=$ 3 Output the number once , Otherwise output $-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

The question : Or for all odd bits , Or operate on all even bits once , Ask whether the parity performance of the last array is consistent .

operation ： $+1or+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

The question : The length is n String ,RB The seal , Judge whether the string is legal . The seal can rotate ,RB,BR, And the print will cover the last time , When printing, the seal R and B Must be inside the string .

Ideas : With W Characters separate each paragraph RB Sequence . Not in line with the situation ： The length is 1, Or all R, Or all B. Other conditions can be satisfied , Provable evidence .

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

The question : Ask for this $(i,j)$ The number of pairs , Satisfy $i<jandAnd{S}_{i}And{S}_{j}onlyYesOneindividualwordoperatorNoSame\; as$. Violent solution .

Code 1 ：

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

Code 2 ：

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

The question : The left and right find disjoint prefixes with the same value , In this case of seeking the maximum , Add up the total number of digits .

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

The question : * Fall down , Simulation is fine

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

The question : k operations , Each operation can select a number in the array in any bit （$<=30$） Set up 1, Find the maximum sum of all elements of the last array .

Ideas : greedy , From the top , In the $i$ position Can fill 1 Just consume k Go fill in .

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

---