CF1099

一场爆肝场。
如果不是划水划到太晚才不会打呢(大雾)
整体来说难度较低…但是EF都没做出来,丢人。


CF1099A
一道简单题。直接处理贡献即可。


#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#include<vector>
using namespace std;

int w,h;
int d1,w1,d2,w2;
void init(){
	scanf("%d%d%d%d%d%d",&w,&h,&w1,&d1,&w2,&d2);
	int ans=w;
	for(int i=h;i>=0;--i){
		ans+=i;
		if(d1==i){
			ans-=w1;
			ans=std::max(ans,0);
			continue;
		}
		if(d2==i){
			ans-=w2;
			ans=std::max(ans,0);
			continue;
		}
		
	}
	printf("%d\n",ans);
}
int main(){
	init();
	return 0;
}


CF1099B
找规律题。
解一个二次方程很容易就可以找到最优解。
实际情况当然是大力分类讨论。


#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#include<vector>
#include<cmath>
using namespace std;
int n;
void init(){
	int ans=0;
	scanf("%d",&n);
	int flr=(floor(sqrt(n)));
	ans=2*flr;
	n-=flr*flr;
	if(n&&n<=flr){
		++ans;
	}else if(n&&n>flr){
		ans+=2;
	}
	printf("%d\n",ans);
}
int main(){
	init();
	return 0;
}


CF1099C
一道有一定难度的模拟题。
很容易可以想到朴素的贪心做法。就是,能删的全都删;要加的一次加光。
要考虑很多细节。注意对无解情况的判定。


#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#include<vector>
using namespace std;
char base[205];
int len,del,ad,gl;
void init(){
	cin>>base+1;
	scanf("%d",&gl);
	len=strlen(base+1);
	for(int i=1;i<=len;++i){
		if(base[i]=='?'){
			++del;
		}
		if(base[i]=='*'){
			++ad;
		}
	}
	int n=len;
	len-=del;
	len-=ad;
	if(len-del-ad>gl||(!ad&&len<gl)){
		puts("Impossible");
	}else{
		if(len==gl){
			for(int i=1;i<=n;++i){
				if(base[i]!='?'&&base[i]!='*'){
					putchar(base[i]);
				}
			}
		}else if(len>gl){
			int cnt=len-gl;
			for(int i=1;i<=n;++i){
				if(base[i]=='*'){
					base[i]='?';
				}
			}
			for(int i=1;i<=n;++i){
				if(base[i+1]=='?'&&cnt){
					++i;
					--cnt;
				}else if(base[i]=='?'){
					continue;
				}else{
					putchar(base[i]);
				}
			}
			return;
		}else if(len<gl){
			int cnt=gl-len;
			for(int i=1;i<=n;++i){
				if(base[i+1]=='*'&&cnt){
					for(int j=0;j<=cnt;++j){
						putchar(base[i]);
					}
					cnt=0;
				}else if(base[i]=='?'||base[i]=='*'){
					continue;
				}else{
					putchar(base[i]);
				}
			}
		}
	}
}
int main(){
	init();
	return 0;
}


CF1099D
一道有一定思维难度的树形DP。
很容易可以证明,贪心地取子树最小总是更优的;下方只要不比上方大那就始终是有解的。


#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#include<vector>
using namespace std;
struct ee{
	int v;
	int nxt;
}e[200005];
int h[100005],et=0,fa[100005],dep[100005];
inline void add(int U,int V){
	e[++et]=(ee){V,h[U]};
	h[U]=et;
}
int n,s[100005],a[100005];
inline void dfs0(int X){
	for(int i=h[X];i;i=e[i].nxt){
		if(e[i].v==fa[X]){
			continue;
		}
		dep[e[i].v]=dep[X]+1;
		dfs0(e[i].v);
	}
}
inline void dfs(int X){
	for(int i=h[X];i;i=e[i].nxt){
		if(e[i].v==fa[X]){
			continue;
		}
		dfs(e[i].v);
	}
	for(int i=h[X];i;i=e[i].nxt){
		if(e[i].v==fa[X]){
			continue;
		}
		if(!(dep[X]&1)){
			s[X]=std::min(s[X],s[e[i].v]);
		}
	}
	if(s[X]==0x3f3f3f3f){
		s[X]=s[fa[X]];
	}
}
void init(){
	scanf("%d",&n);
	int v;
	for(int i=2;i<=n;++i){
		scanf("%d",&v);
		fa[i]=v;
		add(i,v);
		add(v,i);
	}
	dep[1]=1,fa[1]=0;
	dfs0(1);
	for(int i=1;i<=n;++i){
		scanf("%d",s+i);
	}
	for(int i=1;i<=n;++i){
		if(s[i]==-1){
			s[i]=0x3f3f3f3f;
		}
	}
	dfs(1);
//	for(int i=1;i<=n;++i){
//		printf("%d ",dep[i]);
//	}
//	puts("");
	long long ans=0;
	for(int i=1;i<=n;++i){
		a[i]=s[i]-s[fa[i]];
		ans+=a[i];
		if(a[i]<0){
			puts("-1");
			return;
		}
	}
	printf("%I64d\n",ans);
}
int main(){
	init();
	return 0;
}

发表评论

您的电子邮箱地址不会被公开。