2020/8/21 晚上打完球就22:10了，愣是沒(méi)報(bào)上名（cf打不開，然后就做了一下賽后交的過(guò)了3個(gè)題

A - Distance and Axis

數(shù)學(xué)題分類討論一下即可

#define IO ios::sync_with_stdio(false);cin.tie();cout.tie(0) #pragma GCC optimize(2) #include<iostream> #include<algorithm> 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<<res<<endl;}return 0; }

B - Ternary Sequence

貪心，先讓第一個(gè)序列的2找第二個(gè)序列的1配對(duì)（加分）， 然后看看第一個(gè)序列的1先找第二個(gè)序列的0和1配對(duì)（分?jǐn)?shù)不變），最后找第二個(gè)序列2配對(duì)（減分）

#define IO ios::sync_with_stdio(false);cin.tie();cout.tie(0) #pragma GCC optimize(2) #include<iostream> #include<algorithm> using namespace std; typedef long long ll; typedef pair<int,int> 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<<res<<endl;}return 0; }

C - Mere Array

這題是個(gè)腦筋急轉(zhuǎn)彎。首先先找到數(shù)組中最小的數(shù)mina如果想要交換兩個(gè)數(shù)，那么兩個(gè)數(shù)的最大公因數(shù)必須是mina，然后可以先把原數(shù)組排序不妨記作數(shù)組b[]，如果a[i]!=b[i]說(shuō)明原數(shù)組中該位置的值需要交換位置，那么這個(gè)數(shù)必須是mina的倍數(shù)，并且只要是這個(gè)數(shù)的倍數(shù)就一定能交換（我們可以考慮讓它和mina所在位置交換）。因此只要位置不正確的數(shù)全都是mina的倍數(shù)就可以滿足題意。

#define IO ios::sync_with_stdio(false);cin.tie();cout.tie(0) #pragma GCC optimize(2) #include<iostream> #include<algorithm> using namespace std; typedef long long ll; typedef pair<int,int> 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"<<endl;else cout<<"NO"<<endl;}return 0; }

D - Maximum Distributed Tree

貪心：可以考慮統(tǒng)計(jì)每條邊通過(guò)的次數(shù)，然后通過(guò)次數(shù)多的分配邊權(quán)最大。
如何統(tǒng)計(jì)每條邊通過(guò)次數(shù)？
考慮樹中的一條邊，如果將該邊去掉將會(huì)分成兩部分，可以統(tǒng)計(jì)該兩部分的點(diǎn)的數(shù)量，該邊的通過(guò)次數(shù)即兩部分相乘一部分點(diǎn)數(shù)為sz那么另一部分即為n-sz那么該邊通過(guò)次數(shù)即sz*(n-sz)。跑一個(gè)dfs即可統(tǒng)計(jì)出來(lái)。
目前有n-1條邊待分配邊權(quán)，有m個(gè)邊權(quán)值，如果m>n-1，把前幾個(gè)大數(shù)乘起來(lái)（保證所有邊權(quán)乘起來(lái)等于k）分配給經(jīng)過(guò)邊數(shù)最多的那條邊。如果m==n-1那么就一個(gè)邊一個(gè)數(shù)貪心經(jīng)過(guò)次數(shù)多的邊權(quán)重大。如果m<n-1最后幾條邊權(quán)重是1。
（之前沒(méi)考慮m>n-1這種情況wwwsTO）

#define IO ios::sync_with_stdio(false);cin.tie();cout.tie(0) #pragma GCC optimize(2) #include<vector> #include<iostream> #include<algorithm> using namespace std; typedef long long ll; typedef pair<int,int> pii; const int mod=1e9+7; const int N=100010,M=2*N; int n,m; int h[N],e[M],ne[M],idx; vector<ll>w; 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<n;i++){int a,b;cin>>a>>b;add(a,b);add(b,a);}cin>>m;for(int i=0;i<m;i++) cin>>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<m;i++) res=(res+1ll*(w[i]%mod*p[i]%mod))%mod;for(int i=m;i<w.size();i++) res=(res+w[i])%mod;}else{int k=m-w.size();res=w[0]%mod;for(int i=0;i<=k;i++) res=res*p[i]%mod;for(int i=k+1;i<m;i++) res=(res+w[i-k]%mod*p[i]%mod)%mod;}cout<<res<<endl;}return 0; }

F-Reverse and Swap

F題Reverse and Swap
留個(gè)坑，回來(lái)補(bǔ)這題數(shù)據(jù)結(jié)構(gòu)
2020/8/23補(bǔ)
方法一：
首先這題單點(diǎn)修改，區(qū)間查詢無(wú)疑線段樹可以做。
考慮如何進(jìn)行區(qū)間交換？
由于數(shù)組線段樹固定做兒子和右兒子的下標(biāo)父節(jié)點(diǎn) u 左孩子u<<1 右孩子u<<1|1，傳統(tǒng)方式不宜進(jìn)行區(qū)間交換，因此采用指針?lè)绞接涗涀笥液⒆?#xff08;主席樹方式）那么區(qū)間交換直接交換左右孩子即可，而區(qū)間反轉(zhuǎn)則是遞歸交換左右子樹直到葉子節(jié)點(diǎn)。
嘗試用懶標(biāo)極維護(hù)區(qū)間操作：lazy看成一個(gè)二進(jìn)制數(shù)（狀態(tài)壓縮），對(duì)于一個(gè)節(jié)點(diǎn)如果lazy^id!=0說(shuō)明id中的1所在的位置lazy中也是1那么表示需要該節(jié)點(diǎn)的左右子樹。
于是區(qū)間反轉(zhuǎn)則是在根節(jié)點(diǎn)直接打上標(biāo)記tree[root].lazy^=(1<<(k+1))-1;
區(qū)間交換則tree[root].lazy^=1<<(k+1);
參考大佬題解

// [1 2 3 4 5 6 7 8] 1000 id:3 // [1 2 3 4] [5 6 7 8] 0100 id:2 // [1 2] [3 4] [5 6] [7 8] 0010 id:1 // [1][2][3][4][5][6][7][8] 0001 id:0 #define IO ios::sync_with_stdio(false);cin.tie();cout.tie(0) #pragma GCC optimize(2) #include<vector> #include<set> #include<map> #include<string> #include<cstring> #include<iostream> #include<algorithm> using namespace std; typedef long long ll; typedef pair<int,int> 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<<n;i++) cin>>a[i];build(root,1,1<<n);while(q--){int op,x,y;cin>>op;if(op==1){cin>>x>>y;modify(root,1,1<<n,x,y);}else if(op==2){cin>>x;rev(x);}else if(op==3){cin>>x;swp(x);}else {cin>>x>>y;cout<<query(root,1,1<<n,x,y)<<endl;}}return 0; }

看standing發(fā)現(xiàn)了一個(gè)神奇的做法自己寫一下
方法二：
把線段樹看成一層一層的，可以發(fā)現(xiàn)反轉(zhuǎn)和交換操作都是在同層進(jìn)行，因此可以以層數(shù)記錄lazy，方法一是用swap操作實(shí)現(xiàn)reverse操作，同樣其實(shí)也可以用reverse操作實(shí)現(xiàn)swap：可以先把上一層每個(gè)區(qū)間進(jìn)行reverse然后把該層的每個(gè)區(qū)間再reverse實(shí)際上實(shí)現(xiàn)的就是swap操作。
之前說(shuō)過(guò)傳統(tǒng)線段樹不宜進(jìn)行區(qū)間反轉(zhuǎn)等操作，這個(gè)方法秒在不進(jìn)行區(qū)間反轉(zhuǎn)操作，只記錄每層的區(qū)間是否需要進(jìn)行反轉(zhuǎn)，僅僅在查詢和更改時(shí)候進(jìn)行相應(yīng)的坐標(biāo)變化即可。

// [1 2 3 4 5 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 // 區(qū)間交換 level=2 只需要先反轉(zhuǎn)level=3 然后再反轉(zhuǎn)level=2即可 #define IO ios::sync_with_stdio(false);cin.tie();cout.tie(0) #pragma GCC optimize(2) #include<vector> #include<set> #include<map> #include<string> #include<cstring> #include<iostream> #include<algorithm> using namespace std; typedef long long ll; typedef pair<int,int> 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<<n;i++) cin>>a[i];build(1,1,1<<n,n);while(q--){int op,x,y;cin>>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<<query(1,x,y)<<endl;}}return 0; }

要加油哦~

總結(jié)

以上是生活随笔為你收集整理的Codeforces Round #665 (Div. 2)的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。