My approach during CodeForces Round 959
Разница между en2 и en3, 2 символ(ов) изменены
## 0. Feeling↵

[**Welcome to the easiest Div.1 + Div.2 ever.**](https://codeforces.net/contest/1994)↵

Got accepted on ABCDE.↵

And there's also a version in Chinese [here](https://www.cnblogs.com/SyuAyaka/articles/-/cf1994).↵

## 1. Diverse Game↵

Given a permutation with a size of $nm$, construct another permutation with a size of $nm$ satisfies that it's different to the previous permutation in each position.↵

$a_i=a_i\bmod nm+1$. The time complexity is $O(nm)$.↵

<spoiler summary="Code">↵
```c++↵
#include <iostream>↵
using namespace std;↵
const int N = 5e4 + 10;↵
int n, m;↵
void run()↵
{↵
    scanf("%d%d", &n, &m);↵
    if (n == 1 and m == 1)↵
    {↵
        scanf("%*d");↵
        puts("-1");↵
        return;↵
    }↵
    for (int i = 1, x; i <= n; i++)↵
    {↵
        for (int j = 1; j <= m; j++)↵
        {↵
            scanf("%d", &x);↵
            printf("%d%c", x % (n * m) + 1, " \n"[j == m]);↵
        }↵
    }↵
}↵
int main()↵
{↵
    int T = 1;↵
    scanf("%d", &T);↵
    while (T--)↵
        run();↵
}↵
```↵
</spoiler>↵

## 2. Fun Game↵

Given two binary sequences $a$ and $b$,unlimited operation to make from $a_l$ to $a_r$ **simultaneously** xor $a_1$ to $a_{r-l+1}$。Determine if it's able to turn $a$ into $b$。↵

Because I was watching Zenless Zone Zero videos on Bilibili, I suddenly realized that, it's able to consider the prefix zeros in $a$ and $b$ as "hollow". Because, under the constriants of the problem, regardless how many operations you do, the size of their "hollow" won't decrease.↵

With only one $1$, we can freely modify the following zeros and ones.↵

Only one line of code to solve this problem. The time complexity is $O(n)$.↵

<spoiler summary="Code">↵
```c++↵
#include <iostream>↵
#include <string>↵
using namespace std;↵
const int N = 1e5 + 10;↵
int n;↵
string s, t;↵
void run()↵
{↵
    cin >> n >> s >> t;↵
    puts(s.find('1') <= t.find('1') ? "YES" : "NO");↵
}↵
int main()↵
{↵
    int T = 1;↵
    scanf("%d", &T);↵
    while (T--)↵
        run();↵
}↵
```↵
</spoiler>↵

## 3. Hungry Games↵

Too lazy to write the statement again.↵

Answer = total number of possible ranges &mdash; ranges with final toxicity of $0$.↵

Looks like topological sort.↵

Define $d_i$ as the number of left borders $j$ when set $i$ as the right border satisfying the final toxicity of the range $[j,i]$ equals zero.↵

When enumerating $i$, find the first $t$ safisfies $\sum_{j=i}^t a_j>x$, add 
将 $d_i+1$ to $d_t$. because, $d_i$ ranges satisfying the final toxicity equals zero, and the range $[i,t]$ also makes zero, it's able to combine these two ranges together, that the final toxicity is still zero.↵

The time complexity is $O(n)$.↵

<spoiler summary="Code">↵
```c++↵
#include <iostream>↵
#include <cstring>↵
using namespace std;↵
const int N = 2e5 + 10;↵
using ll = long long;↵
int n, k, r;↵
ll a[N], dp[N], cur, res;↵
void run()↵
{↵
    scanf("%d%d", &n, &k);↵
    for (int i = 1; i <= n; i++)↵
    {↵
        scanf("%lld", a + i);↵
    }↵
    memset(dp + 2, 0, n << 3);↵
    cur = 0;↵
    r = 1;↵
    for (int i = 1; i <= n; i++)↵
    {↵
        cur -= a[i - 1];↵
        while (r <= n and cur <= k)↵
            cur += a[r], r++;↵
        if (cur <= k)↵
            continue;↵
        dp[r] += dp[i] + 1;↵
    }↵
    res = n;↵
    res *= n + 1;↵
    res /= 2;↵
    for (int i = 2; i <= n + 1; i++)↵
    {↵
        res -= dp[i];↵
    }↵
    printf("%lld\n", res);↵
}↵
int main()↵
{↵
    int T = 1;↵
    scanf("%d", &T);↵
    while (T--)↵
        run();↵
}↵
```↵
</spoiler>↵

## 4. Funny Game↵

In a complete graph with $n$ nodes, each node has a value $a_i$. The weight of the edge connecting node $i$ and $j$ is $|a_i-a_j|$. Find a spanning tree in this graph satisfying $i$ divides the weight of the $i$-th edge.↵

I didn't realize the pigeonhole here, so I had a different approach.↵

A smaller $i$ has an **expectational** bigger number of edges satisfying $i$ divides its weight.↵

So, enumerate $i$ in decreasing order, then use union-find to handle connected components.↵

The time complexity is $O(n^2)$.↵

<spoiler summary="Code">↵
```c++↵
#include <iostream>↵
#include <list>↵
#include <cstring>↵
using namespace std;↵
const int N = 2e3 + 10;↵
int n, a[N], f[N], v[N], p;↵
bool fl;↵
using pii = pair<int, int>;↵
list<pii> ret;↵
inline int find(int x)↵
{↵
    return x == f[x] ? x : f[x] = find(f[x]);↵
}↵
inline void merge(int x, int y)↵
{↵
    f[find(y)] = find(x);↵
}↵
void run()↵
{↵
    scanf("%d", &n);↵
    for (int i = 1; i <= n; i++)↵
    {↵
        f[i] = i;↵
        scanf("%d", a + i);↵
    }↵
    ret.clear();↵
    for (int i = n - 1; i; i--)↵
    {↵
        memset(v, 0, i << 2);↵
        fl = false;↵
        for (int j = 1; j <= n; j++)↵
        {↵
            p = a[j] % i;↵
            if (!v[p])↵
            {↵
                v[p] = j;↵
                continue;↵
            }↵
            if (find(j) == find(v[p]))↵
                continue;↵
            merge(j, v[p]);↵
            ret.push_front({j, v[p]});↵
            fl = true;↵
            break;↵
        }↵
        if (!fl)↵
            return puts("NO"), void();↵
    }↵
    puts("YES");↵
    for (auto &[tx, ty] : ret)↵
        printf("%d %d\n", tx, ty);↵
}↵
int main()↵
{↵
    int T = 1;↵
    scanf("%d", &T);↵
    while (T--)↵
        run();↵
}↵
```↵
</spoiler>↵

## 5. Wooden Game↵

Too lazy to rewrite the statement again.↵

The contribution of a tree with a size of $x$ is able to be any integer in range $[1,x]$, regardless its structure, because we can remove its leaves one by one.↵

When I realized that, I f**ked up.↵

The time complexity is $O(n)$.↵

<spoiler summary="Code">↵
```c++↵
#include <iostream>↵
#include <vector>↵
#include <algorithm>↵
using namespace std;↵
const int N = 1e6 + 10;↵
int n, a[N], t, res;↵
void run()↵
{↵
    scanf("%d", &n);↵
    for (int i = 1; i <= n; i++)↵
    {↵
        scanf("%d", a + i);↵
        for (int j = 1; j < a[i]; j++)↵
            scanf("%*d");↵
    }↵
    sort(a + 1, a + n + 1);↵
    t = 1;↵
    for (; t < a[n]; t = t * 2 + 1)↵
        ;↵
    res = 0;↵
    for (int i = n; i; i--)↵
    {↵
        while ((t > a[i]) or (t & res))↵
            t--;↵
        res |= t;↵
    }↵
    printf("%d\n", res);↵
}↵
int main()↵
{↵
    int T = 1;↵
    scanf("%d", &T);↵
    while (T--)↵
        run();↵
}↵
```↵
</spoiler>↵

## 6. After↵

![+117](https://images.cnblogs.com/cnblogs_com/blogs/816976/galleries/2400123/o_240719021741_%E5%B1%8F%E5%B9%95%E6%88%AA%E5%9B%BE%202024-07-19%20072249.png)↵

Man!↵

What can I say?↵

[user:74TrAkToR,2024-07-19] out!↵

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en7 Английский shiny_shine 2024-07-19 09:07:49 6
en6 Английский shiny_shine 2024-07-19 06:46:24 217
en5 Английский shiny_shine 2024-07-19 06:40:09 34
en4 Английский shiny_shine 2024-07-19 06:09:00 6 Tiny change: 'ty is $O(n)$.\n\n<s' -> 'ty is $O(n\log n)$.\n\n<s'
en3 Английский shiny_shine 2024-07-19 05:58:50 2 Tiny change: 'j>x$, add 将 $d_i+1$ t' -> 'j>x$, add $d_i+1$ t'
en2 Английский shiny_shine 2024-07-19 05:55:08 38
en1 Английский shiny_shine 2024-07-19 05:54:22 6611 Initial revision (published)