制作图片网站,中国企业500强利润排行,北京网站建设公司网站优化资讯,北京做彩右影影视公司网站A#xff1a;
这种操作题#xff0c;每次先想这个操作有什么性质
对于2^0来说可以操作 第1位 对于2^1来说可以操作 第1-2位
对于2^2来说可以操作 第1-4位 #xff08;第3位无法单独修改#xff09;
对于2^3来说可以操作 第1-8位#xff08;第5 6 7位无法单独修改…A
这种操作题每次先想这个操作有什么性质
对于2^0来说可以操作 第1位 对于2^1来说可以操作 第1-2位
对于2^2来说可以操作 第1-4位 第3位无法单独修改
对于2^3来说可以操作 第1-8位第5 6 7位无法单独修改
可以观察到我们要求无法修改的数要按顺序才能满足
#includebits/stdc.h
using namespace std;
const int N 1e610,mod 998244353;
#define int long long
typedef long long LL;
typedef pairint, int PII;
const long long inf1e17;
int n,m,k;
vectorint g[N];
int a[N];
void solve()
{cinn;for(int i1;in;i){cina[i];}for(int i2;i5;i){bool oktrue;// coutpow(2,i-1) pow(2,i)\n;for(int jpow(2,i-1)1;jpow(2,i);j){if(j1n||jn) break;if(a[j]a[j1]) continue;okfalse;} if(!ok){coutNO\n;return ;}}coutYES\n;
}signed main()
{cin.tie(0);cout.tie(0);ios::sync_with_stdio(0);int t1;cint;while(t--) solve();
}
B
操作题还是想操作当前数x对每个数组a的每个数有啥影响
如果当前数a[i]可以整除2^x然后加上2^(x-1)那么下次这个数就不能整除2^x
那么他就会变成2^(x-1)的倍数了他的因子不包含2^x,所以不会再操作
然后x最多30个数去重后操作即可
#includebits/stdc.h
using namespace std;
const int N 1e610,mod1e97;
#define int long long
typedef long long LL;
typedef pairint, int PII;
const long long inf1e17;
int n,m,k;
vectorint g[N];
int a[N];class BitTree {public:vectorint tree;int n;BitTree(int _n) : n(_n) {tree.resize(n1);fill(tree.begin(),tree.end(),0);}inline int lowbit(int x) { return x-x; }inline void Modify(int x,int v) {for(;xn;xlowbit(x)) tree[x]v;}inline int q(int x) {int ret0;if(x0) return 0;for(;x;x-lowbit(x)) rettree[x];return ret;}inline int Query(int l,int r) {return q(r)-q(l-1);}
};
int l[N],r[N];
void solve()
{vectorint b;mapint,int mp;cinnm;for(int i1;in;i) cina[i];for(int i1;im;i){int x;cinx;if(mp.count(x)) continue;mp[x];b.push_back(x);}for(int i1;in;i){int xa[i];for(auto y:b){if(x%(1y)0){x(1y-1);}}coutx \n[in];}}signed main()
{cin.tie(0);cout.tie(0);ios::sync_with_stdio(0);int t1;cint;while(t--) solve();
}
C贪心肯定是积个大的秒后面数量多的然后当操作最后一个数的时候尽量别浪费当前计数器的数要分奇偶性和1比如8前面已经有2了那么再操作2次计数器变成4操作个计数器秒掉如果当前是8前面计数器是3为了不浪费计数器最后一次肯定是直接消灭而不是使用计数器所以先-1变成偶数如果不这样做最后计数器会多1次数可能会增加再换成偶数操作即可特判1
#includebits/stdc.h
using namespace std;
const int N 1e610,mod 998244353;
#define int long long
typedef long long LL;
typedef pairint, int PII;
const long long inf1e17;
int n,m,k;
vectorint g[N];
int a[N];
void solve()
{cinn;for(int i1;in;i) cina[i];sort(a1,a1n);int res0;int l1,rn;int sum0;while(lr){if(a[l]0){l;continue;}if(lr){if(a[l]1){res;break;}if((a[l]-sum)%21){res(a[l]-sum)/21;res;}else{res(a[l]-sum)/21;}coutres\n;return ;}if(a[r]suma[l]){int xa[r]-sum;resx1;a[l]-x;r--;sum0;} else{suma[l];resa[l];l; }}coutres\n;
}signed main()
{cin.tie(0);cout.tie(0);ios::sync_with_stdio(0);int t1;cint;while(t--) solve();
}
D套路题求两个区间差即可
然后我画图你应该能看懂 g的函数的值最多有两个不同因为3 4 5...的增长比2增长快所以最多两个
可以观察到g的值怎么求
比如8 到 15
用3的倍数求
16到31用 4倍数求他们的g的值然后乘上求区间个数即可
#includebits/stdc.h
using namespace std;
const int N 1e610,mod1e97;
#define int long long
typedef long long LL;
typedef pairint, int PII;
const long long inf1e17;
int n,m,k;
vectorint g[N];
int a[N];
void solve()
{auto get[](int x){int res0;int c2;for(int i4;ix;i*2){int cnt0;int rmin(x,i*2-1);__int128 now1;while(nowi) cnt,now*c;c;if(nowr){res(r-i1)%mod*(cnt-1)%mod;}else{int tr-now1;t%mod;rest*cnt%mod(now-i)%mod*(cnt-1);}}return res%mod;};int l,r;cinlr;cout((get(r)-get(l-1))%modmod)%mod\n;
}signed main()
{cin.tie(0);cout.tie(0);ios::sync_with_stdio(0);int t1;cint;while(t--) solve();
}
F首先肯定要把数dfs一遍弄出来把不然鬼知道子树有哪些
然后我们把树画出来 假设 5是新增的节点我们怎么操作
直接把前面5节点的数全部减成0即可
然后就是差分咯因为子树增加是增加整个区间的
#includebits/stdc.h
using namespace std;
const int N 1e610,mod1e97;
#define int long long
typedef long long LL;
typedef pairint, int PII;
const long long inf1e17;
int n,m,k;
vectorint g[N];
int a[N];class BitTree {public:vectorint tree;int n;BitTree(int _n) : n(_n) {tree.resize(n1);fill(tree.begin(),tree.end(),0);}inline int lowbit(int x) { return x-x; }inline void Modify(int x,int v) {for(;xn;xlowbit(x)) tree[x]v;}inline int q(int x) {int ret0;if(x0) return 0;for(;x;x-lowbit(x)) rettree[x];return ret;}inline int Query(int l,int r) {return q(r)-q(l-1);}
};
int l[N],r[N];
void solve()
{cinn;for(int i1;in*210;i)g[i].clear();vectorarrayint,3query;int now1;for(int i0;in;i){int op;cinop;if(op1){now;int v;cinv;query.push_back({op,v,0});g[v].push_back(now);}else{int v,x;cinvx;query.push_back({op,v,x});}}int dfn0;functionvoid(int) dfs[](int u){l[u]dfn;for(auto v:g[u]){dfs(v);}r[u]dfn;};dfs(1);BitTree tr(n*210);now1;for(auto [op,v,x]:query){if(op1){//v增加一个子节点now;int ttr.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 i1;inow;i){couttr.q(l[i]) \n[inow];}
}signed main()
{cin.tie(0);cout.tie(0);ios::sync_with_stdio(0);int t1;cint;while(t--) solve();
}
