Codeforces Round #784 (Div. 4)题解

• A - Division
• B - Triple
• C - Odd/Even Increments
• D - Colorful Stamp
• E - 2-Letter Strings
• F - Eating Candies
• G - Fall Down
• H - Maximal AND
• 总结

题目链接

题意：根据分数输出段位。
题解：签到题。
code:

#include
using namespace std;
typedef long long ll;
const ll inf = 0x3f3f3f3f3f3f3f3f;

void solve() {
	int n;
	cin >> n;
	if (n >= 1900) printf("Division 1n");
	else if (n >= 1600 && n <= 1899) printf("Division 2n");
	else if (n >= 1400 && n <= 1599) printf("Division 3n");
	else printf("Division 4n");
}
int main() {
	int t;
	std::cin.tie(nullptr);
	cin >> t;
	while (t--) {
		solve();
	}

}

题意：给定一组数，输出其中出现个数大于等于3中的最大数，如果没有输出-1.
题解：输入时，就计数，不断更新max。
code:

#include
using namespace std;
typedef long long ll;
const ll inf = 0x3f3f3f3f3f3f3f3f;
void solve() {
	int n;
	cin >> n;
	int bb[200006];
	memset(bb, 0, sizeof(bb));
	int x;
	int max = -1;
	for (int i = 0; i < n; i++) {
		cin >> x, bb[x]++;
		if (bb[x] >= 3) {
			if (x > max) max = x;
		}
	}

	int cnt = 0;
	int pos = bb[0];
	int flag = 0;

	cout << max << endl;
}
int main() {
	std::cin.tie(nullptr);
	int t;
	cin >> t;
	while (t--) {
		solve();
	}

}

题意：给定一组数，你有两种操作，第一种是数组下标为奇数的所有数+1，第二种是数组下标为偶数的所有数+1，操作数任意，问是否可以将数组所有数变成奇数或者偶数？
题解：我们只需判断下标为奇数的所有数的奇偶性是否相同，或判断下标为偶数的所有数奇偶性是否相同，只要有一种不相同，就不成立，反之，成立。
code:

#include
using namespace std;
typedef long long ll;
const ll inf = 0x3f3f3f3f3f3f3f3f;
ll a[66];
void solve() {
	int n;
	cin >> n;
	int flag = 0;
	int oo = 0;
	for (int i = 1; i <= n; i++) cin >> a[i];
	int flag1 = 0;
	if (a[1] % 2 == 0) flag = 1;
	else if (a[1] % 2 != 0)flag = 2;
	if (a[2] % 2 == 0) flag1 = 1;
	else if (a[2] % 2 != 0)flag1 = 2;
	for (int i = 3; i <= n; i++) {
		if (i % 2 != 0) {
			if (flag == 1) {
				if (a[i] % 2 != 0) {
					oo = 1;
					break;
				}
			}
			if (flag == 2) {
				if (a[i] % 2 == 0) {
					oo = 1;
					break;
				}
			}

		}
		else {
			if (flag1 == 1) {
				if (a[i] % 2 != 0) {
					oo = 1;
					break;
				}
			}
			if (flag1 == 2) {
				if (a[i] % 2 == 0) {
					oo = 1;
					break;
				}
			}
		}
	}
	if (oo == 1) cout << "NO" << endl;
	else cout << "YES" << endl;
}
int main() {
	std::cin.tie(nullptr);
	int t;
	cin >> t;
	while (t--) {
		solve();
	}

}

题意：给你一张印好的邮票，问能否把空白邮票印成目标状态，共有两种印法，BR或者RB，可以重复印。
题解：遇到W检查一次，如果前面同时出现了B,R则可以，否则不可以，还要注意的是，跳出循环时也要检查一次。
code:

#include
using namespace std;
typedef long long ll;
const ll inf = 0x3f3f3f3f3f3f3f3f;
void solve() {
	int n;
	cin >> n;
	string s;
	cin >> s;
	int flag = 0;
	int oo = 0;
	int pp = 0;
	for (int i = 0; i < s.length(); i++) {
		if (s[i] == 'B') {
			oo = 1;
		}
		else if (s[i] == 'R') {
			pp = 1;
		}
		else if (s[i] == 'W') {
			if ((oo == 1 && pp == 0)) {
				flag = 1;
				break;
			}
			if ((pp == 1 && oo == 0)) {
				flag = 1;
				break;
			}
			oo = 0;
			pp = 0;
		}

	}
	if ((oo == 1 && pp == 0) || (pp == 1 && oo == 0)) flag = 1;
	if (flag == 0) cout << "YES" << endl;
	else cout << "NO" << endl;
}
int main() {
	std::cin.tie(nullptr);
	int t;
	cin >> t;
	while (t--) {
		solve();
	}

}

题意：给定一组长度为2的字符串，请计算其中只有一个对应位置相同的配对数？
题解：我们用map分别存字符串，字符串第一个字符，字符串第二个字符的出现次数，计算配对数，详情见代码。
code:

#include
using namespace std;
typedef long long ll;
const ll inf = 0x3f3f3f3f3f3f3f3f;
void solve() {
    int n;
    cin >> n;

    ll ans = 0;
    map m;//字符串
    map m1, m2;//字符串第一个数，字符串第二个
    vector v(n + 1);

    for (int i = 0; i < n; i++) {
        getline(cin, v[i]);
        m[v[i]]++;//计数
        m1[v[i][0]]++;
        m2[v[i][1]]++;
    }
    for (int i = 0; i < n; i++) {
        ans += m1[v[i][0]] + m2[v[i][1]] - 2 * m[v[i]];//第一个字符出现个数+第二个字符出现个数-重复的个数
    }
    cout << ans / 2 << endl;//因为相互配对，前面配对好的应该不计，答案为1/2.
}

int main() {
    int t;
    cin >> t;
    while (t--) {
        solve();
    }
}

题意：左边一个人和右边一个人，两个人吃相同的糖果重量，请计算两人吃的糖果个数最多多少？
题解：模拟即可。
code:

#include
using namespace std;
typedef long long ll;
const ll inf = 0x3f3f3f3f3f3f3f3f;
void solve() {
    int n;
    int a[200006];
    cin >> n;
    for (int i = 1; i <= n; i++)
        cin >> a[i];
    int i = 1;
    int j = n;
    int ans = 0;
    int w1 = 0;
    int x1 = 0;
    int w2 = 0;
    int x2 = 0;
    while (i <= j) {
        if (w1 < w2) {
            x1++;
            w1 += a[i];
            i++;

        }
        if (w2 < w1) {
            x2++;
            w2 += a[j];
            j--;
        }
        if (w1 == w2) {
            if (x1 + x2 > ans) ans = x1 + x2;
            w2 += a[j];
            j--;
            x2++;
        }
    }
    cout << ans << endl;
}
int main() {
    std::cin.tie(nullptr);
    int t;
    cin >> t;
    while (t--) {
        solve();
    }

}

题意：给一个二维图，图中的石子所在的列只要无障碍物和其他石子，就可以下落，输出最后状态图。
题解：对倒数一二行进行特判，然后从倒数第三行开始向上遍历，如果遇到石子，就再开一个循环，对石子所在列的下面几行进行分析，如果遇到石子或者障碍物便停止在上一行，遇到最后一行进行特判，注意，每次石子转换后需要跳出循环。
code:

#include
using namespace std;
typedef long long ll;
const ll inf = 0x3f3f3f3f3f3f3f3f;
void solve() {
	int n, m;
	cin >> n >> m;
	char a[60][60];
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			cin >> a[i][j];
		}
	}
	for (int j = 1; j <= m; j++) {
		if (a[n - 1][j] == '*' && a[n][j] == '.') a[n][j] = '*', a[n - 1][j] = '.';
	}
	for (int i = n - 2; i >= 1; i--) {
		for (int j = 1; j <= m; j++) {
			if (a[i][j] == '*') {
				for (int k = i + 1; k <= n; k++) {
					if (k == n && a[k][j] == '.') {
						a[k][j] = '*', a[i][j] = '.';
						break;
					}
					if (a[k][j] == '*' || a[k][j] == 'o') {
						if (k != i + 1) {
							a[k - 1][j] = '*', a[i][j] = '.';
							break;
						}
						else {
							break;
						}
					}
				}
			}

		}
	}
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			cout << a[i][j];
		}
		cout << endl;
	}
}
int main() {
	std::cin.tie(nullptr);
	int t;
	cin >> t;
	while (t--) {
		solve();
	}

}

题意：给定n元素个数，k操作数，给定一个数组，操作为把元素的二进制第j位置1（1<=j<=30),最后元素两两与运算，输出最大的结果。
题解：建立一个数组，计算n个元素从1到30位中权值为1的总个数，然后i从30开始遍历到0，a[i]=n的时候无需操作，其余的在能操作的情况下把a[i]补成n就可以了。
code:

#include
using namespace std;
typedef long long ll;
const ll inf = 0x3f3f3f3f3f3f3f3f;
ll a[31];
void f(ll x) {//计算数组a
	int cnt = 0;
	while (x > 0) {
		if (x % 2 == 1)
			a[cnt]++;
		x = x / 2;
		cnt++;
	}
	return;
}
void solve() {
	ll n, k;
	memset(a, 0, sizeof(a));
	cin >> n >> k;

	for (int i = 0; i < n; i++) {
		ll x;
		cin >> x;
		f(x);
	}

	for (int i = 30; i >= 0; i--) {
		if (k - (n - a[i]) >= 0 && n != a[i]) k -= (n - a[i]), a[i] = n;//能操作的情况下，把a[i]置成n
	}


	ll res = 0;
	for (int i = 30; i >= 0; i--) {
		if (a[i] == n) res += pow(2, i);//输出
	}
	cout << res << endl;
}
int main() {
	std::cin.tie(nullptr);
	int t;
	cin >> t;
	while (t--) {
		solve();
	}

}

比赛时网页崩了心态有点炸，不过队友很不错。