锐客网

  1. 首页 > it技术 > >

Codeforces Round #665 (Div. 2)

codeforces

【Codeforces Round #665 (Div. 2)】2020/8/21 晚上打完球就22:10了，愣是没报上名（cf打不开，然后就做了一下赛后交的过了3个题
A - Distance and Axis
数学题分类讨论一下即可

#define IO ios::sync_with_stdio(false); cin.tie(); cout.tie(0) #pragma GCC optimize(2) #include #include using namespace std; int n,k; int main() { IO; int T; cin>>T; while(T--) { cin>>n>>k; int res=0; if(k>n) { res+=k-n; } else { if(k%2!=n%2) res++; } cout<

B - Ternary Sequence
贪心，先让第一个序列的2找第二个序列的1配对（加分）， 然后看看第一个序列的1先找第二个序列的0和1配对（分数不变），最后找第二个序列2配对（减分）
#define IO ios::sync_with_stdio(false); cin.tie(); cout.tie(0) #pragma GCC optimize(2) #include #include using namespace std; typedef long long ll; typedef pair pii; ll x,y,z; ll a,b,c; int main() { IO; int T; cin>>T; while(T--) { cin>>x>>y>>z; cin>>a>>b>>c; ll res=0; res+=2*min(z,b); y-=a; y-=b-min(z,b); if(y>0) res-=2*y; cout<

C - Mere Array
这题是个脑筋急转弯。首先先找到数组中最小的数mina如果想要交换两个数，那么两个数的最大公因数必须是mina，然后可以先把原数组排序不妨记作数组b[]，如果a[i]!=b[i]说明原数组中该位置的值需要交换位置，那么这个数必须是mina的倍数，并且只要是这个数的倍数就一定能交换（我们可以考虑让它和mina所在位置交换）。因此只要位置不正确的数全都是mina的倍数就可以满足题意。
#define IO ios::sync_with_stdio(false); cin.tie(); cout.tie(0) #pragma GCC optimize(2) #include #include using namespace std; typedef long long ll; typedef pair pii; const int N=200010; int a[N],b[N]; int n; int main() { IO; int T; cin>>T; while(T--) { cin>>n; int mina=1e9+1; for(int i=1; i<=n; i++) { cin>>a[i]; b[i]=a[i]; mina=min(mina,a[i]); } sort(b+1,b+1+n); bool ok=1; for(int i=1; i<=n; i++) if(a[i]!=b[i]&&a[i]%mina!=0) { ok=0; break; } if(ok) cout<<"YES"<

D - Maximum Distributed Tree
贪心：可以考虑统计每条边通过的次数，然后通过次数多的分配边权最大。
如何统计每条边通过次数？
考虑树中的一条边，如果将该边去掉将会分成两部分，可以统计该两部分的点的数量，该边的通过次数即两部分相乘一部分点数为sz那么另一部分即为n-sz那么该边通过次数即sz*(n-sz)。跑一个dfs即可统计出来。
目前有n-1条边待分配边权，有m个边权值，如果m>n-1，把前几个大数乘起来（保证所有边权乘起来等于k）分配给经过边数最多的那条边。如果m==n-1那么就一个边一个数贪心经过次数多的边权重大。如果m最后几条边权重是1。
（之前没考虑m>n-1这种情况wwwsTO）
#define IO ios::sync_with_stdio(false); cin.tie(); cout.tie(0) #pragma GCC optimize(2) #include #include #include using namespace std; typedef long long ll; typedef pair pii; const int mod=1e9+7; const int N=100010,M=2*N; int n,m; int h[N],e[M],ne[M],idx; vectorw; ll sz[N],p[N]; void add(int a,int b) { e[idx]=b; ne[idx]=h[a]; h[a]=idx++; } void dfs(int u,int fa) { sz[u]=1; for(int i=h[u]; i!=-1; i=ne[i]) { int j=e[i]; if(j==fa) continue; dfs(j,u); sz[u]+=sz[j]; w.push_back(1ll*sz[j]*(n-sz[j])); } } void init(int n) { for(int i=0; i<=n; i++) h[i]=-1; w.clear(); idx=0; } int main() { IO; int T; cin>>T; while(T--) { cin>>n; init(n); for(int i=1; i>a>>b; add(a,b); add(b,a); } cin>>m; for(int i=0; i>p[i]; sort(p,p+m); reverse(p,p+m); dfs(1,-1); sort(w.begin(),w.end()); reverse(w.begin(),w.end()); ll res=0; if(m<=w.size()) { for(int i=0; i

F-Reverse and Swap
F题Reverse and Swap
留个坑，回来补这题数据结构
2020/8/23补
方法一：
首先这题单点修改，区间查询无疑线段树可以做。
考虑如何进行区间交换？
由于数组线段树固定做儿子和右儿子的下标父节点 u 左孩子u<<1 右孩子u<<1|1，传统方式不宜进行区间交换，因此采用指针方式记录左右孩子（主席树方式）那么区间交换直接交换左右孩子即可，而区间反转则是递归交换左右子树直到叶子节点。
尝试用懒标极维护区间操作：lazy看成一个二进制数（状态压缩），对于一个节点如果lazy^id!=0说明id中的1所在的位置lazy中也是1那么表示需要该节点的左右子树。
于是区间反转则是在根节点直接打上标记tree[root].lazy^=(1<<(k+1))-1;
区间交换则tree[root].lazy^=1<<(k+1);
参考大佬题解
// [1 2 3 45 6 7 8]1000id:3 // [1 2 3 4][5 6 7 8]0100id:2 // [1 2] [3 4][5 6] [7 8]0010id:1 // [1][2][3][4][5][6][7][8]0001id:0 #define IO ios::sync_with_stdio(false); cin.tie(); cout.tie(0) #pragma GCC optimize(2) #include #include #include #include #include #include #include using namespace std; typedef long long ll; typedef pair pii; const int N=(1<<18)+10; int n,q; ll a[N]; struct node { int l,r; ll s; int id,lazy; }tree[40*N]; int cnt,root; void pushup(int u) { tree[u].s=tree[tree[u].l].s+tree[tree[u].r].s; } void pushdown(int u) { if(tree[u].id&tree[u].lazy) { swap(tree[u].l,tree[u].r); tree[u].lazy^=tree[u].id; } tree[tree[u].l].lazy^=tree[u].lazy; tree[tree[u].r].lazy^=tree[u].lazy; tree[u].lazy=0; } void build(int &u,int l,int r) { u=++cnt; tree[u].id=r-l+1; tree[u].lazy=0; if(l==r) { tree[u].s=a[l]; return; } int mid=l+r>>1; build(tree[u].l,l,mid); build(tree[u].r,mid+1,r); pushup(u); } void modify(int u,int l,int r,int pos,int x) { if(l==r) { tree[u].s=x; return; } pushdown(u); int mid=l+r>>1; if(pos<=mid) modify(tree[u].l,l,mid,pos,x); else modify(tree[u].r,mid+1,r,pos,x); pushup(u); } ll query(int u,int l,int r,int vl,int vr) { if(vl<=l&&r<=vr) return tree[u].s; pushdown(u); int mid=l+r>>1; ll v=0; if(vl<=mid) v+=query(tree[u].l,l,mid,vl,vr); if(vr>mid) v+=query(tree[u].r,mid+1,r,vl,vr); pushup(u); return v; } void rev(int k) { tree[root].lazy^=(1<<(k+1))-1; if(tree[root].id&tree[root].lazy) { swap(tree[root].l,tree[root].r); tree[root].lazy^=tree[root].id; } } void swp(int k) { tree[root].lazy^=1<<(k+1); if(tree[root].id&tree[root].lazy) { swap(tree[root].l,tree[root].r); tree[root].lazy^=tree[root].id; } } int main() { IO; cin>>n>>q; for(int i=1; i<=1<>a[i]; build(root,1,1<>op; if(op==1) { cin>>x>>y; modify(root,1,1<>x; rev(x); } else if(op==3) { cin>>x; swp(x); } else { cin>>x>>y; cout<

看standing发现了一个神奇的做法自己写一下
方法二：
把线段树看成一层一层的，可以发现反转和交换操作都是在同层进行，因此可以以层数记录lazy，方法一是用swap操作实现reverse操作，同样其实也可以用reverse操作实现swap：可以先把上一层每个区间进行reverse然后把该层的每个区间再reverse实际上实现的就是swap操作。
之前说过传统线段树不宜进行区间反转等操作，这个方法秒在不进行区间反转操作，只记录每层的区间是否需要进行反转，仅仅在查询和更改时候进行相应的坐标变化即可。
// [1 2 3 45 6 7 8]level:3 // [1 2 3 4][5 6 7 8]level:2 // [1 2] [3 4][5 6] [7 8]level:1 // [1][2][3][4][5][6][7][8]level:0 // 区间交换 level=2 只需要先反转level=3 然后再反转level=2即可 #define IO ios::sync_with_stdio(false); cin.tie(); cout.tie(0) #pragma GCC optimize(2) #include #include #include #include #include #include #include using namespace std; typedef long long ll; typedef pair pii; const int N=(1<<18)+10; int n,q; int b[20]; ll a[N]; struct node { int l,r,level; ll val; }tree[4*N]; void pushup(int u) { tree[u].val=tree[u<<1].val+tree[u<<1|1].val; } void build(int u,int l,int r,int level) { tree[u]={l,r,level}; if(l==r) { tree[u].val=a[l]; return; } int mid=l+r>>1; build(u<<1,l,mid,level-1); build(u<<1|1,mid+1,r,level-1); pushup(u); } void modify(int u,int pos,int x) { if(tree[u].l==tree[u].r) { tree[u].val=x; return; } if(b[tree[u].level]) pos=tree[u].r-(pos-tree[u].l); int mid=tree[u].l+tree[u].r>>1; if(pos<=mid) modify(u<<1,pos,x); else modify(u<<1|1,pos,x); pushup(u); } ll query(int u,int l,int r) { if(tree[u].l==l&&r==tree[u].r) return tree[u].val; int lnow=l,rnow=r; if(b[tree[u].level]) { lnow=tree[u].r-(r-tree[u].l); rnow=tree[u].r-(l-tree[u].l); } ll v=0; int mid=tree[u].l+tree[u].r>>1; if(rnow<=mid) v+=query(u<<1,lnow,rnow); else if(lnow>mid) v+=query(u<<1|1,lnow,rnow); else { v+=query(u<<1,lnow,mid); v+=query(u<<1|1,mid+1,rnow); } return v; } int main() { cin>>n>>q; for(int i=1; i<=1<>a[i]; build(1,1,1<>op; if(op==1) { cin>>x>>y; modify(1,x,y); } else if(op==2) { cin>>x; b[x]^=1; } else if(op==3) { cin>>x; b[x]^=1; b[x+1]^=1; } else { cin>>x>>y; cout<

要加油哦~

    推荐阅读


    上一篇：[51nod1227]平均最小公倍数（莫比乌斯反演+杜教筛）

    下一篇：#|51nod1227 平均最小公倍数