Codeforces Round 894 (Div. 3)

因为最近开学了，所以晚上可能就没有什么时间打这个了，不过以后一定会在第二天把题给补掉

A题传送门

A题意：

就是在一个n * m的的字符矩阵中从左往右依次取出4列，使得每列包含vika这四个字符中按顺序出现一个。必须保证是按顺序出现。

A思路：

这是一个简单的签到题，我们可以按列枚举，如果能按顺序找到对应的四列就可以，输出"YES"，如果找不到，就输出"NO"，如果行数和列数都不够4，那一定是NO。

A代码：

#include<bits/stdc++.h>
using namespace std;
const int N=23;

char a[N][N];

void solve(){
    int n,m;
    cin>>n>>m;
    string s="vika";
    int flag=0;
    int l=0;
    // cout<<s<<endl;
    
    for(int i=1;i<=n;i++){
      for(int j=1;j<=m;j++){
        cin>>a[i][j];
      }
    }
    if(n<4&&m<4){
      cout<<"NO"<<endl;
    }
    else{
      for(int i=1;i<=m;i++){
        for(int j=1;j<=n;j++){
          if(a[j][i]==s[l]){
              l++;
              flag++;
              break;
          }
        }
      }
      if(flag==4){
        cout<<"YES"<<endl;
      }
      else{
        cout<<"NO"<<endl;
        
      }
    }
} 
int main(){
  int t;
  cin>>t;
  // t=1;
  
  while(t--){
    solve();
  }
  return 0;

}

B题传送门

B题意：

刚开始给一个数组a，执行下面操作：
1.输出a1
2.对于所有2<=i<=n的点，若ai-1<=ai，就将ai输出
从而得到数组b，让求原数组a

B思路：

由题意，我们可以在得到的数组中找到ai小于ai-1的的位置，在其中插入一个1，这样得到的数组就可能是原数组中的一组解

B代码：

#include<bits/stdc++.h>
using namespace std;
const int N=23;
void solve(){
    int n;
    cin>>n;
    std::vector<int> v;
    std::vector<int> v1;
    for(int i=0;i<n;i++){
      int x;
      cin>>x;
      v.push_back(x);

    }
    for(int i=0;i<n;i++){
      if(i){
        if(v[i]<v[i-1]){
          v1.push_back(1);
        }
      }
      v1.push_back(v[i]);
    }
    cout<<v1.size()<<endl;
    for(int i=0;i<v1.size();i++){
      cout<<v1[i]<<" ";
    }
    cout<<endl;
    
} 
int main(){
  int t;
  cin>>t;
  // t=1;
  
  while(t--){
    solve();
  }
  return 0;

}

（思路挺新奇的一个题）C题传送门

C题意：

给出一个由n个长方形拼成的图形，在第i个的长方形高度为ai，宽为1（ai-1>=ai）。问把它换一个方向摆之后是否和原图像一样。

C思路：

这个题就是判断组成的图形旋转后原图形能否重合，也就是能否相等，如果相等输出YES，不等输出NO
判断可不可以重合，我们只需要把旋转后的图形构造出来，再与原图形比较一下即可。
如何构造旋转后的图形呢？这里我门运用的是差分的思想去构造旋转后的图形

代码：

#include<bits/stdc++.h>
using namespace std;
const int N=23;
void solve(){
    int n;
    cin>>n;
    std::vector<int> a(n+1);
    for(int i=1;i<=n;i++){
      cin>>a[i];
    }
    if(a[1]!=n){
      cout<<"NO"<<endl;
      return ;
    }
    std::vector<int> b(n+2);
    for(int i=1;i<=n;i++){
      b[1]++;//表示最高的那个地方
      b[a[i]+1]--;//为了构造一个差分数组

    }
    for(int i=1;i<=n;i++){
      b[i]+=b[i-1];

    }
    bool flag=true;
    for(int i=1;i<=n;i++){
      if(a[i]!=b[i]){
        flag=false;

      }
    }
    if(flag){
      cout<<"YES"<<endl;
    }
    else{
      cout<<"NO"<<endl;
    }
    return ;
} 
int main(){
  int t;
  cin>>t;
  // t=1;
  
  while(t--){
    solve();
  }
  return 0;
}