Codeforces Round #740 (Div. 2, based on VK Cup 2021 - Final (Engine))
Codeforces Round #740 (Div. 2, based on VK Cup 2021 - Final (Engine))(https://codeforces.com/contest/1561)
一边被折磨一边打代码
A. Simply Strange Sort (https://codeforces.com/contest/1561/problem/A)
You have a permutation: an array a=[a1,a2,…,an] of distinct integers from 1 to n. The length of the permutation n is odd.
Consider the following algorithm of sorting the permutation in increasing order.
A helper procedure of the algorithm, f(i), takes a single argument i (1≤i≤n−1) and does the following. If ai>ai+1, the values of ai and ai+1 are exchanged. Otherwise, the permutation doesn’t change.
The algorithm consists of iterations, numbered with consecutive integers starting with 1. On the i-th iteration, the algorithm does the following:
if i is odd, call f(1),f(3),…,f(n−2);
if i is even, call f(2),f(4),…,f(n−1).
It can be proven that after a finite number of iterations the permutation will be sorted in increasing order.
After how many iterations will this happen for the first time?
Input
Each test contains multiple test cases. The first line contains the number of test cases t (1≤t≤100). Description of the test cases follows.
The first line of each test case contains a single integer n (3≤n≤999; n is odd) — the length of the permutation.
The second line contains n distinct integers a1,a2,…,an (1≤ai≤n) — the permutation itself.
It is guaranteed that the sum of n over all test cases does not exceed 999.
Output
For each test case print the number of iterations after which the permutation will become sorted in increasing order for the first time.
If the given permutation is already sorted, print 0.
Example
inputCopy
3
3
3 2 1
7
4 5 7 1 3 2 6
5
1 2 3 4 5
outputCopy
3
5
0
Note
In the first test case, the permutation will be changing as follows:
after the 1-st iteration: [2,3,1];
after the 2-nd iteration: [2,1,3];
after the 3-rd iteration: [1,2,3].
In the second test case, the permutation will be changing as follows:
after the 1-st iteration: [4,5,1,7,2,3,6];
after the 2-nd iteration: [4,1,5,2,7,3,6];
after the 3-rd iteration: [1,4,2,5,3,7,6];
after the 4-th iteration: [1,2,4,3,5,6,7];
after the 5-th iteration: [1,2,3,4,5,6,7].
In the third test case, the permutation is already sorted and the answer is 0.
题意：给定一个有偶数个数的序列，定义一个函数f(i),函数功能是：如果a[i]>a[i+1]交换二者的值，否则不操作，现在问你经过几次迭代能让数组升序排列。在第i次迭代时，若i是奇数，调用f(1),f(3),…,f(n-2)相反调用f(2),f(4),…,f(n−1).
n的范围很小，直接On^2模拟就行
AC代码：
#include <bits/stdc++.h>
using namespace std;
#define reset(x) memset(x, 0, sizeof(x))
#define Q_in_out \
ios::sync_with_stdio(false); \
cin.tie(0); \
cout.tie(0);
typedef long long int ll;
typedef long double ld;
typedef pair<int, int> P;
#define forl(l,r) for(int i=l;i<r;i++)
#define forr(r,l) for(int i=r;i>=l;i--)
const int N = 1e5+5;
const int modp = 1e9+7;
const int inf = 0x3f3f3f3f;
const double eps = 1e-6;
const double pi = acos(-1.0);
const double e = 2.718281828459045;
int solve()
{
int n;
cin>>n;
int a[1000];
for(int i=1;i<=n;i++) cin>>a[i];
int res=0;
for(int i=1;i<=n;i++){
int f=0;
for(int k=1;k<n;k++) if(a[k]>a[k+1]){f=1;break;}
if(!f) break;
int j=(i%2==0?2:1);
for(;j<n;j+=2)
if(a[j]>a[j+1]) swap(a[j],a[j+1]);
res++;
}
cout<<res;
return 0;
}
int main()
{
Q_in_out;
int t;
t = 1;
cin >> t;
while (t--)
{
solve();
cout<<endl;
}
return 0;
}
B. Charmed by the Game(https://codeforces.com/contest/1561/problem/B)
Alice and Borys are playing tennis.
A tennis match consists of games. In each game, one of the players is serving and the other one is receiving.
Players serve in turns: after a game where Alice is serving follows a game where Borys is serving, and vice versa.
Each game ends with a victory of one of the players. If a game is won by the serving player, it’s said that this player holds serve. If a game is won by the receiving player, it’s said that this player breaks serve.
It is known that Alice won a games and Borys won b games during the match. It is unknown who served first and who won which games.
Find all values of k such that exactly k breaks could happen during the match between Alice and Borys in total.
Input
Each test contains multiple test cases. The first line contains the number of test cases t (1≤t≤103). Description of the test cases follows.
Each of the next t lines describes one test case and contains two integers a and b (0≤a,b≤105; a+b>0) — the number of games won by Alice and Borys, respectively.
It is guaranteed that the sum of a+b over all test cases does not exceed 2⋅105.
Output
For each test case print two lines.
In the first line, print a single integer m (1≤m≤a+b+1) — the number of values of k such that exactly k breaks could happen during the match.
In the second line, print m distinct integers k1,k2,…,km (0≤k1<k2<…<km≤a+b) — the sought values of k in increasing order.
Example
inputCopy
3
2 1
1 1
0 5
outputCopy
4
0 1 2 3
2
0 2
2
2 3
Note
In the first test case, any number of breaks between 0 and 3 could happen during the match:
Alice holds serve, Borys holds serve, Alice holds serve: 0 breaks;
Borys holds serve, Alice holds serve, Alice breaks serve: 1 break;
Borys breaks serve, Alice breaks serve, Alice holds serve: 2 breaks;
Alice breaks serve, Borys breaks serve, Alice breaks serve: 3 breaks.
In the second test case, the players could either both hold serves (0 breaks) or both break serves (2 breaks).
In the third test case, either 2 or 3 breaks could happen:
Borys holds serve, Borys breaks serve, Borys holds serve, Borys breaks serve, Borys holds serve: 2 breaks;
Borys breaks serve, Borys holds serve, Borys breaks serve, Borys holds serve, Borys breaks serve: 3 breaks.
题意：A和B打球，两个人轮流发球(我们不知道谁先发第一局的球，两人都可能发第一局的球)，如果某个人发球但对手赢得比赛就记作对手打破发球(breaks serve)…例如:当前是A发球，如果A赢了比赛就什么也不记，但如果B赢了就说B breaks serve…,总之，给定你A、B赢得的比赛数，让你推测有多少种可能的breaks serve的数量，例如样例中：A赢了两场，B赢了一场，总共进行三次比赛，我们假设A先发第一局的球，那么三局游戏的发球顺序为：ABA，且A赢了两场,假设AB获胜顺序为ABA，根据定义，就没有breaks，因此一种可能的结果为0，若获胜顺序为AAB，则第二场和第三场各有一次breaks，总共为2，依次类推，最终发现有0，1，2，3四种可能。
了解题意后我们可以进行假设，现在，假设A赢了a场，B赢了b场，并且我们假设A先发球(情况和B先发球是对称的)，那么我们可以计算出A和B发球的场数，假设a+b是偶数，那么两个人一人各发了(a+b)/2场，如果a+b是奇数，那么A发了(a+b+1)/2,B发了(a+b-1)/2场，为了方便打代码我们把奇偶两种情况用取整统一起来，即假设A发了p次，B发了q次,p=ceil((a+b)/2.0),q=(a+b)/2(int下取整后的结果)；现在我们来计算可能的breaks数量，假设A所有发球的比赛里有x次breaks(p次里B赢了x次)，B有y次breaks(q次里A赢了y次),那么有a=(p-x)+y,根据我们上面的定义，0<=x<=p，0<=y<=q，由于p<a+b<=2e5,我们就可以枚举所有的x,且y=a-(p-x),当我们发现计算出的y处于[0,q]的范围里时，证明这对x,y是可能的，那么x+y就是一个可能的值，同时，B先发第一局球时情况会与此相反，因此a+b-(x+y)也是一种可能的值。
AC代码：
#include <bits/stdc++.h>
using namespace std;
#define reset(x) memset(x, 0, sizeof(x))
#define Q_in_out \
ios::sync_with_stdio(false); \
cin.tie(0); \
cout.tie(0);
typedef long long int ll;
typedef long double ld;
typedef pair<int, int> P;
#define forl(l,r) for(int i=l;i<r;i++)
#define forr(r,l) for(int i=r;i>=l;i--)
const int N = 1e5+5;
const int modp = 1e9+7;
const int inf = 0x3f3f3f3f;
const double eps = 1e-6;
const double pi = acos(-1.0);
const double e = 2.718281828459045;
int solve()
{
int a,b;
cin>>a>>b;
set<int>res;
int p,q;
p=ceil((a+b)*1.0/2.0);
q=(a+b)/2;
for(int i=0;i<=p;i++){
int j=a-(p-i);
if(j>=0&&j<=q) {
res.insert(i+j);
res.insert(a+b-i-j);
}
}
cout<<res.size()<<endl;
for(auto &v:res) cout<<v<<' ';
return 0;
}
int main()
{
Q_in_out;
int t;
t = 1;
cin >> t;
while (t--)
{
solve();
cout<<endl;
}
return 0;
}
C. Deep Down Below(https://codeforces.com/contest/1561/problem/C)
In a certain video game, the player controls a hero characterized by a single integer value: power. The hero will have to beat monsters that are also characterized by a single integer value: armor.
On the current level, the hero is facing n caves. To pass the level, the hero must enter all the caves in some order, each cave exactly once, and exit every cave safe and sound. When the hero enters cave i, he will have to fight ki monsters in a row: first a monster with armor ai,1, then a monster with armor ai,2 and so on, finally, a monster with armor ai,ki.
The hero can beat a monster if and only if the hero’s power is strictly greater than the monster’s armor. If the hero can’t beat the monster he’s fighting, the game ends and the player loses. Note that once the hero enters a cave, he can’t exit it before he fights all the monsters in it, strictly in the given order.
Each time the hero beats a monster, the hero’s power increases by 1.
Find the smallest possible power the hero must start the level with to be able to enter all the caves in some order and beat all the monsters.
Input
Each test contains multiple test cases. The first line contains the number of test cases t (1≤t≤105). Description of the test cases follows.
The first line of each test case contains a single integer n (1≤n≤105) — the number of caves.
The i-th of the next n lines contains an integer ki (1≤ki≤105) — the number of monsters in the i-th cave, followed by ki integers ai,1,ai,2,…,ai,ki (1≤ai,j≤109) — armor levels of the monsters in cave i in order the hero has to fight them.
It is guaranteed that the sum of ki over all test cases does not exceed 105.
Output
For each test case print a single integer — the smallest possible power the hero must start the level with to be able to enter all the caves in some order and beat all the monsters.
Example
inputCopy
2
1
1 42
2
3 10 15 8
2 12 11
outputCopy
43
13
Note
In the first test case, the hero has to beat a single monster with armor 42, it’s enough to have power 43 to achieve that.
In the second test case, the hero can pass the level with initial power 13 as follows:
enter cave 2:
beat a monster with armor 12, power increases to 14;
beat a monster with armor 11, power increases to 15;
enter cave 1:
beat a monster with armor 10, power increases to 16;
beat a monster with armor 15, power increases to 17;
beat a monster with armor 8, power increases to 18.
题意：
有n个洞穴，每个洞穴里有k只怪兽，并且给出k只怪兽的战力值，只有当英雄的战力值大于怪兽时才能打败怪兽，并且每当打败一只怪兽，英雄战力值加1，现在，在不改变每个洞穴里怪兽顺序前提下，可以任意选择进入n个洞穴的顺序，问英雄的起始战力值最低为多少才能通过所有的洞穴，并打败所有怪兽。
先单独考虑每个洞穴i我们所需要的最低战力bi,对于一个洞穴，我们假设所需战力为x,那么必有x>a[1],x+1>a[2],…,x+k-1>a[k],变一下形得到：
x>a[1],x>a[2]-1,…,x>a[k]-k+1,这个不等式与:x>max(a[1],a[2]-1,…,a[k]-k+1)是等价的，也即是说对于每个洞穴i来说，最小战力bi>max(a[1],a[2]-1,…,a[k]-k+1);我们再来考虑整体的洞穴情况，假设整体情况下需要战力为x,由于每通过一个洞穴i，战力值会增长ki,那么有x>b[1],x+k1>b[2],x+k1+k2>b[3],…,变形后有：
x>b[1],x>b[2]-k1,x>b[3]-k1-k2…,与单个洞穴类似,上式等于:
x>max(b[1],b[2]-k1,b[3]-k1-k2…);现在，假若我们知道洞穴的进入顺序后，就能根据上面两个式子求出最小战力值，观察式子：
x>max(b[1],b[2]-k1,b[3]-k1-k2…)，要想让最大值最小，由于，k[i]是常数，于是我们让大的b[i]尽量靠后，因此我们对洞穴排序，先进b[i]小的洞穴就能保证最终解最小。
AC代码：
#include <bits/stdc++.h>
using namespace std;
#define reset(x) memset(x, 0, sizeof(x))
#define Q_in_out \
ios::sync_with_stdio(false); \
cin.tie(0); \
cout.tie(0);
typedef long long int ll;
typedef long double ld;
typedef pair<int, int> P;
#define forl(l,r) for(int i=l;i<r;i++)
#define forr(r,l) for(int i=r;i>=l;i--)
const int N = 3e5+5;
const int modp = 1e9+7;
const int inf = 0x3f3f3f3f;
const double eps = 1e-6;
const double pi = acos(-1.0);
const double e = 2.718281828459045;
int solve()
{
int n;
cin>>n;
vector<pair<int,int>>all;
while (n--)
{
int k;
cin>>k;
int b=-inf,a;
for(int i=0;i<k;i++){
cin>>a;
b=max(b,a-i);
}
all.push_back({b,k});
}
sort(all.begin(),all.end());
int res=-inf,s=0;
for(auto &v:all){
int b=v.first;
int k=v.second;
res=max(b-s,res);
s+=k;
}
cout<<res+1; //要严格大于怪兽战力值，因此得+1
return 0;
}
int main()
{
Q_in_out;
int t;
t = 1;
cin >> t;
while (t--)
{
solve();
cout<<endl;
}
return 0;
}
D1. Up the Strip (simplified version)(https://codeforces.com/contest/1561/problem/D1)
This version of the problem differs from the next one only in the constraint on n.
Note that the memory limit in this problem is lower than in others.
You have a vertical strip with n cells, numbered consecutively from 1 to n from top to bottom.
You also have a token that is initially placed in cell n. You will move the token up until it arrives at cell 1.
Let the token be in cell x>1 at some moment. One shift of the token can have either of the following kinds:
Subtraction: you choose an integer y between 1 and x−1, inclusive, and move the token from cell x to cell x−y.
Floored division: you choose an integer z between 2 and x, inclusive, and move the token from cell x to cell ⌊xz⌋ (x divided by z rounded down).
Find the number of ways to move the token from cell n to cell 1 using one or more shifts, and print it modulo m. Note that if there are several ways to move the token from one cell to another in one shift, all these ways are considered distinct (check example explanation for a better understanding).
Input
The only line contains two integers n and m (2≤n≤2⋅105; 108<m<109; m is a prime number) — the length of the strip and the modulo.
Output
Print the number of ways to move the token from cell n to cell 1, modulo m.
Examples
inputCopy
3 998244353
outputCopy
5
inputCopy
5 998244353
outputCopy
25
inputCopy
42 998244353
outputCopy
793019428
Note
In the first test, there are three ways to move the token from cell 3 to cell 1 in one shift: using subtraction of y=2, or using division by z=2 or z=3.
There are also two ways to move the token from cell 3 to cell 1 via cell 2: first subtract y=1, and then either subtract y=1 again or divide by z=2.
Therefore, there are five ways in total.
题意：给定n，m，每次可以将n减去[1,n-1]的任意一个数或者将n除以一个[2,n]的任意一个数，然后将n变成操作后的值，问总共有多少种方案能将n变为1,最终输出模m的结果；
首先我们先考虑最朴素的转移方程，f[i]表示从i变到1的总方案数，有：f[1]=1,f[i]=f[i-j](1<=j<=i-1)+f[floor(i/j)](2<=j<=i),直接暴力计算的话复杂度是On^2,我们观察转移方程的第一部分：f[i-j](1<=j<=i-1),对于任意n有f[n]=f[n-1]+f[n-2]+…f[1]，这提示我们这部分的结果我们可以用前缀和保存下来，再看转移方程第二部分：f[floor(i/j)](2<=j<=i)，
我们不必要将j从2遍历到i，容易发现，当j<sqrt(i)时，我们只可能有一种方案除以某一个数得到i/j，例如假设n=128,我们可以且只能通过除以9下取整得到14，因此只用将f[14]的值加入f[128]中即可，
当j>=sqrt(i)时，例如n等于128，我们可以通过除以13或者14得到9，共两种方案可以到达9，也即是说我们需要将2*f[9]加入到f[128]当中，至于f[9]前面的系数2我们可以用O(1)的时间计算得出，总共时间复杂度为On^(3/2).
AC代码：
#include <bits/stdc++.h>
using namespace std;
#define reset(x) memset(x, 0, sizeof(x))
#define Q_in_out \
ios::sync_with_stdio(false); \
cin.tie(0); \
cout.tie(0);
typedef long long int ll;
typedef long double ld;
typedef pair<int, int> P;
#define forl(l,r) for(int i=l;i<r;i++)
#define forr(r,l) for(int i=r;i>=l;i--)
const int N = 2e5+5;
const int modp = 1e9+7;
const int inf = 0x3f3f3f3f;
const double eps = 1e-6;
const double pi = acos(-1.0);
const double e = 2.718281828459045;
int n,m;
ll f[N];
int solve()
{
cin>>n>>m;
f[1]=1;f[2]=2;
ll s=f[1]+f[2];
for(int i=3;i<=n;i++){
f[i]=s; //通过减掉某一个数可能得到的方案数
//通过除以某个数可能得到的方案数
for(int j=2;j*j<=i;j++) { //小于sqrt(i)的情况
if(i/j>j)
f[i]=(f[i/j]+f[i])%m;
}
//为了便于理解，我将上下两个循环拆开来写了
for(int j=1;j*j<=i;j++){ //大于等于sqrt(i)的情况
f[i]+=(i/j-(i/(j+1)+1)+1)*f[j]; //系数：(i/j-(i/(j+1)+1)+1)
f[i]%=m;
}
//更新前缀
s=(f[i]+s)%m;
}
cout<<f[n];
return 0;
}
int main()
{
Q_in_out;
int t;
t = 1;
// cin >> t;
while (t--)
{
solve();
cout<<endl;
}
return 0;
}
D2. Up the Strip(https://codeforces.com/contest/1561/problem/D2)
本题是上一题的困难版本，上题里On^(3/2)的复杂度不能在本题通过了，我们换一个方向思考转移方程，f[i]相对于f[i-1]会多出一个f[i-1]和一个f[1]两种状态，因为可以有i-1和i/i两个操作;
也即有f[i]+=f[i-1]+f[i-1]+f[1];而对于其他的状态(除法的部分)，通过几个样例：
3：1 1
4：1 1 2
5：1 1 1 2
6：1 1 1 2 3
7：1 1 1 1 2 3
8：1 1 1 1 2 3 4
9：1 1 1 1 1 2 3 4
发现对于一个i来说，相比于i-1，i的所有因数会多出来一个状态。综合上面所述，i的状态比i-1多出来一个f[i]、f[1]、f[j]-f[j-1]，其中j是i的所有因数；由于空间限制我们不把因数存下来，而是在计算的过程中提前将结果更新到f[i*j]中。
AC代码：
#include <bits/stdc++.h>
using namespace std;
#define reset(x) memset(x, 0, sizeof(x))
#define Q_in_out \
ios::sync_with_stdio(false); \
cin.tie(0); \
cout.tie(0);
typedef long long int ll;
typedef long double ld;
typedef pair<int, int> P;
#define forl(l,r) for(int i=l;i<r;i++)
#define forr(r,l) for(int i=r;i>=l;i--)
const int N = 4e6+5;
const int modp = 1e9+7;
const int inf = 0x3f3f3f3f;
const double eps = 1e-6;
const double pi = acos(-1.0);
const double e = 2.718281828459045;
int n,m;
ll f[N];
int solve()
{
cin>>n>>m;
f[1]=1;f[2]=2;
for(int i=2;i*2<=n;i++) f[i*2]++; //2的倍数特殊处理
for(int i=3;i<=n;i++){
f[i]=(f[i]+2*f[i-1]+1)%m;
for(int j=2;j*i<=n;j++) f[j*i]=(f[j*i]+f[i]-f[i-1]+m)%m;
}
cout<<f[n];
return 0;
}
int main()
{
Q_in_out;
int t;
t = 1;
// cin >> t;
while (t--)
{
solve();
cout<<endl;
}
return 0;
}