当前位置: 首页 > news >正文

Codeforces Round 889 (Div. 2)(视频讲解A——D)

文章目录

  • A Dalton the Teacher
  • B Longest Divisors Interval
  • C2 Dual (hard Version)
  • D Earn or Unlock

Codeforces Round 889 (Div. 2)(视频讲解A——D)
在这里插入图片描述

A Dalton the Teacher

#include<bits/stdc++.h>
#define endl '\n'
#define INF 0x3f3f3f3f
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int N = 1e5 + 10;void solve()
{int n;cin >> n;vector<int>a(n + 1);int ans = 0;for(int i = 1; i <= n; i ++){cin >> a[i];if(a[i] == i)ans ++;}cout << (ans + 1) / 2 << endl;
}	signed main()
{ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);int t;cin >> t;while(t--)solve();
}

B Longest Divisors Interval

#include<bits/stdc++.h>
#define endl '\n'
#define INF 0x3f3f3f3f
#define int long long
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int N = 1e5 + 10;void solve()
{int n;cin >> n;if(n <= 2){cout << n << endl;return;}for(int i = 1; i <= n; i ++){if((n % i) != 0){cout << i - 1 << endl;return;}}
}signed main()
{ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);int t;cin >> t;while(t--)solve();
}

C2 Dual (hard Version)

#include<bits/stdc++.h>
#define endl '\n'
#define INF 0x3f3f3f3f
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int N = 1e5 + 10;void add_1(vector<int>&a, vector<pii>&ans)
{for(int i = 0; i < a.size() - 1; i ++){a[i + 1] += a[i];ans.push_back({i + 1, i});}cout << ans.size() << endl;for(auto [a, b] : ans)cout << a + 1 << " " << b + 1 << endl;return;
}void add_2(vector<int>&a, vector<pii>&ans)
{for(int i = a.size() - 1; i >= 1; i --){a[i - 1] += a[i];ans.push_back({i - 1, i});}cout << ans.size() << endl;for(auto [a, b]: ans)cout << a + 1 << " " << b + 1 << endl;return;
}void solve()
{int n;cin >> n;vector<int>a(n);int p_max = 0, p_min = 0;int cnt_1 = 0, cnt_2 = 0;vector<pii>ans;for(int i = 0; i < n; i ++){cin >> a[i];if(a[p_max] < a[i])p_max = i;if(a[p_min] > a[i])p_min = i;if(a[i] < 0)cnt_2 ++;if(a[i] > 0)cnt_1 ++;}if(a[p_min] >= 0){add_1(a, ans);return;}if(a[p_max] <= 0){add_2(a, ans);return;}if(abs(a[p_max]) >= abs(a[p_min])){if(cnt_2 <= 12){for(int i = 0; i < n; i ++){if(a[i] < 0){a[i] += a[p_max];ans.push_back({i, p_max});}}add_1(a, ans);}else{for(int i = 0; i < 5; i ++){if(abs(a[p_min]) >= abs(a[p_max]))break;ans.push_back({p_min, p_min});a[p_min] += a[p_min];}for(int i = 0; i < n; i ++){if(a[i] > 0){a[i] += a[p_min];ans.push_back({i, p_min});}}add_2(a, ans);}}else{if(cnt_1 <= 12){for(int i = 0; i < n; i ++){if(a[i] > 0){a[i] += a[p_min];ans.push_back({i, p_min});}}add_2(a, ans);}else{for(int i = 0; i < 5; i ++){if(abs(a[p_max]) >= abs(a[p_min]))break;	a[p_max] += a[p_max];ans.push_back({p_max, p_max});}for(int i = 0; i < n; i ++){if(a[i] < 0){a[i] += a[p_max];ans.push_back({i, p_max});}}add_1(a, ans);}}}signed main()
{ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);int t;cin >> t;while(t--)solve();
}

D Earn or Unlock

#include<bits/stdc++.h>
#define endl '\n'
#define INF 0x3f3f3f3f
#define int long long
using namespace std;typedef long long ll;
typedef pair<int,int> pii;
const int N = 2e5 + 10;
bitset<N>f;
int n, a[N], sum[N];
void solve()
{cin >> n;for(int i = 1; i <= n; i ++)cin >> a[i];for(int i = 1; i <= 2 * n; i ++)sum[i] = sum[i - 1] + a[i];int ans = 0;f[1] = 1;for(int i = 1; i <= 2 * n; i ++){f |= (f << a[i]);if(f[i]){ans = max(sum[i] - i + 1, ans);f[i] = 0;}}cout << ans << endl;
}signed main()
{ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);solve();
}
http://www.lryc.cn/news/105510.html

相关文章:

  • K8s安全配置:CIS基准与kube-bench工具
  • linux安装python和部署Django项目
  • 00-Hadoop入门
  • SE-Net注意力机制详解
  • 商城免费搭建之java商城 开源java电子商务Spring Cloud+Spring Boot+mybatis+MQ+VR全景+b2b2c bbc
  • 推理加速 --- torch.compile
  • JS-----数据结构与算法(2)
  • 手把手安装TomCat;并部署JPress
  • tensorflow1.13分布式训练 参考资料 -教程原理
  • DP学习第五篇之礼物的最大价值
  • cURL error 1: Protocol “https“ not supported or disabled in libcurl
  • XCode升级后QT无法编译的问题
  • springboot编写mp4视频播放接口
  • 华为OD机试真题 JavaScript 实现【机器人活动区域】【2023Q1 200分】,附详细解题思路
  • C++中的静态分配和动态分配
  • 【Android常见问题(五)】- Flutter项目性能优化
  • JSON转换:实体类和JSONObject互转,List和JSONArray互转(fastjson版)
  • Java单例模式几种代码详解
  • PHP代码审计--理论
  • 在云服务器上,clone github时报Connection timed outexit code: 128
  • 小型双轮差速底盘寻迹功能的实现
  • 第七篇:k8s集群使用helm3安装Prometheus Operator
  • Chrome 75不支持保存成mhtml的解决方法
  • 工程监测振弦采集仪应用于岩土工程监测案例
  • 配置HDFS单机版,打造数据存储的强大解决方案
  • U盘删除的文件怎么找回?4个简单方法分享!
  • 【雕爷学编程】MicroPython动手做(27)——物联网之掌控板小程序2
  • 形参动态内存开辟和柔性数组
  • 【LLM系列之指令微调】长话短说大模型指令微调的“Prompt”
  • MacOS使用brew如何下载Nginx