题目1

题目链接
题目大意：
给出n个整数，求移除掉最少的整数，要求：
剩下的整数中，任意两个相邻整数之和都是偶数；

输入：
第一行，整数𝑡 表示t个样例𝑡 (1≤𝑡≤100)
每个样例俩行，第一行 整数 𝑛 (3≤𝑛≤1e5)
第二行n个整数，𝑎1,𝑎2,…,𝑎𝑛 (1≤𝑎𝑖≤1e9)

输出：
每个样例一行，输出最少的移除整数。

Examples
input
2
5
2 4 3 6 8
6
3 5 9 7 1 3
output
1
0

题目解析：
奇+奇=偶；
偶+偶=偶；
奇偶和偶奇都是奇数；
所以剩下的整数中，要么全部是整数，要么全部是奇数；

枚举下这两种情况即可。

class Solution {
    static const int N = 201010;
    int a[N];

public:
    void solve() {
        int t;
        cin >> t;
        while (t--) {
            int n;
            cin >> n;
            int x = 0, y = 0;
            while (n--) {
                int k;
                cin >> k;
                x += k % 2;
                y += (k + 1) % 2;
            }
            cout << min(x, y) << endl;
        }
    }
}
ac;

题目2

题目链接
题目大意：
给出n个整数的数组a，a[i]<=a[i+1]；
现在需要调整这些整数的顺序，得到新的数组b；
要求b[i]>=a[i]；

输入：
第一行，整数𝑡 表示t个样例𝑡 (1≤𝑡≤100)
每个样例俩行，第一行 整数 𝑛 (1≤𝑛≤1e5)
第二行n个整数，𝑎1,𝑎2,…,𝑎𝑛 (1≤𝑎𝑖≤1e9, 𝑎𝑖≤𝑎𝑖+1)

输出：
每个样例一行，如果有解则输出调换后的顺序；（不能和原来一样）
如果无解则输出-1；

Examples
input
2
5
1 1 1 1 1
6
3 6 8 13 15 21

output
5 1 2 3 4
-1

题目解析：
由于调换之后，要保持新的数字大于旧的数字，那么可以推出只能换相同的数字，因为假如换过来一个更大的数字，那么这个数字所在的位置就无法得到一个更大的数字；

于是，我们只需要遍历数组，遇到不同的数字，则检查下前面不同整数的情况，如果大于1个，则挪一个位置即可；

class Solution {
    static const int N = 201010;
    int a[N];
    int c[N];

public:
    void solve() {
        int t;
        cin >> t;
        while (t--) {
            int n;
            cin >> n;
            vector<int> vec;
            for (int i = 0; i < n; ++i) {
                scanf("%d", &a[i]);
            }

            int left = 0, right = 0;
            int ans = 1;

            for (int i = 1; i <= n; ++i) {
                if ((i == n) || (a[i] != a[i - 1])) {
                    right = i;
                    // [left, right)
                    if (right - left <= 1) {
                        ans = 0;
                        break;
                    }
                    for (int j = left; j < right - 1; ++j) {
                        c[j] = j + 1;
                    }
                    c[right - 1] = left;
                    left = i;
                }
            }
            if (ans) {
                for (int i = 0; i < n; ++i) {
                    cout << c[i] + 1 << " ";
                }
                cout << endl;
            }
            else {
                cout << -1 << endl;
            }
        }
    }
}
ac;

题目3

题目链接
题目大意：
给出一个长度为n的二进制字符串s，现在定义一个函数f(s)为数字中的所有两两相邻数字组成的十进制数字之和，比如说：
𝑠=1011 时，可以得到10、01、11，那么𝑓(𝑠)=10+01+11=22；

现在最多可以执行k次操作，每次操作可以交换一次相邻数字，问f(s)最小值是多少；

输入：
第一行，整数𝑡 表示t个样例𝑡 (1≤𝑡≤1e5)
每个样例俩行，第一行 整数 𝑛 and 𝑘 (2≤𝑛≤1e5, 0≤𝑘≤1e9)
第二行长度为n的字符串s；

输出：
每个样例一行，输出最小的f(s)；

Examples
input
3
4 0
1010
7 1
0010100
5 2
00110
output
21
22
12

题目解析：
根据f(s)的定义，我们知道大部分数字都会被使用两次，一次是在十位数，一次是在个位数；第一个数字只会用在十位数，最后一个数字只会用在个位数；
那么如果想要令f(s)尽可能小，就是要将数字尽可能放在头尾两边；

考虑数字1可能会在出现在多个位置，我们用left和right来表示数字1最左边和最右边的位置；（最右边不包括第n个位置）
假如剩余的交换次数，足够right位置的1交换到最右边，则交换；
假如剩余的交换次数，足够left位置的1交换到最左边，则交换；

然后再遍历整个数组，按照规则计算得到f(s)即可。

class Solution {
    static const int N = 201010;
    string s;

public:
    void solve() {
        int t;
        cin >> t;
        while (t--) {
            int n, k;
            cin >> n >> k;
            cin >> s;
            int left = n, right = 0, sum = 0;
            int ans = 0;
            for (int i = 0; i < (n - 1); ++i) {
                if (s[i] == '1') {
                    ++sum;
                    left = min(left, i);
                    right = i;
                }
            }
            if (sum > 0 && s[n - 1] == '0') {
                if (k >= n - 1 - right) {
                    --sum;
                    k -= n - 1 - right;
                    s[right] = '0';
                    s[n - 1] = '1';
                }
            }
            if (sum > 0 && k > 0 && s[0] == '0') {
                if (k >= left) {
                    --sum;
                    k -= left;
                    s[left] = '0';
                    s[0] = '1';
                }
                
            }
            for (int i = 0; i < n - 1; ++i) {
                ans += (s[i] - '0') * 10 + (s[i + 1] - '0');
            }
            cout << ans << endl;
        }
    }
}
ac;

题目4

题目链接
题目大意：
给出在一个字符串s，现在可以将字符串s复制一遍，然后重新排序字符顺序；
希望能得到一个回文串。

输入：
第一行，整数𝑡 表示t个样例𝑡 (1≤𝑡≤100)
每个样例1行，字符串 𝑠 (1≤|𝑠|≤100)

输出：
每个样例一行，输出满足最终的回文串。

Examples
input
4
a
sururu
errorgorn
anutforajaroftuna
output
aa
suurruurruus
rgnororerrerorongr
aannuuttffoorraajjaarrooffttuunnaa

题目解析：
一个回文串的要求是从左到右，从右到左 两次遍历的字符串是一样的。
那么对于给出的字符串s，我们只需要反着生产一遍即可，比如说：
abc，我们得到abc + cba= abccba

除了此办法，由于题目允许随意排序，那么遍历字符串，记住a-z的数量，然后左右两边再一起填字符也是可以的。

class Solution {
    static const int N = 201010;
    char str[N];
public:
    void solve() {
        int t;
        cin >> t;
        while (t--) {
            cin >> str;
            int n = strlen(str);
            cout << str;
            for (int i = n - 1; i >= 0; --i) putchar(str[i]);
            cout << endl;
        }
    }
}
ac;

题目5

题目链接
题目大意：
给出整数n，现在需要找到n个整数𝑎1,𝑎2,…,𝑎𝑛 满足 1≤𝑎[𝑖]≤1e9，并且有：
𝑎1⊕𝑎2⊕⋯⊕𝑎𝑛=(𝑎1+𝑎2+⋯+𝑎𝑛)/𝑛。

输入：
第一行，整数𝑡 表示t个样例𝑡 (1≤𝑡≤100)
每个样例1行，整数 𝑛 (1≤𝑛≤1e5)

输出：
每个样例一行，输出满足要求的n个整数。

Examples
input
3
1
4
3
output
69
13 2 8 1
7 7 7

题目解析：
先从n=1开始考虑，此时任意数字都满足；
n=2时，首先a1+a2必须是偶数，那么我们可以推测二进制尾部一定都是0或者1，假设a1+a2结果是4，那么有1和3符合要求；
n=3时，类似n=1，我们加入两个相同数字，1+1+1也满足；
n=4时，我们知道n=2时，有1+3满足要求，并且结果是2，那么可以加入2个2，得到1、3、2、2；
...

思考：
题目的重点在于关注到异或的特点，两个相同数字异或值为0；

class Solution {
    static const int N = 201010;
public:
    void solve() {
        int t;
        cin >> t;
        while (t--) {
            int n;
            cin >> n;
            if (n % 2) {
                for (int i = 0; i < n; ++i) cout << 1 << " ";
                cout << endl;
            }
            else {
                cout << "1 3 ";
                for (int i = 0; i < n - 2; ++i) cout << 2 << " ";
                cout << endl;
            }
        }
    }
}
ac;