Codeforces Round #894 (Div.3)

朱雀 2024-03-24 21:12 55阅读 0赞

![在这里插入图片描述][f4e0159841ab450d861dde9e8fb5ba0d.gif_pic_center]

#### 文章目录 ####

*  前言
 *  A. Gift Carpet
 *   *  题目：
     *  输入：
     *  输出：
     *  思路：
     *  代码：
 *  B. Sequence Game
 *   *  题目：
     *  输入：
     *  输出：
     *  思路：
     *  代码：
 *  C. Flower City Fence
 *   *  题目：
     *  输入：
     *  输出：
     *  思路：
     *  代码：
 *  D. Ice Cream Balls
 *   *  题目：
     *  输入：
     *  输出：
     *  思路：
     *  代码：
 *  E. Kolya and Movie Theatre
 *   *  题目：
     *  输入：
     *  输出：
     *  思路：
     *  代码：
 *  总结

--------------------

## 前言 ##

昨天晚上打了一场Codeforces Div3 唉 打的很不好，只AC了两道思维题目。

![在这里插入图片描述][9752395cad6748bf9096ec01a8d25aaa.png]

--------------------

## A. Gift Carpet ##

### 题目： ###

链接：[A. Gift Carpet][]  
最近，Tema和Vika庆祝了家庭日。他们的朋友阿里娜给了他们一块地毯，可以表示为n⋅m  
小写拉丁字母表。

维卡还没有看到礼物，但特玛知道她喜欢什么样的地毯。维卡会喜欢地毯，如果她能读上她的名字。她从左到右逐列阅读，并从当前列中选择一个或多个或零个字母。

从形式上讲，如果可以按从左到右的顺序选择四列不同的列，例如第一列包含“v”，第二列包含“i”，第三列包含“k”，第四列包含“a”，女孩会喜欢地毯。

帮助特玛提前了解维卡是否会喜欢艾琳娜的礼物。

### 输入： ###

每个测试由多个测试用例组成。输入的第一行包含单个整数t  
(1≤t≤100） — 测试用例的数量。然后是测试用例的说明。

每个测试用例的第一行包含两个整数n,m  
(1≤n，m≤20） — 地毯的尺寸。

下一个n行包含m每个小写拉丁字母，描述给定的地毯。

### 输出： ###

对于每组输入数据，如果 Vika 喜欢地毯，则输出“YES”，否则输出“NO”。  
您可以以任何大小写（小写或大写）输出每个字母。例如，字符串“yEs”、“yes”、“Yes”和“YES”将被接受为肯定答案。  
![在这里插入图片描述][47a293d194714c229aac66aefe8dec95.png]

### 思路： ###

控制行和列的for循环互换，然后一列一列的去找，找到就k++然后跳出去下一列  
最后如果`k==4` 就是输出`yes`否则就是输出`no`即可。

tip：唉 继续加油！！！

### 代码： ###

#include<iostream>
    using namespace std;
    int main()
    {
        
    	int t;
    	cin>>t;
    	while(t--)
    	{
        
    		int n,m;
    		cin>>n>>m;
    		char s[22][22];
    		for(int i=0;i<n;i++)
    		{
        
    			for(int j=0;j<m;j++)
    			{
        
    				cin>>s[i][j];	
    			}
    		}
    		int k=0;
    		for(int i=k;i<m;i++)
    		{
        
    			for(int j=0;j<n;j++)
    			{
        
    				if(s[j][i]=='v')
    				{
        
    					if(k==0) 
    					{
        
    						k++;
    						break;
    					}
    				}
    				if(s[j][i]=='i')
    				{
        
    					if(k==1)
    					{
        
    						k++;
    						break;
    					}
    				}
    				if(s[j][i]=='k')
    				{
        
    					if(k==2)
    					{
        
    						k++;
    						break;
    					}
    				}
    				if(s[j][i]=='a')
    				{
        
    					if(k==3)
    					{
        
    						k++;
    						break;
    					}
    				}
    			}
    		}
    		if(k==4) cout<<"yes"<<endl;
    		else cout<<"no"<<endl;
    	}
    	return 0;
    }

## B. Sequence Game ##

### 题目： ###

链接：[B. Sequence Game][]  
Tema and Vika are playing the following game.

First, Vika comes up with a sequence of positive integers a  
of length m  
and writes it down on a piece of paper. Then she takes a new piece of paper and writes down the sequence b  
according to the following rule:

First, she writes down a1  
Then, she writes down only those ai (2≤i≤m) such that ai−1≤ai  
Let the length of this sequence be denoted as n

For example, from the sequence a=\[4,3,2,6,3,3\]  
Vika will obtain the sequence b=\[4,6,3\]

She then gives the piece of paper with the sequence b  
to Tema. He, in turn, tries to guess the sequence a

Tema considers winning in such a game highly unlikely, but still wants to find at least one sequence a  
that could have been originally chosen by Vika. Help him and output any such sequence.

Note that the length of the sequence you output should not exceed the input sequence length by more than two times.

大概意思：

就是输入一个数组b，大小为n然后推测数组a里面的数字  
推测的依据是：

*  先写出来一个a\[1\];
 *  然后如果a\[i-1\]<a\[i\]的话就存放到b数组里面

题目也是让你从b—>a，用b推出a数组酱紫

### 输入： ###

Each test consists of multiple test cases. The first line of input data contains a single integer t (1≤t≤104) — the number of test cases. This is followed by a description of the test cases.

The first line of each test case contains a single integer n (1≤n≤2⋅105) — the length of the sequence b

The second line of each test case contains n  
integers b1,b2,b3,…,bn (1≤bi≤10^9) — the elements of the sequence.

The sum of the values of n over all test cases does not exceed 2⋅10^5

### 输出： ###

For each test case, output two lines. In the first line, output a single integer m  
— the length of the sequence (n≤m≤2⋅n). In the second line, output m integers a1,a2,a3,…,am (1≤ai≤109) — the assumed sequence that Vika could have written on the first piece of paper.

If there are multiple suitable sequences, you can output any of them.

![在这里插入图片描述][c18ea79392a94ab0a62650a1ef0efd98.png]

### 思路： ###

emm勉强可以说是双指针算法吧，就是开一个result数组存放需要添加的内容，然后设置一个m=0指针去添加数据就行了

核心地方就是当遇到降序的时候：直接添加一个数字1解决所有问题，就这样…

### 代码： ###

#include<iostream>
    using namespace std;
     
    int n,a[200005],m,b[400005];
    
    int main()
    {
        
    	int t;
    	scanf("%d\n",&t);
    	while(t--)
    	{
        
    		cin>>n;
    		for(int i=1;i<=n;i++) cin>>a[i];
    		m=0;
    		b[++m]=a[1];
    		for(int i=2;i<=n;i++)
    		{
        
    			if(a[i]<a[i-1]) b[++m]=1;
    			b[++m]=a[i];
    		}
    		printf("%d\n",m);
    		for(int i=1;i<=m;i++) printf("%d ",b[i]);
    		puts("");
    	}
    	return 0;
    }

## C. Flower City Fence ##

链接：[C. Flower City Fence][]

### 题目： ###

Anya lives in the Flower City. By order of the city mayor, she has to build a fence for herself.  
The fence consists of nplanks, each with a height of aimeters. According to the order, the heights of the planks must not increase. In other words, it is true that ai≥aj for all i<j.

Anya became curious whether her fence is symmetrical with respect to the diagonal. In other words, will she get the same fence if she lays all the planks horizontally in the same order.

For example, for n=5, a=\[5,4,3,2,1\], the fence is symmetrical. Because if all the planks are laid horizontally, the fence will be \[5,4,3,2,1\], as shown in the diagram.

![在这里插入图片描述][1c6243387c154ed585215742c15181db.png]  
But for n=3, a=\[4,2,1\], the fence is not symmetrical. Because if all the planks are laid horizontally, the fence will be \[3,2,1,1\], as shown in the diagram.

![在这里插入图片描述][e5f489378ca141928cc715d806fea566.png]  
Help Anya and determine whether her fence is symmetrical.

### 输入： ###

The first line of the input contains an integer t (1≤t≤104) — the number of test cases.

The description of the test cases follows.

The first line of a test case contains a single integer n (1≤n≤2⋅105) — the length of the fence.

The second line of a test case contains n integers a1≥a2≥a3≥⋯≥an (1≤ai≤109) — the heights of the planks.

The sum of the values of n for all test cases does not exceed 2⋅105.

### 输出： ###

For each test case, output “YES” if the fence is symmetrical, otherwise output “NO”.

You can output each letter in any case (lowercase or uppercase). For example, the strings “yEs”, “yes”, “Yes” and “YES” will be accepted as a positive answer.

![在这里插入图片描述][74a535eb60784e1ea4147b6d05d6c5b7.png]

### 思路： ###

题目大意就是给你一个数组让你把这个数组抽象成长方体然后组合在一起，然后从对角线切分看是否关于切割线对称，如果对称就输出YES 否则 输出NO

**算法标签：思维题**

其实解决思路就是 `a[a[i]]`这个方法，其实`a[a[i]]`完美的解决了对称的问题，真的很不错，仔细想想是不是呢？？？  
**确实是这样的。**

### 代码： ###

#include<stdio.h>
    
    int a[200005];
    
    void solve()
    {
        
    	int n;
    	scanf("%d",&n);
    	for(int i=1;i<=n;i++) scanf("%d",&a[i]);
    	
    	for(int i=1;i<=n;++i)
    	{
        
    		if(a[i]>n || a[a[i]]<i) 
    		{
        
    			puts("No");
    			return;
    		}
    	}
    	puts("Yes");
    	return;
    }
    int main()
    {
        
    	int t;
    	scanf("%d",&t);
    	
    	while(t--) solve();
    	
    	return 0;
    }

## D. Ice Cream Balls ##

### 题目： ###

链接：[D. Ice Cream Balls][]  
Tema decided to improve his ice cream making skills. He has already learned how to make ice cream in a cone using exactly two balls.

Before his ice cream obsession, Tema was interested in mathematics. Therefore, he is curious about the minimum number of balls he needs to have in order to make exactly ndifferent types of ice cream.

There are plenty possible ice cream flavours: 1,2,3,…. Tema can make two-balls ice cream with any flavours (probably the same).

Two ice creams are considered different if their sets of ball flavours are different. For example, \{1,2\}=\{2,1\}, but \{1,1\}≠\{1,2\}.

For example, having the following ice cream balls: \{1,1,2\}, Tema can make only two types of ice cream: \{1,1\} and \{1,2\}

Note, that Tema do not need to make all the ice cream cones at the same time. This means that he making ice cream cones independently. Also in order to make a following cone \{x,x\} for some x, Tema needs at least 2 balls of type x

Help Tema answer this question. It can be shown that answer always exist.

### 输入： ###

Each test consists of multiple test cases. The first line of input contains a single integer t (1≤t≤104) — the number of test cases. Then follows the description of the test cases.

The first line of each test case contains a single integer n (1≤n≤1018) — the number of ice cream types that Tema wants to make.

### 输出： ###

For each test case, output a single integer — the minimum number of balls Tema needs to buy.  
![在这里插入图片描述][f4eddf32085b4bc9bfc716f370331750.png]

### 思路： ###

可以抽象成为一个二叉树，就是一种雪糕必须有两种数字组合，然后我就蒙了哈哈哈，看大佬的代码大佬应该是总结出来了规律然后利用数学知识写出来了，反正我太菜了…对不起佬们

### 代码： ###

#include<iostream>
    #include<cmath>
    
    using namespace std;
    
    int a[200005];
    
    void solve()
    {
        
    	long long n;
    	cin>>n;
    	
    	long long p=(1+sqrt(n*8+1))/2;
    	cout<<p+n-p*(p-1)/2<<endl;
    	
    	return;
    }
    
    int main()
    {
        
    	long long t;
    	cin>>t;
    	
    	while(t--) solve(); 
    	
    	return 0;
    }

## E. Kolya and Movie Theatre ##

链接：[E. Kolya and Movie Theatre][]

### 题目： ###

Recently, Kolya found out that a new movie theatre is going to be opened in his city soon, which will show a new movie every day for n days. So, on the day with the number 1≤i≤n, the movie theatre will show the premiere of the i-th movie. Also, Kolya found out the schedule of the movies and assigned the entertainment value to each movie, denoted by ai

However, the longer Kolya stays without visiting a movie theatre, the larger the decrease in entertainment value of the next movie. That decrease is equivalent to d⋅cnt, where d is a predetermined value and cnt is the number of days since the last visit to the movie theatre. It is also known that Kolya managed to visit another movietheatre a day before the new one opened — the day with the number 0. So if we visit the movie theatre the first time on the day with the number i, then cnt — the number of days since the last visit to the movie theatre will be equal to i

For example, if d=2 and a=\[3,2,5,4,6\], then by visiting movies with indices 1 and 3, cnt value for the day 1 will be equal to 1−0=1 and cnt value for the day 3 will be 3−1=2, so the total entertainment value of the movies will be a1−d⋅1+a3−d⋅2=3−2⋅1+5−2⋅2=2.

Unfortunately, Kolya only has time to visit at most m movies. Help him create a plan to visit the cinema in such a way that the total entertainment value of all the movies he visits is maximized.

### 输入： ###

Each test consists of multiple test cases. The first line contains a single integer t (1≤t≤104) — the number of test cases. The description of the test cases follows.

The first line of each test case contains three integers n, m, and d (1≤n≤2⋅105, 1≤m≤n, 1≤d≤109).

The second line of each set of input data contains n integers a1,a2,…,an (−109≤ai≤109) — the entertainment values of the movies.

It is guaranteed that the sum of n over all test cases does not exceed 2⋅105.

### 输出： ###

For each test case, output a single integer — the maximum total entertainment value that Kolya can get.

![在这里插入图片描述][48656f7fae5a4df4973cb31fc2977168.png]

### 思路： ###

**算法标签：贪心算法**

利用优先队列(priority\_queue)的用法进行编写代码，优先队列的知识点：[C++中优先队列的priority\_queue＜int,vector＜int＞,greater＜int＞＞与priority＜int＞的用法][C_priority_queue_int_vector_int_greater_int_priority_int]

主要用优先队列存放大于0的元素，然后除了第一个数据后的每m个数据就可以存放到记录数组里面，最后遍历找价值最大的即可

### 代码： ###

#include<bits/stdc++.h>
    #define int long long
    using namespace std;
     
    int n,m,d,a[200005],b[200005];
     
    void solve()
    {
        
    	priority_queue<int,vector<int>,greater<int> >q;
    	cin>>n>>m>>d;
    	for(int i=1;i<=n;i++) cin>>a[i];
    	int s=0,ans=0;
    	for(int i=1;i<=n;i++)
    	{
        
    		if(a[i]>0)
    		{
        
    			s+=a[i];
    			q.push(a[i]);
    			while(q.size()>m) s-=q.top(),q.pop();
    		}
    		b[i]=s;
    	}
    	for(int i=1;i<=n;i++) ans=max(ans,b[i]-d*i);
    	cout<<ans<<endl;
    }
     
    signed main()
    {
        
    	int t;
    	scanf("%lld\n",&t);
    	while(t--) solve();
    	return 0;
    }

--------------------

## 总结 ##

第二次打CF Div3 比起大一寒假那次多写出来一道思维题，也算是有点点进步吧，今天早上起来锻炼完身体后就开始补题，把我蹦一蹦能够到的"桃子"给摘下来进行学习，虽然打的时候很坐牢，但是成长后的感觉真的很不错，慢慢进步慢慢比赛总会有一天你会变强的，加油夏目浅石.

![在这里插入图片描述][a8cb87c52fe2437381305911521fc5a9.png]

[f4e0159841ab450d861dde9e8fb5ba0d.gif_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/13/e0a5b51146b1490cb478772f737241ee.png
[9752395cad6748bf9096ec01a8d25aaa.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/13/416c2764225e432cbb00b7d1c79bec77.png
[A. Gift Carpet]: https://codeforces.com/contest/1862/problem/A
[47a293d194714c229aac66aefe8dec95.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/13/5f6161cc9acd481b97ca36f24b0c6b18.png
[B. Sequence Game]: https://codeforces.com/contest/1862/problem/B
[c18ea79392a94ab0a62650a1ef0efd98.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/13/0877262beb0843888d5e0a42a858e02e.png
[C. Flower City Fence]: https://codeforces.com/contest/1862/problem/C
[1c6243387c154ed585215742c15181db.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/13/efd4b6483fdf4871b94b5b97fcb25a60.png
[e5f489378ca141928cc715d806fea566.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/13/1eed9ab58a874cb9bb061adf7671862b.png
[74a535eb60784e1ea4147b6d05d6c5b7.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/13/19243b4ba2f54af297bde34bdb7c4ddf.png
[D. Ice Cream Balls]: https://codeforces.com/contest/1862/problem/D
[f4eddf32085b4bc9bfc716f370331750.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/13/6bcc52eed6aa49778becb0723a0c4eeb.png
[E. Kolya and Movie Theatre]: https://codeforces.com/contest/1862/problem/E
[48656f7fae5a4df4973cb31fc2977168.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/13/fa23b4a4679e4967a3e9b61adf4a036c.png
[C_priority_queue_int_vector_int_greater_int_priority_int]: https://blog.csdn.net/Appleeatingboy/article/details/118895918?spm=1001.2014.3001.5506
[a8cb87c52fe2437381305911521fc5a9.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/13/c3726aa689084d999d8e5531c9b08fac.png