题目大意: 有一个高h重w的雪球从山上滚下来,每下降一米,重量+=高度,中间会碰到两个石头,碰到后雪球减去石头的重量,问到达高度为 0 是重量为多少
小于0则看做0
模拟题……
#include <cstdio>
int w,h;
int u1,u2,d1,d2;
int main(){
scanf("%d%d%d%d%d%d",&w,&h,&u1,&d1,&u2,&d2);
while(h){
w+=h;
if(h==d1) w-=u1;
if(h==d2) w-=u2;
if(w<0) w=0;
h--;
}
printf("%d",w);
}
B
现在需要画$n$个正方形,问最少需要几个单位线段可以保证画出来的$n$个正方形的每条边都可以通过已有线段平行得到
贪心就对了
#include <cstdio>
#include <cmath>
int n,tmp,ans;
int main(){
scanf("%d",&n);
tmp=std::sqrt(n);
if(n%tmp==0){
printf("%d",tmp+(n/tmp));
return 0;
}
else {
ans=tmp+(n/tmp);
printf("%d",ans+1);
}
}
C
给你一个字符串,如果一个字母后跟的是
*
表示这个字母可以被删除,保留或重复多次,如果跟的是?
表示这个字母可以被删除或者保留,如果都不是,则表明其必须留在原位置
贪心题目,比较原字符串长度与要求的长度,然后分段讨论
#include <cstdio>
#include <cstring>
int k,len,zlen,sfcnt,tmp;
bool sf,cd;
char s[1000];
int main(){
scanf("%s",s+1);
scanf("%d",&k);
len=strlen(s+1);
for(int i=1;i<=len;i++){
if(s[i]>='a'&&s[i]<='z')
zlen++;
if(s[i]=='?') sfcnt++;
if(s[i]=='*') {cd=true;sfcnt++;}
}
if(zlen>k){
if(sfcnt<zlen-k){
printf("Impossible");
return 0;
}
for(int i=1;i<=len;i++){
if(s[i]=='*'||s[i]=='?') continue;
if(s[i+1]=='?'||s[i+1]=='*'){
if(zlen>k) {zlen--;sfcnt--;}
else printf("%c",s[i]);
}
else printf("%c",s[i]);
}
}
else if(zlen==k){
for(int i=1;i<=len;i++){
if(s[i]=='*'||s[i]=='?') continue;
else printf("%c",s[i]);
}
}
else if(zlen<k){
if(!cd){
printf("Impossible");
return 0;
}
for(int i=1;i<=len;i++){
if(s[i]=='*'||s[i]=='?') continue;
else if(s[i+1]=='*'){
printf("%c",s[i]);
while(1){
if(zlen>=k) break;
printf("%c",s[i]);
zlen++;
}
}
else printf("%c",s[i]);
}
}
}
D
现在已知树的形态与奇数深度点到根的长度(最短路径所经过的边的边权和)
因为交叉未知……所以直接贪心!!!
#include <cstdio>
#include <cstdlib>
inline int Min(int a,int b){return a<b?a:b;}
const int N=1e5+2e4;
const int INF=2147483640;
int n,v;
long long sum=0;
int s[N],a[N],son[N];
// edge start
struct edge{
int to,next;
}e[N<<1];
int ehead[N],ecnt;
inline void add_edge(int now,int to){
ecnt++;
e[ecnt].to=to;
e[ecnt].next=ehead[now];
ehead[now]=ecnt;
}
// edge end
void dfs(int now,int val){
if(s[now]<=-1){
int tmp=INF;
for(int i=ehead[now];i;i=e[i].next){
tmp=Min(s[e[i].to],tmp);
}
if(tmp==INF) return ;
tmp-=val;a[now]=tmp;
for(int i=ehead[now];i;i=e[i].next){
s[e[i].to]-=val+a[now];
}
for(int i=ehead[now];i;i=e[i].next){
dfs(e[i].to,val+a[now]);
}
return ;
}
a[now]=s[now];
for(int i=ehead[now];i;i=e[i].next){
dfs(e[i].to,val+a[now]);
}
}
int main(){
scanf("%d",&n);
for(int i=2;i<=n;i++){
scanf("%d",&v);
add_edge(v,i);
}
for(int i=1;i<=n;i++){
scanf("%d",&s[i]);
if(s[i]!=-1&&s[i]<s[1]){
printf("-1");
return 0;
}
}
dfs(1,0);
sum=0;
for(int i=1;i<=n;i++){
if(a[i]<0){
printf("-1");
return 0;
}
sum+=a[i];
}
printf("%lld",sum);
}
]]>