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!!!