Codeforces Round #595 (Div. 3) A-F

写在前面：

个人感觉这场题目不错，~~可能是本人太菜！~~

A. Yet Another Dividing into Teams 题目大意:

分成尽量少的组，使组内任意两个数不相邻（abs>1)。

思路：

可以看出最多分成两组。

Code:

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
//#include 
#define guo312 std::ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
#define ll long long
#define Inf LONG_LONG_MAX
#define inf INT_MAX
#define endl "n"
#define PI 3.1415926535898
using namespace std;
const int N=2e5+10;
int a[N];
bool work(int n){
	for(int i=2;i<=n;i++){
		if(a[i]-a[i-1]==1) return 1;
	}
	return 0;
}

int main(){
guo312;
	int t; cin>>t;
	while(t--){
		int n; cin>>n;
		for(int i=1;i<=n;i++){
			cin>>a[i];
		}
		sort(a+1,a+1+n);
		if(work(n)) cout<<"2n";
		else cout<<"1n";
	}
	return 0;
}

B2. Books Exchange (hard version) 题目大意：

每个人都有一本书和他要传给的人，问每人自己的书再次回到自己时经过的时间。

思路：

传递的过程是一个环，数据保证了环之间是独立的，环上所有人经过的时间是一样的且都是环的大小。

Code:

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
//#include 
#define guo312 std::ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
#define ll long long
#define Inf LONG_LONG_MAX
#define inf INT_MAX
#define endl "n"
#define PI 3.1415926535898
using namespace std;
const int N=2e5+10;
int p[N],ans[N];
int main(){
guo312;
	int t; cin>>t;
	while(t--){
		int n; cin>>n;
		for(int i=1;i<=n;i++){
			cin>>p[i];
		}
		for(int i=1;i<=n;i++){
			if(ans[i]!=0) continue;
			int now=p[i],cnt=1;
			while(now!=i){
				cnt++,now=p[now];
			}
			ans[now]=cnt,now=p[i];
			while(now!=i){
				ans[now]=cnt,now=p[now];
			}
		}
		for(int i=1;i<=n;i++){
			cout< 
C2. Good Numbers (hard version) 
题目大意： 
定义了一个好数是可以写成
    
     
      
       
        3
       
      
      
       3
      
     
    3的
    
     
      
       
        不
       
       
        同
       
       
        次
       
       
        幂
       
      
      
       不同次幂
      
     
    不同次幂 的合，问最小大于等于x的好数。 
思路： 
像分解2进制一样，从高位向地位分解并标记存在的次幂，最后为0那x就是好数。否则，从低位遍历，找到第一个未出现且合大于x的数。（具体看代码） 
Code: 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
//#include 
#define guo312 std::ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
#define ll long long
#define Inf LONG_LONG_MAX
#define inf INT_MAX
#define endl "n"
#define PI 3.1415926535898
using namespace std;
const int N=2e5+10;

ll c[N];
void init(){
	c[0]=1;
	for(int i=1;i<=64;i++){
		c[i]=c[i-1]*3;
		if(c[i]>1e18){
			break;
		}
	}
}

int flag[N];
int main(){
guo312;
	int t; cin>>t; init();
	while(t--){
		ll x; cin>>x; ll num=x,maxn=0;
		for(int i=0;i<=38;i++) flag[i]=0;
		for(int i=37;i>=0;i--){
			if(num>=c[i]){
				maxn=max(maxn,(ll)i);
				flag[i]=1;
				num-=c[i];
			}
		}
		if(num==0){
			cout<
			for(int i=0;i<=38;i++){
				if(flag[i]==0&&c[i]>num){
					cout<
					num+=c[i];
				}
			}
		}
	}
	return 0;
}
 
D2. Too Many Segments (hard version) 
题目大意： 
删除最少的段使最多被覆盖点的次数小于等于k。 
思路： 
最明显的贪心思路是每次删除包含最多坏点的段但，实现麻烦。
 假设当一个点前面的点都合法时，删除的段应该尽量包含右边的点，故把区间排序后用数据结构维护即可。 
Code： 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
//#include 
#define guo312 std::ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
#define ll long long
#define Inf LONG_LONG_MAX
#define inf INT_MAX
#define endl "n"
#define PI 3.1415926535898
using namespace std;
const int N=2e5+10;
struct PW{
	int l,r,lazy,maxn;
}a[N*4];

void pushdown(int id){
	if(a[id].lazy>0){
		a[id<<1].maxn+=a[id].lazy,a[id<<1|1].maxn+=a[id].lazy;
		
		a[id<<1].lazy+=a[id].lazy,a[id<<1|1].lazy+=a[id].lazy;
	}
	a[id].lazy=0;
}

void pushup(PW &s1,PW &s2,PW &s3){
	s3.lazy=0;
	s3.maxn=max(s1.maxn,s2.maxn);
}

void pushup(int id){
	pushup(a[id<<1],a[id<<1|1],a[id]);
}

void build(int id,int l,int r){
	a[id].l=l,a[id].r=r;
	if(l==r){
		a[id].maxn=0;
		a[id].lazy=0;
		return ;
	}
	else{
		int mid=l+r>>1;
		build(id<<1,l,mid),build(id<<1|1,mid+1,r);
		pushup(id);
	}
}

void modify(int id,int l,int r){
	if(a[id].l>=l&&a[id].r<=r){
		a[id].maxn++,a[id].lazy++;
		return ;
	}
	else{
		pushdown(id);
		int mid=a[id].l+a[id].r>>1;
		if(r<=mid) modify(id<<1,l,r);
		else if(l>mid) modify(id<<1|1,l,r);
		else modify(id<<1,l,r),modify(id<<1|1,l,r);
		pushup(id);
	}
}

PW query(int id,int l,int r){
	if(a[id].l>=l&&a[id].r<=r){
		return a[id];
	}
	else{
		pushdown(id);
		int mid=a[id].l+a[id].r>>1;
		if(r<=mid) return query(id<<1,l,r);
		else if(l>mid) return query(id<<1|1,l,r);
		else{
			PW s1=query(id<<1,l,r);
			PW s2=query(id<<1|1,l,r);
			PW s3;
			pushup(s1,s2,s3);
			return s3;
		}
	}
}

struct P{
	int l,r,id;
}b[N];

bool cmp(P s1,P s2){
	if(s1.r==s2.r){
		return s1.l
		return s1.r
guo312;
	int n,k; cin>>n>>k; queue ans;
	for(int i=1;i<=n;i++){
		cin>>b[i].l>>b[i].r; b[i].id=i;
	}
	sort(b+1,b+1+n,cmp);
	build(1,0,2e5+1);
	for(int i=1;i<=n;i++){
		int s=query(1,b[i].l,b[i].r).maxn;
		if(s==k){
			ans.push(b[i].id);
		}
		else{
			modify(1,b[i].l,b[i].r);
		}
	}
	cout<
		int s=ans.front(); cout< 
E. By Elevator or Stairs? 
题目大意： 
有两种上楼模式，问从第一层到每一层的最短时间。 
思路： 
本质上更像是区间的替换，考虑
    
     
      
       
        d
       
       
        p
       
      
      
       dp
      
     
    dp写法
    
     
      
       
        d
       
       
        p
       
       
        [
       
       
        i
       
       
        ]
       
      
      
       dp[i]
      
     
    dp[i]记录的是到
    
     
      
       
        i
       
      
      
       i
      
     
    i层的最段距离，主线段以走楼梯为例，枚举上电梯的层数：状态转移方程就是 
    
     
      
       
        d
       
       
        p
       
       
        [
       
       
        i
       
       
        ]
       
       
        =
       
       
        m
       
       
        i
       
       
        n
       
       
        (
       
       
        d
       
       
        p
       
       
        [
       
       
        i
       
       
        ]
       
       
        ,
       
       
        d
       
       
        p
       
       
        [
       
       
        x
       
       
        −
       
       
        1
       
       
        ]
       
       
        +
       
       
        s
       
       
        u
       
       
        m
       
       
        2
       
       
        [
       
       
        i
       
       
        ]
       
       
        −
       
       
        s
       
       
        u
       
       
        m
       
       
        [
       
       
        x
       
       
        −
       
       
        1
       
       
        ]
       
       
        +
       
       
        c
       
       
        )
       
       
        x
       
       
        >
       
       
        =
       
       
        1
       
       
        ,
       
       
        x
       
       
        <
       
       
        i
       
      
      
       dp[i]=min(dp[i],dp[x-1]+sum2[i]-sum[x-1]+c) x>=1,x=1,x 
Code: 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
//#include 
#define guo312 std::ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
#define ll long long
#define Inf LONG_LONG_MAX
#define inf INT_MAX
#define endl "n"
#define PI 3.1415926535898
using namespace std;
const int N=2e5+10;
ll a[N],b[N],c,n;
ll sum1[N],sum2[N],dp[N];
int main(){
guo312;
	cin>>n>>c; ll last=0;
	for(int i=2;i<=n;i++) cin>>a[i],sum1[i]=sum1[i-1]+a[i];
	for(int i=2;i<=n;i++) cin>>b[i],sum2[i]=sum2[i-1]+b[i];
	if(a[2]
		ll s1=dp[i-1]+a[i];
		ll s2=minn+c+sum2[i];
		ll s3=dp[i-1]+c+b[i];
		dp[i]=min(s1,s2),dp[i]=min(dp[i],s3);
		minn=min(minn,dp[i]-sum2[i]);
	}
	for(int i=1;i<=n;i++){
		cout< 
F. Maximum Weight Subset 
题目大意： 
一颗有点权的树，求一个权值合最大的集合，集合内各点之间的简单路径严格大于k。 
思路： 
题目解法比较多，这里写的是贪心解法。
 考虑选择
    
     
      
       
        x
       
      
      
       x
      
     
    x,将答案累加
    
     
      
       
        v
       
       
        a
       
       
        l
       
       
        [
       
       
        x
       
       
        ]
       
      
      
       val[x]
      
     
    val[x],同时将与
    
     
      
       
        x
       
      
      
       x
      
     
    x距离
    
     
      
       
        <
       
       
        =
       
       
        k
       
      
      
       <=k
      
     
    <=k的所有点的点权减少
    
     
      
       
        v
       
       
        a
       
       
        l
       
       
        [
       
       
        x
       
       
        ]
       
      
      
       val[x]
      
     
    val[x],等同于给这些点添加上不选点
    
     
      
       
        x
       
      
      
       x
      
     
    x的代价
 如果这些点中存在点权
    
     
      
       
        >
       
       
        0
       
      
      
       >0
      
     
    >0的点,那么表示选择这个点比选择
    
     
      
       
        x
       
      
      
       x
      
     
    x的贡献大,累加这个点的权值,等同于改为选择这个点而不选点
    
     
      
       
        x
       
      
      
       x
      
     
    x,
 然后把这个新选择的点的
    
     
      
       
        k
       
      
      
       k
      
     
    k距离内点的点权减少,但是因为这个点与点x之间有距离,所以这时候某些点的点权其实是要加回去
    
     
      
       
        v
       
       
        a
       
       
        l
       
       
        [
       
       
        x
       
       
        ]
       
      
      
       val[x]
      
     
    val[x]的。
 子节点必须处理完再向上走（这个时候父节点的决策在当前一定是正确的），求出
    
     
      
       
        b
       
       
        f
       
       
        s
       
       
        序
       
      
      
       bfs序
      
     
    bfs序逆序遍历即可，同时换点时,需要加回
    
     
      
       
        v
       
       
        a
       
       
        l
       
       
        [
       
       
        x
       
       
        ]
       
      
      
       val[x]
      
     
    val[x]的点一定在后面,而后面的点的点权一定<=0,可以不管,无影响。 
Code: 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
//#include 
#define guo312 std::ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
#define ll long long
#define Inf LONG_LONG_MAX
#define inf INT_MAX
#define endl "n"
#define PI 3.1415926535898
using namespace std;
const int N=2e5+10;
int val[N],n,k; 
vector ve[N];

int b[N],flag[N],cnt=0;
void bfs(int u){
	queue p; p.push(u); flag[u]=1; 
	while(!p.empty()){
		int u=p.front(); p.pop(); b[++cnt]=u;
		for(auto it:ve[u]){
			if(flag[it]==0){
				p.push(it);
				flag[it]=1;
			}
		}
	}
}

void modify(int now,int last,int dep,int num){
	if(dep>k) return ;
	val[now]-=num;
	for(auto it:ve[now]){
		if(it==last) continue;
		modify(it,now,dep+1,num);
	}
}

int main(){
guo312;
	cin>>n>>k;
	for(int i=1;i<=n;i++){
		cin>>val[i];
	}
	for(int i=1;i
		int u,v; cin>>u>>v;
		ve[u].push_back(v);
		ve[v].push_back(u);
	}
	bfs(1);
	ll ans=0;
	for(int i=cnt;i>=1;i--){
		if(val[b[i]]>0){
			ans+=val[b[i]];
			modify(b[i],-1,0,val[b[i]]);
		}
	}
	cout<

Codeforces Round #595 (Div. 3) A-F

C/C++/C#相关栏目本月热门文章