比赛链接

B题 #NCPC#

题目描述

给定n个整数，每次可以选定两个整数比较，若不等，留下较大值，否则全部删除，问对于每个整数能否是最后剩下的数字。

思路

因为是任意比较，所以我们还是考虑极限的情况，对于最大值，需要有奇数个才能留下；对于不是最大值，让最大值先比较其余值，需要偶数个最大值相互抵消才能留下。

代码

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

int main(){
    int t;
    cin >>t;
    while (t--){
        int n;
        cin >> n;
        vector<int> a(n);
        int mx = 0;
        for (int i = 0; i < n; ++i) {
            cin >> a[i];
            if (a[i] > mx) mx = a[i];
        }
        
        int cnt = 0;
        for (int x:a) if (x==mx) cnt++;
        
        string ans;
        for (int x:a) {
            if (x == mx) {
                ans += (cnt%2 ? '1' : '0');
            } else {
                ans += (cnt%2 ? '0' : '1');
            }
        }
        cout << ans << endl;
    }
    return 0;
}

I题 #01回文#

题目描述

给定n×m的01矩阵，询问任意一个位置开始拼接字符，任意非起始位置结束，能否拼接得到一个回文串。

思路

当时写的时候把每个位置记下来遍历，回头看题解把这题的难度给到了签到，大概思路好像还是贪心，一步步试探。关键在于整个矩阵只有0和1两种，那么我们就可以每次都走相反的格子，最后只要走回最初的格子即可。比如起始位置为c（0或1），如果下一个也是c，那么直接构成回文；如果相邻的格子不是c，那么第一步就需要走一个字符为c⊕1的格子，重复这个过程，再次遇到c就必定构成回文，形如：c, c⊕1, c, c⊕1, …, c，如果不存在另一个同色格子，那么无论如何也构造不出回文路径，由此我们取最近同色格子走最短路径，得到如下结论：

对于一个位置 (i,j)，它能满足题意的充分必要条件是：整个矩阵中与它字符相同的格子至少有 2 个（包括它自己）。

如果该字符个数 ≥ 2 → 输出 Y

如果该字符出个数 = 1 → 输出 N

因此，只需统计 0 和 1 的个数，然后对每个格子直接判断即可。

代码

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

int main() {
    int t;
    cin >> t;
    while (t--) {
        int n, m;
        cin >> n >> m;
        vector<string> a(n);
        
        int cnt0 = 0, cnt1 = 0;
        for (int i = 0; i < n; ++i) {
            cin >> a[i];
            for (char ch : a[i]) {
                if (ch == '0') cnt0++;
                else cnt1++;
            }
        }
        
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < m; ++j) {
                if (a[i][j] == '0')
                    cout << (cnt0 >= 2 ? 'Y' : 'N');
                else
                    cout << (cnt1 >= 2 ? 'Y' : 'N');
            }
            cout << '\n';
        }
    }
    return 0;
}