Codeforces Round #665 (Div. 2) 题解
写得有点晚了，估计都官方题解看完切掉了，没人看我的了qaq。
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;
}