自学内容网 自学内容网

Codeforces Round 960 (Div. 2)A~D

我只能说我越来越废了,写不了一点

Codeforces Round 960 (Div. 2)

A. Submission Bait

链接:Problem - A - Codeforces

思路:

要想赢,那么就必须存在奇数个相等的数,注意不是看最大值是否有奇数个,而是看是否存在奇数个相等的数,因为可以从这个数开始算,之后必定都是偶数个相等的数,偶数的话,先选的人必输

代码:

#include <bits/stdc++.h>
#define int long long
using namespace std;

void solve() {
  int n;
  cin >> n;
  vector<int> a(n);
  for(int i = 0 ; i < n ; i++) cin >> a[i];
  sort(a.begin() , a.end());
  bool falg = n % 2 == 0;//看总共的个数是否为偶数,如果为奇数表示一定存在相等的数有奇数个
  for(int i = 0 ; i + 1 < n ; i += 2) {
    if(a[i] != a[i + 1]) {//表示存在奇数个相等的数
      falg = false;
      break;
    }
  }
  if(!falg) cout << "YES" << endl;
  else cout << "NO" << endl;
}

signed main()
{
  ios::sync_with_stdio(false);
  int t = 1;
  cin >> t;
  while(t--) solve();
  return 0;
}

B. Array Craft

链接:Problem - B - Codeforces

思路:

首先 y < x y < x y<x,所以在这里面的数肯定都为 1 1 1,如果要在 x x x的位置停下,那么大于 x x x的数必定的一负一正的排列,这样后面的数要么为 0 0 0,要么为 − 1 -1 1,这样要使前缀和最大的最小位置就是 x x x了,因为往后面加并不会影响前缀和的大小;而 y y y这边也是如此,从 y − 1 y-1 y1 1 1 1这里也是一负一正的排列,这样后缀和最大的最大位置就是 y y y

代码:

#include <bits/stdc++.h>
#define int long long
using namespace std;

void solve() {
  int n , x , y;
  cin >> n >> x >> y;
  for(int i = 1 ; i <= n ; i++) {
    if(i < y) cout << ((y - i) % 2 == 0 ? 1 : -1) << " ";//小于y的排列
    else if(i < x) cout << 1 << " ";//y~x之间都为1
    else cout << ((i - x) % 2 == 0 ? 1 : -1) << " ";//大于x的排列
  }
  cout << endl;
}

signed main()
{
  ios::sync_with_stdio(false);
  int t = 1;
  cin >> t;
  while(t--) solve();
  return 0;
}

C. Mad MAD Sum

链接:Problem - C - Codeforces

思路:

首先,我们可以发现经过一次变换之后的序列都是递增的,经过第二次变换,如果这个序列够长,那么最前面两个不为零的数会相等,并且一直循环下去

例如:
原序列:1 2 3 1 2 3 4 4 4 4 6 6 7 8 7 8 9 9 9
第一次:0 0 0 1 2 3 3 4 4 4 4 6 6 6 7 8 8 9 9
第二次:0 0 0 0 0 0 3 3 4 4 4 4 6 6 6 6 8 8 9
第三次:0 0 0 0 0 0 0 3 3 4 4 4 4 6 6 6 6 8 8
第四次:0 0 0 0 0 0 0 0 3 3 4 4 4 4 6 6 6 6 8
第五次:0 0 0 0 0 0 0 0 0 3 3 4 4 4 4 6 6 6 6
第六次:0 0 0 0 0 0 0 0 0 0 3 3 4 4 4 4 6 6 6
… …

我们可以发现经历了两次变换之后,基本上所有的非零数的出现个数都是大于等于 2 2 2,除了最后一个数,然后后面的变换基本都是往后平移一个单位,他们要求的是前缀和的和,那么我们求出这个数出现了几次即可。我们知道他每一次变换都是往后平移一个单位,那么就是这个数在他之后的位置都会出现,所以我们只要求出 a [ i ] ∗ ( n − i ) a[i]*(n-i) a[i](ni)之和就是最后的结果

代码:

#include <bits/stdc++.h>
#define int long long
using namespace std;

void solve() {
  int n;
  cin >> n;
  vector<int> a(n);
  for(int i = 0 ; i < n ; i++) cin >> a[i];
  int ans = 0;
  for(int t = 0 ; t < 2 ; t++) {//先进行两次变换,后面的数都是平移
    int mx = 0;//用来记录出现两次以上的最大数
    vector<int> v(n + 1);//用来判断当前数是否出现过
    for(auto &i : a) {
      ans += i;//前两次也要计算前缀和,加到最后的结果中
      if(v[i]) mx = max(mx , i);//计算出现两次的最大值
      v[i] = 1;
      i = mx;//替换
    }
  }
  //下面就是平移了,看这个数出现了几次
  for(int i = 0 ; i < n ; i++) {
    ans += (n - i) * a[i]; 
  }
  cout << ans << endl;
}

signed main()
{
  ios::sync_with_stdio(false);
  int t = 1;
  cin >> t;
  while(t--) solve();
  return 0;
}

D. Grid Puzzle

链接:Problem - D - Codeforces

思路:

其实这种题还是主要靠发现,我们发现 2 、 4 、 4 、 2 2、4、4、2 2442就是一组特别的数据,他可以只要 3 3 3次即可全部变为白色
首先,如果这个数大于 4 4 4的话,那么按照第一种操作方法他至少需要两次或两次以上,那么还不如直接将其用第二种方法
解法一:

  1. 如果这个数大于 4 4 4,操作数加一,将其变为零
  2. 如果 a i = 1 a_i=1 ai=1将其变为 2 2 2,如果 a i = 3 a_i=3 ai=3将其变为 4 4 4
  3. 扫一遍,如果存在相邻两行都为 4 4 4,那么操作数加一,且这两行的数都变为 2 2 2(用的是第一种变法,后面的2*2的格子变为白色,前面不变),如果只是一行为 4 4 4,那么操作数加一,将其变为 0 0 0(用的是第二种方法,将一行变为零)
  4. 再扫一遍,如果数为 2 2 2,操作数加一, i i i++,即只用第一种方法,后面一行不管是否为 2 2 2,都可以直接跳过

解法二: 我是看不懂一点,有看懂的朋友可以给我讲讲

代码:

解法一:

#include <bits/stdc++.h>
#define int long long
using namespace std;

void solve() {
  int n;
  cin >> n;
  vector<int> a(n);
  int ans = 0;
  for(int i = 0 ; i < n ; i++) {
    cin >> a[i];
    //预处理
    if(a[i] == 1) a[i] = 2;
    if(a[i] == 3) a[i] = 4;
    if(a[i] > 4) {
      a[i] = 0;
      ans++;
    }
  }
  //第一次先找4
  for(int i = 0 ; i < n ; i++) {
    if(a[i] == 4) {
      if(i + 1 < n && a[i + 1] == 4) {
        ans++;
        a[i] = 2;
        i++;
        a[i] = 2;
      } else {
        ans++;
        a[i] = 0;
      }
    }
  }
  //第二次找2
  for(int i = 0 ; i < n ; i++) {
    if(a[i] == 2) {
      ans++;
      i++;
    }
  }
  cout << ans << endl;
}

signed main()
{
  ios::sync_with_stdio(false);
  int t = 1;
  cin >> t;
  while(t--) solve();
  return 0;
}

解法二:

#include <bits/stdc++.h>
#define int long long
using namespace std;

const int inf = 1e9;

void chmin(int &a , int b) {
  if(a > b) a = b;
}

void solve() {
  int n;
  cin >> n;
  vector<int> a(n);
  int ans = 0;
  for(int i = 0 ; i < n ; i++) cin >> a[i];
  vector<int> f(n + 1 , inf) , g(n + 1 , inf);
  f[0] = 0;
  for(int i = 0 ; i < n ; i++) {
    chmin(f[i + 1] , f[i] + (a[i] > 0));
    if(a[i] <= 2) {
      chmin(g[i + 1] , f[i] + 1);
      chmin(f[i + 1] , g[i]);
    }
    if(i + 1 < n && a[i] <= 4 && a[i + 1] <= 4) {
      chmin(g[i + 2] , g[i] + 2);
    }
  }
  cout << f[n] << endl;
}

signed main()
{
  ios::sync_with_stdio(false);
  int t = 1;
  cin >> t;
  while(t--) solve();
  return 0;
}

原文地址:https://blog.csdn.net/ZYH_5201314/article/details/140591806

免责声明:本站文章内容转载自网络资源,如本站内容侵犯了原著者的合法权益,可联系本站删除。更多内容请关注自学内容网(zxcms.com)!