|
Codeforces Round #738 (Div. 2)(http://codeforces.com/contest/1559)
A. Mocha and Math(http://codeforces.com/contest/1559/problem/A)
Mocha is a young girl from high school. She has learned so much interesting knowledge from her teachers, especially her math teacher. Recently, Mocha is learning about binary system and very interested in bitwise operation.
This day, Mocha got a sequence a of length n. In each operation, she can select an arbitrary interval [l,r] and for all values i (0≤i≤r?l), replace al+i with al+i&ar?i at the same time, where & denotes the bitwise AND operation. This operation can be performed any number of times.
For example, if n=5, the array is [a1,a2,a3,a4,a5], and Mocha selects the interval [2,5], then the new array is [a1,a2&a5,a3&a4,a4&a3,a5&a2].
Now Mocha wants to minimize the maximum value in the sequence. As her best friend, can you help her to get the answer?
Input
Each test contains multiple test cases.
The first line contains a single integer t (1≤t≤100) — the number of test cases. Each test case consists of two lines.
The first line of each test case contains a single integer n (1≤n≤100) — the length of the sequence.
The second line of each test case contains n integers a1,a2,…,an (0≤ai≤109).
Output
For each test case, print one integer — the minimal value of the maximum value in the sequence.
Example
inputCopy
4
2
1 2
3
1 1 3
4
3 11 3 7
5
11 7 15 3 7
outputCopy
0
1
3
3
Note
In the first test case, Mocha can choose the interval [1,2], then the sequence becomes [0,0], where the first element is 1&2, and the second element is 2&1.
In the second test case, Mocha can choose the interval [1,3], then the sequence becomes [1,1,1], where the first element is 1&3, the second element is 1&1, and the third element is 3&1.
题意：给定长度为n的序列，可以进行任意次操作，每次选择区间[l,r],并且用a[l+i]&a[r?i]替换a[l+i]，问你如何操作能使最终数组中最大值最小
两个数做与运算的结果一定不大于二者中的最小值，并且每次我们每次选择相邻两个数与运算后能使最终结果尽可能小，因此，我们只需从头开始，不断用a[i]&a[i+1]更新a[i]和a[i+1],最终a[n-1]就是答案
AC代码：
#include <bits/stdc++.h>
using namespace std;
#define reset(x) memset(x, 0, sizeof(x))
#define Q_in_out \
ios::sync_with_stdio(false); \
cin.tie(0); \
cout.tie(0);
typedef long long int ll;
typedef long double ld;
typedef pair<int, int> P;
#define forl(l,r) for(int i=l;i<r;i++)
#define forr(r,l) for(int i=r;i>=l;i--)
const int N = 1e5+5;
const int modp = 1e9+7;
const int inf = 0x3f3f3f3f;
const double eps = 1e-6;
const double pi = acos(-1.0);
const double e = 2.718281828459045;
int solve()
{
int n;
cin>>n;
ll a[105];
for(int i=0;i<n;i++) cin>>a[i];
for(int i=1;i<n;i++){
a[i]=a[i]&a[i-1];
}
cout<<a[n-1];
return 0;
}
int main()
{
Q_in_out;
int t;
t = 1;
cin >> t;
while (t--)
{
solve();
cout<<endl;
}
return 0;
}
B. Mocha and Red and Blue(http://codeforces.com/contest/1559/problem/B)
As their story unravels, a timeless tale is told once again…
Shirahime, a friend of Mocha’s, is keen on playing the music game Arcaea and sharing Mocha interesting puzzles to solve. This day, Shirahime comes up with a new simple puzzle and wants Mocha to solve them. However, these puzzles are too easy for Mocha to solve, so she wants you to solve them and tell her the answers. The puzzles are described as follow.
There are n squares arranged in a row, and each of them can be painted either red or blue.
Among these squares, some of them have been painted already, and the others are blank. You can decide which color to paint on each blank square.
Some pairs of adjacent squares may have the same color, which is imperfect. We define the imperfectness as the number of pairs of adjacent squares that share the same color.
For example, the imperfectness of “BRRRBBR” is 3, with “BB” occurred once and “RR” occurred twice.
Your goal is to minimize the imperfectness and print out the colors of the squares after painting.
Input
Each test contains multiple test cases.
The first line contains a single integer t (1≤t≤100) — the number of test cases. Each test case consists of two lines.
The first line of each test case contains an integer n (1≤n≤100) — the length of the squares row.
The second line of each test case contains a string s with length n, containing characters ‘B’, ‘R’ and ‘?’. Here ‘B’ stands for a blue square, ‘R’ for a red square, and ‘?’ for a blank square.
Output
For each test case, print a line with a string only containing ‘B’ and ‘R’, the colors of the squares after painting, which imperfectness is minimized. If there are multiple solutions, print any of them.
Example
inputCopy
5
7
?R???BR
7
???R???
1
?
1
B
10
?R??RB??B?
outputCopy
BRRBRBR
BRBRBRB
B
B
BRRBRBBRBR
Note
In the first test case, if the squares are painted “BRRBRBR”, the imperfectness is 1 (since squares 2 and 3 have the same color), which is the minimum possible imperfectness.
题意：给定一个长为n的字符串，字符串由B、R和?组成，对于问号可以让其变成B或者R，问你如何转换所有的问号，让最终字符串不完美值最小，不完美值的定义为:若相邻两个字母相同则不完美值加一，例如:BRRRBBR不完美值为3
对于一个字符串，若其全是问号，我们只用从第一个问号开始交替放置B和R，最终不完美值为0，反之，我们找到第一个不为问号的字母，从该字母左右两端分别从后往前和从前往后交替放置B和R即可
AC代码：
#include <bits/stdc++.h>
using namespace std;
#define reset(x) memset(x, 0, sizeof(x))
#define Q_in_out \
ios::sync_with_stdio(false); \
cin.tie(0); \
cout.tie(0);
typedef long long int ll;
typedef long double ld;
typedef pair<int, int> P;
#define forl(l,r) for(int i=l;i<r;i++)
#define forr(r,l) for(int i=r;i>=l;i--)
const int N = 1e5+5;
const int modp = 1e9+7;
const int inf = 0x3f3f3f3f;
const double eps = 1e-6;
const double pi = acos(-1.0);
const double e = 2.718281828459045;
int solve()
{
int n;
cin>>n;
string s;
cin>>s;
int key=0;
for(int i=0;i<n;i++)
{
if(s[i]!='?'){
key=i;break;
}
}
char tp='B'+'R';
char last='B';
for(int i=key;i<n;i++){
if(s[i]=='?'){
s[i]=last;
last=tp-last;
}
else{
last=tp-s[i];
}
}
for(int i=key;i>=0;i--){
if(s[i]=='?'){
s[i]=last;
last=tp-last;
}
else{
last=tp-s[i];
}
}
cout<<s;
return 0;
}
int main()
{
Q_in_out;
int t;
t = 1;
cin >> t;
while (t--)
{
solve();
cout<<endl;
}
return 0;
}
C. Mocha and Hiking(http://codeforces.com/contest/1559/problem/C)
The city where Mocha lives in is called Zhijiang. There are n+1 villages and 2n?1 directed roads in this city.
There are two kinds of roads:
n?1 roads are from village i to village i+1, for all 1≤i≤n?1.
n roads can be described by a sequence a1,…,an. If ai=0, the i-th of these roads goes from village i to village n+1, otherwise it goes from village n+1 to village i, for all 1≤i≤n.
Mocha plans to go hiking with Taki this weekend. To avoid the trip being boring, they plan to go through every village exactly once. They can start and finish at any villages. Can you help them to draw up a plan?
Input
Each test contains multiple test cases.
The first line contains a single integer t (1≤t≤20) — the number of test cases. Each test case consists of two lines.
The first line of each test case contains a single integer n (1≤n≤104) — indicates that the number of villages is n+1.
The second line of each test case contains n integers a1,a2,…,an (0≤ai≤1). If ai=0, it means that there is a road from village i to village n+1. If ai=1, it means that there is a road from village n+1 to village i.
It is guaranteed that the sum of n over all test cases does not exceed 104.
Output
For each test case, print a line with n+1 integers, where the i-th number is the i-th village they will go through. If the answer doesn’t exist, print ?1.
If there are multiple correct answers, you can print any one of them.
Example
inputCopy
2
3
0 1 0
3
1 1 0
outputCopy
1 4 2 3
4 1 2 3
Note
In the first test case, the city looks like the following graph:
So all possible answers are (1→4→2→3), (1→2→3→4).
In the second test case, the city looks like the following graph:
So all possible answers are (4→1→2→3), (1→2→3→4), (3→4→1→2), (2→3→4→1).
题意：先给定一个n，代表有n+1个节点，并且从节点1开始有，1到2，2到3…,n-1到n各有一条有向边，输入再给出n个数，
若第i个数为0表示从i到n+1有一条单向边，为1表示从n+1到i的单向边，问能不能找到一条路径能遍历所有的节点恰好一次，有输出任意一条这样的路径，否则输出-1。
我们可以明确的一点是:一定有一条路径是：1->2->…->n，因此，若从n+1到1有一条路，即a[1]=1时(a数组是输入的n个数)，有一条路径为：
n+1->1->2->…->n;若从n到n+1有一条路，即a[n]=0时有一条路径:1->2->…->n+1，若以上两种情况均不满足则我们的路径需要以1为起点，因此我们需要从1~n-1之间找到点i和i+1，
其中i到n+1有边，且n+1到i+1有一条边，即a[i]=0且a[i+1]=1,我们能找到路径1->…->i->n+1->i+1->…->n;若上述三种情况均不满足则无解输出-1；
AC代码：
#include <bits/stdc++.h>
using namespace std;
#define reset(x) memset(x, 0, sizeof(x))
#define Q_in_out \
ios::sync_with_stdio(false); \
cin.tie(0); \
cout.tie(0);
typedef long long int ll;
typedef long double ld;
typedef pair<int, int> P;
#define forl(l,r) for(int i=l;i<r;i++)
#define forr(r,l) for(int i=r;i>=l;i--)
const int N = 1e4+5;
const int modp = 1e9+7;
const int inf = 0x3f3f3f3f;
const double eps = 1e-6;
const double pi = acos(-1.0);
const double e = 2.718281828459045;
int solve()
{
int n;
cin>>n;
vector<int>a(n+2,0);
int x;
for(int i=1;i<=n;i++){
cin>>x;
if(!x) a[i]=1;
else a[i]=0;
}
if(a[1]==0){
cout<<n+1<<' ';
for(int i=1;i<=n;i++) cout<<i<<' ';
return 0;
}
if(a[n]){
for(int i=1;i<=n+1;i++) cout<<i<<' ';
return 0;
}
int k1,k2;
int f=0;
for(int i=1;i<=n-1;i++){
if(a[i]==1&&a[i+1]==0){
k1=i;k2=i+1;
f=1;
break;
}
}
if(f){
for(int i=1;i<=k1;i++) cout<<i<<' ';
cout<<n+1<<' ';
for(int i=k2;i<=n;i++) cout<<i<<' ';
return 0;
}
cout<<-1;
return 0;
}
int main()
{
Q_in_out;
int t;
t = 1;
cin >> t;
while (t--)
{
solve();
cout<<endl;
}
return 0;
}
D1. Mocha and Diana (Easy Version)(http://codeforces.com/contest/1559/problem/D1)
This is the easy version of the problem. The only difference between the two versions is the constraint on n. You can make hacks only if all versions of the problem are solved.
A forest is an undirected graph without cycles (not necessarily connected).
Mocha and Diana are friends in Zhijiang, both of them have a forest with nodes numbered from 1 to n, and they would like to add edges to their forests such that:
After adding edges, both of their graphs are still forests.
They add the same edges. That is, if an edge (u,v) is added to Mocha’s forest, then an edge (u,v) is added to Diana’s forest, and vice versa.
Mocha and Diana want to know the maximum number of edges they can add, and which edges to add.
Input
The first line contains three integers n, m1 and m2 (1≤n≤1000, 0≤m1,m2<n) — the number of nodes and the number of initial edges in Mocha’s forest and Diana’s forest.
Each of the next m1 lines contains two integers u and v (1≤u,v≤n, u≠v) — the edges in Mocha’s forest.
Each of the next m2 lines contains two integers u and v (1≤u,v≤n, u≠v) — the edges in Diana’s forest.
Output
The first line contains only one integer h, the maximum number of edges Mocha and Diana can add (in each forest).
Each of the next h lines contains two integers u and v (1≤u,v≤n, u≠v) — the edge you add each time.
If there are multiple correct answers, you can print any one of them.
Examples
inputCopy
3 2 2
1 2
2 3
1 2
1 3
outputCopy
0
inputCopy
5 3 2
5 4
2 1
4 3
4 3
1 4
outputCopy
1
2 4
inputCopy
8 1 2
1 7
2 6
1 5
outputCopy
5
5 2
2 3
3 4
4 7
6 8
Note
In the first example, we cannot add any edge.
In the second example, the initial forests are as follows.
We can add an edge (2,4).
题意：给两张图，往图里添加边时必须同时往两张图的相同两个节点添加，问最多添加多少条边使得两张图中不会产生环
题目中表述得很清楚，我们添加的边不能让图中产生环，因此不能往任意一棵树中的某两个节点添加边，我们可以On^2遍历所有节点判断有哪些节点不处于同一棵树上，若两张图均满足条件则将此边添加进图中并更新信息。
维护上述过程可以通过并查集来完成
AC代码:
#include <bits/stdc++.h>
using namespace std;
#define reset(x) memset(x, 0, sizeof(x))
#define Q_in_out \
ios::sync_with_stdio(false); \
cin.tie(0); \
cout.tie(0);
typedef long long int ll;
typedef long double ld;
typedef pair<int, int> P;
#define forl(l,r) for(int i=l;i<r;i++)
#define forr(r,l) for(int i=r;i>=l;i--)
const int N = 1e4+5;
const int modp = 1e9+7;
const int inf = 0x3f3f3f3f;
const double eps = 1e-6;
const double pi = acos(-1.0);
const double e = 2.718281828459045;
int fa1[N],fa2[N];
int n,m1,m2;
int init(int fa[]){
for(int i=1;i<=n;i++) fa[i]=i;
return 0;
}
int find(int x,int fa[]){
if(x==fa[x]) return x;
return fa[x]=find(fa[x],fa);
}
int Union(int x,int y,int fa[]){
int fax=find(x,fa);
int fay=find(y,fa);
fa[fax]=fay;
return 0;
}
int solve()
{
int a,b;
cin>>n>>m1>>m2;
init(fa1);
init(fa2);
for(int i=0;i<m1;i++){
cin>>a>>b;
Union(a,b,fa1);
}
for(int i=0;i<m2;i++){
cin>>a>>b;
Union(a,b,fa2);
}
vector<pair<int,int>>res;
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
int x,y,x2,y2;
x=find(i,fa1);y=find(j,fa1);
x2=find(i,fa2);y2=find(j,fa2);
if(x!=y&&x2!=y2){
res.push_back({i,j});
Union(x,y,fa1);
Union(x2,y2,fa2);
}
}
}
cout<<res.size()<<endl;
for(auto &v:res) cout<<v.first<<' '<<v.second<<endl;
return 0;
}
int main()
{
Q_in_out;
int t;
t = 1;
while (t--)
{
solve();
cout<<endl;
}
return 0;
}
D2. Mocha and Diana (Hard Version)(http://codeforces.com/contest/1559/problem/D2)
这题和D1的唯一区别就是本题数据范围n变得更大，因此我们不能通过再去枚举所有点对来判断这些点是否可以建边，于是，赛后打开大佬们优美的代码，发现这样一种思路：我们最终把所有的点都合并进入根为1的这棵树中，利用根为1的这棵树来枚举另外不在这棵树上的节点，判断是否能合并，这样遍历复杂度能降到On，具体看代码实现：
AC代码：
#include <bits/stdc++.h>
using namespace std;
#define reset(x) memset(x, 0, sizeof(x))
#define Q_in_out \
ios::sync_with_stdio(false); \
cin.tie(0); \
cout.tie(0);
typedef long long int ll;
typedef long double ld;
typedef pair<int, int> P;
#define forl(l,r) for(int i=l;i<r;i++)
#define forr(r,l) for(int i=r;i>=l;i--)
const int N = 1e5+5;
const int modp = 1e9+7;
const int inf = 0x3f3f3f3f;
const double eps = 1e-6;
const double pi = acos(-1.0);
const double e = 2.718281828459045;
int fa1[N],fa2[N];
int n,m1,m2;
int init(int fa[]){
for(int i=1;i<=n;i++) fa[i]=i;
return 0;
}
int find(int x,int fa[]){
if(x==fa[x]) return x;
return fa[x]=find(fa[x],fa);
}
int Union(int x,int y,int fa[]){
int fax=find(x,fa);
int fay=find(y,fa);
if(fax<fay) fa[fay]=fax;
else fa[fax]=fay;
return 0;
}
int solve()
{
int a,b;
cin>>n>>m1>>m2;
init(fa1);
init(fa2);
for(int i=0;i<m1;i++){
cin>>a>>b;
Union(a,b,fa1);
}
for(int i=0;i<m2;i++){
cin>>a>>b;
Union(a,b,fa2);
}
cout<<n-1-max(m1,m2)<<endl;
for(int i=2;i<=n;i++){
int t1=find(i,fa1);
int t2=find(i,fa2);
if(t1!=1&&t2!=1){
cout<<i<<" 1"<<endl;
fa1[t1]=1;fa2[t2]=1;
}
}
vector<int>res1,res2;
for(int i=2;i<=n;i++){
int t1=find(i,fa1),t2=find(i,fa2);
if(t1!=1) {res1.push_back(i);fa1[t1]=1;}
else if(t2!=1) {res2.push_back(i);fa2[t2]=1;}
}
for(int i=0;i<min(res1.size(),res2.size());i++) cout<<res1[i]<<' '<<res2[i]<<endl;
return 0;
}
int main()
{
Q_in_out;
int t;
t = 1;
while (t--)
{
solve();
cout<<endl;
}
return 0;
}
|