## 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 — 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↵
↵
↵
↵
Man!↵
↵
What can I say?↵
↵
[user:74TrAkToR,2024-07-19] out!↵
↵
[**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 — 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↵
↵
↵
↵
Man!↵
↵
What can I say?↵
↵
[user:74TrAkToR,2024-07-19] out!↵
