A - Scoreboard
大意
高桥队和青木队进行了场比赛，给出每场比赛中高桥队和青木队的积分，问最后谁总分更高或平局。
思路
统计总分比较即可。
代码
#include<iostream>
using namespace std;
int main(){
int n, a=0, b=0;
cin >> n;
while(n--){
int x, y;
cin >> x > >y;
a += x, b += y;
}
if(a < b) cout << "Aoki" << endl;
else if(a == b) cout << "Draw" << endl;
else cout << "Takahashi" << endl;
return 0;
}B - Extended ABC
大意
给定一个字符串，问是否形如，
A、B和C的数量可以为零。
思路
遍历字符串判断是否有序即可。
代码
#include<iostream>
using namespace std;
int main(){
string s;
cin >> s;
char cur = s[0];
for(auto i: s){
if(cur == i) continue;
if(i < cur){
cout << "No" << endl;
return 0;
}
if(i > cur) cur = i;
}
cout << "Yes" << endl;
return 0;
}C - Lining Up 2
大意
有 人在排队。
给你一个长度为的序列
来排列这些人。
表示以下信息：
- 如果
，则
排在队伍的最前面；
- 如果
，则
后面。
从前面到后面打印一行人的编号。
思路
设置数组表示第
个人的后面是
，读入
时，如果不为-1，则令
。
否则，确定第一个人。
确定队首后，根据数组推出队伍。
代码
#include <iostream>
using namespace std;
const int N = 3e5 + 9;
int a[N], b[N];
int main() {
int n;
cin >> n;
for (int i = 1; i <= n; i++) {
int x; cin >> x;
if (x == -1) b[1] = i;
else a[x] = i;
}
int cur = b[1];
for (int i = 2; i <= n; i++) {
b[i] = a[cur];
cur = b[i];
}
for (int i = 1; i <= n; i++) cout << b[i] << " ";
return 0;
}D - Cheating Gomoku Narabe
大意
给定的二维网格，格子上有
xo.三种之一。
问最少进行的操作数，使得网格有连续（水平或垂直）个格子都是
o。
操作为：将一个为.的格子改为o。
思路
因此可以枚举这连续个格子的左端点 ，然后往右的
个格子里，不能有x，然后对
.的数量取个最小值。事先预处理一下关于x和.数量的前缀和。（为了方便，可以将x设为极大值）
水平计算一次后，旋转九十度再计算一次即可。
代码
#include <iostream>
#include <vector>
#include <climits>
#include <unordered_map>
using namespace std;
vector<string> grid, T;
#define int long long
int solve(const vector<string>& grid, int k) {
int h = grid.size();
int w = grid[0].size();
unordered_map<char, int> mp;
mp['.'] = 1;
mp['x'] = INT_MAX;
mp['o'] = 0;
vector<vector<int>> pref(h, vector<int>(w));
int ans = INT_MAX;
for (int i = 0; i < h; i++) {
for (int j = 0; j < w; j++) {
if (j == 0) pref[i][j] = mp[grid[i][j]];
else pref[i][j] = pref[i][j - 1] + mp[grid[i][j]];
if (j >= k - 1) {
ans = min(ans, pref[i][j] - (j == k - 1 ? 0 : pref[i][j - k]));
}
}
}
return ans;
}
signed main() {
int h, w, k;
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
cin >> h >> w >> k;
for (int i = 0; i < h; i++) {
string s;
cin >> s;
grid.push_back(s);
}
int ans = solve(grid, k);
T.assign(w, string(h, 'w'));
for (int i = 0; i < h; i++)
for (int j = 0; j < w; j++) T[j][i] = grid[i][j];
ans = min(ans, solve(T, k));
cout << (ans < INT_MAX ? ans : -1) << endl;
return 0;
}E - Bad Juice
大意
有瓶果汁，其中有一瓶变质了，喝了变质的果汁会拉肚子，但你不知道哪瓶变质了。
你需要找最少的朋友，然后给他们一些果汁喝。一瓶果汁可以给多个朋友喝，一个朋友也可以喝多瓶果汁。
第二天，朋友们会告诉你他们是否不舒服，你需要据此找到变质的果汁。
思路
考虑对果汁编号到
，考虑其二进制。对于坏的果汁
，我们需要确定
的二进制下，哪些数位是1。
把 到
中，所有二进制下第
位为1的都给第
个朋友喝，如果它第二天肚子疼了，说明
的第
位为1。
需要个朋友来试毒。
代码
#include<iostream>
#include<vector>
using namespace std;
int main(){
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
int n;
cin >> n;
int m = 0;
while((1 << m) < n) m++;
cout << m << endl;
for(int i = 0; i < m; i++){
vector<int> c;
for(int j = 0; j < n; j++)
if((j >> i) & 1) c.push_back(j);
cout << c.size() << " ";
for(auto x: c) cout << x + 1 << " ";
cout << endl;
}
string s;
cin >> s;
int ans = 0;
for(int i = 0; i < s.size(); i++)
if(s[i] == '1') ans += (1 << i);
cout << ans + 1 << endl;
return 0;
}
