Codeforces Round 894 (Div. 3)

还是打一下卡!!!

(A,B,C)

目录

A. Gift Carpet

链接 : 

题面 : 

 题目意思 : 

思路 : 

代码 : 

 

B. Sequence Game

链接 :

题面 : 

​编辑 

题目意思 :

 

 思路  :

代码 : 

C. Flower City Fence

原题链接 : 

题面 : 

 题目意思 :

思路 : 

代码 :

---

A. Gift Carpet

链接 : 

Problem - A - Codeforces

题面 : 

 

 题目意思 : 

最近，Tema和Vika庆祝了家庭日。他们的朋友Arina送给他们一块地毯，可以表示为一个n×m的小写拉丁字母表格。

Vika还没看到礼物，但是Tema知道她喜欢什么样的地毯。如果她能够在上面读到她的名字，她就会喜欢这块地毯。她按照从左到右、逐列阅读的方式，每列选择一个或零个字母。

具体来说，如果可以按照从左到右的顺序选择四列不同的列，使得第一列包含"v"，第二列包含"i"，第三列包含"k"，第四列包含"a"，那么这个女孩就会喜欢这块地毯。

帮助Tema提前了解Vika是否会喜欢Arina的礼物。

思路 : 

就是一个暴力的遍历整个矩阵，然后运用贪心的思想，最好在前面能找到的字母就将其标出来,然后记录找到vika的出现字母次数的变量t加一，最后返回t==4;

代码 : 

// A
#include<bits/stdc++.h>
#define IOS ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define endl '\n'using namespace std;
typedef long long LL;
const int N = 21;
int n,m,t;
char a[N][N];inline void solve(){cin>>n>>m;for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) cin>>a[i][j];if(m<4){ cout<<"NO"<<endl; return ; }t = 0;for(int j=1;j<=m;j++){for(int i=1;i<=n;i++){if(t==0){if(a[i][j] == 'v'){ t++; break;}}else if(t==1){if(a[i][j] == 'i'){ t++; break;}}else if(t==2){if(a[i][j] == 'k'){ t++; break;}}else if(t==3){if(a[i][j] == 'a'){ t++; break;}} }if(t==4) break;	}if(t==4) cout<<"YES"<<endl;else cout<<"NO"<<endl;
}int main()
{IOSint _;cin >> _;// _ = 1; while(_ --) solve();return 0;
}

 

B. Sequence Game

链接 :

Problem - B - Codeforces

题面 : 

 

题目意思 :

 

Tema和Vika正在玩以下游戏。

首先，Vika想出一个长度为m的正整数序列a，并将其写在一张纸上。然后她拿一张新纸，按照以下规则写下序列b：

首先，她写下a1。 然后，她只写下那些满足ai-1≤ai的ai（2≤i≤m）。将这个序列的长度表示为n。 例如，从序列a=[4,3,2,6,3,3]，Vika将得到序列b=[4,6,3]。

然后她将带有序列b的纸递给Tema。他尝试猜出序列a。

Tema认为在这样的游戏中赢得胜利非常不可能，但还是希望找到至少一个可能由Vika最初选择的序列a。帮助他输出任何这样的序列。

请注意，输出序列的长度不应超过输入序列长度的两倍。

 思路  :

数组构造题 : 

例如给定[4,6,3]要在a[i-1]和a[i]两数中间加或不加一个数x满足a[i-1]>x && x <=a[i],那么怎么构造呢?

1.如果a[i]>=a[i-1]的话，就不用插入x了，已经满足同时取a[i-1]和a[i]了;

2.否则 : 也就是要插入一个数了,一定要看清题目:构造数组中元素的值>=1,所以a[i]=1的情况下，x取比a[i]小的数的话，就会造成插入数为0或负数的可能，那么就只剩下插a[i]了，这样符合题意;

下面请看代码 : 

代码 : 

// B
#include<bits/stdc++.h>
#define IOS ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define endl '\n'using namespace std;
typedef long long LL;
const int N = 2e5+10;
int n,a[N],mi;
vector<int> v;inline void solve(){cin>>n;for(int i=1;i<=n;i++) cin>>a[i];v.clear();v.push_back(a[1]);for(int i=2;i<=n;i++){if(a[i] >= a[i-1]) v.push_back(a[i]);else {v.push_back(a[i]);v.push_back(a[i]);}}cout<<v.size()<<endl;for(int num : v) cout<<num<<" ";cout<<endl;
}int main()
{IOSint _;cin >> _;// _ = 1; while(_ --) solve();return 0;
}

C. Flower City Fence

个人认为这是一道比较有意思的题目(数学模拟题),hhh;

原题链接 : 

Problem - C - Codeforces

题面 : 

 

 题目意思 :

也就是给你一个非递减数组，数组凑想为一个长度递减围栏，请你该围栏判断是否为一个对称(关于45对称)围栏。

思路 : 

先看图 (较潦草hhh): 

 

先看左上角的，构建两个vector,v1和v2,v1里面存每层上表面的长度，v2从上往下看存每个纵界面的长度;

例如 ： 

5

5 4 3 2 1

这个例子 : 

v1 : 1 1 1 1 1;

v2 : 1 1 1 1 1;

例如 ： 

3

3 1 1

这个例子 : 

v1 : 1 2;

v2 : 2 1;

最后判断这两个vector是不是能由另一个翻转得到，即可!!! (讲不清楚，自己画图理解，只要两个数组翻转相等，那么就一定围栏对称);

代码 :

// C
#include<bits/stdc++.h>
#define IOS ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define endl '\n'using namespace std;
typedef long long LL;
const int N = 2e5+10;
int n,a[N];
bool tag;
vector<int> v1;
vector<int> v2;inline void solve(){cin>>n;for(int i=1;i<=n;i++)	cin>>a[i];a[n+1] = 0;tag = true; v1.clear(); v2.clear();for(int i=1;i<=n;i++){int j = i+1;while(j<=n && a[j]==a[i]) j++;j--;v1.push_back(j-i+1);i = j;}for(int i=1;i<=n;i++){int j = i + 1;while(j<=n && a[j]==a[i]) j++;if(j==n+1) v2.push_back(a[i]);else v2.push_back(a[i]-a[j]);i = j - 1;}
// 测试代码
//	for(auto num : v1) cout<<num<<" ";
//	cout<<endl;
//	for(auto num : v2) cout<<num<<" ";
//	cout<<endl;if(v1.size() != v2.size()) tag = false;else {for(int i=0;i<v1.size();i++){if(v1[i] != v2[v1.size()-i-1]){tag = false;break;}}}if(tag) cout<<"YES"<<endl;else cout<<"NO"<<endl;
}int main()
{IOSint _;cin >> _;// _ = 1; while(_ --) solve();return 0;
}

好吧，就三题了,hh!!!