公司企业做网站,湖南十大龙头企业,个人电商怎么做,挂号网站制作layout: post title: Codeforces Round 546 (Div. 2) author: luowentaoaa catalog: true tags: mathjax: true - codeforces - 贪心 - 数学 - 线段树 传送门 A - Nastya Is Reading a Book (签到) 题意 给出每一章的页数范围#xff0c;然后告诉你当前看到那一页…layout: post title: Codeforces Round 546 (Div. 2) author: luowentaoaa catalog: true tags: mathjax: true - codeforces - 贪心 - 数学 - 线段树 传送门 A - Nastya Is Reading a Book (签到) 题意 给出每一章的页数范围然后告诉你当前看到那一页求还没看完的章节数目 #includebits/stdc.h
using namespace std;
typedef long long ll;
const ll mod1e97;
const int maxn2e550;
const ll inf1e17;
typedef unsigned long long ull;
int l[maxn],r[maxn];
int main()
{int n;scanf(%d,n);for(int i1;in;i)scanf(%d%d,l[i],r[i]);int k;scanf(%d,k);int numn1;for(int i1;in;i){if(kr[i])continue;else{numi;break;}}coutn-num1endl;return 0;
} B - Nastya Is Playing Computer Games (模拟) 题意 一排井盖井盖下面有金币你需要拿走所有金币拿走井盖下的金币需要井盖上没有石头 一开始井盖上面都有一个石头。 每一秒你可以进行以下一种操作 1向左走或者向右走 2把一个石头扔到其他任意一个井盖上面 3取走金币 现在给你起始位置和井盖个数 问你把所有金币取走需要多少步 思路 很明显的一个贪心策略可以把所有石头都扔到一个不需要的井盖上面 但是第一个扔的还需要再扔回去 然后因为可能要会出生在中间点所以可以贪心的选择先向左还是向右走 首先 扔石头肯定需要扔n1次 金币也需要捡n次走路也需要走n-1次 然后就是重复走的距离min(n-k,k-1) #includebits/stdc.h
using namespace std;
typedef long long ll;
const ll mod1e97;
const int maxn2e550;
const ll inf1e17;
typedef unsigned long long ull;int main()
{int n,k;scanf(%d%d,n,k);if(n1||nk)printf(%d\n,n*3);else{int sum3*n;summin((k-1),(n-k));printf(%d\n,sum);}return 0;
} C - Nastya Is Transposing Matrices (神奇) 题意 矩阵a和b 每次可以把a的一个子矩阵按照左对角线翻转问你能否使a变成b 思路 一开始题目的反转理解错了没想到 后来发现 如果对于一个2*2的矩阵一次反转就相当于把左下和右上对调。所以只需要保证这一条线的值都相同就肯定可以通过反转变成B #includebits/stdc.h
using namespace std;
typedef long long ll;
const ll mod1e97;
const int maxn2e550;
const ll inf1e17;
typedef unsigned long long ull;
vectorintv1[500*5005];
vectorintv2[500*5005];
int main()
{int n,m;scanf(%d%d,n,m);for(int i1;in;i){for(int j1;jm;j){int a;scanf(%d,a);v1[ij].push_back(a);}}for(int i1;in;i){for(int j1;jm;j){int a;scanf(%d,a);v2[ij].push_back(a);}}for(int i1;inm;i){sort(v1[i].begin(),v1[i].end());sort(v2[i].begin(),v2[i].end());if(v1[i]!v2[i])puts(NO),exit(0);}puts(YES);return 0;
} D - Nastya Is Buying Lunch (贪心) 题意 给出一个1-n的数列然后给你m个关系 如果前面的数正好在后面的数前面一个位置那么就可以把这两个数交换位置 问你最多可以让最后一个数(a[n])向前走多少步 思路 首先我们可以把点分成两类。 1可以让n和她交换位置 2不可以让n和她交换位置 那么题目就是让n最后能有多少个连续的1类点 所以我们考虑贪心能不能把经可能多的一类点向后移动 #includebits/stdc.h
using namespace std;
typedef long long ll;
const ll mod1e97;
const int maxn6e550;
const ll inf1e17;
typedef unsigned long long ull;int a[maxn];
mapint,intmp[maxn];
int vis[maxn];
int main()
{int n,m;scanf(%d%d,n,m);for(int i1;in;i){scanf(%d,a[i]);}for(int i1;im;i){int u,v;scanf(%d%d,u,v);mp[u][v]1;if(va[n])vis[u]1;}for(int in-1;i1;i--){if(vis[a[i]]){for(int ji1;jn;j){if(mp[a[j-1]].find(a[j])!mp[a[j-1]].end()){swap(a[j],a[j-1]);}else break;}}}int ans0;for(int in-1;i1;i--){if(vis[a[i]])ans;else break;}printf(%d\n,ans);return 0;
} E - Nastya Hasnt Written a Legend 线段树 题意 给你两个序列 \(a_1,a_2\dots a_n\) 和 $ k_1,k_2,\dots k_{n-1}\(,输入保证\) a_{i}k_{i}a_{i-1}$. 两种操作: 1区间求$ \sum_{il}^{r}a_i$ 2给单点$ a_i\(加\)x$ 同时会有连锁反应若\(a_pk_pa_{p1}\),则\(a_{p1}\) 更新为$ a_pk_p$ 同理更新到\(a_p2\) 知道不能更新 思路 来自群友的做法 感谢这位巨佬 首先根据题意会发现一个式子\[ a_1\leq a_2-k_1\leq a3-k_2-k_2 \dots \leq a_n-\sum_{i1}^{n-1}k_i \] 给\(p\)位置加上值\(x\) 之后,\(a_p-\sum_{i1}^{p-1}k_i\)也增加了x。更新之前已知\(a_p-\sum_{i1}^{p-1}k_i\leq a_{p1}-\sum_{i1}^{p}k_i\) 如果\(a_pk_px a_{p1}\) 那么\(a_{p1}a_pk_px\) 并且\(a_{p1}-\sum_{i1}^{p}k_ia_p-\sum_{i1}^{p}k_ix\) $a_{p2} $同理 最后 我们令\(b_xa_x-\sum_{i1}^{x-1}k_i\),我们给\(p\)单点加上\(x\)之后的效果就是把\(i\in[p1,n]\) 内所有小于\(b_px\)的值赋值为\(b_px\) 所有修改我们已经搞定了用线段树或者其他数据结构维护就可以了求和就是\(\sum_{il}^{r}b_i\sum_{il}^{r}\sum_{j1}^{i-1}k_j\) 更新就是区间赋值了因为\(b_x\) 满足单调不减性所以直接二分查找右端点 #includebits/stdc.h
using namespace std;
typedef long long ll;
const ll mod1e97;
const int maxn2e550;
const ll inf1e17;
typedef unsigned long long ull;int n,m;
ll a[maxn],k[maxn],ks[maxn];
struct SegTree{ll sum[maxn2],flag[maxn2];void build(int o,int l,int r){flag[o]inf;if(lr){sum[o]a[l]-k[l-1];return;}int mid(lr)/2;build(o1,l,mid);build(o1|1,mid1,r);sum[o]sum[o1]sum[o1|1];}void push_down(int o,int l,int r){if(flag[o]inf)return;int mid(lr)/2;flag[o1]flag[o1|1]flag[o];sum[o1]flag[o]*(mid-l1);sum[o1|1]flag[o]*(r-mid);flag[o]inf;}void update(int o,int l,int r,int ql,int qr,ll v){if(qllrqr){flag[o]v;sum[o]v*(r-l1);return;}int mid(lr)/2;push_down(o,l,r);if(qlmid)update(o1,l,mid,ql,qr,v);if(qrmid)update(o1|1,mid1,r,ql,qr,v);sum[o]sum[o1]sum[o1|1];}ll query(int o,int l,int r,int ql,int qr){if(qllrqr)return sum[o];int mid(lr)/2;push_down(o,l,r);ll res0;if(qlmid)resquery(o1,l,mid,ql,qr);if(qrmid)resquery(o1|1,mid1,r,ql,qr);return res;}
}segtree;
int main()
{scanf(%d,n);for(int i1;in;i)scanf(%lld,a[i]);for(int i1;in;i)scanf(%lld,k[i]);for(int i2;in;i)k[i]k[i-1];for(int i1;in;i)ks[i]ks[i-1]k[i];segtree.build(1,1,n);scanf(%d,m);while(m--){char op[5];int l,r;scanf(%s%d%d,op,l,r);if(op[0]s)printf(%lld\n,segtree.query(1,1,n,l,r)ks[r-1]-(l2?ks[l-2]:0));else{int Ll,Rn,mid,ansl;ll sumsegtree.query(1,1,n,l,l)r;// coutsumsumendl;while(LR){mid(LR)/2;// coutmidmidendl;if(sumsegtree.query(1,1,n,mid,mid)){ansmid;Lmid1;}elseRmid-1;}// coutansansendl;segtree.update(1,1,n,l,ans,sum);}}return 0;
} 转载于:https://www.cnblogs.com/luowentao/p/10520658.html
