A. Two distinct points
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output
You are given two segments [l1;
r1][l1;
r1] and [l2;
r2][l2;
r2] on the xx-axis. It is guaranteed that l1
文章图片
The example of two segments on the xx-axis.
Your problem is to find two integers aa and bb such that l1≤a≤r1l1≤a≤r1, l2≤b≤r2l2≤b≤r2 and a≠ba≠b. In other words, you have to choose two distinct integer points in such a way that the first point belongs to the segment [l1;
r1][l1;
r1] and the second one belongs to the segment [l2;
r2][l2;
r2].
It is guaranteed that the answer exists. If there are multiple answers, you can print any of them.
You have to answer qq independent queries.
Input
The first line of the input contains one integer qq (1≤q≤5001≤q≤500) — the number of queries.
Each of the next qq lines contains four integers l1i,r1i,l2il1i,r1i,l2i and r2ir2i (1≤l1i,r1i,l2i,r2i≤109,l1i
Print 2q2q integers. For the ii-th query print two integers aiai and bibi — such numbers that l1i≤ai≤r1il1i≤ai≤r1i, l2i≤bi≤r2il2i≤bi≤r2i and ai≠biai≠bi. Queries are numbered in order of the input.
It is guaranteed that the answer exists. If there are multiple answers, you can print any.
Example
input
Copy
5 1 2 1 2 2 6 3 4 2 4 1 3 1 2 1 3 1 4 5 8
output
Copy
2 1 3 4 3 2 1 2 3 7
签到题
#include
using namespace std;
typedef long long ll;
int main()
{
int q;
cin>>q;
int l1,r1,l2,r2;
while(q--)
{
cin>>l1>>r1>>l2>>r2;
if(l1!=l2) printf("%d %d\n",l1,l2);
else if(r1!=r2) printf("%d %d\n",r1,r2);
else if(l1!=r2) printf("%d %d\n",l1,r2);
else if(r1!=r2) printf("%d %d\n",r1,r2);
}
} B. Divisors of Two Integers
time limit per test
1 second
memory limit per test
【Codeforces Round #535 (Div. 3)】256 megabytes
input
standard input
output
standard output
Recently you have received two positive integer numbers xx and yy. You forgot them, but you remembered a shuffled list containing all divisors of xx (including 11 and xx) and all divisors of yy (including 11 and yy). If dd is a divisor of both numbers xx and yy at the same time, there are two occurrences of dd in the list.
For example, if x=4x=4 and y=6y=6 then the given list can be any permutation of the list [1,2,4,1,2,3,6][1,2,4,1,2,3,6]. Some of the possible lists are: [1,1,2,4,6,3,2][1,1,2,4,6,3,2], [4,6,1,1,2,3,2][4,6,1,1,2,3,2] or [1,6,3,2,4,1,2][1,6,3,2,4,1,2].
Your problem is to restore suitable positive integer numbers xx and yy that would yield the same list of divisors (possibly in different order).
It is guaranteed that the answer exists, i.e. the given list of divisors corresponds to some positive integers xx and yy.
Input
The first line contains one integer nn (2≤n≤1282≤n≤128) — the number of divisors of xx and yy.
The second line of the input contains nn integers d1,d2,…,dnd1,d2,…,dn (1≤di≤1041≤di≤104), where didi is either divisor of xx or divisor of yy. If a number is divisor of both numbers xx and yy then there are two copies of this number in the list.
Output
Print two positive integer numbers xx and yy — such numbers that merged list of their divisors is the permutation of the given list of integers. It is guaranteed that the answer exists.
Example
input
Copy
10 10 2 8 1 2 4 1 20 4 5
output
Copy
20 8
第一数直接取a里面最大的，然后遍历一遍，将能整除的去掉，再找最大的
#include
using namespace std;
typedef long long ll;
const int N=200,maxn=1e4+50;
int a[N],n,b[N];
int vis[maxn];
int main()
{
cin>>n;
int mx=-1;
for(int i=1;
i<=n;
i++)
{
scanf("%d",&a[i]);
mx=max(mx,a[i]);
vis[a[i]]++;
}
sort(a+1,a+1+n);
int j=0;
for(int i=1;
i<=n;
i++)
{
if(mx%a[i]==0)
{
vis[a[i]]--;
}
if(vis[a[i]]) b[++j]=a[i];
}
int mi=b[j];
printf("%d %d\n",mx,mi);
} C. Nice Garland
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output
You have a garland consisting of nn lamps. Each lamp is colored red, green or blue. The color of the ii-th lamp is sisi ('R', 'G' and 'B' — colors of lamps in the garland).
You have to recolor some lamps in this garland (recoloring a lamp means changing its initial color to another) in such a way that the obtained garland is nice.
A garland is called nice if any two lamps of the same color have distance divisible by three between them. I.e. if the obtained garland is tt, then for each i,ji,j such that ti=tjti=tj should be satisfied |i?j| mod 3=0|i?j| mod 3=0. The value |x||x| means absolute value of xx, the operation x mod yx mod y means remainder of xx when divided by yy.
For example, the following garlands are nice: "RGBRGBRG", "GB", "R", "GRBGRBG", "BRGBRGB". The following garlands are not nice: "RR", "RGBG".
Among all ways to recolor the initial garland to make it nice you have to choose one with the minimum number of recolored lamps. If there are multiple optimal solutions, print any of them.
Input
The first line of the input contains one integer nn (1≤n≤2?1051≤n≤2?105) — the number of lamps.
The second line of the input contains the string ss consisting of nn characters 'R', 'G' and 'B' — colors of lamps in the garland.
Output
In the first line of the output print one integer rr — the minimum number of recolors needed to obtain a nice garland from the given one.
In the second line of the output print one string tt of length nn — a nice garland obtained from the initial one with minimum number of recolors. If there are multiple optimal solutions, print any of them.
Examples
input
Copy
3 BRB
output
Copy
1 GRB
input
Copy
7 RGBGRBB
output
Copy
3 RGBRGBR
把六种情况的RGB构造一个新的字符串，然后对比不同之处的数量，求最小值
#include
using namespace std;
typedef long long ll;
const int N=2e5+10;
char s[N],a[7][10]={"RGB","RBG","GBR","GRB","BGR","BRG"},s1[N],s2[N];
int n;
int main()
{
cin>>n>>s+1;
int ans=0x3f3f3f3f;
int t=6;
for(int j=0;
j<=5;
j++)
{
memset(s1,0,sizeof(s1));
for(int i=1;
i<=n;
i++)
{
s1[i]=a[j][i%3];
}
int num=0;
for(int i=1;
i<=n;
i++)
{
if(s1[i]!=s[i]) num++;
}
if(num D. Diverse Garland
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output
You have a garland consisting of nn lamps. Each lamp is colored red, green or blue. The color of the ii-th lamp is sisi ('R', 'G' and 'B' — colors of lamps in the garland).
You have to recolor some lamps in this garland (recoloring a lamp means changing its initial color to another) in such a way that the obtained garland is diverse.
A garland is called diverse if any two adjacent (consecutive) lamps (i.?e. such lamps that the distance between their positions is 11) have distinct colors.
In other words, if the obtained garland is tt then for each ii from 11 to n?1n?1 the condition ti≠ti+1ti≠ti+1 should be satisfied.
Among all ways to recolor the initial garland to make it diverse you have to choose one with the minimum number of recolored lamps. If there are multiple optimal solutions, print any of them.
Input
The first line of the input contains one integer nn (1≤n≤2?1051≤n≤2?105) — the number of lamps.
The second line of the input contains the string ss consisting of nn characters 'R', 'G' and 'B' — colors of lamps in the garland.
Output
In the first line of the output print one integer rr — the minimum number of recolors needed to obtain a diverse garland from the given one.
In the second line of the output print one string tt of length nn — a diverse garland obtained from the initial one with minimum number of recolors. If there are multiple optimal solutions, print any of them.
Examples
input
Copy
9 RBGRRBRGG
output
Copy
2 RBGRGBRGR
input
Copy
8 BBBGBRRR
output
Copy
2 BRBGBRGR
input
Copy
13 BBRRRRGGGGGRR
output
Copy
6 BGRBRBGBGBGRG
遇到相同数连在一起，就将第二个数变成与第一个和第三个不同的字符就可以了
#include
using namespace std;
typedef long long ll;
const int N=2e5+10;
char s[N],s1[N];
int ans,n;
char a[3]={'R','G','B'};
bool vis[3];
char get(char c,char c1)
{
memset(vis,0,sizeof(vis));
for(int i=0;
i<3;
i++) if(c==a[i]) vis[i]=1;
for(int i=0;
i<3;
i++) if(c1==a[i]) vis[i]=1;
for(int i=0;
i<3;
i++) if(!vis[i]) return a[i];
}
int main()
{
cin>>n>>s+1;
for(int i=1;
i+2<=n;
i++)
{
if(s[i]==s[i+1])
{
ans++;
s[i+1]=get(s[i],s[i+2]);
}
}
if(s[n-1]==s[n]) s[n]=get(s[n-1],s[n-1]),ans++;
printf("%d\n",ans);
printf("%s\n",s+1);
} E1. Array and Segments (Easy version)
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output
The only difference between easy and hard versions is a number of elements in the array.
You are given an array aa consisting of nn integers. The value of the ii-th element of the array is aiai.
You are also given a set of mm segments. The jj-th segment is [lj; rj][lj; rj], where 1≤lj≤rj≤n1≤lj≤rj≤n.
You can choose some subset of the given set of segments and decrease values on each of the chosen segments by one (independently). For example, if the initial array a=[0,0,0,0,0]a=[0,0,0,0,0] and the given segments are [1; 3][1; 3] and [2; 4][2; 4] then you can choose both of them and the array will become b=[?1,?2,?2,?1,0]b=[?1,?2,?2,?1,0].
You have to choose some subset of the given segments (each segment can be chosen at most once) in such a way that if you apply this subset of segments to the array aa and obtain the array bb then the value maxi=1nbi?mini=1nbimaxi=1nbi?mini=1nbi will be maximum possible.
Note that you can choose the empty set.
If there are multiple answers, you can print any.
If you are Python programmer, consider using PyPy instead of Python when you submit your code.
Input
The first line of the input contains two integers nn and mm (1≤n≤300,0≤m≤3001≤n≤300,0≤m≤300) — the length of the array aa and the number of segments, respectively.
The second line of the input contains nn integers a1,a2,…,ana1,a2,…,an (?106≤ai≤106?106≤ai≤106), where aiai is the value of the ii-th element of the array aa.
The next mm lines are contain two integers each. The jj-th of them contains two integers ljlj and rjrj (1≤lj≤rj≤n1≤lj≤rj≤n), where ljlj and rjrj are the ends of the jj-th segment.
Output
In the first line of the output print one integer dd — the maximum possible value maxi=1nbi?mini=1nbimaxi=1nbi?mini=1nbi if bb is the array obtained by applying some subset of the given segments to the array aa.
In the second line of the output print one integer qq (0≤q≤m0≤q≤m) — the number of segments you apply.
In the third line print qq distinct integers c1,c2,…,cqc1,c2,…,cq in any order (1≤ck≤m1≤ck≤m) — indices of segments you apply to the array aa in such a way that the value maxi=1nbi?mini=1nbimaxi=1nbi?mini=1nbi of the obtained array bb is maximum possible.
If there are multiple answers, you can print any.
Examples
input
Copy
5 4 2 -2 3 1 2 1 3 4 5 2 5 1 3
output
Copy
6 2 1 4
input
Copy
5 4 2 -2 3 1 4 3 5 3 4 2 4 2 5
output
Copy
7 2 3 2
input
Copy
1 0 1000000
output
Copy
0 0
Note
In the first example the obtained array bb will be [0,?4,1,1,2][0,?4,1,1,2] so the answer is 66.
In the second example the obtained array bb will be [2,?3,1,?1,4][2,?3,1,?1,4] so the answer is 77.
In the third example you cannot do anything so the answer is 00.
暴力枚举最大位置和最小位置，然后枚举区间是否包含最小位置
更新答案即可
#include
using namespace std;
typedef long long ll;
const int N=2e5+10;
int a[N],l[320],r[320],n,m,pre[320];
vectorG;
int main()
{
cin>>n>>m;
for(int i=1;
i<=n;
i++) scanf("%d",&a[i]);
for(int i=1;
i<=m;
i++) scanf("%d%d",&l[i],&r[i]);
int ans=0;
for(int i=1;
i<=n;
i++)//枚举最小位置
{
for(int j=1;
j<=n;
j++)//枚举最大位置
{
int temp=a[j]-a[i],cnt=0;
for(int k=1;
k<=m;
k++)
{
if(l[k]<=i&&i<=r[k]&&(l[k]>j||r[k] E2. Array and Segments (Hard version)
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output
The only difference between easy and hard versions is a number of elements in the array.
You are given an array aa consisting of nn integers. The value of the ii-th element of the array is aiai.
You are also given a set of mm segments. The jj-th segment is [lj; rj][lj; rj], where 1≤lj≤rj≤n1≤lj≤rj≤n.
You can choose some subset of the given set of segments and decrease values on each of the chosen segments by one (independently). For example, if the initial array a=[0,0,0,0,0]a=[0,0,0,0,0] and the given segments are [1; 3][1; 3] and [2; 4][2; 4] then you can choose both of them and the array will become b=[?1,?2,?2,?1,0]b=[?1,?2,?2,?1,0].
You have to choose some subset of the given segments (each segment can be chosen at most once) in such a way that if you apply this subset of segments to the array aa and obtain the array bb then the value maxi=1nbi?mini=1nbimaxi=1nbi?mini=1nbi will be maximum possible.
Note that you can choose the empty set.
If there are multiple answers, you can print any.
If you are Python programmer, consider using PyPy instead of Python when you submit your code.
Input
The first line of the input contains two integers nn and mm (1≤n≤105,0≤m≤3001≤n≤105,0≤m≤300) — the length of the array aa and the number of segments, respectively.
The second line of the input contains nn integers a1,a2,…,ana1,a2,…,an (?106≤ai≤106?106≤ai≤106), where aiai is the value of the ii-th element of the array aa.
The next mm lines are contain two integers each. The jj-th of them contains two integers ljlj and rjrj (1≤lj≤rj≤n1≤lj≤rj≤n), where ljlj and rjrj are the ends of the jj-th segment.
Output
In the first line of the output print one integer dd — the maximum possible value maxi=1nbi?mini=1nbimaxi=1nbi?mini=1nbi if bb is the array obtained by applying some subset of the given segments to the array aa.
In the second line of the output print one integer qq (0≤q≤m0≤q≤m) — the number of segments you apply.
In the third line print qq distinct integers c1,c2,…,cqc1,c2,…,cq in any order (1≤ck≤m1≤ck≤m) — indices of segments you apply to the array aa in such a way that the value maxi=1nbi?mini=1nbimaxi=1nbi?mini=1nbi of the obtained array bb is maximum possible.
If there are multiple answers, you can print any.
Examples
input
Copy
5 4 2 -2 3 1 2 1 3 4 5 2 5 1 3
output
Copy
6 2 4 1
input
Copy
5 4 2 -2 3 1 4 3 5 3 4 2 4 2 5
output
Copy
7 2 3 2
input
Copy
1 0 1000000
output
Copy
0 0
Note
In the first example the obtained array bb will be [0,?4,1,1,2][0,?4,1,1,2] so the answer is 66.
In the second example the obtained array bb will be [2,?3,1,?1,4][2,?3,1,?1,4] so the answer is 77.
In the third example you cannot do anything so the answer is 00.
这题我是真不会，看别人题解补的。
https://blog.csdn.net/qq_41286356/article/details/88915986
