Location>code7788 >text

Codeforces Round 1006 (Div. 3) Competition Record

Popularity：74 ℃/2025-02-26 16:04:34

Codeforces Round 1006 (Div. 3) Competition Record

Competition link
The title of this game is very long~.
It was a very simple game (after all, it was div3, how could it be simple) and I cut off A-F during the game. Question C took a lot of time, and Question G met the finale of mathematics and tried my best to defeat it.

A. New World, New Me, New Array

Since the value range is\(-p\)arrive\(p\), so it's obvious\(k\)It doesn't matter whether the maximum value can be obtained is greater than or equal to\(k\), and then use\(k\)Divide by\(p\)Just round down.

void solve()
{
    int n, k, p;cin >> n >> k >> p;

    k = abs(k);
    int mx = n * p;

    if(k == 0) {
        cout << 0 << '\n';
        return;
    }

    if(k > mx) {
         cout << -1 << '\n';
         return;
    } else {
         cout << (k - 1) / p + 1 << '\n';
    }
}

B. Having Been a Treasurer in the Past, I Help Goblins Deceive

Combining math problems, two - and one - to form an expression, it is obvious that if we want the most, we put all of them together is the most common one, because at this time they can share all - and then enumerate them again Multiply the number of left and right sides to get the maximum.

void solve()
{
    int n;cin >> n;
    string s;cin >> s;

    int cnt = 0;
    int ck = 0;
    for(auto &i : s) {
        cnt += (i == '-');
        ck += (i == '_');
    }

    int ans = 0;
    for(int i = 1;i <= cnt;i ++) {
        ans = max(ans, i * (cnt - i) * ck);
    }

    cout << ans << '\n';
}

C. Creating Keys for StORages Has Become My Main Skill

The topic needs to be constructed\(MEX\)The value can only be large, then directly from\(0\)Start enumeration, check whether this number can be added. If it can be added, stop the loop if it cannot be added, and then check whether the prefix or sum at this time is\(x\), if not, then set the next number to\(x\)(If the position is not enough, set the current last one to\(x\)), then continue to fill in\(0\)。
After the game, I saw other big shots in the group with a more elegant approach: first\(0\)arrive\(n - 1\)Join them all, and then check whether they are legal one by one. If they are not legal, they will be replaced by\(x\), then prefix or sum to calculate, if not\(x\)Just replace the last one with\(x\)。

//In fact, this check can be replaced directly with x | i == i, and the coins were minted during the game
 bool check(int x, int y) {
     for(int i = 0;i <= 31;i ++) {
         if(!(x & (1ll << i)) && (y & (1ll << i))) {
             return false;
         }
     }
     return true;
 }

 void solve()
 {
     int n, x;cin >> n >> x;

     int ix = 0;

     for(int i = 0;ix < n;i ++) {
         if(check(x, i)) {
             a[++ ix] = i;
         } else break;
     }

     int pre = 0;
     for(int i = 1;i <= ix;i ++) {
         pre |= a[i];
     }

     if(pre != x) {
         if(ix == n)a[ix] = x;
         else a[++ ix] = x;
     }

     while(ix <= n) {
         a[++ ix] = 0;
     }

     for(int i = 1;i <= n;i ++) {
         cout << a[i] << " \n"[i == n];
     }

 }

D. For Wizards, the Exam Is Easy, but I Couldn't Handle It

Select a sub-interval and move the end of the interval to the end so that there are as few pairs of reverse orders as possible after the change.
When you see the reverse order pair, you first think of the tree-like array, and then look at the data range:\(1000\)？！
direct\(n ^ 2\)Violent start.
Enumerate every point\(i\)As a starting point, search later\(j\),if\(a_j > a_i\), the reverse order pair will be increased after moving\(1\),if\(a_j < a_i\), the reverse order pair will be reduced after moving\(1\), update the decrease of the current reverse order pair at all times, and once it is reduced more, update the answer interval.

void solve()
{
    int n;cin >> n;
    for(int i = 1;i <= n;i ++)cin >> a[i];

    pair<int, int> ans = {1, 1};
    int mx = 0;
    int sum[2] = {0};
    for(int i = 1;i <= n;i ++) {
        sum[1] = 0;
        sum[0] = 0;

        for(int j = i + 1;j <= n;j ++) {
            if(a[j] < a[i])sum[1] ++;
            if(a[j] > a[i])sum[0] ++;
            int now = sum[1] - sum[0];
            if(now > mx) {
                ans = {i, j};
                mx = now;
            }
        }
    }

    cout <<  << ' ' <<  << '\n';
}

E. Do You Love Your Hero and His Two-Hit Multi-Target Attacks?

This question can be done with a similar multiplication idea.
If a bunch of\(x\)The coordinates are the same, so the logarithm that can be selected in these piles of points is\(C(n, 2)\)。
Then we can pre-process it first\(1\)arrive\(500\)of\(C(n, 2)\)and then select as large as possible to satisfy the remaining value of the current value\(n\)To connect it into a line, this can be realized in two parts.
In order to save money, we can put one vertically and horizontally, so that we can save one every time (but it is actually not necessary, just at the end of each time\(x\)and\(y\)If you add one, you can disconnect from the previous one. The number is enough and there is no need to save it).

void init() {
    for(int i = 1;i <= 500;i ++) {
        a[i] = i * (i - 1) / 2;
    }
}

void solve()
{
    int k;cin >> k;
    int ix = upper_bound(a + 1, a + 500 + 1, k) - a;

    int sum = k;
    int cnt = 0;
    int x = 0;
    int y = 0;
    
    vector<pair<int, int> > ans;
    ans.push_back({0, 0});

    while(sum) {
        cnt ++;
        int ix = upper_bound(a + 1, a + 500 + 1, sum) - a - 1;
        sum -= a[ix];
        if(cnt & 1) {
            x ++;
            for(int i = 1;i < ix;i ++) {
                ans.push_back({x, y});
                x ++;
            }
            x --;
        } else {
            y ++;
            for(int i = 1;i < ix;i ++) {
                ans.push_back({x, y});
                y ++;
            }
            y --;
        }
    }

    cout << () << '\n';
    for(auto &[u, v ] : ans) {
        cout << u << ' ' << v << '\n';
    }
}

F. Goodbye, Banker Life

After playing with a few examples, I found that\(k\)It doesn't matter at all.
You can find that if\(x\)If it is an even number, the construction of this line is equivalent to\(x / 2\)The construct of rows occurs twice adjacent to each number.
Therefore, choose the recursive implementation:

  • if\(x\)It's an even number, then go\(x / 2\)Recursively, stack each value adjacent to it twice when passing.
  • if\(x\)It's an odd number, then\(x - 1\)It's an even number,\(x - 1\)Recursively, then calculate according to the rules of the question\(x\)Just do it.

But in fact, this approach is complicated, because in fact, every position is XOR\(1\)The number of times is the Yang Hui triangle value at this position, and the method of passing the question is also transmitted according to the rules of the Yang Hui triangle.
So you only need to calculate whether the combination number of this position is odd or even, and you will know that this position is\(0\)still\(1\)Now.
Finally, multiply all\(k\)Just do it.
(But I think the recursion is quite clever)

void get(int x) {
    if(x == 1) {
        a[1] = 1;
        return;
    }

    if(x & 1) {
        get(x - 1);
        for(int i = 1;i <= x;i ++) {
            if(i == 1) {
                tmp[i] = a[i];
            } else if(i == x) {
                tmp[i] = a[1];
            } else {
                tmp[i] = a[i - 1] ^ a[i];
            }
        }
        for(int i = 1;i <= x;i ++) {
            a[i] = tmp[i];
        }
    } else {
        get(x / 2);
        for(int i = 1;i <= x / 2;i ++) {
            tmp[i * 2] = tmp[i * 2 - 1] = a[i];
        }
        for(int i = 1;i <= x;i ++) {
            a[i] = tmp[i];
        }
    } 
}

void solve()
{
    int n, k;cin >> n >> k;
    get(n);

    for(int i = 1;i <= n;i ++) {
        cout << a[i] * k << " \n"[i == n];
    }
}

The closest thing to AK, I hope to get AK div3 one day!

<Previous