AtCoder Beginner Contest 337 A - E

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