CF731

A

#include<iostream>

using namespace std;

void solve(){
    int xa, xb, ya, yb, fa, fb;
    scanf("%d%d%d%d%d%d", &xa, &xb, &ya, &yb, &fa, &fb);
    int ans = abs(xa - ya) + abs(xb - yb);
    if(xb == yb && xb == fb && ((fa < xa && fa > ya) || (fa > xa && fa < ya))) ans += 2;
    if(xa == ya && xa == fa && ((fb < xb && fb > yb) || (fb > xb && fb < yb))) ans += 2;
    printf("%d\n", ans);
}

int main(){
    int T;
    scanf("%d", &T);
    while(T --){
        solve();
        printf("\n");
    }

    return 0;
}

B

思路

双指针算法

#include<iostream>

using namespace std;

void solve(){
    string str;
    cin >> str;
    int i = 0;
    int j = str.size() - 1;
    while(i < j){
        if(str[i] == 'a' + j - i) i ++;
        else if (str[j] == 'a' + j - i) j --;
        else break;
    }
    if(i == j && str[i] == 'a') cout << "yes" << endl;
    else cout << "no" << endl;
}

int main(){
    int T;
    cin >> T;
    while(T --){
        solve();
    }

    return 0;
}

C

题意(当时看不懂)

直接解释样例：

3 2 2
2 0
0 5

k = 3， 代表文本一开始有3行, n = 2 a[n] = {2,0}是第一个人可进行操作的数量与顺序,
m = 2 b[m] = {0,5}是第二个人可进行操作的数量与顺序.
输出样例：

2 0 0 5
1. 2 （> 0）, 即修改第二行， 2 <= k合法
2. 0, 即再加一行，此时4行, k = 4
3. 0， 即再加一行, 此时5行, k = 5
4. 5, (>0), 即修改第5行， 5 <= k 合法

贪心即可

#include<iostream>
#include<vector>

using namespace std;

void solve(){
    int k, n, m;
    cin >> k >> n >> m;
    vector<int> a(n), b(m), ans(n + m);
    for(int i = 0; i < n; i ++) cin >> a[i];
    for(int j = 0; j < m; j ++) cin >> b[j];

    int i = 0, j = 0, cnt = 0;
    while(cnt < n + m){
        if(i < n && a[i] == 0) ans[cnt ++] = a[i ++], k ++;
        else if(j < m && b[j] == 0) ans[cnt ++] = b[j ++], k ++;
        else{
            if(i < n && a[i] <= k) ans[cnt ++] = a[i ++];
            else if(j < m && b[j] <= k) ans[cnt ++] = b[j ++];
            else break;
        }
    }

    if(cnt < n + m){
        cout << -1 << endl;
    }
    else{
        for(auto x : ans) cout << x << ' ';
        cout << endl;
    }
}

int main(){
    int T;
    cin >> T;
    while(T --)
        solve();
    return 0;
}

D

题意：

输出最小字典序列y[] 使得原数组成为为growing序列。

还是贪心，局部最优使之全局最优
要使a[]为growing序列， 当前位置a[i]的res应该res = a[i - 1] | a[i], 则y[i] = a[i] ^ res

举例： 11, 101
此时不是growing序列, 则101变为 101 | 11 = 111，
则 11, 111, 就是growing序列了

#include<iostream>
#include<vector>

using namespace std;

void solve(){
    int n;
    cin >> n;
    vector<int> a(n), ans;
    for(int i = 0; i < n; i ++) cin >> a[i];
    cout << "0 ";
    for(int i = 1; i < n; i ++) {
        int res = (a[i] | a[i - 1]) ^ a[i];
        a[i] = a[i] | a[i - 1];
        ans.push_back(res);
    }

    for(auto x : ans)
        cout << x << ' ';
    cout << endl;
}

int main(){
    int T;
    cin >> T;
    while(T --){
        solve();
    }

    return 0;
}