Codeforces Round 907 (Div. 2) (C 贪心 D套路? F dfs序+差分树状数组)

2023-11-30 05:44

本文主要是介绍Codeforces Round 907 (Div. 2) (C 贪心 D套路? F dfs序+差分树状数组),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

A:

这种操作题,每次先想这个操作有什么性质

对于2^0来说可以操作 第1位

 对于2^1来说可以操作 第1-2位

对于2^2来说可以操作 第1-4位 (第3位无法单独修改)

对于2^3来说可以操作 第1-8位(第5 6 7位无法单独修改)

可以观察到我们要求无法修改的数要按顺序才能满足

#include<bits/stdc++.h>
using namespace std;
const int N = 1e6+10,mod= 998244353;
#define int long long
typedef long long LL;
typedef pair<int, int> PII;
const long long inf=1e17;
int n,m,k;
vector<int> g[N];
int a[N];
void solve()
{cin>>n;for(int i=1;i<=n;i++){cin>>a[i];}for(int i=2;i<=5;i++){bool ok=true;// cout<<pow(2,i-1)<<" "<<pow(2,i)<<"\n";for(int j=pow(2,i-1)+1;j<pow(2,i);j++){if(j+1>n||j>n) break;if(a[j]<=a[j+1]) continue;ok=false;}    if(!ok){cout<<"NO\n";return ;}}cout<<"YES\n";
}signed main()
{cin.tie(0);cout.tie(0);ios::sync_with_stdio(0);int t=1;cin>>t;while(t--) solve();
}

B:

操作题,还是想操作当前数x对每个数组a的每个数有啥影响

如果当前数a[i]可以整除2^x,然后加上2^(x-1),那么下次这个数就不能整除2^x

那么他就会变成2^(x-1)的倍数了,他的因子不包含2^x,所以不会再操作

然后x最多30个数,去重后操作即可

#include<bits/stdc++.h>
using namespace std;
const int N = 1e6+10,mod=1e9+7;
#define int long long
typedef long long LL;
typedef pair<int, int> PII;
const long long inf=1e17;
int n,m,k;
vector<int> g[N];
int a[N];class BitTree {public:vector<int> tree;int n;BitTree(int _n) : n(_n) {tree.resize(n+1);fill(tree.begin(),tree.end(),0);}inline int lowbit(int x) { return x&-x; }inline void Modify(int x,int v) {for(;x<=n;x+=lowbit(x)) tree[x]+=v;}inline int q(int x) {int ret=0;if(x<=0) return 0;for(;x;x-=lowbit(x)) ret+=tree[x];return ret;}inline int Query(int l,int r) {return q(r)-q(l-1);}
};
int l[N],r[N];
void solve()
{vector<int> b;map<int,int> mp;cin>>n>>m;for(int i=1;i<=n;i++) cin>>a[i];for(int i=1;i<=m;i++){int x;cin>>x;if(mp.count(x)) continue;mp[x]++;b.push_back(x);}for(int i=1;i<=n;i++){int x=a[i];for(auto y:b){if(x%(1<<y)==0){x+=(1<<y-1);}}cout<<x<<" \n"[i==n];}}signed main()
{cin.tie(0);cout.tie(0);ios::sync_with_stdio(0);int t=1;cin>>t;while(t--) solve();
}

C:贪心,肯定是积个大的秒后面数量多的,然后当操作最后一个数的时候,尽量别浪费当前计数器的数,要分奇偶性和1,比如8,前面已经有2了,那么再操作2次,计数器变成4,操作个计数器秒掉,如果当前是8,前面计数器是3,为了不浪费计数器,最后一次肯定是直接消灭而不是使用计数器,所以先-1变成偶数(如果不这样做,最后计数器会多1,次数可能会增加),再换成偶数操作即可,特判1

#include<bits/stdc++.h>
using namespace std;
const int N = 1e6+10,mod= 998244353;
#define int long long
typedef long long LL;
typedef pair<int, int> PII;
const long long inf=1e17;
int n,m,k;
vector<int> g[N];
int a[N];
void solve()
{cin>>n;for(int i=1;i<=n;i++) cin>>a[i];sort(a+1,a+1+n);int res=0;int l=1,r=n;int sum=0;while(l<=r){if(a[l]==0){l++;continue;}if(l==r){if(a[l]==1){res++;break;}if((a[l]-sum)%2==1){res+=(a[l]-sum)/2+1;res++;}else{res+=(a[l]-sum)/2+1;}cout<<res<<"\n";return ;}if(a[r]<=sum+a[l]){int x=a[r]-sum;res+=x+1;a[l]-=x;r--;sum=0;}    else{sum+=a[l];res+=a[l];l++;    }}cout<<res<<"\n";
}signed main()
{cin.tie(0);cout.tie(0);ios::sync_with_stdio(0);int t=1;cin>>t;while(t--) solve();
}

D:套路题,求两个区间差即可

然后我画图你应该能看懂

g的函数的值最多有两个不同,因为3 4 5...的增长比2增长快,所以最多两个

可以观察到g的值怎么求

比如8 到 15

用3的倍数求

16到31用 4倍数求他们的g的值,然后乘上求区间个数即可

#include<bits/stdc++.h>
using namespace std;
const int N = 1e6+10,mod=1e9+7;
#define int long long
typedef long long LL;
typedef pair<int, int> PII;
const long long inf=1e17;
int n,m,k;
vector<int> g[N];
int a[N];
void solve()
{auto get=[&](int x){int res=0;int c=2;for(int i=4;i<=x;i*=2){int cnt=0;int r=min(x,i*2-1);__int128 now=1;while(now<=i) cnt++,now*=c;c++;if(now>r){res+=(r-i+1)%mod*(cnt-1)%mod;}else{int t=r-now+1;t%=mod;res+=t*cnt%mod+(now-i)%mod*(cnt-1);}}return res%mod;};int l,r;cin>>l>>r;cout<<((get(r)-get(l-1))%mod+mod)%mod<<"\n";
}signed main()
{cin.tie(0);cout.tie(0);ios::sync_with_stdio(0);int t=1;cin>>t;while(t--) solve();
}

F:首先肯定要把数dfs一遍弄出来把,不然鬼知道子树有哪些

然后我们把树画出来

假设 5是新增的节点,我们怎么操作,

直接把前面5节点的数全部减成0即可

然后就是差分咯,因为子树增加是增加整个区间的

#include<bits/stdc++.h>
using namespace std;
const int N = 1e6+10,mod=1e9+7;
#define int long long
typedef long long LL;
typedef pair<int, int> PII;
const long long inf=1e17;
int n,m,k;
vector<int> g[N];
int a[N];class BitTree {public:vector<int> tree;int n;BitTree(int _n) : n(_n) {tree.resize(n+1);fill(tree.begin(),tree.end(),0);}inline int lowbit(int x) { return x&-x; }inline void Modify(int x,int v) {for(;x<=n;x+=lowbit(x)) tree[x]+=v;}inline int q(int x) {int ret=0;if(x<=0) return 0;for(;x;x-=lowbit(x)) ret+=tree[x];return ret;}inline int Query(int l,int r) {return q(r)-q(l-1);}
};
int l[N],r[N];
void solve()
{cin>>n;for(int i=1;i<=n*2+10;i++)g[i].clear();vector<array<int,3>>query;int now=1;for(int i=0;i<n;i++){int op;cin>>op;if(op==1){now++;int v;cin>>v;query.push_back({op,v,0});g[v].push_back(now);}else{int v,x;cin>>v>>x;query.push_back({op,v,x});}}int dfn=0;function<void(int)> dfs=[&](int u){l[u]=++dfn;for(auto v:g[u]){dfs(v);}r[u]=++dfn;};dfs(1);BitTree tr(n*2+10);now=1;for(auto [op,v,x]:query){if(op==1){//v增加一个子节点now++;int t=tr.q(l[now]);tr.Modify(l[now],-t);tr.Modify(r[now],t);}else{tr.Modify(l[v],x);tr.Modify(r[v],-x);}}for(int i=1;i<=now;i++){cout<<tr.q(l[i])<<" \n"[i==now];}
}signed main()
{cin.tie(0);cout.tie(0);ios::sync_with_stdio(0);int t=1;cin>>t;while(t--) solve();
}

这篇关于Codeforces Round 907 (Div. 2) (C 贪心 D套路? F dfs序+差分树状数组)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/435845

相关文章

MySQL查询JSON数组字段包含特定字符串的方法

《MySQL查询JSON数组字段包含特定字符串的方法》在MySQL数据库中,当某个字段存储的是JSON数组,需要查询数组中包含特定字符串的记录时传统的LIKE语句无法直接使用,下面小编就为大家介绍两种... 目录问题背景解决方案对比1. 精确匹配方案(推荐)2. 模糊匹配方案参数化查询示例使用场景建议性能优

关于集合与数组转换实现方法

《关于集合与数组转换实现方法》:本文主要介绍关于集合与数组转换实现方法,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录1、Arrays.asList()1.1、方法作用1.2、内部实现1.3、修改元素的影响1.4、注意事项2、list.toArray()2.1、方

MySQL JSON 查询中的对象与数组技巧及查询示例

《MySQLJSON查询中的对象与数组技巧及查询示例》MySQL中JSON对象和JSON数组查询的详细介绍及带有WHERE条件的查询示例,本文给大家介绍的非常详细,mysqljson查询示例相关知... 目录jsON 对象查询1. JSON_CONTAINS2. JSON_EXTRACT3. JSON_TA

JAVA数组中五种常见排序方法整理汇总

《JAVA数组中五种常见排序方法整理汇总》本文给大家分享五种常用的Java数组排序方法整理,每种方法结合示例代码给大家介绍的非常详细,感兴趣的朋友跟随小编一起看看吧... 目录前言:法一:Arrays.sort()法二:冒泡排序法三:选择排序法四:反转排序法五:直接插入排序前言:几种常用的Java数组排序

Java数组初始化的五种方式

《Java数组初始化的五种方式》数组是Java中最基础且常用的数据结构之一,其初始化方式多样且各具特点,本文详细讲解Java数组初始化的五种方式,分析其适用场景、优劣势对比及注意事项,帮助避免常见陷阱... 目录1. 静态初始化:简洁但固定代码示例核心特点适用场景注意事项2. 动态初始化:灵活但需手动管理代

C++中初始化二维数组的几种常见方法

《C++中初始化二维数组的几种常见方法》本文详细介绍了在C++中初始化二维数组的不同方式,包括静态初始化、循环、全部为零、部分初始化、std::array和std::vector,以及std::vec... 目录1. 静态初始化2. 使用循环初始化3. 全部初始化为零4. 部分初始化5. 使用 std::a

shell编程之函数与数组的使用详解

《shell编程之函数与数组的使用详解》:本文主要介绍shell编程之函数与数组的使用,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录shell函数函数的用法俩个数求和系统资源监控并报警函数函数变量的作用范围函数的参数递归函数shell数组获取数组的长度读取某下的

C++原地删除有序数组重复项的N种方法

《C++原地删除有序数组重复项的N种方法》给定一个排序数组,你需要在原地删除重复出现的元素,使得每个元素只出现一次,返回移除后数组的新长度,不要使用额外的数组空间,你必须在原地修改输入数组并在使用O(... 目录一、问题二、问题分析三、算法实现四、问题变体:最多保留两次五、分析和代码实现5.1、问题分析5.

Java中数组转换为列表的两种实现方式(超简单)

《Java中数组转换为列表的两种实现方式(超简单)》本文介绍了在Java中将数组转换为列表的两种常见方法使用Arrays.asList和Java8的StreamAPI,Arrays.asList方法简... 目录1. 使用Java Collections框架(Arrays.asList)1.1 示例代码1.

C++一个数组赋值给另一个数组方式

《C++一个数组赋值给另一个数组方式》文章介绍了三种在C++中将一个数组赋值给另一个数组的方法:使用循环逐个元素赋值、使用标准库函数std::copy或std::memcpy以及使用标准库容器,每种方... 目录C++一个数组赋值给另一个数组循环遍历赋值使用标准库中的函数 std::copy 或 std::