(Codeforces) (Round) (635)
A. Ichihime and Triangle
(Description:)
给定四个整数(a,b,c,d)，找到三个整数(x,y,z)满足(aleq xleq bleq yleq cleq zleq d)
使得(x,y,z)能构成三角形
(Solution:)
签到题，直接令(x=b,y=c,z=)c即可，小边尽可能大，大边尽可能小
(Code:)
#include<bits/stdc++.h>
using namespace std;
int main(){
int t;
scanf("%d",&t);
while(t--){
int a,b,c,d;
scanf("%d%d%d%d",&a,&b,&c,&d);
printf("%d %d %d
",b,c,c);
}
return 0;
}
B. Kana and Dragon Quest game
(Description:)
一条龙有(h)的生命值，你总共有两种技能可以释放：
1.将龙的血量变为(lfloor frac{h}{2} floor+10)
2.将龙的血量变为(h-10)
已知第一个技能可以用(n)次，第二个技能可以用(m)次，请问能否打败巨龙
(Solution:)
我的做法是(dp)
(f[i][j])表示用(1)技能(i)次，用(2)技能(j)次后龙的最小血量
跑完(dp)之后扫一遍看有没有(0)出现即可
(Code:)
#include<bits/stdc++.h>
using namespace std;
int t,h,n,m,f[35][35];
int main(){
int i,j;
scanf("%d",&t);
while(t--){
memset(f,0x3f,sizeof(f));
scanf("%d%d%d",&h,&n,&m);
f[0][0]=h;
for(i=0;i<=n;i++){
for(j=0;j<=m;j++){
if(i<n)f[i+1][j]=max(0,min(f[i+1][j],f[i][j]/2+10));
if(j<m)f[i][j+1]=max(0,min(f[i][j+1],f[i][j]-10));
}
}
bool flag=0;
for(i=0;i<=n;i++)
for(j=0;j<=m;j++)
if(f[i][j]==0)flag=1;
if(flag)printf("YES
");
else printf("NO
");
}
return 0;
}
C. Linova and Kingdom
(Description:)
给你一棵以(1)为根节点的树，你可以在这棵树上设定(k)个关键节点
使得所有非关键节点到根的路径上关键节点数的总和最大
求出这个最大值
(Solution:)
手算几组数据之后发现在最优的情况下，如果一个节点是关键节点，那么它的父节点也是关键节点
那么此时增加一个关键节点所获得的收益就是(size_i-depth_i)
其中(size)为以(i)为根节点的子树的大小，(depth)为(i)的深度
我们直接一个(dfs)处理出(size)和(depth)，然后排序统计答案即可
(Code:)
#include<bits/stdc++.h>
using namespace std;
typedef long long lol;
int n,m,head[200005],size;
struct node{
int to,next;
}edge[500005];
struct point{
int x,son,depth;
}p[200005];
void putin(int from,int to){
size++;
edge[size].to=to;
edge[size].next=head[from];
head[from]=size;
}
void dfs(int r,int fa,int dep){
int i;
p[r].son=1;p[r].depth=dep;
for(i=head[r];i!=-1;i=edge[i].next){
int j=edge[i].to;
if(j!=fa){
dfs(j,r,dep+1);
p[r].son+=p[j].son;
}
}
}
bool cmp(const point a,const point b){
return a.son-a.depth>b.son-b.depth;
}
int main(){
int i,j;
memset(head,-1,sizeof(head));
scanf("%d%d",&n,&m);m=n-m;
for(i=1;i<n;i++){
int u,v;
scanf("%d%d",&u,&v);
putin(u,v);
putin(v,u);
}
for(i=1;i<=n;i++)p[i].x=i;
dfs(1,0,1);
sort(p+1,p+n+1,cmp);
lol ans=0;
for(i=1;i<=m;i++)
ans+=p[i].son-p[i].depth;
printf("%lld
",ans);
return 0;
}
D. Xenia and Colorful Gems
(Description:)
给定三个数列，在每个数列中分别选取一个数(x,y,z)
使得((x-y)^+(y-z)^2+(x-z)^2)最小，并输出这个最小值
(Solution:)
先把三个数列排序，然后让(i,j,k)分别指向三个数列的最小值
再贪心的选取(i,j,k)中的(+1)，使得变化后的((x-y)^+(y-z)^2+(x-z)^2)最小
不是很懂这个贪心策略为什么是对的，比赛的时候也只是碰碰运气，结果莫名其妙的对了
显然正解因该是枚举第一个数列的数，然后对另外连个数列进行二分查找
(Code:)
#include<bits/stdc++.h>
#define inf (9223372036854775807)
using namespace std;
typedef long long lol;
int t,A,B,C;
lol a[100005],b[100005],c[100005];
lol cal(int i,int j,int k){
return (a[i]-b[j])*(a[i]-b[j])+(b[j]-c[k])*(b[j]-c[k])+(a[i]-c[k])*(a[i]-c[k]);
}
int main(){
int i,j,k;
scanf("%d",&t);
while(t--){
scanf("%d%d%d",&A,&B,&C);
for(i=1;i<=A;i++)scanf("%lld",&a[i]);
for(i=1;i<=B;i++)scanf("%lld",&b[i]);
for(i=1;i<=C;i++)scanf("%lld",&c[i]);
sort(a+1,a+A+1);
sort(b+1,b+B+1);
sort(c+1,c+C+1);
i=1;j=1;k=1;
lol ans=inf;
while(i<=A&&j<=B&&k<=C){
lol tmp=cal(i,j,k),sum1=i<A?cal(i+1,j,k):inf,sum2=j<B?cal(i,j+1,k):inf,sum3=k<C?cal(i,j,k+1):inf;
ans=min(ans,tmp);
sum1=sum1-tmp;sum2=sum2-tmp;sum3=sum3-tmp;
if(sum1<=sum2&&sum1<=sum3)i++;
else if(sum2<=sum1&&sum2<=sum3)j++;
else if(sum3<=sum1&&sum3<=sum2)k++;
}
printf("%lld
",ans);
}
return 0;
}
E. Kaavi and Magic Spell
(Description:)
给定两个字符串(s,t)，现在你有一个空串(a)，每次操作可以将(s)的首字母提取出来并放在(a)的最前面或者最后面
操作过程中使得(a)的前缀是(t)的情况有多少种
(Solution:)
显然(lentleq lens)，我们不妨将(t)拓展到和(s)一样长，其中拓展的一部分可以是任意字母
定义状态(f[l][r])表示当前状态下，操作过程中a的前缀为(t_lsim t_r)的情况数
外层循环遍历(s)，枚举当前要添加的字母，那么
如果当前枚举到的(s_i=t_r)，那么(f[l][r]=f[l][r]+f[l][r-1])
特别注意的是，由于(t)的延长部分可以为任何字母，所以一旦(r>lent)，也要执行上述转移
如果当前枚举到的(s_i=t_l)，那么(f[l][r]=f[l][r]+f[l+1][r])
特别注意的是，由于(t)的延长部分可以为任何字母，所以一旦(l>lent)，也要执行上述转移
最后统计以下(f[1][lentsim lens])的和即可
(Code:)
#include<bits/stdc++.h>
#define mod (998244353)
using namespace std;
char s[3005],t[3005];
int lens,lent,f[3005][3005];
int main(){
int i,j,len;
scanf("%s%s",s+1,t+1);
lens=strlen(s+1);lent=strlen(t+1);
for(i=1;i<=lens+1;i++)f[i][i-1]=1;
for(i=1,len=1;i<=lens;i++,len++){
for(int l=1,r=l+len-1;r<=lens;l++,r++){
if(l>lent||s[i]==t[l])f[l][r]=(f[l][r]+f[l+1][r])%mod;
if(r>lent||s[i]==t[r])f[l][r]=(f[l][r]+f[l][r-1])%mod;
}
}
int ans=0;
for(i=lent;i<=lens;i++)
ans=(ans+f[1][i])%mod;
printf("%d
",ans);
return 0;
}
BBT
运气比较好吧，有几个结论是猜对的。
但是还是被自己菜到:
(T2)明明是个数学题，偏偏要去整什么dp，简直就是耽误比赛时间。。。
(T3)交的时候手抖选错编译器，编译错误一次，简直是在搞笑，改完之后还没有一遍过，菜的不行。。。
(T4)那么简单的二分查找想不到，非要去整一个自己都不确定的贪心。。。不过还好，蒙对了（手动狗头）