一场爆肝场。
如果不是划水划到太晚才不会打呢（大雾）
整体来说难度较低…但是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;
}