ABC349 A-E题解
下面的内容不包括题目翻译,要想获取题目翻译,请参照 这篇教程 来获取题目翻译。
A
题目
解法就藏在题目中。
对于一局对局,一个人得一分,一个人失一分,那么这两个人的分数和不变。如果这样进行了无数次,这些人的分数和也不变。我们知道了其他人的分数,就可以通过一开始的分数和( 0 0 0)来减去现在其他人的分数和来得到答案。
AC Code(CPP):
#include <iostream>
using namespace std;
int n, a[1010];
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin >> n;
for (int i = 1; i < n; i++) cin >> a[i];
int sum = 0;
for (int i = 1; i <= n; i++) sum += a[i];
cout << -sum;
return 0;
}
AC Code(Python)
n = int(input())
print(-sum([int(i)for i in input().split()]))
B
题目
我们可以暴力地统计每一个字母出现的次数,和每一种出现次数的次数,最终在这些次数中判断即可。
AC Code(CPP):
#include <iostream>
using namespace std;
string s;
int cnt[30], cntt[300];
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin >> s;
for (int i = 0; i < (int)s.size(); i++) cnt[s[i] - 'a']++;
for (int i = 0; i < 26; i++) {
cntt[cnt[i]]++;
}
int cnttt = 0;
for (int i = 1; i <= (int)s.size(); i++) {
if (cntt[i] != 2 && cntt[i] != 0) {
cout << "No\n";
return 0;
}
}
cout << "Yes\n";
return 0;
}
AC Code(Python)
from collections import Counter
s = input()
counter = Counter(s)
counter1 = Counter(counter.values())
print(('Yes', 'No')[len([i for i in counter1.values() if i != 0 and i != 2]) >= 1])
C
题目
这个时候我们可以先遍历 S S S,如果在 S S S 中找到了 T T T 的第一个字母,那么寻找 T T T 的第二个字母,直到找完。如果到结束后都没有找完,就输出 No
即可。
AC Code(CPP):
#include <iostream>
using namespace std;
string s, t;
int main() {
cin >> s >> t;
int len = 3;
if (t[2] == 'X') len--;
int idx = 0;
for (int i = 0; i < (int)s.size(); i++) {
if (s[i] - 'a' + 'A' == t[idx]) {
idx++;
if (idx >= len) break;
}
}
if (idx < len) {
cout << "No\n";
}
else cout << "Yes\n";
return 0;
}
AC Code(Python):
s = input()
t = input()
t = t.lower()
a = (t[0] in s) and (t[1] in s[s.find(t[0]) + 1:])
print(('No', 'Yes')[a and (t[2] == 'x' or (t[2] in s[s.find(t[0]) + 1:][s[s.find(t[0]) + 1:].find(t[1]) + 1:]))])
D
题目
我们希望每一次增加的尽量的多,这样答案最优。
证明如下:
假设当前数目为 p p p,可以被 2 i 2^i 2i 和 2 i + 1 2^{i +1} 2i+1 整除,且 p + 2 i + 1 p +2^{i + 1} p+2i+1 不超过终点。
如果我们选择跳 2 i 2^i 2i,那么跳 2 2 2 次后才可以跳到 2 i + 1 2^{i+1} 2i+1,如果跳 2 i + 1 2^{i+1} 2i+1,那么跳一次就可以达到上面的数值。
所以每一次跳尽可能大的数值要更快。
AC Code(CPP):
#include <iostream>
#define int long long
using namespace std;
int l, r;
int pow_2[70];
int m;
int ans[100100][3];
signed main() {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin >> l >> r;
pow_2[0] = 1;
for (int i = 1; i <= 62; i++) pow_2[i] = pow_2[i - 1] * 2;
int now = l;
while (now <= r - 1) {
int k = 0;
for (k = 0; k < 62; k++) {
if (now % pow_2[k] || now + pow_2[k] > r) {
k--;
break;
}
}
m++;
ans[m][0] = now;
now += pow_2[k];
ans[m][1] = now;
}
cout << m << '\n';
for (int i = 1; i <= m; i++) {
cout << ans[i][0] << ' ' << ans[i][1] << '\n';
}
return 0;
}
AC Code(Python):
l, r = [int(i)for i in input().split()]
pow_2 = [1]
for i in range(1, 62):
pow_2.append(pow_2[i - 1] * 2)
now = l
ans = []
while now <= r - 1:
k = 0
for i in range(62):
if now % pow_2[i] > 0 or now + pow_2[i] > r:
k = i - 1
break
ans.append([now, now + pow_2[k]])
now += pow_2[k]
print(len(ans))
for i in ans:
print('{0} {1}'.format(i[0], i[1]))
E
题目
我们可以让 f ( a , b ) f(a, b) f(a,b) 表示当棋盘为 a a a,当前玩家为 b b b 是的赢家。因为都是用最优策略,所以我们的玩家可以知道当他通过某一种方法落子时的赢家。如果有一种落子方法可以让 f ( a , b ) f(a, b) f(a,b) 为 b b b 时,那么 b b b 就一定可以通过某种方法胜利;如果 f ( a , b ) f(a, b) f(a,b) 都不是 b b b 时,那么 b b b 无论如何也赢不了。
结束判定方式
如果棋盘满了,那么分数多的那一方获胜。如果某一方下成了一条线,那一方获胜。
实现小技巧:
因为棋盘只有九个格子,所以可以用两个整数表示当前棋盘,一个表示高桥的棋子,一个表示青木的棋子。通过 位运算 可以快速地在棋盘上进行操作。
AC Code(CPP):
#include <iostream>
using namespace std;
long long a[5][5];
int line[10] = {
0b000000111,
0b000111000,
0b111000000,
0b100100100,
0b010010010,
0b001001001,
0b100010001,
0b001010100
};
bool check(int x) {
for (int i = 0; i < 8; i++) {
if ((x & line[i]) == line[i]) {
return 1;
}
}
return 0;
}
bool dfs(const int Taka, const int Aoki, const bool is_T) {
if (Taka + Aoki == 0b111111111) {
long long T_score = 0;
for (int i = 0; i < 9; i++) {
if ((Taka >> i) & 1) T_score += a[i / 3][i % 3];
else T_score -= a[i / 3][i % 3];
}
return (T_score > 0);
}
if (is_T) {
for (int i = 0; i < 9; i++) {
if (((Taka >> i) & 1) || ((Aoki >> i) & 1)) continue;
if (check((Taka | (1 << i)))) return 1;
if (dfs((Taka | (1 << i)), Aoki, !is_T)) {
return 1;
}
}
return 0;
}
else {
for (int i = 0; i < 9; i++) {
if (((Taka >> i) & 1) || ((Aoki >> i) & 1)) continue;
if (check(Aoki | (1 << i))) return 0;
if (!dfs(Taka, (Aoki | (1 << i)), !is_T)) {
return 0;
}
}
return 1;
}
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
for (int i = 0; i < 3; i++) {
for (int j = 0; j < 3; j++)
cin >> a[i][j];
}
if (dfs(0, 0, 1)) cout << "Takahashi";
else cout << "Aoki";
return 0;
}
AC Code(Python):
a = []
line = {
0b000000111,
0b000111000,
0b111000000,
0b100100100,
0b010010010,
0b001001001,
0b100010001,
0b001010100
}
def check(x):
for idx in line:
if x & idx == idx:
return True
return False
def print_num(x):
for temp in range(9):
print(x & 1, end='')
x >>= 1
print()
def dfs(x, y, is_x):
if x + y == 0b111111111:
t_score = 0
for x1 in range(0, 3):
for y1 in range(0, 3):
if (x >> (x1 * 3 + y1)) & 1:
t_score += a[x1][y1]
else:
t_score -= a[x1][y1]
return t_score > 0
if is_x:
for idx in range(0, 9):
if ((x >> idx) & 1) or ((y >> idx) & 1):
continue
if check(x | (1 << idx)):
return True
if dfs(x | (1 << idx), y, not is_x):
return True
return False
else:
for idx in range(0, 9):
if ((x >> idx) & 1) or ((y >> idx) & 1):
continue
if check(y | (1 << idx)):
return False
if not dfs(x, y | (1 << idx), not is_x):
return False
return True
for i in range(3):
a.append([int(i)for i in input().split()])
print(['Aoki', 'Takahashi'][dfs(0, 0, 1)])