C2

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
Copy 
5
1 2 4 3 2
output
Copy 
4
LRRR
input
Copy 
7
1 3 5 6 5 4 2
output
Copy 
6
LRLRRR
input
Copy 
3
2 2 2
output
Copy 
1
R
input
Copy 
4
1 2 4 3
output
Copy 
4
LLRR
Note

The first example is described in the problem statement.

 

思路：

这题其实是一个很水的模拟题。但是我卡在了如果左右两边的相同应该往哪去走。

既然不知道往哪里走，不妨两边都走试试！然后找到最大的就是答案！

 

 1 #include <stdio.h>
 2 #include <algorithm>
 3 #include <iostream>
 4 #include <stdlib.h>
 5 #include <string>
 6 #include <string.h>
 7 #include <math.h>
 8 #include <vector>
 9 #include <queue>
10 #include <stack>
11 #include <map>
12  
13  
14 #define INF 0x3f3f3f3f
15 #define LL long long
16 #define MAXN 200005
17 using namespace std;
18  
19 int n;
20 int a[MAXN];
21 char str1[MAXN],str2[MAXN];
22  
23 int main()
24 {
25     scanf("%d",&n);
26     for (int i=1;i<=n;i++)
27         cin >> a[i];
28     int l = 1;
29     int r = n;
30     int temp = 0;
31     int cnt = 0;
32     while (l<=r)
33     {
34         if (a[l]<=a[r] && a[l]>temp || (a[l]>temp && a[r]<=temp))
35         {
36             str1[cnt++] = 'L';
37             temp = a[l];
38             l++;
39         }
40         else if (a[l]>a[r] && a[r]>temp || (a[r]>temp && a[l]<=temp))
41         {
42             str1[cnt++] = 'R';
43             temp = a[r];
44             r--;
45         }
46         else
47             break;
48     }
49     int ans = 0;
50     l = 1;
51     r = n;
52     temp = 0;
53     while (l<=r)
54     {
55         if (a[l]<a[r] && a[l]>temp || (a[l]>temp && a[r]<=temp))
56         {
57             str2[ans++] = 'L';
58             temp = a[l];
59             l++;
60         }
61         else if (a[l]>=a[r] && a[r]>temp || (a[r]>temp && a[l]<=temp))
62         {
63             str2[ans++] = 'R';
64             temp = a[r];
65             r--;
66         }
67         else
68             break;
69     }
70     if (cnt>=ans){
71         cout << cnt << endl;
72         for (int i=0;i<cnt;i++)
73             cout << str1[i];
74     }
75     else{
76         cout << ans << endl;
77         for (int i=0;i<ans;i++)
78             cout << str2[i];
79     }
80     return 0;
81 }
Ackerman

 

D

 

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
Copy 
26 6
output
Copy 
YES
1 2 4 5 6 8
input
Copy 
8 3
output
Copy 
NO
input
Copy 
1 1
output
Copy 
YES
1
input
Copy 
9 4
output
Copy 
NO

 

思路：

有趣的构造题。。

设数列的和为S

先考虑和最小的一种构造方案。由题目可得，这个数列必须是一个单调上升的序列，因此和最小的数列显然就是一个首项为1，公差为1，项数为k的等差数列

如果此时S>n，那么显然是无解的

否则我们考虑往数列的某些位置加数

显然所有公差为11的等差数列都是符合题意的数列，因此我们可以先把数列的每一项都加上一个⌊n−S​⌋/k

现在还剩(n−S) mod k需要加。

前面说过，每一个公差为1的等差数列都是满足的，因此我们可以考虑每次把数列的某个后缀都加1

假设我们把从i到k的这个后缀加1，那么i必须满足
a[i] + 1 <= 2a[i-1]​，这里暴力的加就好了

如果已经加不下去了，那么就已经无解了

 

 1 #include <algorithm>
 2 #include <cstdio>
 3 
 4 using namespace std ;
 5 
 6 typedef long long LL ;
 7 const int N=2e5+10 ;
 8 
 9 int a[N] ;
10 int n , k ;
11 LL sum ;
12 
13 int main ()
14 {
15     int i ;
16     scanf("%d%d",&n,&k);
17     for ( i=1 ; i<=k ; i++ ) a[i]=i,sum+=(LL)i;
18     if ( sum>n ) return puts("NO")*0;
19     LL d=(n-sum)/k , l=n-sum-d*k;
20     while ( l )
21     {
22         for ( i=k ; l && i>=1 ; i-- ) 
23             if ( a[i]+d+1<=2*(a[i-1]+d) ) a[i]++,l--;
24         if ( l && a[k]+d+1>2*(a[k-1]+d) ) return puts("NO")*0;
25     }
26     puts("YES");
27     for ( i=1 ; i<=k ; i++ ) printf("%lld ",a[i]+d);
28     return 0 ;
29 }
Ackerman

 

 

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
Copy 
4
0 1 2 1
3 2 1 1
output
Copy 
1 0 0 2
input
Copy 
7
2 5 1 5 3 4 3
2 4 3 5 6 5 1
output
Copy 
0 0 0 1 0 2 4

 

思路：

争取让(a[i]+b[i])%n最小也就是让所以当前b[i]能取的最小值为n-a[i]​。如果不能取n-a[i]​，那么就要取n-a[i]+1，以此类推。 

学会使用multset

 

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 int n,a[200001];
 4 multiset<int>s;
 5 int main(){
 6     scanf("%d",&n);
 7     for(int i=1;i<=n;++i)scanf("%d",&a[i]);
 8     for(int i=1;i<=n;++i)scanf("%d",&a[0]),s.insert(a[0]);
 9     for(int x,i=1;i<=n;++i){
10         auto it=s.lower_bound((n-a[i])%n);
11         if(it==s.end())x=*s.begin(),s.erase(s.begin());
12         else x=*it,s.erase(it);
13         printf("%d ",(x+a[i])%n);
14     }
15 }
Ackerman

 

 

Maximum Balanced Circle

 

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|≤1should 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
Copy 
7
4 3 5 1 2 2 1
output
Copy 
5
2 1 1 2 3
input
Copy 
5
3 7 5 1 5
output
Copy 
2
5 5
input
Copy 
3
5 1 4
output
Copy 
2
4 5
input
Copy 
7
2 2 3 2 1 2 2
output
Copy 
7
1 2 2 2 2 3 2

 

 思路：

如果要成环可以发现，题目中描述的环，拆成序列之后应该满足 al,al+1,...,ar,ar−1,...,al+1的形态，即：

除了 al,ar 之外的其他所有值应该都有至少两个。因此，开一个桶记录一下每个元素出现的次数，并对原序列进行去重。可知，对于满足 1,2,2,...2,1形态的序列中的任何一个 2 的位置的答案都是相同的。因此，考虑使用双指针法，每次都找到 1 出现的位置，统计答案并更新答案即可。

 

 1 #include <stdio.h>
 2 #include <algorithm>
 3 #include <iostream>
 4 #include <stdlib.h>
 5 #include <string>
 6 #include <string.h>
 7 #include <math.h>
 8 #include <vector>
 9 #include <queue>
10 #include <stack>
11 #include <map>
12 #include <set>
13  
14  
15 #define INF 0x3f3f3f3f
16 #define LL long long
17 #define MAXN 200005
18 using namespace std;
19  
20 const int N = 2e5 + 5;
21 int n;
22 int a[N], c[N];
23 int main() {
24     //freopen("../in.txt","r",stdin);
25     scanf("%d", &n);
26     for(int i = 1; i <= n; i++) scanf("%d", &a[i]), c[a[i]]++;
27     int ans = 0;
28     int l, r;
29     int ansl, ansr;
30     int sum = 0;
31     for(int i = 1; i < N; i++) {
32         if(c[i] >= 1 && sum == 0) {
33             l = i;
34             sum += c[i] ;
35         }else if(c[i] > 1) {
36             sum += c[i];
37         }else if(sum > 0){
38             if(c[i] == 1) sum++, r = i;
39             else r = i - 1;
40             if(sum > ans) {
41                 ans = sum ;
42                 ansl = l;
43                 ansr = r;
44             }
45             sum = 0;
46             if(c[i] == 1) {
47                 sum++;
48                 l = i;
49             }
50         }
51     }
52     cout << ans << '\n' ;
53     if(c[ansl] == 1) cout << ansl << ' ', ansl++ ;
54     for(int i = ansl; i <= ansr; i++) {
55         for(int j = 1; j < c[i]; j++) {
56             printf("%d ",i) ;
57         }
58     }
59     for(int i = ansr; i >= ansl; i--) {
60         printf("%d ",i);
61     }
62     return 0;
63 }
Ackerman