Codeforces Round ＃804 (Div. 2)

Catalog

Official explanation

A. The Third Three Number Problem

B. Almost Ternary Matrix

C. The Third Problem

---

Official explanation

Click the jump ： Official explanation

A. The Third Three Number Problem

A. The Third Three Number Problem

Ideas ：

First ,⊕( Exclusive or ) Also known as non carry addition , therefore ： about (a⊕b)+(b⊕c)+(a⊕c) For the last one of

(a⊕b)+(b⊕c)+(a⊕c) = a + b + b + c + a + c = 2*(a + b + c) Must be an even number

so ： When n In an odd number of , unsolvable

When n For even when ：

know ：a⊕0 = a , therefore , Make a = 0, b = n / 2, c = n / 2;

here ：a⊕b = n/2,a⊕c = n/2,b⊕c = 0, The result is n establish

The code is as follows ：

#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

Ideas ：

similar ：

10011001

01100110

01100110

10011001

Simulate the structure

The code is as follows ：

#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;
}

This code has a similar effect ： 

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

Ideas ：

res = The range that each number can transform

analysis ：

01 The position of the cannot be changed ;

For the rest , Numbers less than this number are on one side of this number , Then this number cannot be moved ;

The rest can move , The active range is the interval composed of numbers smaller than this number ;

The code is as follows ：

#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;
}