Codeforces Round ＃804 (Div. 2)

目录

官方题解

A. The Third Three Number Problem

B. Almost Ternary Matrix

C. The Third Problem

---

官方题解

点击跳转：官方题解

A. The Third Three Number Problem

A. The Third Three Number Problem

思路：

首先，⊕(异或) 又称不进位加法，所以：对于 (a⊕b)+(b⊕c)+(a⊕c) 的最后的一位而言

(a⊕b)+(b⊕c)+(a⊕c) = a + b + b + c + a + c = 2*(a + b + c) 必为偶数

故：当 n 为奇数时，无解

当 n 为偶数时：

知：a⊕0 = a ，所以，令 a = 0, b = n / 2, c = n / 2;

此时：a⊕b = n/2，a⊕c = n/2，b⊕c = 0，结果为 n 成立

代码如下：

#include <bits/stdc++.h>

#define fast ios::sync_with_stdio(false),cin.tie(0), cout.tie(0)

using namespace std;

typedef long long LL;
typedef pair<int, int> PII;

const int N = 2e5 + 10, mod = 1e9 + 7;

int T;

int lowbit(int x)
{
    return x & -x;
}

void solve()
{
    int n, c;
    scanf("%d", &n);

    if(n%2)
    {
        puts("-1");
        return ;
    }

    printf("%d %d %d\n", 0, n/2, n/2);

    //printf("%d\n", res);
}

int main()
{
    //fast;
    //cin >> T;
    scanf("%d", &T);
    while(T -- )
        solve();

    return 0;
}

B. Almost Ternary Matrix

B. Almost Ternary Matrix

思路：

类似：

10011001

01100110

01100110

10011001

模拟构造即可

代码如下：

#include <bits/stdc++.h>

#define fast ios::sync_with_stdio(false),cin.tie(0), cout.tie(0)

using namespace std;

typedef long long LL;
typedef pair<int, int> PII;

const int N = 110, mod = 1e9 + 7;

int T;

int lowbit(int x)
{
    return x & -x;
}

void solve()
{
    int n, m;
    scanf("%d %d", &n, &m);
    string r1, r2;
    while(true)
    {
        if(r1.size() < 2 * m) r1 += "1 0 ";
        else break;
        if(r1.size() < 2 * m) r1 += "0 1 ";
        else break;
    }
    while(true)
    {
        if(r2.size() < 2 * m) r2 += "0 1 ";
        else break;
        if(r2.size() < 2 * m) r2 += "1 0 ";
        else break;
    }

    int a[N][N];
    for(int i = 1; i <= n; i ++ )
    {
        if(i % 4 == 1 || i % 4 == 0) cout << r1 << endl;
        else cout << r2 << endl;
    }

    //printf("%d\n", res);
}

int main()
{
    //fast;
    //cin >> T;
    scanf("%d", &T);
    while(T -- )
        solve();

    return 0;
}

此段代码也有类似效果： 

void solve()
{
    int n, m;
    scanf("%d %d", &n, &m);

    for(int i = 1; i <= n; i ++ )
    {
        for(int j = 1; j <= m; j ++ )
            cout << ((i % 4 <= 1)==(j % 4 <= 1)) << " ";
        puts("");
    }

    //printf("%d\n", res);
}

C. The Third Problem

C. The Third Problem

思路：

res = 每个数能变换的范围

分析：

01的位置不能变；

对于其余的数，小于本数的数在本数的一侧，则本数也不能动；

其余的数能动，能动的范围为比本数小的数组成的区间；

代码如下：

#include <bits/stdc++.h>

#define fast ios::sync_with_stdio(false),cin.tie(0), cout.tie(0)

using namespace std;

typedef long long LL;
typedef pair<int, int> PII;

const int N = 1e5 + 10, mod = 1e9 + 7;

int T;

void solve()
{
    int n, m;
    scanf("%d", &n);

    int a[N] = {0}, p[N] = {0};
    for(int i = 0; i < n; i ++ )
    {
        scanf("%d", &a[i]);
        p[a[i]] = i;
    }

    int res = 1;
    int l = p[0], r = p[0];
    for(int i = 1; i < n; i ++ )
    {
        if(p[i] < l) l = p[i];
        else if(p[i] > r) r = p[i];
        else res = (LL)res*(r - l + 1 - i) % mod;
        //cout << res << endl;
    }

    printf("%d\n", res);

    //printf("%d\n", res);
}

int main()
{
    //fast;
    //cin >> T;
    scanf("%d", &T);
    while(T -- )
        solve();

    return 0;
}