codeforces每日5题(均1500)-第二十四天_codeforce 题库题目推荐

Hyperset

题面翻译

有n张卡，每张卡有k个特征，每个特征有三种（‘S’, ‘E’, ‘T’），让你选出三张卡组成一套，使得三张卡中的每个特征全部相等或者全部不同。如样例三中的"SETT", “TEST”, "EEET"是一套，“TEST”, “ESTE”, "STES"也是一套，问一共能选出几套。

题目描述

Bees Alice and Alesya gave beekeeper Polina famous card game “Set” as a Christmas present.

The deck consists of cards that vary in four features across three options for each kind of feature: number of shapes, shape, shading, and color.

In this game, some combinations of three cards are said to make up a set.

For every feature — color, number, shape, and shading — the three cards must display that feature as either all the same, or pairwise different.

The picture below shows how sets look.

Polina came up with a new game called “Hyperset”. In her game, there are $n$ cards with $k$ features, each feature has three possible values: “S”, “E”, or “T”.

The original “Set” game can be viewed as “Hyperset” with $k=4$ .

Similarly to the original game, three cards form a set, if all features are the same for all cards or are pairwise different.

The goal of the game is to compute the number of ways to choose three cards that form a set.

Unfortunately, winter holidays have come to an end, and it’s time for Polina to go to school.

Help Polina find the number of sets among the cards lying on the table.

输入格式

The first line of each test contains two integers $n$ and $k$ ( $1\le n\le 1500$ , $1\le k\le 30$ ) — number of cards and number of features.

Each of the following $n$ lines contains a card description: a string consisting of $k$ letters “S”, “E”, “T”.

The $i$ -th character of this string decribes the $i$ -th feature of that card.

All cards are distinct.

输出格式

Output a single integer — the number of ways to choose three cards that form a set.

样例 #1

样例输入 #1

3 3
SET
ETS
TSE
1
2
3
4

样例输出 #1

1
1

样例 #2

样例输入 #2

3 4
SETE
ETSE
TSES
1
2
3
4

样例输出 #2

0
1

样例 #3

样例输入 #3

5 4
SETT
TEST
EEET
ESTE
STES
1
2
3
4
5
6

样例输出 #3

2
1

提示

In the third example test, these two triples of cards are sets:

1. “SETT”, “TEST”, “EEET”
2. “TEST”, “ESTE”, “STES”

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
typedef long long ll;
int n,k;
string s[N];
ll ss=0;
map<string,int> gg;
int main(){
	cin>>n>>k;
	for(int i=1;i<=n;i++)  cin>>s[i];
	for(int i=1;i<=n;i++){
		for(int j=i+1;j<=n;j++){
			string p="";
			for(int kk=0;kk<k;kk++){
				if(s[i][kk]==s[j][kk]) p+=s[i][kk];
				else{
					if(s[i][kk]!='S'&&s[j][kk]!='S') p+='S';
					if(s[i][kk]!='E'&&s[j][kk]!='E') p+='E';
					if(s[i][kk]!='T'&&s[j][kk]!='T') p+='T';
				}
			}
			ss+=gg[p];
		}gg[s[i]]++;
	}
	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
23
24
25
26
27
28

Motarack’s Birthday

题面翻译

$t$ 组数据。

给定一个 $n$ 和一个长度为 $n$ 的，除 $-1$ 外其它数字均为非负数的序列 $a$，要求将 $a$ 中所有 $-1$ 填充为 $k$，使得该序列相邻数字绝对值之差最小。

输出最小绝对值之差及填充的数字 $k$，如果有多个可能的 $k$，输出任意一个。

题目描述

Dark is going to attend Motarack’s birthday.

Dark decided that the gift he is going to give to Motarack is an array $a$ of $n$ non-negative integers.

Dark created that array $1000$ years ago, so some elements in that array disappeared.

Dark knows that Motarack hates to see an array that has two adjacent elements with a high absolute difference between them.

He doesn’t have much time so he wants to choose an integer $k$ ( $0\le k\le 10^9$ ) and replaces all missing elements in the array $a$ with $k$ .

Let $m$ be the maximum absolute difference between all adjacent elements (i.e. the maximum value of $|a_i-a_{i+1}|$ for all $1\le i\le n-1$ ) in the array $a$ after Dark replaces all missing elements with $k$ .

Dark should choose an integer $k$ so that $m$ is minimized. Can you help him?

输入格式

The input consists of multiple test cases.

The first line contains a single integer $t$ ( $1\le t\le 10^4$ ) — the number of test cases.

The description of the test cases follows.

The first line of each test case contains one integer $n$ ( $2\le n\le 10^5$ ) — the size of the array $a$ .

The second line of each test case contains $n$ integers $a_1,a_2,\dots ,a_n$ ( $-1\le a_i\le 10^9$ ).

If $a_i=-1$ , then the $i$ -th integer is missing. It is guaranteed that at least one integer is missing in every test case.

It is guaranteed, that the sum of $n$ for all test cases does not exceed $4\cdot 10^5$ .

输出格式

Print the answers for each test case in the following format:

You should print two integers, the minimum possible value of $m$ and an integer $k$ ( $0\le k\le 10^9$ ) that makes the maximum absolute difference between adjacent elements in the array $a$ equal to $m$ .

Make sure that after replacing all the missing elements with $k$ , the maximum absolute difference between adjacent elements becomes $m$ .

If there is more than one possible $k$ , you can print any of them.

样例 #1

样例输入 #1

7
5
-1 10 -1 12 -1
5
-1 40 35 -1 35
6
-1 -1 9 -1 3 -1
2
-1 -1
2
0 -1
4
1 -1 3 -1
7
1 -1 7 5 2 -1 5
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

样例输出 #1

1 11
5 35
3 6
0 42
0 0
1 2
3 4
1
2
3
4
5
6
7

提示

In the first test case after replacing all missing elements with $11$ the array becomes $[11,10,11,12,11]$ .

The absolute difference between any adjacent elements is $1$ .

It is impossible to choose a value of $k$ , such that the absolute difference between any adjacent element will be $\le 0$ .

So, the answer is $1$ .

In the third test case after replacing all missing elements with $6$ the array becomes $[6,6,9,6,3,6]$ .

• $|a_1-a_2|=|6-6|=0$ ;
• $|a_2-a_3|=|6-9|=3$ ;
• $|a_3-a_4|=|9-6|=3$ ;
• $|a_4-a_5|=|6-3|=3$ ;
• $|a_5-a_6|=|3-6|=3$ .

So, the maximum difference between any adjacent elements is $3$ .

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
typedef long long ll;
int t,n,kmax,kmin,k,a[N],s=0;
int main(){
	cin>>t;
	while(t--){
		scanf("%d",&n);
		kmax=-1,kmin=2e9;
		for(int i=1;i<=n;i++) scanf("%d",&a[i]);
		a[n+1]=0;
		for(int i=1;i<=n;i++){
			if(a[i]!=-1&&(a[i-1]==-1||a[i+1]==-1)){
				kmax=max(kmax,a[i]);
				kmin=min(kmin,a[i]);
			}
		}
		k=(kmin+kmax)/2;
		for(int i=1;i<=n;i++){
			if(a[i]==-1) a[i]=k;
			if(i!=1) s=max(s,abs(a[i]-a[i-1]));
		} 
		printf("%d %d\n",s,k);
		s=k=0;
	}
	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

Air Conditioner

题面翻译

• 一个餐馆中有个空调，每分钟可以选择上调 $1$ 个单位的温度或下调 $1$ 个单位的温度，当然你也可以选择不变，初始的温度为 $m$ 。

• 有 $n$ 个食客，每个食客会在 $t_i$ 时间点到达，他所能适应的最低温度是 $l_i$ ，最高温度是 $h_i$ ，他只会在 $t_i$ 时刻逗留。

• 如果温度不在食客的适应范围内，他就会不舒服，请你判断，空调能否使得 $n$ 位来就餐的食客都感到舒服。

• 本题多组数据，数据组数不大于 $500$。

• $1\le n\le 100$，$-10^9\le m,l_i,h_i\le 10^9$，$1\le t_i\le 10^9$。

题目描述

Gildong owns a bulgogi restaurant.

The restaurant has a lot of customers, so many of them like to make a reservation before visiting it.

Gildong tries so hard to satisfy the customers that he even memorized all customers’ preferred temperature ranges!

Looking through the reservation list, he wants to satisfy all customers by controlling the temperature of the restaurant.

The restaurant has an air conditioner that has 3 states: off, heating, and cooling.

When it’s off, the restaurant’s temperature remains the same.

When it’s heating, the temperature increases by 1 in one minute.

Lastly, when it’s cooling, the temperature decreases by 1 in one minute.

Gildong can change the state as many times as he wants, at any integer minutes.

The air conditioner is off initially.

Each customer is characterized by three values: $t_i$ — the time (in minutes) when the $i$ -th customer visits the restaurant, $l_i$ — the lower bound of their preferred temperature range, and $h_i$ — the upper bound of their preferred temperature range.

A customer is satisfied if the temperature is within the preferred range at the instant they visit the restaurant.

Formally, the $i$ -th customer is satisfied if and only if the temperature is between $l_i$ and $h_i$ (inclusive) in the $t_i$ -th minute.

Given the initial temperature, the list of reserved customers’ visit times and their preferred temperature ranges, you’re going to help him find if it’s possible to satisfy all customers.

输入格式

Each test contains one or more test cases.

The first line contains the number of test cases $q$ ( $1\le q\le 500$ ).

Description of the test cases follows.

The first line of each test case contains two integers $n$ and $m$ ( $1\le n\le 100$ , $-10^9\le m\le 10^9$ ), where $n$ is the number of reserved customers and $m$ is the initial temperature of the restaurant.

Next, $n$ lines follow.

The $i$ -th line of them contains three integers $t_i$ , $l_i$ , and $h_i$ ( $1\le t_i\le 10^9$ , $-10^9\le l_i\le h_i\le 10^9$ ), where $t_i$ is the time when the $i$ -th customer visits, $l_i$ is the lower bound of their preferred temperature range, and $h_i$ is the upper bound of their preferred temperature range.

The preferred temperature ranges are inclusive.

The customers are given in non-decreasing order of their visit time, and the current time is $0$ .

输出格式

For each test case, print “YES” if it is possible to satisfy all customers. Otherwise, print “NO”.

You can print each letter in any case (upper or lower).

样例 #1

样例输入 #1

4
3 0
5 1 2
7 3 5
10 -1 0
2 12
5 7 10
10 16 20
3 -100
100 0 0
100 -50 50
200 100 100
1 100
99 -100 0
1
2
3
4
5
6
7
8
9
10
11
12
13
14

样例输出 #1

YES
NO
YES
NO
1
2
3
4

提示

In the first case, Gildong can control the air conditioner to satisfy all customers in the following way:

• At $0$ -th minute, change the state to heating (the temperature is 0).
• At $2$ -nd minute, change the state to off (the temperature is 2).
• At $5$ -th minute, change the state to heating (the temperature is 2, the $1$ -st customer is satisfied).
• At $6$ -th minute, change the state to off (the temperature is 3).
• At $7$ -th minute, change the state to cooling (the temperature is 3, the $2$ -nd customer is satisfied).
• At $10$ -th minute, the temperature will be 0, which satisfies the last customer.

In the third case, Gildong can change the state to heating at $0$ -th minute and leave it be.

Then all customers will be satisfied.

Note that the $1$ -st customer’s visit time equals the $2$ -nd customer’s visit time.

In the second and the fourth case, Gildong has to make at least one customer unsatisfied.

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
typedef long long ll;
int t,n,m;
struct stu{
	int t,l,r;
}s[N];
bool cmp(stu x,stu y){
	return x.t<y.t;
}
int main(){
	cin>>t;
	while(t--){
		scanf("%d%d",&n,&m);
		for(int i=1;i<=n;i++){
			scanf("%d%d%d",&s[i].t,&s[i].l,&s[i].r);
		}
		sort(s+1,s+1+n,cmp);
		int l=m,r=m;
		bool ok=1;
		for(int i=1;i<=n;i++){
			int d=s[i].t-s[i-1].t;
			l-=d,r+=d;
			l=max(l,s[i].l);
			r=min(r,s[i].r);
			if(l>r){
				ok=0;
				break;
			}
		}
		if(ok) puts("YES");
		else 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

Binary String Reconstruction

题面翻译

一共有 $t$ 组数据。

每组数据有三个整数 $n_0,n_1,n_2$。

你需要构造一个 $01$ 串，长度为 $n_0+n_1+n_2+1$，对于每一个长度为 $2$ 的连续子串，总共有 $n_0$ 个和为 $0$， 有 $n_1$ 个和为 $1$，有 $n_2$ 个和为 $2$。

保证输入有解，对于每一组数据，输出一行，为一个 $01$ 串，没有空格，如果有多组解，输出任意一个即可。

题目描述

For some binary string $s$ (i.e. each character $s_i$ is either ‘0’ or ‘1’), all pairs of consecutive (adjacent) characters were written.

In other words, all substrings of length $2$ were written.

For each pair (substring of length $2$ ), the number of ‘1’ (ones) in it was calculated.

You are given three numbers:

• $n_0$ — the number of such pairs of consecutive characters (substrings) where the number of ones equals $0$ ;
• $n_1$ — the number of such pairs of consecutive characters (substrings) where the number of ones equals $1$ ;
• $n_2$ — the number of such pairs of consecutive characters (substrings) where the number of ones equals $2$ .

For example, for the string $s=$ “1110011110”, the following substrings would be written: “11”, “11”, “10”, “00”, “01”, “11”, “11”, “11”, “10”.

Thus, $n_0=1$ , $n_1=3$ , $n_2=5$ .

Your task is to restore any suitable binary string $s$ from the given values $n_0,n_1,n_2$ .

It is guaranteed that at least one of the numbers $n_0,n_1,n_2$ is greater than $0$ .

Also, it is guaranteed that a solution exists.

输入格式

The first line contains an integer $t$ ( $1\le t\le 1000$ ) — the number of test cases in the input.

Then test cases follow.

Each test case consists of one line which contains three integers $n_0,n_1,n_2$ ( $0\le n_0,n_1,n_2\le 100$ ; $n_0+n_1+n_2>0$ ).

It is guaranteed that the answer for given $n_0,n_1,n_2$ exists.

输出格式

Print $t$ lines.

Each of the lines should contain a binary string corresponding to a test case.

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

样例 #1

样例输入 #1

7
1 3 5
1 1 1
3 9 3
0 1 0
3 1 2
0 0 3
2 0 0
1
2
3
4
5
6
7
8

样例输出 #1

1110011110
0011
0110001100101011
10
0000111
1111
000
1
2
3
4
5
6
7

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
typedef long long ll;
int t,n0,n1,n2;
int main(){
	cin>>t;
	while(t--){
		scanf("%d%d%d",&n0,&n1,&n2);
		if(n1==0){
			if(n0) for(int i=1;i<=n0+1;i++) cout<<0;
			else for(int i=1;i<=n2+1;i++) cout<<1;
			cout<<endl;
		}
		else{
			for(int i=1;i<=n0+1;i++) cout<<0;
			for(int i=1;i<=n2+1;i++) cout<<1;
			n1--;
			for(int i=1;i<=n1;i++){
				if(i%2) cout<<0;
				else cout<<1;
			}
			cout<<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