Codeforces 1108 A. Two distinct points
time limit per test1 second memory limit per test256
You are given two segments [?1;?1][l1;r1] and [?2;?2][l2;r2] on the ?x-axis. It is guaranteed that ?1<?1l1<r1 and ?2<?2l2<r2. Segments may intersect, overlap or even coincide with each other.
The example of two segments on the ?x-axis.
Your problem is to find two integers ?a and ?b such that ?1≤?≤?1l1≤a≤r1, ?2≤?≤?2l2≤b≤r2 and ?≠?a≠b. In other words, you have to choose two distinct integer points in such a way that the first point belongs to the segment [?1;?1][l1;r1] and the second one belongs to the segment [?2;?2][l2;r2].
It is guaranteed that the answer exists. If there are multiple answers, you can print any of them.
You have to answer ?q independent queries.Input
The first line of the input contains one integer ?q (1≤?≤5001≤q≤500) — the number of queries.
Each of the next ?q lines contains four integers ?1?,?1?,?2?l1i,r1i,l2i and ?2?r2i (1≤?1?,?1?,?2?,?2?≤109,?1?<?1?,?2?<?2?1≤l1i,r1i,l2i,r2i≤109,l1i<r1i,l2i<r2i) — the ends of the segments in the ?i-th query.Output
Print 2?2q integers. For the ?i-th query print two integers ??ai and ??bi — such numbers that ?1?≤??≤?1?l1i≤ai≤r1i, ?2?≤??≤?2?l2i≤bi≤r2i and ??≠??ai≠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.
Exampleinput
5
1 2 1 2
2 6 3 4
2 4 1 3
1 2 1 3
1 4 5 8
output
2 1
3 4
3 2
1 2
3 7
题解：签到题，注意输出顺序不能反
#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define dep(i,a,b) for(int i=(a);i>=(b);--i)
#define pb push_back
typedef long long ll;
const int maxn=(int)2e5+100;
const int INF=0x3f3f3f3f;
int main(){
int T;cin>>T;
while(T--){
int l1,l2,r1,r2;
scanf("%d%d%d%d",&l1,&r1,&l2,&r2);
int minl=min(l1,l2);
if(minl==l1){
rep(i,l2,r2) if(i!=minl){
printf("%d %d\n",minl,i);
break;
}
}
else{
rep(i,l1,r1) if(i!=minl){
printf("%d %d\n",i,minl);
break;
}
}
}
return 0;
}
Codeforces 1108 B. Divisors of Two Integers
time limit per test1 second memory limit per test256 megabyte
Recently you have received two positive integer numbers ?x and ?y. You forgot them, but you remembered a shuffled list containing all divisors of ?x (including 11 and ?x) and all divisors of ?y (including 11 and ?y). If ?d is a divisor of both numbers ?x and ?y at the same time, there are two occurrences of ?d in the list.
For example, if ?=4x=4 and ?=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 ?x and ?y 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 ?x and ?y.Input
The first line contains one integer ?n (2≤?≤1282≤n≤128) — the number of divisors of ?x and ?y.
The second line of the input contains ?n integers ?1,?2,…,??d1,d2,…,dn (1≤??≤1041≤di≤104), where ??di is either divisor of ?x or divisor of ?y. If a number is divisor of both numbers ?x and ?y then there are two copies of this number in the list.Output
Print two positive integer numbers ?x and ?y — such numbers that merged list of their divisors is the permutation of the given list of integers. It is guaranteed that the answer exists.
Exampleinput
10
10 2 8 1 2 4 1 20 4 5
output
20 8
题意：给你两个整数的所有除数列表，让你输出这两个数
题解：暴力，首先升序排列，最大的肯定是一个数，再枚举这个数的每个除数，从原序列中减去，剩下的最大的那个数就是第二个数
#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define dep(i,a,b) for(int i=(a);i>=(b);--i)
#define pb push_back
typedef long long ll;
const int maxn=(int)2e5+100;
const int INF=0x3f3f3f3f;
int n,a[200],num[10010];
int main(){
cin>>n;
rep(i,1,n){
scanf("%d",&a[i]);
num[a[i]]++;
} sort(a+1,a+1+n);
printf("%d ",a[n-1]);
for(int i=1;i<=a[n-1];++i){
if(a[n-1]%i==0){
num[i]--;
}
}
for(int i=n-2;i>=0;--i){
if(num[a[i]]){
printf("%d\n",a[i]);
break;
}
}
return 0;
}
Codeforces 1108 C. Nice Garland
time limit per test1 second memory limit per test256 megabyte
You have a garland consisting of ?n lamps. Each lamp is colored red, green or blue. The color of the ?i-th lamp is ??si (‘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 ?t, then for each ?,?i,j such that ??=??ti=tj should be satisfied |?−?| ??? 3=0|i−j| mod 3=0. The value |?||x| means absolute value of ?x, the operation ? ??? ?x mod y means remainder of ?x when divided by ?y.
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 ?n (1≤?≤2⋅1051≤n≤2⋅105) — the number of lamps.
The second line of the input contains the string ?s consisting of ?n characters ‘R’, ‘G’ and ‘B’ — colors of lamps in the garland.Output
In the first line of the output print one integer ?r — 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 ?t of length ?n — a nice garland obtained from the initial one with minimum number of recolors. If there are multiple optimal solutions, print any of them.
Examplesinput
3
BRB
output
1
GRB
input
7
RGBGRBB
output
3
RGBRGBR
题解：对于每个重新涂色的花圈，其颜色都是“RGB”或“BGR”的循环，因此枚举六个长度为n的目标串，枚举六次答案，选最小的那个
#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define dep(i,a,b) for(int i=(a);i>=(b);--i)
#define pb push_back
typedef long long ll;
const int maxn=(int)2e5+100;
const int INF=0x3f3f3f3f;
int n;
string str;
int main(){
map<int,char> mp; mp[0]='R'; mp[1]='G'; mp[2]='B';
cin>>n; getline(cin,str);
string s1,s2,s3,t1,t2,t3,s4,s5,s6;
s1.clear();s2.clear();s3.clear();
for(int i=0;i<n;++i){
t1.pb(mp[i%3]);
t2.pb(mp[(i+1)%3]);
t3.pb(mp[(i+2)%3]);
}
s1=t1;s2=t2;s3=t3;
reverse(t1.begin(), t1.end());
reverse(t2.begin(), t2.end());
reverse(t3.begin(), t3.end());
s4=t1;s5=t2;s6=t3;
int ans1,ans2,ans3,ans4,ans5,ans6;
ans1=ans2=ans3=ans4=ans5=ans6=0;
for(int i=0;i<str.length();++i){
if(str[i]!=s1[i]) ans1++;
if(str[i]!=s2[i]) ans2++;
if(str[i]!=s3[i]) ans3++;
if(str[i]!=s4[i]) ans4++;
if(str[i]!=s5[i]) ans5++;
if(str[i]!=s6[i]) ans6++;
}
int ans=min(min(min(min(min(ans1,ans2),ans3),ans4),ans5),ans6);
printf("%d\n",ans);
if(ans==ans1){cout<<s1<<endl;return 0;}
else if(ans==ans2){cout<<s2<<endl;return 0;}
else if(ans==ans3){cout<<s3<<endl;return 0;}
else if(ans==ans4){cout<<s4<<endl;return 0;}
else if(ans==ans5){cout<<s5<<endl;return 0;}
else if(ans==ans6){cout<<s6<<endl;return 0;}
}
Codeforces 1108 D. Diverse Garland
time limit per test1 second memory limit per test256 megabytes
You have a garland consisting of ?n lamps. Each lamp is colored red, green or blue. The color of the ?i-th lamp is ??si (‘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 ?t then for each ?i from 11 to ?−1n−1 the condition ??≠??+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 ?n (1≤?≤2⋅1051≤n≤2⋅105) — the number of lamps.
The second line of the input contains the string ?s consisting of ?n characters ‘R’, ‘G’ and ‘B’ — colors of lamps in the garland.Output
In the first line of the output print one integer ?r — 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 ?t of length ?n — a diverse garland obtained from the initial one with minimum number of recolors. If there are multiple optimal solutions, print any of them.
Examplesinput
9
RBGRRBRGG
output
2
RBGRGBRGR
input
8
BBBGBRRR
output
2
BRBGBRGR
input
13
BBRRRRGGGGGRR
output
6
BGRBRBGBGBGRG
题解：对于每个灯笼，如果它和前面那个颜色一样，就把它换成和后面颜色不一样的颜色，这样肯定是最优解
#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define dep(i,a,b) for(int i=(a);i>=(b);--i)
#define pb push_back
typedef long long ll;
const int maxn=(int)2e5+100;
const int INF=0x3f3f3f3f;
int main(){
int n;cin>>n;
map<int,char> mp;
mp[0]='R';mp[1]='G';mp[2]='B';
string str;getline(cin,str);str+='0';
int ans=0;
for(int i=1;i<n;++i){
if(str[i]==str[i-1]){
for(int j=0;j<3;++j){
if(mp[j]!=str[i]&&mp[j]!=str[i+1]){
str[i]=mp[j];ans++;break;
}
}
}
}
str.erase(str.length()-1);
printf("%d\n",ans);
cout<<str<<endl;
}
Codeforces 1108 E1. Array and Segments (Easy version)
time limit per test2 seconds memory limit per test256 megabytes
The only difference between easy and hard versions is a number of elements in the array.
You are given an array ?a consisting of ?n integers. The value of the ?i-th element of the array is ??ai.
You are also given a set of ?m segments. The ?j-th segment is [??;??][lj;rj], where 1≤??≤??≤?1≤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 ?=[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 ?=[−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 ?a and obtain the array ?b then the value max?=1???−min?=1???maxi=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 ?n and ?m (1≤?≤300,0≤?≤3001≤n≤300,0≤m≤300) — the length of the array ?a and the number of segments, respectively.
The second line of the input contains ?n integers ?1,?2,…,??a1,a2,…,an (−106≤??≤106−106≤ai≤106), where ??ai is the value of the ?i-th element of the array ?a.
The next ?m lines are contain two integers each. The ?j-th of them contains two integers ??lj and ??rj (1≤??≤??≤?1≤lj≤rj≤n), where ??lj and ??rj are the ends of the ?j-th segment.Output
In the first line of the output print one integer ?d — the maximum possible value max?=1???−min?=1???maxi=1nbi−mini=1nbi if ?b is the array obtained by applying some subset of the given segments to the array ?a.
In the second line of the output print one integer ?q (0≤?≤?0≤q≤m) — the number of segments you apply.
In the third line print ?q distinct integers ?1,?2,…,??c1,c2,…,cq in any order (1≤??≤?1≤ck≤m) — indices of segments you apply to the array ?a in such a way that the value max?=1???−min?=1???maxi=1nbi−mini=1nbi of the obtained array ?b is maximum possible.
If there are multiple answers, you can print any.
input
5 4
2 -2 3 1 2
1 3
4 5
2 5
1 3
output
6
2
1 4
input
5 4
2 -2 3 1 4
3 5
3 4
2 4
2 5
output
7
2
3 2
input
1
0
1000000
output
0
0
Note
In the first example the obtained array ?b will be [0,−4,1,1,2][0,−4,1,1,2] so the answer is 66.
In the second example the obtained array ?b 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<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define dep(i,a,b) for(int i=(a);i>=(b);--i)
#define pb push_back
typedef long long ll;
const int maxn=(int)2e5+100;
const int INF=0x3f3f3f3f;
int main(){
int n,m;
pair<int,int> p[305];
vector<int> v;
int pre[305], a[305];
cin>>n>>m;
for(int i=1;i<=n;i++) scanf("%d",&a[i]);
for(int i=1;i<=m;i++){
scanf("%d%d",&p[i].first, &p[i].second);
}
int cnt;
int ans = 0;
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
if(i == j) continue;
cnt = 0;
int xx = a[j] - a[i];
for(int k=1;k<=m;k++){
if(i >= p[k].first && i <= p[k].second && (j < p[k].first || j > p[k].second)){
pre[cnt++] = k;
xx ++;
}
}
if(ans < xx){
ans = xx;
v.clear();
for(int i=0;i<cnt;i++) v.push_back(pre[i]);
}
}
}
cout<<ans<<endl;
cout<<v.size()<<endl;
for(int i=0;i<v.size();i++){
cout<<v[i]<<" ";
}
return 0;
}
F. MST Unification
time limit per test3 seconds memory limit per test256 megabytes
You are given an undirected weighted connected graph with ?n vertices and ?m edges without loops and multiple edges.
The ?i-th edge is ??=(??,??,??)ei=(ui,vi,wi); the distance between vertices ??ui and ??vi along the edge ??ei is ??wi (1≤??1≤wi). The graph is connected, i. e. for any pair of vertices, there is at least one path between them consisting only of edges of the given graph.
A minimum spanning tree (MST) in case of positive weights is a subset of the edges of a connected weighted undirected graph that connects all the vertices together and has minimum total cost among all such subsets (total cost is the sum of costs of chosen edges).
You can modify the given graph. The only operation you can perform is the following: increase the weight of some edge by 11. You canincrease the weight of each edge multiple (possibly, zero) times.
Suppose that the initial MST cost is ?k. Your problem is to increase weights of some edges with minimum possible number of operations in such a way that the cost of MST in the obtained graph remains ?k, but MST is unique (it means that there is only one way to choose MST in the obtained graph).
Your problem is to calculate the minimum number of operations required to do it.Input
The first line of the input contains two integers ?n and ?m (1≤?≤2⋅105,?−1≤?≤2⋅1051≤n≤2⋅105,n−1≤m≤2⋅105) — the number of vertices and the number of edges in the initial graph.
The next ?m lines contain three integers each. The ?i-th line contains the description of the ?i-th edge ??ei. It is denoted by three integers ??,??ui,viand ??wi (1≤??,??≤?,??≠??,1≤?≤1091≤ui,vi≤n,ui≠vi,1≤w≤109), where ??ui and ??vi are vertices connected by the ?i-th edge and ??wi is the weight of this edge.
It is guaranteed that the given graph doesn't contain loops and multiple edges (i.e. for each ?i from 11 to ?m ??≠??ui≠vi and for each unordered pair of vertices (?,?)(u,v) there is at most one edge connecting this pair of vertices). It is also guaranteed that the given graph is connected.Output
Print one integer — the minimum number of operations to unify MST of the initial graph without changing the cost of MST.
Examplesinput
8 10 1 2 1 2 3 2 2 4 5 1 4 2 6 3 3 6 1 3 3 5 2 3 7 1 4 8 1 6 2 4
output
1
input
4 3 2 1 3 4 3 4 2 4 1
output
0
input
3 3 1 2 1 2 3 2 1 3 3
output
0
input
3 3 1 2 1 2 3 3 1 3 3
output
1
input
1 0
output
0
input
5 6 1 2 2 2 3 1 4 5 3 2 4 2 1 4 2 1 5 3
output
2
Note
The picture corresponding to the first example:
You can, for example, increase weight of the edge (1,6)(1,6) or (6,3)(6,3) by 11 to unify MST.
The picture corresponding to the last example:
You can, for example, increase weights of edges (1,5)(1,5) and (2,4)(2,4) by 11 to unify MST.
先把所有边按照边权进行排序，然后再去处理矛盾的边
#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define dep(i,a,b) for(int i=(a);i>=(b);--i)
#define pb push_back
typedef long long ll;
const int maxn=(int)2e5+100;
const int INF=0x3f3f3f3f;
int pre[maxn];
int n,m;
struct node{
int fr,to,dis;
}edge[maxn];
int cmp(node a,node b){return a.dis<b.dis;}
void init(){rep(i,0,n) pre[i]=i;}
int find(int x){return x==pre[x]?x:pre[x]=find(pre[x]);}
void join(int x,int y){
x=find(x);y=find(y);
if(x!=y) pre[x]=y;
}
int main(){
cin>>n>>m;init();
int ans=0;
rep(i,0,m-1) scanf("%d%d%d",&edge[i].fr,&edge[i].to,&edge[i].dis);
sort(edge,edge+m,cmp);
for(int i=0;i<m;){
int num=0,j=i;
while(edge[j].dis==edge[i].dis) j++;
for(int k=i;k<j;++k){
if(find(edge[k].fr)!=find(edge[k].to)) num++;
}
for(int k=i;k<j;++k){
if(find(edge[k].fr)!=find(edge[k].to)){
join(find(edge[k].fr),find(edge[k].to));
num--;
}
} ans+=num; i=j;
}
printf("%d\n",ans);
}
