当前位置:网站首页>Codeforces Round #808 (Div. 2) - A,B,C
Codeforces Round #808 (Div. 2) - A,B,C
2022-07-21 08:53:00 【小酒窝.】
https://codeforces.com/contest/1708
C. Doremy’s IQ
题意
给定长度为 n n n 的数组,给定一个值 m m m。从前往后对于每个位置 i i i:
- 如果 a i ≤ m a_i ≤ m ai≤m,那么这个位置可拿;
- 否则,如果拿这个位置的话, m − 1 m-1 m−1;否则无变化。
问,最多拿多少位置?
1 ≤ n ≤ 1 0 5 , 1 ≤ m ≤ 1 0 9 1 \le n \le 10^5,1 \le m \le 10^9 1≤n≤105,1≤m≤109
思路
#include<bits/stdc++.h>
using namespace std;
#define Ios ios::sync_with_stdio(false),cin.tie(0)
const int N = 200010, mod = 1e9+7;
int T, n, m;
int a[N];
int f[N], ans[N];
signed main(){
Ios;
cin >> T;
while(T--)
{
cin >> n >> m;
for(int i=1;i<=n;i++) cin >> a[i];
f[n + 1] = 0;
for(int i=n;i>=1;i--){
if(a[i] <= f[i+1]) f[i] = f[i+1];
else f[i] = f[i+1] + 1;
}
for(int i=1;i<=n;i++)
{
if(a[i] <= m) ans[i] = 1;
else if(f[i] <= m)
{
for(int j=i;j<=n;j++) ans[j] = 1;
break;
}
else ans[i] = 0;
}
for(int i=1;i<=n;i++) cout << ans[i];
cout << endl;
}
return 0;
}
经验
关键在于贪心思想,既然都会花费代价,不妨留到最后再花费,中间还可能会有贡献。
留到最后在什么地方呢?
如果给定的钱数对于某个位置到末位置能花费完的话,那就是最后的位置了。
可以先预处理出每个位置到末位置所需要的花费为多少。
B. Difference of GCDs
题意
问是否存在 n n n 个位于区间 [ l , r ] [l, r] [l,r] 中的数 a i a_i ai,满足 g c d ( i , a i ) gcd(i, a_i) gcd(i,ai) 互不相同?
1 ≤ n ≤ 1 0 5 , 1 ≤ l ≤ r ≤ 1 0 9 1 \le n \le 10^5,1\le l\le r\le 10^9 1≤n≤105,1≤l≤r≤109
思路
n 个 gcd 互不相同,如果不想特殊情况的话也太复杂了。
那就直接考虑特殊的, i i i 和 a i a_i ai 的 g c d gcd gcd 为 i i i,这样 n 个位置就互不相同了。
那就是看是否有 i 的倍数在区间 [l, r] 中,O(1)得出答案。
直接用 l/i
得到最大因子,如果能整除 l 就满足,否则就看 i*(l/i+1)
在不在区间中。
Code
#include<bits/stdc++.h>
using namespace std;
#define Ios ios::sync_with_stdio(false),cin.tie(0)
const int N = 200010, mod = 1e9+7;
int T, n, m;
int a[N];
signed main(){
Ios;
cin >> T;
while(T--)
{
cin >> n;
int l, r; cin>>l>>r;
int x = l, flag = 0;
for(int i=1;i<=n;i++)
{
int t = x/i;
if(x % i == 0) a[i] = x;
else a[i] = (t+1)*i;
if(a[i] > r) flag = 1;
}
if(flag){
cout << "NO\n";
continue;
}
cout << "YES\n";
for(int i=1;i<=n;i++) cout << a[i] << " ";
cout << endl;
}
return 0;
}
A. Difference Operations
题意
给定长度为 n 的数列,判断能否经过若干次下面操作使 2~n 位置变为 0?
- 选择一个位置 i ( 2 ≤ i ≤ n ) i(2 \le i \le n) i(2≤i≤n),将 a i a_i ai 变为 a i − a i − 1 a_i - a_{i-1} ai−ai−1
2 ≤ n ≤ 100 , 1 ≤ a i ≤ 1 0 9 2 \le n \le 100,1 \le a_i \le 10^9 2≤n≤100,1≤ai≤109
思路
如果后面所有数都是 a[1] 的倍数则可以,否则不可以。
经验
注意看清题目,是选择一些位置,不是对所有位置。。
既然是选择一些,如果考虑选哪些选哪些就太复杂了,这时就应该考虑特殊情况或者最终状态,寻找共性。
太菜了。。
多刷题,多总结,多动脑。
做题时提高专注力,把一个思路想到底,看看最后会怎么样。
边栏推荐
猜你喜欢
Advanced C language: data storage (deep analysis - integer)
安全之路 —— 单管道反向连接后门解析
05-1. Default member function: copy constructor, assignment operator overload
SparkSql中的窗口函数
BGP—— 边界网关协议
每个博主都需要问自己的7个基本问题
2022-7-17 FTP客户端项目实现 - 总结
Easyexcel realizes file upload - batch insert file download
TCP的滑动窗口、单例模式(懒汉饿汉)双检锁/双重校验锁(DCL,即 double-checked locking)
Jugement des chaînes vides dans Oracle
随机推荐
ssh方式登录huawei设备
swift 【block】
Pytorch common code snippet collection
一文深入浅出理解国产开源木兰许可系列协议
请问这是表示mysql的binlog已经开启吗?
Aruba学习笔记03-Web UI --Monitoring面板介绍
URLEncode.encode(String,String) 和 new String(byte[],String) 的区别
谷歌展示 Chrome 浏览器图标废案,曾打算做成小火箭
Leetcode 206反转链表、3无重复字符的最长子串、912排序数组(快排)、215数组中的第k个最大元素、53最大子数组和、152乘积最大子数组
BGP—— 边界网关协议
The Linux server installed the graphical interface, but failed to display the initialization graphical interface when installing the database
SQL164 2021年11月每天新用户的次日留存率
xshell连接时显示“服务器发送了一个意外的数据包。received:3,expected:20
企业电表数据采集 局域网本地存储软件系统
动态规划多重背包一维
Huirong technology and jiangbolong work together to improve the competitiveness of mobile phone storage
一文深入浅出理解国产开源木兰许可系列协议
2022-7-17 FTP client project implementation - Summary
Screen sharing software --deskreen
多重背包问题代码模板