Codeforces round #665 (Div. 2) problem solution (primary school Olympiad special session)

A. Distance and Axis


  • If k > NK > NK > N, it is optimal to directly move AAA point to kkk position.
  • Otherwise, we set the shorter distance between BBB point and O, Ao, Ao and a as xxx and the longer as yyy, then there is the equation:
    {x+y=ny−x=k\left\{ \begin{array}{l} x+y=n\\ y-x=k\\ \end{array} \right.{x+y=ny−x=k​

Simultaneous solution
{y=n+k2x=n−k2\left\{ \begin{array}{l} y=\frac{n+k}{2} \\ x=\frac{n-k}{2}\\ \end{array} \right.{y=2n+k​x=2n−k​​

So when
When n+k%2=0n+k\%2=0n+k%2=0, the price is 0;
Otherwise, move A right one unit at A cost of 1.

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

const int N = 500007;

int n, m;
int k;

int main()
{
    int t;
    scanf("%d", &t);
    while(t -- ){
        scanf("%d%d", &n, &k);
        if(k > n)printf("%d\n", k - n);
        else if((n - k) % 2 == 0)
                puts("0");
        else puts("1");

    }
    return 0;
}

B. Terminal sequence (classified discussion)


Classified discussion is enough. I vomited.

We can only compare AAA sequence with BBB sequence, so we can simulate it.

We found that only AI > BIA_ i>B_ When IAI > Bi , there is a positive value of 222, and the rest is either 000 or − 2-2 − 2. So let's assign AI > BIA first_ i>B_ If IAI > Bi, then try to allocate it in the direction where the answer is 000. Finally, add the answer of − 2-2 − 2. After we have used the whole process, we can subtract the corresponding value to fully simulate it.

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

const int N = 500007;

int t;
int x1, y1, z1, x2, y2, z2, ans;

int main()
{
    scanf("%d", &t);
    while(t -- ){
        ans = 0;
        scanf("%d%d%d%d%d%d", &x1, &y1, &z1, &x2, &y2, &z2);
        int a = min(z1, y2);
        z1 -= a;y2 -= a;
        ans += a * 2;
        a = min(z1, z2);
        z2 -= a; z1 -= a;
        a = min(z1, x2);
        z1 -= a; x2 -= a;
        a = min(y1, y2);
        y1 -= a; y2 -= a;
        a = min(y1, x2);
        y1 -= a; x2 -= a;
        a = min(y1, z2);
        y1 -= a; z2 -= a;
        ans -= a * 2;
        a = min(z1, z2);
        z1 -= a; z2 -= a;
        a = min(z2, x1);
        z2 -= a; x1 -= a;
        a = min(z2, y1);
        z2 -= a; y1 -= a;
        ans -= a * 2;
        printf("%d\n", ans);
    }
    return 0;
}

C. Mer array (nature of GCD)

That's a good question.

We find that the problem is to sort the given sequence and give the conditions for exchanging elements.
Ask if we can implement sorting operation.

We refer to bubble sorting and other sorting algorithms. If you want to complete the sorting, you must be able to exchange some numbers. And we want to exchange ai,aja_i,a_jai, aj, gcd ⁡ (ai,aj)\gcd(a_i,a_j)gcd(ai, aj) is equal to the smallest element in the whole array.
Therefore, we first copy the original sequence and then sort it. If the number in the sequence is different from the number after sorting, it means that the number needs to change its position. Then see that the number can be divided by the smallest element of the sequence. If it can be exchanged, it means that it cannot be transposed and is not in the correct position. Output NONONO, otherwise output YESYESYES.
If this number can be divided by the minimum value of the sequence, for the two numbers xxx and yyy that meet this condition, the following operations can be performed with the minimum value zzz:

x y z
x z y
z x y
y x z

Exchange the positions of xxx and yyy, zzz remains unchanged, and complete the exchange operation in sorting.

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

const int N = 200007;

int n, m;
int t;
int a[N], b[N];
int main()
{
    scanf("%d", &t);
    while(t -- ){
        scanf("%d", &n);
        bool flag = 0;
        for(int i = 1; i <= n; ++ i)
            scanf("%d", &a[i]);
        memcpy(b, a, sizeof a);
        sort(b + 1, b + 1 + n);
        for(int i = 1; i <= n; ++ i){
            if(a[i] != b[i] && a[i] % b[1] != 0){
                puts("NO");
                flag = 1;
                break;
            }
        }
        if(!flag)puts("YES");
    }
    return 0;
}

D. Maximum Distributed Tree

E. Divide Square

F. Reverse and Swap


It's easier to use segment tree for the first and fourth.
The second and third operations are divided into 2 ^ k length intervals. It is easy to think that the segment tree is divided into n+1 layers, and each layer is composed of 2 ^ k length intervals. Specify that the root node is layer n and the leaf node is layer 0.
Let's first look at the third swap: it is equivalent to exchanging two adjacent sections of the line segment tree, that is, it is equivalent to directly accessing another section when accessing. A variable can be used to record whether the following left and right nodes need to be changed. For example, the current swap is layer k, so you only need to change the mark of layer k + 1.
The second one is the same as the third one. If you need to reverse layer k at present, it means that you have reversed from layer 0 to layer k, then you need to add + 1 to the marks of layer 0 to layer k.

#include<cmath>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>

typedef long long ll;
using namespace std;
const int N = 2000005;

int n, m;
int a[N];
int rev[N], cnt;
struct tree{
    int l, r;
    ll sum;
}tr[N << 2];

void pushup(int p)
{
    tr[p].sum = tr[p << 1].sum + tr[p << 1 | 1].sum;
}

void build(int p, int l, int r)
{
    tr[p] = {l, r, 0};
    if(l == r){
        tr[p].sum = a[r];
        return ;
    }
    int mid = l + r >> 1;
    build(p << 1, l, mid);
    build(p << 1 | 1, mid + 1, r);
    pushup(p);
}

void modify(int l, int r, int p, int x, int val, int depth)
{
    if(l == r){
        tr[p].sum = val;
        return ;
    }
    int mid = l + r >> 1;
    if(x <= mid)modify(l, mid, p << 1 + (rev[depth] == 1), x, val, depth - 1);
    else modify(mid + 1, r, p << 1 | 1 - (rev[depth] == 1), x, val, depth - 1);
    pushup(p);
}

ll query(int rl, int rr, int p, int l, int r, int depth)
{

    if(rl >= l && rr <= r)
        return tr[p].sum;
    int mid = rl +rr >> 1;
    ll ans = 0;
    if(l <= mid)ans += query(rl, mid, p << 1 + (rev[depth] == 1), l, r, depth - 1);
    if(r > mid)ans += query(mid + 1, rr, p << 1 | 1 - (rev[depth] == 1), l, r, depth - 1);
    return ans ;
}

int main()
{
    scanf("%d%d", &n, &m);
    for(int i = 1; i <= (1ll << n); ++ i)
        scanf("%d", &a[i]);
    build(1, 1, 1 << n);
    while(m -- ){
        int op, x, y;
        scanf("%d%d", &op, &x);
        if(op == 1){
            scanf("%d", &y);
            modify(1, 1 << n, 1, x, y, n);
        }
        else if(op == 2)for(int i = 0; i <= x; ++ i)rev[i] ^= 1;
        else if(op == 3)rev[x + 1] ^= 1;
        else {
            scanf("%d", &y);
            printf("%lld\n", query(1, 1 << n, 1, x, y, n));
        }
    }
    return 0;
}

Posted by samadams83 on Thu, 19 May 2022 11:14:29 +0300