Codeforces Round #665 (Div. 2) 題解
寫得有點晚了，估計都官方題解看完切掉了，沒人看我的了qaq，
目錄
- Codeforces Round #665 (Div. 2) 題解
- A - Distance and Axis
- B - Ternary Sequence
- C - Mere Array
- D - Maximum Distributed Tree
- E - Divide Square
- F - Reverse and Swap
A - Distance and Axis
現在有整數\(n\)，問你執行多少次對\(n\)加一/減一的操作后能有整數\(m\)且\(||n-m|-m|=k\)，
首先，假如\(n\leq k\)，那么把\(n\)變成\(k\)就能滿足條件，然后我們考慮\(n>k\)：假如限定\(0\leq m\leq n\)且\(m\leq n-m\)，得到了\(m=\frac{n-k}2\)，那么只要保證\(n-k\)是偶數就好了，操作一次即可，
程式如下：
#include<bits/stdc++.h>
using namespace std;
int t,n,k;
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin>>t;
while(t--){
cin>>n>>k;
if(n<=k){
cout<<k-n<<'\n';
}else{
cout<<(n-k&1)<<'\n';
}
}
return 0;
}
B - Ternary Sequence
不難看出，只有從\(a\)中取出\(2\)和\(b\)中取出的\(1\)配對時，貢獻為\(2\)；從\(a\)中取出\(1\)和\(b\)中取出的\(2\)配對時，貢獻為\(-2\)，那么我們肯定要最大化第一種情況出現的次數，最小化第二種情況的出現次數，那么先把\(a\)中的\(2\)和\(b\)中的\(1\)配對，然后盡量的使用\(a\)中的\(2\)和\(0\)去匹配\(b\)中的\(2\)即可，可以證明這樣得到的是最優的，
雖然我不會證明但是還是來感性理解一下：
假如把\(a\)中的\(2\)，\(b\)中的\(1\)這樣的匹配拆散，用\(a\)中的\(2\)去匹配\(b\)中的\(2\)，那么答案不變，假如去匹配\(b\)中的其他數，那么結果會更差，其余的都差不多，偷個懶不寫了（
程式如下：
#include<bits/stdc++.h>
using namespace std;
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int T,x1,y1,z1,x2,y2,z2;
cin>>T;
while(T--){
cin>>x1>>y1>>z1>>x2>>y2>>z2;
int ans=0,tmp;
tmp=min(z1,y2);
z1-=tmp;
y2-=tmp;
ans+=tmp*2;
tmp=min(z1,z2);
z1-=tmp;
z2-=tmp;
tmp=min(x1,z2);
x1-=tmp;
z2-=tmp;
tmp=min(y1,z2);
ans-=tmp*2;
cout<<ans<<'\n';
}
return 0;
}
C - Mere Array
為了敘述方便，我們記最小的元素為\(m\)，
我們先來看是\(m\)倍數的元素，可以證明它們之間一定可以互換位置，也只有它們可以互換位置，
證明只有它們可以互換位置很簡單，不是\(m\)倍數的元素，和其他的元素求最大公因數肯定不等于\(m\)，
它們之間一定可以互換位置，是因為假如我們使用\(m\)作為中轉，就可以間接地交換它們，
由于一個有序的序列，子序列一定有序，所以我們就屏蔽不是\(m\)倍數的元素，把剩下的元素排序，再檢查是否為有序序列即可，
程式如下：
#include<bits/stdc++.h>
using namespace std;
int n,a[100005],mn;
bool mark[100005];
void mian(){
cin>>n;
for(int i=1;i<=n;i++){
cin>>a[i];
}
mn=*min_element(a+1,a+1+n);
vector<int> v;
for(int i=1;i<=n;i++){
if(a[i]%mn==0){
v.emplace_back(a[i]);
}
mark[i]=a[i]%mn==0;
}
sort(v.begin(),v.end());
bool f=true;
for(int i=1,j=0;i<=n;i++){
if(mark[i]){
a[i]=v[j++];
}
assert(j<=v.size());
f&=a[i]>=a[i-1];
}
cout<<(f?"YES\n":"NO\n");
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int T;
cin>>T;
while(T--){
mian();
}
return 0;
}
D - Maximum Distributed Tree
首先，反過來考慮，考慮每條邊對于答案的貢獻，每條邊經過的次數越多，那么就需要配上一個更大的權值，
計算邊經過的次數：我們欽點一個根出來，不難發現，一個結點連向它父親的邊，假如有一條路徑經過這條邊，那么一定路徑的一端在子樹內，一端在子樹外，這個我們DFS處理子樹大小就可以計算了，
如何分配權值：首先由于要使得權值中\(1\)的出現次數最小，那么就需要盡量的給每個邊都分出一個\(k\)的因子，假如因子少了，那么只能補充\(1\)，假如因子多了，那么就取最大的一部分因子分配給經過次數最多的邊，其余的小的因子再分配給其他邊，這樣就能保證結果最優，
程式如下，需要注意先sort后取模：
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod=1e9+7;
int n,m;
vector<int> g[100005];
int sz[100005];
vector<ll> e,p;
void dfs(const int &x,const int &p){
sz[x]=1;
for(int &y:g[x])if(y!=p){
dfs(y,x);
sz[x]+=sz[y];
}
if(x!=1){
e.emplace_back((ll)sz[x]*(n-sz[x]));
}
}
void mian(){
cin>>n;
for(int i=1;i<=n;i++){
g[i].clear();
}
for(int i=1;i<n;i++){
static int u,v;
cin>>u>>v;
g[u].emplace_back(v);
g[v].emplace_back(u);
}
e.clear();
dfs(1,-1);
sort(e.begin(),e.end());
reverse(e.begin(),e.end());
for(ll &x:e)x%=mod;
cin>>m;
p.resize(m);
for(int i=0;i<m;i++){
cin>>p[i];
}
sort(p.begin(),p.end());
if(m>n-1){
for(int i=m-2;i>=n-2;i--){
p[i]=p[i]*p[i+1]%mod;
}
p.resize(n-1);
}
reverse(p.begin(),p.end());
while(p.size()<n-1)p.emplace_back(1);
ll ans=0;
for(int i=0;i+1<n;i++){
ans=(ans+e[i]*p[i])%mod;
}
cout<<ans<<'\n';
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int T;
cin>>T;
while(T--){
mian();
}
return 0;
}
E - Divide Square
注意到有兩個限制條件：線段肯定和一條正方形的邊相交、沒有線段在一條直線上，
不難看出（雖然我賽時沒看出），一個和正方形的兩條對邊都相交的線段，會使得答案加一，兩條相交的線段，也會使得答案加一，那么我們就需要計算這些東西了，
和正方形的兩條對邊都相交的線段，可以在讀入時就判斷好，
兩條相交的線段，肯定是橫向的和豎向的相交，這里我們假設有一條橫向的，從下往上移動的掃描線，同時使用樹狀陣列維護，掃描線上每個位置是否有豎向線段與其交叉，那么橫向的線段要計算交叉的豎向線段數，只需要做一次區間和就好，我們離線輸入資料，在豎向線段的底端所在的位置，加入它，在頂端刪去它，就可以維護掃描線上交叉的豎向線段了，
程式如下：
#include<bits/stdc++.h>
using namespace std;
const int bound=1e6+1;
int bit[bound+5];
int sum(int pos){
int res=0;
while(pos>0){
res+=bit[pos];
pos-=pos&-pos;
}
return res;
}
void add(int pos,int val){
while(pos<=bound){
bit[pos]+=val;
pos+=pos&-pos;
}
}
int n,m;
long long ans=1;
vector<pair<int,int>> qs[bound+5];
vector<int> seg[bound+5];
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin>>n>>m;
for(int i=1;i<=n;i++){
int y,l,r;
cin>>y>>l>>r;
y++;l++;r++;
qs[y].emplace_back(l,r);
ans+=l==1&&r==bound;
}
for(int i=1;i<=m;i++){
int x,d,u;
cin>>x>>d>>u;
x++;d++;u++;
seg[d].emplace_back(x);
seg[u+1].emplace_back(-x);
ans+=d==1&&u==bound;
}
for(int y=1;y<=bound;y++){
for(int &x:seg[y])add(abs(x),x/abs(x));
for(pair<int,int> &p:qs[y])ans+=sum(p.second)-sum(p.first-1);
}
cout<<ans<<endl;
return 0;
}
F - Reverse and Swap
裸的資料結構題，最喜歡了?~
不難看出，我們需要線段樹，那么剩下的就是考慮怎么維護了，單點修改和區間求和我就偷懶不講了嗷，萬能的OI Wiki都有，接下來需要用到區間修改的懶標記思想，所以不會的還是要去看OI Wiki，
我們先來處理\(Swap\)操作：把整個序列分成若干個長度為\(2^k\)的區間，假如這些區間編號為\(1,2,3,\dots\)，那么我們交換\(1\)和\(2\)，\(3\)和\(4\)，以此類推，由于線段樹奇妙的結構，對\(2^k\)長的區間進行交換操作，實際上就是對于每個\(2^{k+1}\)的區間，交換它的左右兒子，那么我們只要存一個懶標記就可以了，這里需要記錄各種長度的區間是否要交換，那么我們把它壓進一個int里維護即可，
然后，我們來把\(Reverse\)變成\(Swap\)，\(Reverse\)就是區間把\(2^k\)的區間進行\(Reverse\)操作，實際上相當于對于長度\(2^{k-1},2^{k-2},\dots,2^{1},2^{0}\)的區間執行\(Swap\)操作，好了我們不用實作它了，
程式如下：
#include<bits/stdc++.h>
using namespace std;
struct SegTree{
typedef long long ll;
struct node{
node *l,*r;
ll val;
int len,swp;
node(){
l=r=nullptr;
val=len=swp=0;
}
void pushdown(){
if(swp&len>>1){
node tmp=*r;
*r=*l;
*l=tmp;
swp^=len>>1;
}
l->swp^=swp;
r->swp^=swp;
swp=0;
}
void pullup(){
val=l->val+r->val;
}
};
int sz;
node *root;
void build(node *id,const int &l,const int &r,const vector<int> &a){
id->len=r-l+1;
if(l==r){
id->val=a[l-1];
return;
}
id->l=new node;
id->r=new node;
build(id->l,l,l+r>>1,a);
build(id->r,(l+r>>1)+1,r,a);
id->pullup();
}
SegTree(const int &n,const vector<int> &a){
sz=1<<n;
root=new node;
build(root,1,sz,a);
}
void upd(node *id,const int &l,const int &r,const int &pos,const int &val){
if(pos<l||r<pos)return;
if(pos<=l&&r<=pos){
id->val=val;
return;
}
id->pushdown();
upd(id->l,l,l+r>>1,pos,val);
upd(id->r,(l+r>>1)+1,r,pos,val);
id->pullup();
}
void upd(const int &pos,const int &val){
upd(root,1,sz,pos,val);
}
ll qry(node *id,const int &l,const int &r,const int &ql,const int &qr){
if(qr<l||r<ql)return 0;
if(ql<=l&&r<=qr){
return id->val;
}
id->pushdown();
return qry(id->l,l,l+r>>1,ql,qr)+qry(id->r,(l+r>>1)+1,r,ql,qr);
}
ll qry(const int &l,const int &r){
return qry(root,1,sz,l,r);
}
void reverse(const int &k){
root->swp^=(1<<k)-1;
}
void swap(const int &k){
root->swp^=1<<k;
}
};
int n,q;
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin>>n>>q;
vector<int> a(1<<n);
for(int i=0;i<1<<n;i++){
cin>>a[i];
}
SegTree t(n,a);
while(q--){
int typ,x,y;
cin>>typ>>x;
if(typ==1){
cin>>y;
t.upd(x,y);
}else
if(typ==2){
t.reverse(x);
}else
if(typ==3){
t.swap(x);
}else
if(typ==4){
cin>>y;
cout<<t.qry(x,y)<<'\n';
}
}
return 0;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/2205.html
標籤：其他
上一篇：資料結構與演算法系列2 線性表
下一篇：An approach to implement basic calculator with RPN and stack