codeforces每日5题(均1500)-第十六天_codeforce 题目翻译

Arpa’s obvious problem and Mehrdad’s terrible solution

题面翻译

给出一串数组a1…an，和一个数字x，询问有多少对ai,aj满足ai^aj=x

题目描述

There are some beautiful girls in Arpa’s land as mentioned before.

Once Arpa came up with an obvious problem:

Given an array and a number $x$ , count the number of pairs of indices $i,j$ ( KaTeX parse error: Expected 'EOF', got '&' at position 5: 1<=i&̲lt;j<=n ) such that , where is bitwise xor operation (see notes for explanation).

Immediately, Mehrdad discovered a terrible solution that nobody trusted.

Now Arpa needs your help to implement the solution to that problem.

输入格式

First line contains two integers $n$ and $x$ ( $1<=n<=10^5,0<=x<=10^5$ ) — the number of elements in the array and the integer $x$ .

Second line contains $n$ integers $a_1,a_2,...,a_n$ ( $1<=a_i<=10^5$ ) — the elements of the array.

输出格式

Print a single integer: the answer to the problem.

样例 #1

样例输入 #1

2 3
1 2
1
2

样例输出 #1

1
1

样例 #2

样例输入 #2

6 1
5 1 2 3 4 1
1
2

样例输出 #2

2
1

提示

In the first sample there is only one pair of $i=1$ and $j=2$ . so the answer is $1$ .

In the second sample the only two pairs are $i=3$ , $j=4$ (since ) and $i=1$ , $j=5$ (since ).

A bitwise xor takes two bit integers of equal length and performs the logical xor operation on each pair of corresponding bits.

The result in each position is $1$ if only the first bit is $1$ or only the second bit is $1$ , but will be $0$ if both are $0$ or both are $1$ .

You can read more about bitwise xor operation here: https://en.wikipedia.org/wiki/Bitwise_operation#XOR.

#include<bits/stdc++.h>
using namespace std; 
const int N=2e5+10;
typedef long long ll;
int n,x,k,a[N];
ll s=0;
int main(){
    cin>>n>>x;
    while(n--){
    	scanf("%d",&k);
    	s+=a[x^k];
    	++a[k];
	}
	cout<<s<<endl;
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

Santa Claus and Keyboard Check

题面翻译

题义翻译

圣诞老人拆开、清洁了他的键盘，但是在将所有的按键安好后，他发现一些按键的位置发生了两两交换！

于是，圣诞老人猜测对于键盘上的每一个按键，要么在它本来正确的位置，
要么与另一个按键交换了位置。

为了验证他的猜想，他决定只根据正确的按键位置打出他最爱的文字。

现给出圣诞老人要打出的字符串 s，和他实际敲出的字符串 t,请你确定
哪几组字母发生了两两交换（即每对交换位置的字母不应出现在其他字母对中）

输入格式

非空、等长，且长度最大为1000 的字符串 s、t，所有字母均为小写字母

输出格式

如果圣诞老人的猜想是错的，那么无法将位置交换的按键分为两两一组，此时输出“-1”（不含引号）
否则输出第一行只包含一个非负整数k（可以为0）：交换位置的字母对数；下面的k行分别输出每对交换位置的字母，用空格隔开；所有字母至多出现一次。
如果存在多种答案，输出任意一种；输出字母对的顺序以及每个字母对中两个字母的顺序任意。

题目描述

Santa Claus decided to disassemble his keyboard to clean it.

After he returned all the keys back, he suddenly realized that some pairs of keys took each other’s place!

That is, Santa suspects that each key is either on its place, or on the place of another key, which is located exactly where the first key should be.

In order to make sure that he’s right and restore the correct order of keys, Santa typed his favorite patter looking only to his keyboard.

You are given the Santa’s favorite patter and the string he actually typed.

Determine which pairs of keys could be mixed.

Each key must occur in pairs at most once.

输入格式

The input consists of only two strings $s$ and $t$ denoting the favorite Santa’s patter and the resulting string.

$s$ and $t$ are not empty and have the same length, which is at most $1000$ .

Both strings consist only of lowercase English letters.

输出格式

If Santa is wrong, and there is no way to divide some of keys into pairs and swap keys in each pair so that the keyboard will be fixed, print «-1» (without quotes).

Otherwise, the first line of output should contain the only integer $k$ ( $k>=0$ ) — the number of pairs of keys that should be swapped.

The following $k$ lines should contain two space-separated letters each, denoting the keys which should be swapped.

All printed letters must be distinct.

If there are several possible answers, print any of them.

You are free to choose the order of the pairs and the order of keys in a pair.

Each letter must occur at most once.

Santa considers the keyboard to be fixed if he can print his favorite patter without mistakes.

样例 #1

样例输入 #1

helloworld
ehoolwlroz
1
2

样例输出 #1

3
h e
l o
d z
1
2
3
4

样例 #2

样例输入 #2

hastalavistababy
hastalavistababy
1
2

样例输出 #2

0
1

样例 #3

样例输入 #3

merrychristmas
christmasmerry
1
2

样例输出 #3

-1
1

#include<bits/stdc++.h>
using namespace std; 
const int N=2e5+10;
typedef long long ll;
int n,k=0,s[N],sign[N];
string a,b;
int main(){
   cin>>a>>b;
   	for(int i=0;i<a.size();i++){
   		if(sign[a[i]]==0&&sign[b[i]]==0){
   			sign[a[i]]=b[i];
			sign[b[i]]=a[i];
			if(a[i]!=b[i]) s[++k]=a[i];
		}
		else if(sign[a[i]]!=b[i]||sign[b[i]]!=a[i]){
			puts("-1");
			return 0;
		}
   	}
   	cout<<k<<endl;
   	for(int i=1;i<=k;i++){
   		char x,y;
   		x=s[i];
   		y=sign[x];
   		cout<<x<<" "<<y<<endl;
	}
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

Green and Black Tea

题面翻译

Innokentiy非常喜欢茶，今天他想喝$n$杯茶。他有$a$包绿茶和$b$包红茶。
Innokentiy不喜欢喝同一种茶（绿色或红色）连续超过$k$次。

你的任务是确定喝茶的顺序（用G表示绿茶，B表示红茶。详情请参考样例）以便Innokentiy可以喝$n$杯茶，不喝同样的茶连续超过$k$次。如果你不能做到，输出“NO”。

题目描述

Innokentiy likes tea very much and today he wants to drink exactly $n$ cups of tea.

He would be happy to drink more but he had exactly $n$ tea bags, $a$ of them are green and $b$ are black.

Innokentiy doesn’t like to drink the same tea (green or black) more than $k$ times in a row.

Your task is to determine the order of brewing tea bags so that Innokentiy will be able to drink $n$ cups of tea, without drinking the same tea more than $k$ times in a row, or to inform that it is impossible.

Each tea bag has to be used exactly once.

输入格式

The first line contains four integers $n$ , $k$ , $a$ and $b$ ( $1<=k<=n<=10^5$ , $0<=a,b<=n$ ) — the number of cups of tea Innokentiy wants to drink, the maximum number of cups of same tea he can drink in a row, the number of tea bags of green and black tea.

It is guaranteed that $a+b=n$ .

输出格式

If it is impossible to drink $n$ cups of tea, print “NO” (without quotes).

Otherwise, print the string of the length $n$ , which consists of characters ‘G’ and ‘B’.

If some character equals ‘G’, then the corresponding cup of tea should be green.

If some character equals ‘B’, then the corresponding cup of tea should be black.

If there are multiple answers, print any of them.

样例 #1

样例输入 #1

5 1 3 2
1

样例输出 #1

GBGBG
1

样例 #2

样例输入 #2

7 2 2 5
1

样例输出 #2

BBGBGBB
1

样例 #3

样例输入 #3

4 3 4 0
1

样例输出 #3

NO
1

#include<bits/stdc++.h>
using namespace std; 
const int N=2e5+10;
typedef long long ll;
int n,k,a,b,p=0;
char sa='G',sb='B';
string s;
int main(){
   cin>>n>>k>>a>>b;
   	while(a+b>0){
   		if(a<b||p>=k){
   			swap(a,b);
   			swap(sa,sb);
   			p=0;
		}
		if(a<=0){
			puts("NO");
			return 0;
		}
		a--;
		p++;
		s+=sa;
   	}
   	cout<<s<<endl;
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

Checkpoints

题面翻译

数轴上有 $n$ 个点，分别编号为 $1, 2, ..., n $。你初始位置在 $a$ ，要经过其中的 $n-1$ 个点，求最小总行走距离。

## 输入格式
第一行两个正整数 $n$ 和 $a$。

第二行 $n$ 个正整数 $x_1, x_2, ..., x_n$，表示各个点的位置。

$1 \leq n \leq 10^5, -10^6 \leq a, x_i \leq 10^6$

## 输出格式
一行，一个正整数，表示最小的总行走距离。
1
2
3
4
5
6
7
8
9
10
11

题目描述

Vasya takes part in the orienteering competition.

There are $n$ checkpoints located along the line at coordinates $x_1,x_2,...,x_n$ .

Vasya starts at the point with coordinate $a$ .

His goal is to visit at least $n-1$ checkpoint in order to finish the competition.

Participant are allowed to visit checkpoints in arbitrary order.

Vasya wants to pick such checkpoints and the order of visiting them that the total distance travelled is minimized.

He asks you to calculate this minimum possible value.

输入格式

The first line of the input contains two integers $n$ and $a$ ( $1<=n<=100000$ , $-1000000<=a<=1000000$ ) — the number of checkpoints and Vasya’s starting position respectively.

The second line contains $n$ integers $x_1,x_2,...,x_n$ ( $-1000000<=x_i<=1000000$ ) — coordinates of the checkpoints.

输出格式

Print one integer — the minimum distance Vasya has to travel in order to visit at least $n-1$ checkpoint.

样例 #1

样例输入 #1

3 10
1 7 12
1
2

样例输出 #1

7
1

样例 #2

样例输入 #2

2 0
11 -10
1
2

样例输出 #2

10
1

样例 #3

样例输入 #3

5 0
0 0 1000 0 0
1
2

样例输出 #3

0
1

提示

In the first sample Vasya has to visit at least two checkpoints.

The optimal way to achieve this is the walk to the third checkpoints (distance is $12-10=2$ ) and then proceed to the second one (distance is $12-7=5$ ).

The total distance is equal to $2+5=7$ .

In the second sample it’s enough to visit only one checkpoint so Vasya should just walk to the point $-10$ .

#include<bits/stdc++.h>
using namespace std; 
const int N=1e5+10;
typedef long long ll;
int n,a,b[N],s=INT_MAX;
int main(){
    cin>>n>>a;
    for(int i=1;i<=n;i++){
    	scanf("%d",&b[i]);
	}
	if(n==1) cout<<0<<endl;
	else{
	sort(b+1,b+1+n);
	s=min(min(abs(b[n]-a)+abs(b[n]-b[2]),abs(b[2]-a)+abs(b[n]-b[2])),min(abs(b[n-1]-a)+abs(b[n-1]-b[1]),abs(b[1]-a)+abs(b[n-1]-b[1])));
    cout<<s<<endl;}
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

Powers of Two

题面翻译

给一个长度为$n$的序列$a$

从中选取$a_i,a_j$,使$a_i+a_j=2^x,(x\in N^{\ast },i<j)$

求序列中有多少对这样的数

$P.S$：

样例1：有$(1,4),(2,4)$两对数

题目描述

You are given $n$ integers $a_1,a_2,...,a_n$ .

Find the number of pairs of indexes $i,j$ ( KaTeX parse error: Expected 'EOF', got '&' at position 2: i&̲lt;j ) that $a_i+a_j$ is a power of $2$ (i. e. some integer $x$ exists so that $a_i+a_j=2^x$ ).

输入格式

The first line contains the single positive integer $n$ ( $1<=n<=10^5$ ) — the number of integers.

The second line contains $n$ positive integers $a_1,a_2,...,a_n$ ( $1<=a_i<=10^9$ ).

输出格式

Print the number of pairs of indexes $i,j$ ( KaTeX parse error: Expected 'EOF', got '&' at position 2: i&̲lt;j ) that $a_i+a_j$ is a power of $2$ .

样例 #1

样例输入 #1

4
7 3 2 1
1
2

样例输出 #1

2
1

样例 #2

样例输入 #2

3
1 1 1
1
2

样例输出 #2

3
1

提示

In the first example the following pairs of indexes include in answer: $(1,4)$ and $(2,4)$ .

In the second example all pairs of indexes $(i,j)$ (where KaTeX parse error: Expected 'EOF', got '&' at position 2: i&̲lt;j ) include in answer.

#include<bits/stdc++.h>
using namespace std; 
const int N=1e5+10;
typedef long long ll;
int n,a[N];
ll enD=0;
map<int,int> s;
map<int,int>:: iterator it;
int main(){
    cin>>n;
    for(int i=1;i<=n;i++){
    	cin>>a[i];
	}
	for(ll x=2;x<=2e9;x<<=1,s.clear()){
		for(int i=n;i>=1;i--){
			it=s.find(x-a[i]);
			if(it!=s.end()) enD+=s[x-a[i]];
			s[a[i]]++;
		}
	}
	cout<<enD<<endl;
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23