Contestant. Rank 2267. Rating +74.

A. Probably English

题意

给定一个字符串序列，输出序列中是否包含下面的 \(5\) 个单词：

\(and, not, that, the, you\)。

思路

如题，别打错即可。

时间复杂度：\(O(n)\)

对应AC代码

#include <bits/stdc++.h>

using namespace std;

#define int long long
#define pii pair<int, int>
#define fs first
#define sc second

const int N = 2e5 + 10, inf = 0x3f3f3f3f3f3f3f3f;

void init(){}

void solve() {
    vector<string> mp = {"and", "not", "that", "the", "you"};
    int n;
    cin >> n;
    bool f = false;
    while(n --){
        string s;
        cin >> s;
        for(auto e : mp)
            if(s == e) f = true;
    }
    cout << (f ? "Yes\n" : "No\n");
}

signed main(){
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    init();
    int t = 1;
    //cin >> t;
    while(t --) solve();
}

打错了草

B. Bombs

题意

给定一个矩阵，矩阵由 ".", "#" 和数字组成。对于任意数字 \(x\)，将其周围所有曼哈顿距离小于等于 \(x\) 且为 "#" 的点替换为 "."。输出替换后的矩阵。

其中，对于两个点 \((x_1, y_1), (x_2, y_2)\)，曼哈顿距离为 \(|x_1 - x_2| + |y_1 - y_2|\)。

思路

直接模拟。

当然，不要直接替换，判断一下是不是 "#" 再说。

时间复杂度：\(O(nmp^2)\)

对应AC代码

#include <bits/stdc++.h>

using namespace std;

#define int long long
#define pii pair<int, int>
#define fs first
#define sc second

const int N = 2e5 + 10, inf = 0x3f3f3f3f3f3f3f3f;

void init(){}

void solve() {
    int n, m;
    cin >> n >> m;
    vector<string> s(n);
    for (int i = 0; i < n; i++) cin >> s[i];
    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++) {
            char now = s[i][j];
            if (now != '#' && now != '.') {
                int cnt = now - '0';
                s[i][j] = '.';
                for (int x = 1; x <= cnt; x++)
                    for (int p = 0; p <= x; p++) {
                        int q = x - p;
                        if (i + p < n && j + q < m && s[i + p][j + q] == '#') s[i + p][j + q] = '.';
                        if (i + p < n && j - q >= 0 && s[i + p][j - q] == '#') s[i + p][j - q] = '.';
                        if (i - p >= 0 && j + q < m && s[i - p][j + q] == '#') s[i - p][j + q] = '.';
                        if (i - p >= 0 && j - q >= 0 && s[i - p][j - q] == '#') s[i - p][j - q] = '.';
                    }
            }
        }
    for (auto e: s) cout << e << '\n';
}

signed main(){
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    init();
    int t = 1;
    //cin >> t;
    while(t --) solve();
}

论我debug了半天这道简单题这件事

C. Socks

题意

给定一个序列，在一个元素只能在一对数的条件下，输出可以找出多少对相同的数。

思路

如题，将所有数找出，答案即为各个数量除 \(2\)。

时间复杂度：\(O(n)\)

对应AC代码

#include <bits/stdc++.h>

using namespace std;

#define int long long
#define pii pair<int, int>
#define fs first
#define sc second

const int N = 2e5 + 10, inf = 0x3f3f3f3f3f3f3f3f;

void init(){}

void solve() {
    map<int, int> cnt;
    int n;
    cin >> n;
    for(int i=0;i<n;i++){
        int cur;
        cin >> cur;
        cnt[cur] ++;
    }
    int ans = 0;
    for(auto e : cnt) ans += e.second / 2;
    cout << ans << '\n';
}

signed main(){
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    init();
    int t = 1;
    //cin >> t;
    while(t --) solve();
}

这也太水了（（

D. Three Days Ago

题意

给定一个由 \([0, 9]\) 内数字组成的序列，输出所有连续子序列中满足所有数出现次数均为偶数的个数。

思路

首先，奇偶性相同的前缀和，它们的差值一定是偶数，那么，我们只需考虑奇偶性。

也就是说，对于一种 \([0, 9]\) 的奇偶性排列，若有 \(x\) 个相同的，那么答案加上 \(\frac{x(x - 1)}{2}\)。

对于这种排列，我们不妨用状压，那么，用 \(map\) 就完事了。

时间复杂度：\(O(n)\)

对应AC代码

#include <bits/stdc++.h>

using namespace std;

#define int long long
#define pii pair<int, int>
#define fs first
#define sc second

const int N = 2e5 + 10, inf = 0x3f3f3f3f3f3f3f3f;

void init(){}

void solve() {
    string s;
    cin >> s;
    int n = s.size();
    map<int, int> cnt;
    cnt[0] = 1;
    int cur = 0;
    for(int i=0;i<n;i++){
        int t = s[i] - '0';
        cur ^= (1 << t);
        cnt[cur] ++;
    }
    int ans = 0;
    for(auto i : cnt) ans += (i.second - 1) * i.second / 2;
    cout << ans << '\n';
}

signed main(){
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    init();
    int t = 1;
    //cin >> t;
    while(t --) solve();
}

以后写状压还是写简单一点为好（（