Codeforces Round 960 (Div. 2)A~D

🕗 发布于 2024-07-22 09:26 算法 c++

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

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$ ，所以在这里面的数肯定都为 $1$ ，如果要在 $x$ 的位置停下，那么大于 $x$ 的数必定的一负一正的排列，这样后面的数要么为 $0$ ，要么为 $- 1$ ，这样要使前缀和最大的最小位置就是 $x$ 了，因为往后面加并不会影响前缀和的大小；而 $y$ 这边也是如此，从 $y - 1$ 到 $1$ 这里也是一负一正的排列，这样后缀和最大的最大位置就是 $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$ ，除了最后一个数，然后后面的变换基本都是往后平移一个单位，他们要求的是前缀和的和，那么我们求出这个数出现了几次即可。我们知道他每一次变换都是往后平移一个单位，那么就是这个数在他之后的位置都会出现，所以我们只要求出 $a [i] * (n - i)$ 之和就是最后的结果

代码：

#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$ 就是一组特别的数据，他可以只要 $3$ 次即可全部变为白色
首先，如果这个数大于 $4$ 的话，那么按照第一种操作方法他至少需要两次或两次以上，那么还不如直接将其用第二种方法
解法一：

如果这个数大于 $4$ ，操作数加一，将其变为零
如果 $a_i=1$ 将其变为 $2$ ，如果 $a_i=3$ 将其变为 $4$
扫一遍，如果存在相邻两行都为 $4$ ，那么操作数加一，且这两行的数都变为 $2$ （用的是第一种变法，后面的2*2的格子变为白色，前面不变），如果只是一行为 $4$ ，那么操作数加一，将其变为 $0$ （用的是第二种方法，将一行变为零）
再扫一遍，如果数为 $2$ ，操作数加一， $i$ ++，即只用第一种方法，后面一行不管是否为 $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）！

上一篇：开源智能助手平台Dify是什么？
下一篇：【AI资讯早报】AI科技前沿资讯概览：2024年7月22日早报

免费申请 Let‘s Encrypt SSL 证书
在网络安全日益重要的今天，为网站启用 SSL 证书是保障数据安全和用户信任的关键。Let's Encrypt 提供的免费 SSL 证书是一个很好的选择。下面我们详细介绍如何为网站域名申请该证书。
阅读更多2024-11-16
Spring Boot 中使用 @Transactional 注解配置事务管理
Spring Boot 中使用 @Transactional 注解配置事务管理
阅读更多2024-11-16
自定义实体类中DateTime属性的序列化格式
本文介绍了Newtonsoft.Json与System.Text.Json下如何在实体上自定义DateTime类型的序列化格式。
阅读更多2024-11-16
阅读2020-2023年《国外军用无人机装备技术发展综述》笔记_作战无人机和察打无人机图鉴
本篇对2020-2023年《国外军用无人机装备技术发展综述》这几篇文章中所提到的作战无人机和察打无人机逐个更详细的介绍。
阅读更多2024-11-16
Flutter：InheritedWidget数据共享
未使用数据共享时，要传递数据，只能组件间一级一级向下传递。InheritedWidget数据共享，优化下上边代码。下边代码中，创建了一个按钮，当点击时。
阅读更多2024-11-16
Ubuntu22.04.2 k8s部署
Helm 是 Kubernetes 的一个包管理工具，类似于 Linux 下的 apt 或 yum。它可以帮助用户通过定义配置文件的方式来部署和管理 Kubernetes 应用，极大地简化了应用在 K
阅读更多2024-11-16
推荐一款全能网络视频下载工具：闪豆视频下载器
是一款网络视频，主要支持下载同时，软件还具备4K、1080p60、720p60、1080+、720p、480p、360p画质的视频下载，无论你想要哪种画质，在这里都能满足你。
阅读更多2024-11-16
3D电子商务是什么？如何利用3D技术提升销售转化？
3D电子商务，简而言之，就是利用3D产品模型来优化和提升在线购物体验的一种新型电商模式。它打破了传统二维图片的局限，使消费者能够以前所未有的方式“触摸”和感受商品。无论是家具、服装、电子产品还是艺术品
阅读更多2024-11-16
麒麟系统下docker搭建jenkins
执行这个命令后，我们将启动一个Jenkins容器，并且可以通过宿主机的7083端口访问Jenkins的Web界面，通过7084端口访问Jenkins的调试端口。同时，Jenkins的数据会被存储在宿主
阅读更多2024-11-16
前后端交互之动态列
在做项目时，有时候后会遇到后端使用了**聚合函数**，导致生成的**对象的属性数量或数量不固定**，因此无法建立一个与之对应的对象来向前端传递数据，这时可以采用NameDataListVO向前端传递
阅读更多2024-11-16

Codeforces Round 960 (Div. 2)A~D