Codeworks round 740 Div. 2 problem solving Report

A. Simply Strange Sort

simulation
The question ：
Give you a length of $n$ ($n$<=1000 And $n$ Is odd ) Permutation ;
There's an operation , Definition No $i$ operations ：
If $i$ Is odd , For all odd positions $pos$($pos$<n), If The first $pos$ The bit is greater than the $pos$+1 position , Then exchange .
If $i$ It's even , Do the above operation for all even positions ;
After several operations , The whole sequence is orderly .
Ideas ：
Because of the $n$ Very small , For a number , He returned to his original position , At most $n$ operations , that $n$ Number , most $n²$ Time （ Although it is impossible to achieve ）.
Complexity ：O（ T * n * n );

#include<bits/stdc++.h>
using namespace std;

int n,m;
int s[1001]; 
int main(){
    
	int t;
	scanf("%d",&t);
	while(t--){
    
		int ans=0;
		scanf("%d",&n);
		for(int i=1;i<=n;i++){
    
			scanf("%d",&s[i]);
		}
		while(1){
    
			int f=1; 
			for(int i=1;i<=n;i++)
				if(s[i]!=i)f=0;
			if(f)break;
			ans++;
			if(ans%2==1){
    
				for(int i=1;i<n;i+=2){
    
					if(s[i]>s[i+1])swap(s[i],s[i+1]);
				}
			}else for(int i=2;i<n;i+=2){
    
				if(s[i]>s[i+1])swap(s[i],s[i+1]);
			}
		} 
		printf("%d\n",ans);
	}
	return 0;
}

B. Charmed by the Game

The question :
A game , Two people take turns to take the lead , I won't tell you who got the first hand in the first game . If the player wins a game, he will gain one point . Define a state as , The first player lost the game .
Tell you the scores of the last two players $a$ and $b$, Find out how many possible above states exist , Output all possible .
Ideas ：
Consider enumerating the different situations in which two people are first in the first game , We knew who was first in the first set , We know the number of the general administration that two people took the lead , If a Go first but score less than go first , Then we will know directly ,a At least you have to lose a few games if you take the lead . Then we can lose the first game by two people , Let each side win , This ensures that the score remains the same , Contribution to the number of states +2;
A special case ： The premise of the fake match is , I gave him less points than he did .
Then sort 、 duplicate removal 、 Just output .

#include<bits/stdc++.h>
using namespace std;

int n,m;
int s[1001]; 
vector<int>v;
int main(){
    
	int t;
	scanf("%d",&t);
	while(t--){
    
		int a,b;scanf("%d%d",&a,&b);
		n=a+b;
		v.clear();
		if(a==b){
    
			for(int i=0;i<=n;i+=2)
				v.push_back(i);
		}else{
    
			int p=n/2;
			int q=abs(p-a);
			int cnt=0;
			for(int i=q;i<=n;i+=2)
			{
    
				v.push_back(i);
				cnt++;
				if(cnt>min(a,b))break;
			}
			cnt=0;
			q=abs(p-b);
			for(int i=q;i<=n;i+=2)
			{
    
				v.push_back(i);
				cnt++;
				if(cnt>min(a,b))break;
			}	
		}
		sort(v.begin(),v.end());
		v.erase(unique(v.begin(),v.end()),v.end());
		printf("%d\n",v.size());
		for(int i=0;i<v.size();i++){
    
			printf("%d ",v[i]);
		}
		printf("\n");
	}
	return 0;
}

C. Deep Down Below

The question :
You are a hero , You have an attribute value ： Power . Monster has an attribute value ： Armor .
For a level , Heroes have n There are caves to choose from . To pass the level , The hero must enter all the caves in a certain order , Enter each cave only once , And leave every cave safely . When the hero enters the first hole , He will fight the monsters in order ： Each monster will have armor value $ai$;
If and only if the hero's strength is strictly greater than the monster's armor , Only heroes can defeat monsters . If the hero cannot defeat the monster he is fighting , Player loses .
Every time a hero defeats a monster , The power of heroes increases 1.
Find the minimum initial force , Enable to enter all caves in a certain order and defeat all monsters .
Ideas ：
We can pre process the minimum force that all caves can safely pass through .
Then sort and merge .（ If the initial forces of the two caves are the same , Then the power gain is the sum of the number of monsters in the two caves ）.
Then cover the caves with high requirements for strength to those with low requirements .
The final answer is right 0 take max.

#include<bits/stdc++.h>
using namespace std;

int n,m;
int s[100040]; 
int k[100040];
struct node{
    
	int w,num; 
}p[100040];
struct no{
    
	int val,cnt;
}w[100040];
int cnt=0;
map<int,int>mp;
bool cmp(node a,node b){
    
	return a.w<b.w;
}
int main(){
    
	int t;
	scanf("%d",&t);
	while(t--){
    
		int ans=0;
		cnt=0;
		mp.clear();
		scanf("%d",&n);
		for(int i=1;i<=n;i++){
    
			scanf("%d",&k[i]);
			int res=0;
			for(int j=1;j<=k[i];j++){
    
				scanf("%d",&s[j]);
				res=max(res,s[j]-j+2);
			}
			p[i].w=res;p[i].num=k[i];
		}
		sort(p+1,p+1+n,cmp);
		for(int i=1;i<=n;i++){
    
			if(!mp[p[i].w])mp[p[i].w]=++cnt;
			w[mp[p[i].w]].cnt+=p[i].num;
			w[mp[p[i].w]].val=p[i].w;
		}
		for(int i=cnt;i>1;i--){
    
			w[i-1].val=max(w[i-1].val,w[i].val-w[i-1].cnt);
		}
		ans=max(ans,w[1].val);
		printf("%d\n",ans);
		for(int i=1;i<=cnt;i++)w[i].cnt=0;
	}
	return 0;
}

D1. Up the Strip (simplified version)

The question ：
One 1*n The grid of , We started at n The location of , There are two ways to go in each step ：
Let's say it's in x Location
1. Walk forward 1 ~ x-1 Step ;
2. Select a z( 2 <= z <= x), Go to the x / z ( Rounding down );
Please go there 1 Number of schemes for location , Yes m modulus ;（ For the second operation , Different numbers are also considered as different operations ）;
Ideas ：
The obvious dp topic . For the first operation , Obviously , We can take all of $x+1$ ~ $n$ Turn around , It can be used Suffixes and Optimize dp;
Complex is the second operation , The complexity of violent words is $n^2$ Grade , be unable to do sth. .
But for $x/i$ （$2<=i<=x$） It has very beautiful properties , That's it $x/i$ Round down to 1~ Radical sign x Is a continuous , Then we can solve the inequality and get take 1 ~ Radical sign x The scope of the ; For others greater than the root x The situation of , We take it violently again 2 ~ Radical sign x To transfer .

ops;
harm , I thought of this method very early , Unfortunately, there is a variable in the middle long long , Judge whether it is greater than Radical sign x It blew up when I was , How angry ！ I really want to score .

#include<bits/stdc++.h>
using namespace std;
#define ll long long

ll n,m;
ll dp[200050];
ll sum=0;
int main(){
    
	scanf("%lld%lld",&n,&m);
	dp[n]=1;
	for(int i=n;i>=1;i--){
    
		dp[i]+=sum;
		dp[i]%=m;
		ll l=2,r=i;
		ll cnt=2;
		while(l<r){
    
			ll pos=i/cnt;
			while(pos>=r){
    
				cnt++;
				pos=i/cnt;
			}
			cnt++;
			pos++;
			while(pos<r&&((i/pos) != (i/r) ))
				pos++;
			dp[i/r]+=1LL*(r-pos+1)*dp[i];
			dp[i/r]%=m;
			r=pos-1;
			if(r*r<=i)break;
		}
		for(int j=2;j<=r;j++){
    
			dp[i/j]+=dp[i]; 
			dp[i/j]%=m;
		}
		sum+=dp[i];
		sum%=m;
	}
	printf("%lld\n",dp[1]);
	return 0;
}

D2. Up the Strip

The question ：
This question is an enhanced version of the previous one ,
$n<=4e6$
Ideas ：
Calculate the complexity , The transfer of this problem to the second operation is limited to log Class , It is not very thoughtful yet , Make up tomorrow ;

updated:
It used to enumerate multiple times of a number , Complexity is $nlogn$ Of , I thought in this direction during the game , But it won't be complicated. I gave up the idea .
First ,D1 Our approach is to enumerate the factors and then move down .
namely $i<=x/j<i+1$;
We think from the bottom up .
First, for the first operation , We still use suffixes and optimizations ;

Transformation inequality , It becomes $i\ast j<=x<i\ast j+j$;
For the second operation , We found that for a $i$ We can enumerate its multiples $j$, This confirms $i$ and $j$, We know the range he can transfer . Because he can learn from $i\ast jTo$$i\ast j+j$ Turn around , We can do this with a suffix and an array .
Remember the back endpoint and $n+1$ take min;
Happy ac.

#include<bits/stdc++.h>
using namespace std;
#define ll long long

ll n,m;
ll dp[4000050];
ll sum[4000050];
int main(){
    
	scanf("%lld%lld",&n,&m);
	dp[n]=1;
	sum[n+1]=0;
	for(ll i=n;i>=1;--i){
    
		dp[i]+=sum[i+1];
		dp[i]%=m;
		for(ll j=2;j*i<=n;++j){
    
			ll l=j*i;
			ll r=min(j*i+j,n+1);
			dp[i]+=(sum[l]-sum[r]);
			dp[i]%=m; 
		}
		sum[i]=sum[i+1]+dp[i];
		sum[i]%=m;
	}
	printf("%lld\n",dp[1]);
	return 0;
}

E. Bottom-Tier Reversals

The question :
Here's an arrangement for you , Each time you can select an odd number of end positions pos , Make 1 To pos Position flip . Ask if you can be in $5\ast n/2$ To make a sequence of numbers in order . Output the scheme if possible , If not, output -1.
Ideas ：
I glanced at the topic , The feeling is that the adjacent odd numbers and even numbers should be considered together , Because the right end of our flip can only be an odd number , That means , An even number wants to go to an even number , Then we must ensure that he and his next one are posted . Make up tomorrow （ If there's a chance

ops:
At first sight, I thought it was a bare problem of balanced tree , Abominable , Section reversal is not a random maintenance , Unfortunately, there are limitations .