codeforces每日5题(均1500)-第十一天_yxoryq

k-Multiple Free Set

题面翻译

翻译：

有一个序列n。和一个数k

你要从中挑出尽可能多的数，保证其中不存在一对数，满足一个数是另一个数的k倍。

求最多的挑出的数。

输入格式：
第一行一个数n

第二行n个数a[i]

输出格式：
一个数表示答案。

题目描述

A $k$ -multiple free set is a set of integers where there is no pair of integers where one is equal to another integer multiplied by $k$ .

That is, there are no two integers $x$ and $y$ $(x<y)$ from the set, such that $y=x\cdot k$ .

You’re given a set of $n$ distinct positive integers.

Your task is to find the size of it’s largest $k$ -multiple free subset.

输入格式

The first line of the input contains two integers $n$ and $k$ ( $1<=n<=10^5,1<=k<=10^9$ ).

The next line contains a list of $n$ distinct positive integers $a_1,a_2,...,a_n$ $(1<=a_i<=10^9)$ .

All the numbers in the lines are separated by single spaces.

输出格式

On the only line of the output print the size of the largest $k$ -multiple free subset of $a_1,a_2,...,a_n$ .

样例 #1

样例输入 #1

6 2
2 3 6 5 4 10
1
2

样例输出 #1

3
1

提示

In the sample input one of the possible maximum 2-multiple free subsets is {4, 5, 6}.

#include<bits/stdc++.h>
using namespace std; 
const int N=1e5+10;
typedef long long ll;
ll n,k;
ll a[N],ss=0;
map<ll,bool> s;
int main() {
 cin>>n>>k;
 for(int i=1;i<=n;i++){
 	scanf("%lld",&a[i]);
 }
 sort(a+1, a + n+1);
 for (int i=1;i<=n;i++) {
  	if(s[a[i]]==0){
  		s[a[i]*k]=1;
  		ss++;
 	}
}
cout<<ss<<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

Little Girl and Maximum Sum

题面翻译

有$n$个数字，为$a[1]...a[n]$，$q$个询问。

每次读入$l,r$，询问${\sum }_{i=l}^{r}a[i]$。

这样岂不是很水！

于是你可以重新排列读入的$a$数组，使询问的总和最大。

输出这个最大值。

$n,q\le 2\times 10^5$

$1\le a_i\le 2\times 10^5$

$1\le l_i\le r_i\le n$

题目描述

The little girl loves the problems on array queries very much.

One day she came across a rather well-known problem: you’ve got an array of $n$ elements (the elements of the array are indexed starting from 1); also, there are $q$ queries, each one is defined by a pair of integers $l_i$ , $r_i$ $(1<=l_i<=r_i<=n)$ .

You need to find for each query the sum of elements of the array with indexes from $l_i$ to $r_i$ , inclusive.

The little girl found the problem rather boring.

She decided to reorder the array elements before replying to the queries in a way that makes the sum of query replies maximum possible.

Your task is to find the value of this maximum sum.

输入格式

The first line contains two space-separated integers $n$ ( $1<=n<=2\cdot 10^5$ ) and $q$ ( $1<=q<=2\cdot 10^5$ ) — the number of elements in the array and the number of queries, correspondingly.

The next line contains $n$ space-separated integers $a_i$ ( $1<=a_i<=2\cdot 10^5$ ) — the array elements.

Each of the following $q$ lines contains two space-separated integers $l_i$ and $r_i$ ( $1<=l_i<=r_i<=n$ ) — the $i$ -th query.

输出格式

In a single line print a single integer — the maximum sum of query replies after the array elements are reordered.

Please, do not use the %lld specifier to read or write 64-bit integers in С++.

It is preferred to use the cin, cout streams or the %I64d specifier.

样例 #1

样例输入 #1

3 3
5 3 2
1 2
2 3
1 3
1
2
3
4
5

样例输出 #1

25
1

样例 #2

样例输入 #2

5 3
5 2 4 1 3
1 5
2 3
2 3
1
2
3
4
5

样例输出 #2

33
1

#include<bits/stdc++.h>
using namespace std; 
const int N=2e5+10;
typedef long long ll;
ll n,q,a[N],s=0,l,r,b[N];
int main() {
 	cin>>n>>q;
 	for(ll i=1;i<=n;i++){
 		scanf("%lld",&a[i]);
 	}
 	sort(a+1,a+1+n);
 	for(ll i=1;i<=q;i++){
 		scanf("%lld%lld",&l,&r);
 		b[l]++;
 		b[r+1]--;
 	}
 	for(ll i=1;i<=n;i++){
 		b[i]+=b[i-1];
 	}
 	sort(b+1,b+1+n);
 	for(ll i=1;i<=n;i++){
 		s+=b[i]*a[i];
 	}
 	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

XOR and OR

题面翻译

给定两个$01$ 串$,$ 问$A$ 是否可以通过相邻两位的异或和或操作得到$B$ 串。

异或$:01/10\to 11,11\to 10/01$

或$:10/01\to 11$

题目描述

The Bitlandians are quite weird people.

They do everything differently.

They have a different alphabet so they have a different definition for a string.

A Bitlandish string is a string made only of characters “0” and “1”.

BitHaval (the mayor of Bitland) loves to play with Bitlandish strings.

He takes some Bitlandish string $a$ , and applies several (possibly zero) operations to it.

In one operation the mayor may take any two adjacent characters of a string, define one of them as $x$ and the other one as $y$ .

Then he calculates two values $p$ and $q$ : $p=xxory$ , $q=xory$ .

Then he replaces one of the two taken characters by $p$ and the other one by $q$ .

The $xor$ operation means the bitwise excluding OR operation.

The $or$ operation is the bitwise OR operation.

So for example one operation can transform string 11 to string 10 or to string 01.

String 1 cannot be transformed into any other string.

You’ve got two Bitlandish strings $a$ and $b$ .

Your task is to check if it is possible for BitHaval to transform string $a$ to string $b$ in several (possibly zero) described operations.

输入格式

The first line contains Bitlandish string $a$ , the second line contains Bitlandish string $b$ .

The strings can have different lengths.

It is guaranteed that the given strings only consist of characters “0” and “1”.

The strings are not empty, their length doesn’t exceed $10^6$ .

输出格式

Print “YES” if $a$ can be transformed into $b$ , otherwise print “NO”.

Please do not print the quotes.

样例 #1

样例输入 #1

11
10
1
2

样例输出 #1

YES
1

样例 #2

样例输入 #2

1
01
1
2

样例输出 #2

NO
1

样例 #3

样例输入 #3

000
101
1
2

样例输出 #3

NO
1

#include<bits/stdc++.h>
using namespace std; 
const int N=1e6+10;
typedef long long ll;
char a[N],b[N];
int n1,n2,f1,f2;
int main() {
 	scanf("%s %s",a+1,b+1);
	int l1=strlen(a+1),l2=strlen(b+1);
	if(l1!=l2){
	printf("NO");return 0;
	}
	for(int i=1;i<=l1;i++){
		if(a[i]=='1'){f1=1;break;}
	}
	for(int i=1;i<=l1;i++){
		if(b[i]=='1'){f2=1;break;}
	}
	if((f1&&f2)||(!f1&&!f2)) printf("YES");
	else printf("NO");
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

Painting Eggs

题面翻译

问题描述

有$n$ 个蛋，A和G需要给这$n$ 个鸡蛋涂色。A涂第$i$ 个鸡蛋得到的钱为$A_i$ ，G涂第$i$ 个鸡蛋得到的钱为$G_i$ ，且满足$A_i+G_i=1000$ 。需要把这$n$ 个鸡蛋分配给A和G，求怎样分配使得A和G得到的钱$S_A$ 和$S_G$ 的差不超过$500$ 。

输入输出格式

输入格式：

第一行一个整数$n(1\le n\le 10^6)$ 。

接下来$n$ 行，每行两个整数$A_i,G_i(0\le A_i,G_i\le 1000,A_i+G_i=1000)$ 。

输出格式：

一行，长度为$n$ 的字符串，第$i$ 个字符为A或G，表示分配方案。

有多种解输出任意一种，需要满足$|S_A-S_G|\le 500$ 。

题目描述

The Bitlandians are quite weird people.

They have very peculiar customs.

As is customary, Uncle J. wants to have $n$ eggs painted for Bitruz (an ancient Bitland festival).

He has asked G. and A. to do the work.

The kids are excited because just as is customary, they’re going to be paid for the job!

Overall uncle J. has got $n$ eggs. G. named his price for painting each egg.

Similarly, A. named his price for painting each egg.

It turns out that for each egg the sum of the money both A. and G. want for the painting equals $1000$ .

Uncle J. wants to distribute the eggs between the children so as to give each egg to exactly one child.

Also, Uncle J. wants the total money paid to A. to be different from the total money paid to G. by no more than $500$ .

Help Uncle J.

Find the required distribution of eggs or otherwise say that distributing the eggs in the required manner is impossible.

输入格式

The first line contains integer $n$ $(1<=n<=10^6)$ — the number of eggs.

Next $n$ lines contain two integers $a_i$ and $g_i$ each $(0<=a_i,g_i<=1000;a_i+g_i=1000)$ : $a_i$ is the price said by A.

for the $i$ -th egg and $g_i$ is the price said by G.

for the $i$ -th egg.

输出格式

If it is impossible to assign the painting, print “-1” (without quotes).

Otherwise print a string, consisting of $n$ letters “G” and “A”.

The $i$ -th letter of this string should represent the child who will get the $i$ -th egg in the required distribution.

Letter “A” represents A.

and letter “G” represents G.

If we denote the money Uncle J. must pay A. for the painting as $S_a$ , and the money Uncle J. must pay G. for the painting as $S_g$ , then this inequality must hold: $|S_a-S_g|<=500$ .

If there are several solutions, you are allowed to print any of them.

样例 #1

样例输入 #1

2
1 999
999 1
1
2
3

样例输出 #1

AG
1

样例 #2

样例输入 #2

3
400 600
400 600
400 600
1
2
3
4

样例输出 #2

AGA
1

#include<bits/stdc++.h>
using namespace std; 
const int N=1e6+10;
typedef long long ll;
int n,a[N],b[N];
int sa=0,sb=0;
string s;
int main() {
 	cin>>n;
 	for(int i=1;i<=n;i++){
 		scanf("%d %d",&a[i],&b[i]);
 	}
 	for(int i=1;i<=n;i++){
 		if(abs(sa+a[i]-sb)>500){
 			sb+=b[i];
 			s+='G';
		}
		else sa+=a[i],s+='A';
	 }
	 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

Weird Game

题面翻译

下面仅仅是题意简述（就是只能不影响做题，想看故事还是需要英文水平的）

---

有一天，小A和小B很无聊，于是一起玩游戏，游戏是这样的：先给定一个 n ，然后一行给一个只由‘0’和‘1’组成的数列，它们的长度均为 2n ，小A从第一行中选择数，小B从第二行中选择数，小A先选择一个数，假设取的是第 k 个数，那么小B和小A从今往后再也不能选第k个数，当所有人都不能选数时，游戏结束。小A（B）可以任意排列自己拿到的数字，组成一个数，谁的数大谁获胜。
小A获胜则输出“First”
小B获胜则输出“Second”
平局的话输出“Draw”
（输出引号）
输入：第一行一个 n
接下来两行每行一个长度为 2n 的数字
输出：一个字符串（见题意）

题目描述

Yaroslav, Andrey and Roman can play cubes for hours and hours.

But the game is for three, so when Roman doesn’t show up, Yaroslav and Andrey play another game.

Roman leaves a word for each of them.

Each word consists of $2\cdot n$ binary characters “0” or “1”.

After that the players start moving in turns.

Yaroslav moves first.

During a move, a player must choose an integer from 1 to $2\cdot n$ , which hasn’t been chosen by anybody up to that moment.

Then the player takes a piece of paper and writes out the corresponding character from his string.

Let’s represent Yaroslav’s word as $s=s_1{s}_2...s_{2n}$ .

Similarly, let’s represent Andrey’s word as $t=t_1{t}_2...t_{2n}$ .

Then, if Yaroslav choose number $k$ during his move, then he is going to write out character $s_k$ on the piece of paper.

Similarly, if Andrey choose number $r$ during his move, then he is going to write out character $t_r$ on the piece of paper.

The game finishes when no player can make a move.

After the game is over, Yaroslav makes some integer from the characters written on his piece of paper (Yaroslav can arrange these characters as he wants).

Andrey does the same.

The resulting numbers can contain leading zeroes.

The person with the largest number wins.

If the numbers are equal, the game ends with a draw.

You are given two strings $s$ and $t$ .

Determine the outcome of the game provided that Yaroslav and Andrey play optimally well.

输入格式

The first line contains integer $n$ ( $1<=n<=10^6$ ).

The second line contains string $s$ — Yaroslav’s word.

The third line contains string $t$ — Andrey’s word.

It is guaranteed that both words consist of $2\cdot n$ characters “0” and “1”.

输出格式

Print “First”, if both players play optimally well and Yaroslav wins.

If Andrey wins, print “Second” and if the game ends with a draw, print “Draw”.

Print the words without the quotes.

样例 #1

样例输入 #1

2
0111
0001
1
2
3

样例输出 #1

First
1

样例 #2

样例输入 #2

3
110110
001001
1
2
3

样例输出 #2

First
1

样例 #3

样例输入 #3

3
111000
000111
1
2
3

样例输出 #3

Draw
1

样例 #4

样例输入 #4

4
01010110
00101101
1
2
3

样例输出 #4

First
1

样例 #5

样例输入 #5

4
01100000
10010011
1
2
3

样例输出 #5

Second
1

#include<bits/stdc++.h>
using namespace std; 
const int N=2e6+10;
typedef long long ll;
string a,b;
int x=0,y=0,z=0,s=0,enda=0,endb=0;
int n;
int main() {
 	scanf("%n",&n);
 	n*=2;
 	cin>>a>>b;
	for(int i=1;i<=n;i++){
		if(a[i]=='1'&&b[i]=='1') x++;
		else if(a[i]=='0'&&b[i]=='1') y++;
		else if(a[i]=='1'&&b[i]=='0') z++;
	}
	s=min(y,z);
	y-=s;
	z-=s;
	x%=2;
	enda+=x;
	if(enda){
		enda+=z/2;
		endb+=y/2+y%2;
	}
	else{
		enda+=z/2+z%2;
		endb+=y/2;
	}
	if(enda>endb) printf("First");
	else if(enda<endb) printf("Second");
	else printf("Draw");
	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
29
30
31
32
33
34