Codeforces Round #555 (Div. 3)

由 Edwiv 发布于  ｜  51,249次浏览

A. Reachable Numbers

time limit per test1 second . memory limit per test256 megabytes

Let's denote a function ?(?)f(x) in such a way: we add 11 to ?x, then, while there is at least one trailing zero in the resulting number, we remove that zero. For example,

  • ?(599)=6f(599)=6: 599+1=600→60→6599+1=600→60→6;
  • ?(7)=8f(7)=8: 7+1=87+1=8;
  • ?(9)=1f(9)=1: 9+1=10→19+1=10→1;
  • ?(10099)=101f(10099)=101: 10099+1=10100→1010→10110099+1=10100→1010→101.

We say that some number ?y is reachable from ?x if we can apply function ?f to ?x some (possibly zero) times so that we get ?y as a result. For example, 102102 is reachable from 1009810098 because ?(?(?(10098)))=?(?(10099))=?(101)=102f(f(f(10098)))=f(f(10099))=f(101)=102; and any number is reachable from itself.

You are given a number ?n; your task is to count how many different numbers are reachable from ?n.Input

The first line contains one integer ?n (1≤?≤1091≤n≤109).Output

Print one integer: the number of different numbers that are reachable from ?n.
Examples
input

1098

output

20

input

10

output

19

Note

The numbers that are reachable from 10981098 are:

1,2,3,4,5,6,7,8,9,11,12,13,14,15,16,17,18,19,1098,10991,2,3,4,5,6,7,8,9,11,12,13,14,15,16,17,18,19,1098,1099.

模拟题，签到；注意处理n本来就是10的倍数的情况

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
const int maxn=(int)1e5+100;
int main(){
	int n,ans=9;cin>>n;
	if(n%10==0) ans++,n++;
	while(n>=10){
		ans++,n++;
		while(n%10==0) n/=10;
	}
	cout<<ans<<endl;
}

B. Long Number

time limit per test2 seconds memory limit per test256 megabytes

You are given a long decimal number ?a consisting of ?n digits from 11 to 99. You also have a function ?f that maps every digit from 11 to 99 to some (possibly the same) digit from 11 to 99.

You can perform the following operation no more than once: choose a non-empty contiguous subsegment of digits in ?a, and replace each digit ?x from this segment with ?(?)f(x). For example, if ?=1337a=1337, ?(1)=1f(1)=1, ?(3)=5f(3)=5, ?(7)=3f(7)=3, and you choose the segment consisting of three rightmost digits, you get 15531553 as the result.

What is the maximum possible number you can obtain applying this operation no more than once?Input

The first line contains one integer ?n (1≤?≤2⋅1051≤n≤2⋅105) — the number of digits in ?a.

The second line contains a string of ?n characters, denoting the number ?a. Each character is a decimal digit from 11 to 99.

The third line contains exactly 99 integers ?(1)f(1), ?(2)f(2), ..., ?(9)f(9) (1≤?(?)≤91≤f(i)≤9).Output

Print the maximum number you can get after applying the operation described in the statement no more than once.
Examples
input

4 
1337 
1 2 5 4 6 6 3 1 9

output

1557

input

5 
11111 
9 8 7 6 5 4 3 2 1

output

99999

input

2 
33 
1 1 1 1 1 1 1 1 1

output

33

贪心模拟

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
const int maxn=(int)1e5+100;
int main(){
	int n;cin>>n;
	string s;cin>>s;
	int a[10];rep(i,1,9) cin>>a[i];
	int flag=0;
	for(int i=0;i<n;++i){
		int num=s[i]-'0';
		if(flag==0){
			if(a[num]>num){flag=1;s[i]=a[num]+'0';}
		}
		else{
			if(a[num]<num) break;
			else s[i]=a[num]+'0';
		}
	}
	cout<<s<<endl;
}

C1. Increasing Subsequence (easy version)

time limit per test2 seconds memory limit per test256 megabytes

The only difference between problems C1 and C2 is that all values in input of problem C1 are distinct (this condition may be false for problem C2).

You are given a sequence ?a consisting of ?n integers. All these integers are distinct, each value from 11 to ?n appears in the sequence exactly once.

You are making a sequence of moves. During each move you must take either the leftmost element of the sequence or the rightmost element of the sequence, write it down and remove it from the sequence. Your task is to write down a strictly increasing sequence, and among all such sequences you should take the longest (the length of the sequence is the number of elements in it).

For example, for the sequence [2,1,5,4,3][2,1,5,4,3] the answer is 44 (you take 22 and the sequence becomes [1,5,4,3][1,5,4,3], then you take the rightmost element 33 and the sequence becomes [1,5,4][1,5,4], then you take 44 and the sequence becomes [1,5][1,5] and then you take 55 and the sequence becomes [1][1], the obtained increasing sequence is [2,3,4,5][2,3,4,5]).Input

The first line of the input contains one integer ?n (1≤?≤2⋅1051≤n≤2⋅105) — the number of elements in ?a.

The second line of the input contains ?n integers ?1,?2,…,??a1,a2,…,an (1≤??≤?1≤ai≤n), where ??ai is the ?i-th element of ?a. All these integers are pairwise distinct.Output

In the first line of the output print ?k — the maximum number of elements in a strictly increasing sequence you can obtain.

In the second line print a string ?s of length ?k, where the ?j-th character of this string ??sj should be 'L' if you take the leftmost element during the ?j-th move and 'R' otherwise. If there are multiple answers, you can print any.
Examples
input

5 
2 1 5 4 3

output

4
LRRR

input

7 
1 3 5 6 7 4 2

output

7
LRLRLLL

input

3 
1 2 3

output

3
LLL

input

4 
1 2 4 3

output

4
LLRL

Note

The first example is described in the problem statement.

C2. Increasing Subsequence (hard version)

time limit per test2 seconds memory limit per test256 megabytes

The only difference between problems C1 and C2 is that all values in input of problem C1 are distinct (this condition may be false for problem C2).

You are given a sequence ?a consisting of ?n integers.

You are making a sequence of moves. During each move you must take either the leftmost element of the sequence or the rightmost element of the sequence, write it down and remove it from the sequence. Your task is to write down a strictly increasing sequence, and among all such sequences you should take the longest (the length of the sequence is the number of elements in it).

For example, for the sequence [1,2,4,3,2][1,2,4,3,2] the answer is 44 (you take 11 and the sequence becomes [2,4,3,2][2,4,3,2], then you take the rightmost element 22 and the sequence becomes [2,4,3][2,4,3], then you take 33 and the sequence becomes [2,4][2,4] and then you take 44 and the sequence becomes [2][2], the obtained increasing sequence is [1,2,3,4][1,2,3,4]).Input

The first line of the input contains one integer ?n (1≤?≤2⋅1051≤n≤2⋅105) — the number of elements in ?a.

The second line of the input contains ?n integers ?1,?2,…,??a1,a2,…,an (1≤??≤2⋅1051≤ai≤2⋅105), where ??ai is the ?i-th element of ?a.Output

In the first line of the output print ?k — the maximum number of elements in a strictly increasing sequence you can obtain.

In the second line print a string ?s of length ?k, where the ?j-th character of this string ??sj should be 'L' if you take the leftmost element during the ?j-th move and 'R' otherwise. If there are multiple answers, you can print any.
Examples
input

5 
1 2 4 3 2

output

4
LRRR

input

7 
1 3 5 6 5 4 2

output

6
LRLRRR

input

3 
2 2 2

output

1
R

input

4 
1 2 4 3

output

4
LLRR

Note

The first example is described in the problem statement.

贪心的想，每次取走两边可以取的最小的那个数，然后如果两边数字一样的话，那么选择一边之后另外一边必定不能再走了，所以此时只要判断哪边能走的最长就可以了

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
const int maxn=(int)2e5+100;
int a[maxn];
int main(){
	int n;cin>>n; rep(i,1,n) scanf("%d",&a[i]);
	vector<char> ans;ans.clear();
	int l=1,r=n,pre=-1;
	while(1){
		if(l==r){if(a[l]>pre) ans.pb('L');break;}
		if(a[l]<a[r]){
			if(pre==-1){ans.pb('L');pre=a[l];l++;continue;}
			if(a[r]<=pre) break;
			else if(a[l]<=pre){ans.pb('R');pre=a[r];r--;}
			else {ans.pb('L');pre=a[l];l++;}
		}
		else if(a[l]>a[r]){
			if(pre==-1){ans.pb('R');pre=a[r];r--;continue;}
			if(a[l]<=pre) break;
			else if(a[r]<=pre){ans.pb('L');pre=a[l];l++;}
			else {ans.pb('R');pre=a[r];r--;}
		}
		else{
			if(a[l]<=pre) break;
			int st1=1,st2=1,pre1=a[l],pre2=a[r];
			int lt=l+1,rt=r-1;
			while(a[lt]>pre1&&lt<=n){pre1=a[lt];lt++;st1++;}
			while(a[rt]>pre2&&rt>=1){pre2=a[rt];rt--;st2++;}
			if(st1>=st2) rep(i,1,st1) ans.pb('L');
			else rep(i,1,st2) ans.pb('R');
			break;
		}
	}
	cout<<ans.size()<<endl;
	for(int i=0;i<ans.size();++i) printf("%c",ans[i]);
}

D. N Problems During K Days

time limit per test1 second memory limit per test256 megabytes

Polycarp has to solve exactly ?n problems to improve his programming skill before an important programming competition. But this competition will be held very soon, most precisely, it will start in ?k days. It means that Polycarp has exactly ?k days for training!

Polycarp doesn't want to procrastinate, so he wants to solve at least one problem during each of ?k days. He also doesn't want to overwork, so if he solves ?x problems during some day, he should solve no more than 2?2x problems during the next day. And, at last, he wants to improve his skill, so if he solves ?x problems during some day, he should solve at least ?+1x+1 problem during the next day.

More formally: let [?1,?2,…,??][a1,a2,…,ak] be the array of numbers of problems solved by Polycarp. The ?i-th element of this array is the number of problems Polycarp solves during the ?i-th day of his training. Then the following conditions must be satisfied:

  • sum of all ??ai for ?i from 11 to ?k should be ?n;
  • ??ai should be greater than zero for each ?i from 11 to ?k;
  • the condition ??<??+1≤2??ai<ai+1≤2ai should be satisfied for each ?i from 11 to ?−1k−1.

Your problem is to find any array ?a of length ?k satisfying the conditions above or say that it is impossible to do it.Input

The first line of the input contains two integers ?n and ?k (1≤?≤109,1≤?≤1051≤n≤109,1≤k≤105) — the number of problems Polycarp wants to solve and the number of days Polycarp wants to train.Output

If it is impossible to find any array ?a of length ?k satisfying Polycarp's rules of training, print "NO" in the first line.

Otherwise print "YES" in the first line, then print ?k integers ?1,?2,…,??a1,a2,…,ak in the second line, where ??ai should be the number of problems Polycarp should solve during the ?i-th day. If there are multiple answers, you can print any.
Examples
input

26 6

output

YES 
1 2 4 5 6 8

input

8 3

output

NO

input

1 1

output

YES 
1

input

9 4

output

NO

首先特判一下NO的情况，发现只有在题目数比等差数列和还小或者n=8&&k=3||n=4&&k=2的情况才是NO，其他情况都可以
之后只要构造一个等差数列然后不断从后往前填数就可以了

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
const int maxn=(int)1e5+100;
int main(){
	ll n,k,a[maxn];cin>>n>>k;
	if(k==1){cout<<"YES\n"<<n<<endl;exit(0);}
	rep(i,1,k) {a[i]=i;n-=i;}
    if(n<0||(n==2&&k==3)||(n==1&&k==2)){cout<<"NO\n";exit(0);}
    ll t=n/k;n-=t*k; rep(i,1,k) a[i]+=t;
	while(n){
		for(int i=k;i>=1;--i){
			if(i==1||a[i]+1<=a[i-1]*2) a[i]++,n--;
			else break;
			if(n==0) break;
		}
	}
	cout<<"YES\n";
	for(int i=1;i<=k;++i) printf(i==1?"%lld":" %lld",a[i]);
	
}

E. Minimum Array

time limit per test2 seconds memory limit per test256 megabytes

You are given two arrays ?a and ?b, both of length ?n. All elements of both arrays are from 00 to ?−1n−1.

You can reorder elements of the array ?b (if you want, you may leave the order of elements as it is). After that, let array ?c be the array of length ?n, the ?i-th element of this array is ??=(??+??)%?ci=(ai+bi)%n, where ?%?x%y is ?x modulo ?y.

Your task is to reorder elements of the array ?b to obtain the lexicographically minimum possible array ?c.

Array ?x of length ?n is lexicographically less than array ?y of length ?n, if there exists such ?i (1≤?≤?1≤i≤n), that ??<??xi<yi, and for any ?j (1≤?<?1≤j<i) ??=??xj=yj.Input

The first line of the input contains one integer ?n (1≤?≤2⋅1051≤n≤2⋅105) — the number of elements in ?a, ?b and ?c.

The second line of the input contains ?n integers ?1,?2,…,??a1,a2,…,an (0≤??<?0≤ai<n), where ??ai is the ?i-th element of ?a.

The third line of the input contains ?n integers ?1,?2,…,??b1,b2,…,bn (0≤??<?0≤bi<n), where ??bi is the ?i-th element of ?b.Output

Print the lexicographically minimum possible array ?c. Recall that your task is to reorder elements of the array ?b and obtain the lexicographically minimum possible array ?c, where the ?i-th element of ?c is ??=(??+??)%?ci=(ai+bi)%n.
Examples
input

4 
0 1 2 1 
3 2 1 1

output

1 0 0 2

input

7 
2 5 1 5 3 4 3 
2 4 3 5 6 5 1

output

0 0 0 1 0 2 4

其实就是可以很简单的二分题，但是场上脑子抽了写了个线段树二分，没来得及交，赛后30行就解决了

线段树二分

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
#define delf int m=(l+r)>>1
const int maxn=(int)2e5+100;
int n,a[maxn],b[maxn],c[maxn],num[maxn];
int sum[maxn<<2],lazy[maxn<<2];
void pushup(int rt){sum[rt]=sum[rt<<1]+sum[rt<<1|1];}
void build(int l,int r,int rt){
	if(l==r){sum[rt]=0;return;}
	delf;
	build(lson);build(rson);pushup(rt);
}
void add(int L,int c,int l,int r,int rt){
	if(l==r){sum[rt]+=c;return;}
	delf;
	if(L<=m) add(L,c,lson);
	else add(L,c,rson);
	pushup(rt);
}
int query(int L,int R,int l,int r,int rt){
	if(L<=l&&r<=R) return sum[rt];
	delf;int ans=0;
	if(L<=m) ans+=query(L,R,lson);
	if(R>m) ans+=query(L,R,rson);
	return ans;
}
int dq(int L,int R,int l,int r,int rt){
	if(L==R) return R;
	int mid=L+R>>1;
	if(query(L,mid,1,n,1)) return dq(L,mid,1,n,1);
	else return dq(mid+1,R,1,n,1);
}
int main(){
	cin>>n;
	rep(i,1,n) scanf("%d",&a[i]);
	rep(i,1,n){
		int x;
		scanf("%d",&x);
		num[x]++;
	}
	build(1,n,1);
	rep(i,0,n-1) if(num[i]) add(i+1,num[i],1,n,1);
	rep(i,1,n){
		int ans=(n-a[i])%n,res;
		if(query(ans+1,n,1,n,1)){
			res=dq(ans+1,n,1,n,1);
			num[res-1]--;add(res,-1,1,n,1);
			printf("%d ",(res-1+a[i])%n);
		}
		else{
			res=dq(1,ans,1,n,1);
			num[res-1]--;add(res,-1,1,n,1);
			printf("%d ",(res-1+a[i])%n);
		}
	}
}

multiset

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
const int maxn=(int)2e5+100;
int a[maxn];
multiset<int> s;
int main(){
	int n;cin>>n;
	rep(i,1,n) scanf("%d",&a[i]);
	for(int i=1,x;i<=n;++i){scanf("%d",&x);s.insert(x);}
	rep(i,1,n){
		int ans=(n-a[i])%n;
		auto num=s.lower_bound(ans)!=s.end()?s.lower_bound(ans):s.begin();
		printf(i==1?"%d":" %d",(a[i]+*num)%n);
		s.erase(num);
	}
}

F. Maximum Balanced Circle

time limit per test2 seconds memory limit per test256 megabytes

There are ?n people in a row. The height of the ?i-th person is ??ai. You can choose any subset of these people and try to arrange them into a balanced circle.

A balanced circle is such an order of people that the difference between heights of any adjacent people is no more than 11. For example, let heights of chosen people be [??1,??2,…,???][ai1,ai2,…,aik], where ?k is the number of people you choose. Then the condition |???−???+1|≤1|aij−aij+1|≤1 should be satisfied for all ?j from 11 to ?−1k−1 and the condition |??1−???|≤1|ai1−aik|≤1 should be also satisfied. |?||x| means the absolute value of ?x. It is obvious that the circle consisting of one person is balanced.

Your task is to choose the maximum number of people and construct a balanced circle consisting of all chosen people. It is obvious that the circle consisting of one person is balanced so the answer always exists.Input

The first line of the input contains one integer ?n (1≤?≤2⋅1051≤n≤2⋅105) — the number of people.

The second line of the input contains ?n integers ?1,?2,…,??a1,a2,…,an (1≤??≤2⋅1051≤ai≤2⋅105), where ??ai is the height of the ?i-th person.Output

In the first line of the output print ?k — the number of people in the maximum balanced circle.

In the second line print ?k integers ???1,???2,…,????res1,res2,…,resk, where ????resj is the height of the ?j-th person in the maximum balanced circle. The condition |????−????+1|≤1|resj−resj+1|≤1 should be satisfied for all ?j from 11 to ?−1k−1 and the condition |???1−????|≤1|res1−resk|≤1 should be also satisfied.
Examples
input

7 
4 3 5 1 2 2 1

output

5 
2 1 1 2 3

input

5 
3 7 5 1 5

output

2 
5 5

input

3 
5 1 4

output

2 
4 5

input

7 
2 2 3 2 1 2 2

output

7 
1 2 2 2 2 3 2

可以发现，题目中描述的环，拆成序列之后应该满足 al,al+1,...,ar,ar−1,...,al+1al,al+1,...,ar,ar−1,...,al+1 的形态，即：除了 al,aral,ar 之外的其他所有值应该都有至少两个，因此扫一遍就可以得到答案

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define dep(i,a,b) for(int i=(a);i>=(b);--i)
const int maxn=(int)2e5+100;
int num[maxn],odd[maxn];
set<int> s;
int main(){
	int n;cin>>n;
	for(int i=0,x;i<n;++i){scanf("%d",&x);num[x]++;s.insert(x);}
	int l=*s.begin(),tot=num[l],r,maxx=num[l],pre=l,ansl=l,ansr=l;
	for(auto it=++s.begin();it!=s.end();++it){
		int cnt=*it;
		if(cnt>pre+1){
			if(tot>maxx){maxx=tot;ansl=l;ansr=pre;}
			pre=cnt;l=cnt;tot=num[cnt];
		}
		else if(num[cnt]==1||cnt==*(--s.end())){
			tot+=num[cnt];
			if(tot>maxx){maxx=tot;ansl=l;ansr=cnt;}
			pre=cnt;l=cnt;tot=num[cnt];
		}
		else if(cnt<=pre+1){tot+=num[cnt];pre=cnt;}
	}
	printf("%d\n",maxx);
	rep(i,ansl,ansr) {printf("%d ",i);num[i]--;}
	dep(i,ansr,ansl) {while(num[i]--) printf("%d ",i);}
}

 

订阅评论
提醒
0 评论
内联反馈
查看所有评论