Codeforces Round #704 (Div. 2) 赛后补题题解_you are given three integers n,a,b. determine if t

div2任意门.

这次题目本来有 很大机会 做出C，实力不够哇

A.Three swimmers

题目
Three swimmers decided to organize a party in the swimming pool! At noon, they started to swim from the left side of the pool.

It takes the first swimmer exactly a minutes to swim across the entire pool and come back, exactly b minutes for the second swimmer and c minutes for the third. Hence, the first swimmer will be on the left side of the pool after 0, a, 2a, 3a, … minutes after the start time, the second one will be at 0, b, 2b, 3b, … minutes, and the third one will be on the left side of the pool after 0, c, 2c, 3c, … minutes.

You came to the left side of the pool exactly p minutes after they started swimming. Determine how long you have to wait before one of the swimmers arrives at the left side of the pool.

输入

The first line of the input contains a single integer t (1≤t≤1000) — the number of test cases. Next t lines contains test case descriptions, one per line.

Each line contains four integers p, a, b and c (1≤p,a,b,c≤10¹⁸), time in minutes after the start, when you came to the pool and times in minutes it take the swimmers to cross the entire pool and come back.

输出

For each test case, output one integer — how long you have to wait (in minutes) before one of the swimmers arrives at the left side of the pool.

样例
input
4
9 5 4 8
2 6 10 9
10 2 5 10
10 9 9 9
output
1
4
0
8

题目大意

有三名游泳的人，他们分别需要a,b,c分钟才能在一个游泳池游一个来回，第一个游泳者将在开始时间0，a，2a，3a，…分钟后在游泳池的左侧，第二个游泳者将在0，b，2b，3b，…分钟后，第三个将在0，c，2c，3c，…分钟后出现在池的左侧。
p分钟后最少需要等待多长时间会有一个游泳者到达游泳池左侧。

思路

暴力遍历a，b，c找最小值，a，b，c的倍数离p差多少

代码

#include <iostream>
#include <cmath>

using namespace std;

typedef long long ll;

int t; 

int main()
{
	cin >> t;
	
	while(t --)
	{
		ll p,a,b,c;
		cin >> p >> a >> b >> c;
		
		ll v[3] = {a,b,c};
		ll cnt = 1000000000000000001;
		for(int i = 0;i < 3;i ++)
		{
			ll x = ceil(p * 1.0 / v[i]);
			ll ans = fabs(x * v[i] - p);
			
			cnt = min(cnt,ans);
		}
		
		cout << cnt << 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
29
30
31
32
33

很简单的签到题

B. Card Deck

题目

You have a deck of n cards, and you’d like to reorder it to a new one.

Each card has a value between 1 and n equal to pi. All pi are pairwise distinct. Cards in a deck are numbered from bottom to top, i. e. p1 stands for the bottom card, pn is the top card.

In each step you pick some integer k>0, take the top k cards from the original deck and place them, in the order they are now, on top of the new deck. You perform this operation until the original deck is empty. (Refer to the notes section for the better understanding.)

Let’s define an order of a deck as ∑_i=1 ⁿ nⁿ⁻ⁱ⋅pi.

Given the original deck, output the deck with maximum possible order you can make using the operation above.

输入

The first line contains a single integer t (1≤t≤1000) — the number of test cases.

The first line of each test case contains the single integer n (1≤n≤10⁵) — the size of deck you have.

The second line contains n integers p₁,p₂,…,p_n (1≤p_i≤n; p_i≠p_j if i≠j) — values of card in the deck from bottom to top.

It’s guaranteed that the sum of n over all test cases doesn’t exceed 10⁵.

输出

For each test case print the deck with maximum possible order. Print values of cards in the deck from bottom to top.

If there are multiple answers, print any of them.

样例

input
4
4
1 2 3 4
5
1 5 2 4 3
6
4 2 5 3 6 1
1
1
output
4 3 2 1
5 2 4 3 1
6 1 5 3 4 2
1

题目大意

有n张卡，每张卡的值1-n，等于p_i，p₁代表底卡，p_n是顶卡，在每个步骤中，选择一些k > 0的整数，从原始卡片组中取出前k张卡片，然后按它们现在的顺序将它们放置在新卡片组的顶部。让阶数最大。

思路

找最大的数输出最大的数加后边的所有数，接着找第二个······注意不要重复输出

代码

#include <iostream>
#include <map>
#include <algorithm>
#include <cmath>

using namespace std;

typedef long long ll;

const int N = 1e5 + 10;

int t;
int n;

int main()
{
	scanf("%d",&t);
	
	while(t --)
	{
		scanf("%d",&n);
		int p[N],hp[N],ph[N],e[N];

		for(int i = 1;i <= n;i ++)
		{
			scanf("%d",&p[i]);
			ph[p[i]] = i;
			hp[i] = p[i];
			e[p[i]] = 1;
		}
		
		sort(p + 1,p + 1 + n);
		
		int h = n;
		for(int i = n;i >= 1;i --)
		{
			if(e[p[i]])
			{
				int j = ph[p[i]];
				for(int k = j;k <= h;k ++)
				{
					printf("%d ",hp[k]);
					e[hp[k]] = 0;
					
				}
				h = j - 1;
			} 
		}
			
		
		puts("");
	//	cout << ans << endl;
	}
}
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
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54

刚开始超时了好多次wa的心态崩了，最后发现重复判断了，爆哭

C. Maximum width

题目
Your classmate, whom you do not like because he is boring, but whom you respect for his intellect, has two strings: s of length n and t of length m.

A sequence p₁,p₂,…,p_m, where 1≤p₁<p₂<…<p_m≤n, is called beautiful, if s_pi=t_i for all i from 1 to m. The width of a sequence is defined as max_1≤i<m(p_i+1−p_i).

Please help your classmate to identify the beautiful sequence with the maximum width. Your classmate promised you that for the given strings s and t there is at least one beautiful sequence.

输入

The first input line contains two integers n and m (2≤m≤n≤2⋅10⁵) — the lengths of the strings s and t.

The following line contains a single string s of length n, consisting of lowercase letters of the Latin alphabet.

The last line contains a single string t of length m, consisting of lowercase letters of the Latin alphabet.

It is guaranteed that there is at least one beautiful sequence for the given strings.

输出

Output one integer — the maximum width of a beautiful sequence.

样例
input
5 3
abbbc
abc
output
3

input
5 2
aaaaa
aa
output
4

input
5 5
abcdf
abcdf
output
1

input
2 2
ab
ab
output
1

题目大意

给你两个字符串s,t找s串和t串匹配的下标，然后找相邻下标之间的最大值，管你懂不懂看样例就完事了

思路

前后扫一遍，分别用两个数组去存前后扫的下标结果，取两个数组相邻位置的最大值

代码

#include <iostream>
#include <string>

using namespace std;

const int  N = 2e5 + 10;

int n,m,a[N],b[N];
string s,t;

int main()
{
	cin >> n >> m;
	cin >> s >> t;
	

	int i = 0,j = 0;
	while(j < m)
	{
		if(s[i] == t[j])
		{
			a[j] = i + 1;
			i ++;
			j ++;
		}else i ++;
	}
//	for(int q = 0;q < k;q ++) cout << p[q];
//	for(int q = 0;q < k;q ++) cout << p[q];
	
	i = n - 1,j = m - 1;
	while(j > 0)
	{
		if(s[i] == t[j])
		{
			b[j] = i + 1;
			i --;
			j --;
		}else i --;
	}
	
	
	int ans = 0;
	for(int q = 0;q < m;q ++) ans = max(ans,b[q + 1] - a[q]);
	
	cout << ans << 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
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48

本来有机会做出来的，比赛的时候前后扫的结果存到一个数组里边去了，就很鸡肋

D. Genius’s Gambit

题目
You are given three integers a, b, k.

Find two binary integers x and y (x≥y) such that

1.both x and y consist of a zeroes and b ones;
2.x−y (also written in binary form) has exactly k ones.
You are not allowed to use leading zeros for x and y.

输入
The only line contains three integers a, b, and k (0≤a; 1≤b; 0≤k≤a+b≤2⋅10⁵) — the number of zeroes, ones, and the number of ones in the result.

输出

If it’s possible to find two suitable integers, print “Yes” followed by x and y in base-2.

Otherwise print “No”.

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

样例

input
4 2 3
output
Yes
101000
100001

input
3 2 1
output
Yes
10100
10010

input
3 2 5
output
No

题目大意

给你三个数，a代表0的个数，b代表1的个数，k代表x-y中1的个数，让你求出x，y满足a，b，k三个条件，如果没有输出NO

思路

由题目可知x>y是肯定的，所以我们不妨假设x，y为11…00…，然后对y进行变换，我们发现y最右边的1往后移动一位x-y的值就多一个1，最大为a，然后移动倒数第二个1，发现只能移动一次，如果移动两次不会多一个1。
假设
x 1110000
y 1110000
当y的倒数第一个1往右移动时发现x-y中1的个数+1，当y 1100001时x-y中1的个数为4，然后移动倒数第二个1，移动一次，发现x-y中1的个数变成了5，再移动一次发现又变回4，所以除了倒数第一个1可以移动多次，第一个1不能移动中间的1只能移动一次，我们可以找出规律，最大的值为a+b-2。

代码

#include <iostream>
#include <cstring>

using namespace std;

const int N = 2e5 + 10;

int main()
{
	int a,b,k;
	
	cin >> a >> b >> k;
	
	if(k == 0)
	{
		cout << "YES" << endl;
		
		for(int i = 1;i <= a + b;i ++)
		{
			if(i <= b) cout << "1";
			else cout << "0";
		}
		
		puts("");
		
		for(int i = 1;i <= a + b;i ++)
		{
			if(i <= b) cout << "1";
			else cout << "0";
		}
		
		puts("");
	}
	else if(k > a + b - 2) cout << "NO" << endl;
	else if(a == 0 && k != 0) cout << "NO" << endl;
	else if(b == 1 && k != 0) cout << "NO" << endl;
	else
	{
		cout << "YES" << endl;
		if(a >= k)
		{
			for(int i = 1;i <= a + b;i ++)
			{
				if(i <= b) cout << "1";
				else cout << "0";
			}
			
			puts("");
			
			for(int i = 1;i <= a + b;i ++)
			{
				if(i <= b - 1) cout << "1";
				else if(i < b + k) cout << "0";
				else if(i == b + k) cout << "1";
				else cout << "0";
			}
			
			puts("");
		} 
		else
		{
			for(int i = 1;i <= a + b;i ++)
			{
				if(i <= b) cout << "1";
				else cout << "0";
			}
			
			puts("");
			
			int l = k - a;
			for(int i = 1;i <= a + b;i ++)
			{
				if(i <= b - 1 - l) cout << "1";
				else if(i == b - l) cout << "0";
				else if(i <= b) cout << "1";
				else if(i <= a + b - 1) cout << "0";
				else cout << "1";
			}
			
			puts("");
		}
	}
	
	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
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85

模拟构造，我不会（hhh

E. Almost Fault-Tolerant Database

题目
You are storing an integer array of length m in a database. To maintain internal integrity and protect data, the database stores n copies of this array.

Unfortunately, the recent incident may have altered the stored information in every copy in the database.

It’s believed, that the incident altered at most two elements in every copy. You need to recover the original array based on the current state of the database.

In case there are multiple ways to restore the array, report any. If there is no array that differs from every copy in no more than two positions, report that as well.

输入

The first line contains integers n and m (2≤n; 1≤m; n⋅m≤250000) — the number of copies and the size of the array.

Each of the following n lines describes one of the currently stored copies in the database, it consists of m integers s_i,1,s_i,2,…,s_i,m (1≤s_i,j≤10⁹).

输出
If there is an array consistent with all given copies, print “Yes” and then the array itself. The array must have length m and contain integers between 1 and 10⁹ only.

Otherwise, print “No”.

If there are multiple possible arrays, print any of them.

样例
input
3 4
1 10 10 100
1 1 1 100
10 100 1 100
output
Yes
1 10 1 100

input
10 7
1 1 1 1 1 1 1
1 1 1 1 1 1 2
1 1 1 1 1 2 2
1 1 1 1 2 2 1
1 1 1 2 2 1 1
1 1 2 2 1 1 1
1 2 2 1 1 1 1
2 2 1 1 1 1 1
2 1 1 1 1 1 1
1 1 1 1 1 1 1
output
Yes
1 1 1 1 1 1 1

input
2 5
2 2 1 1 1
1 1 2 2 2
output
No

题目大意

给定n个长度为m的数组，需要输出一个长度为m的数组，使得这些数组之间不同的数不超过两个，输出YES，输出你构造的数组，若有多种情况，可任意输出一种。如若不存在，输出NO。

思路

假设第一个数组为标准数组，遍历
1.不同数小于等于2，没问题
2.不同数大于4，直接输出NO
3.就是3,4的情况，我们找差异数最大的那个也就是4的情况，枚举修改的两个位置，判断是否可以成立。

代码

#include <iostream>
#include <vector>
#include <utility>

using namespace std;

typedef pair <int,int> PII;

const int N = 250010;

int n,m;
vector <int> s[N];

bool check2(vector<int> &v)
{
	for(int i = 1;i < n;i ++)
	{
		int cnt = 0;
		for(int j = 0;j < m;j ++)
		{
			if(s[i][j] != v[j]) cnt ++;
		
		}
		
		if(cnt > 3) return false;
		else if(cnt == 3)
		{
			int ans = 1;
			for(int j = 0;j < m;j ++)
			{
				if(s[i][j] != v[j] && v[j] == -1)
				{
					ans = 0;
					v[j] = s[i][j];
					break;
				}
				
			}
			
			if(ans) return false;
		}
	}
	
	return true;
}


bool check()
{
	int cnt = 0,ax = 0,id;
	
	for(int i = 1;i < n;i ++)
	{
		int ans = 0;
		for(int j = 0;j < m;j ++) 
		{
			if(s[i][j] != s[0][j]) ans ++;
			
		}
		
		if(ans > 4) return false;
		if(ans <= 2) cnt ++;
		if(ans > ax)ax = ans,id = i;
	}
	
	if(cnt == n - 1)
	{
		puts("YES");
		
		for(int i = 0;i < m;i ++) printf("%d ",s[0][i]);
		
		puts("");
		
		return true;
	}
	
	vector<int> a;
	
	for(int i = 0;i < m;i ++)
	{
		if(s[0][i] != s[id][i]) a.push_back(i);
	}
	
	for(int i = 0;i < a.size();i ++)
	{
		for(int j = 0;j < a.size();j ++)
		{
			if(i == j) continue;
			
			vector<int> b = s[0];
			
			b[a[i]] = s[id][a[i]];
			b[a[j]] = -1;
			
			if(check2(b))
			{
				puts("YES");
				
				for(int i = 0;i < m;i ++) printf("%d ",b[i] == -1 ? s[0][i] : b[i]);
				puts("");
				
				return true;
			}
		}
	}
	return false;
}

int main()
{
	scanf("%d %d",&n,&m);
	
	for(int i = 0;i < n;i ++)
	{
		for(int j = 0;j < m;j ++)
		{
			int x;
			scanf("%d",&x);
			s[i].push_back(x);
		}
	}
	
	if(!check()) puts("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
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126

DE都是我做不出来的题目，真菜