难得的国人赛，但我是憨憨。

Problem A

Analysis

考虑贪心，我一个点选了，那么这个点必然子树也选了，所以一个点$u$的贡献是$sz[u]-dep[u]$。直接排序选前$k$大的就行。

Attention

无

Code

//Code by Enderturtle
#include<bits/stdc++.h>
#define rep(i,a,b) for(register int i=a;i<=b;++i)
#define repe(i,a) for(register int i=head[a];i;i=e[i].nxt)
#define il inline
#define pii pair<int,int>
#define mp(a,b) make_pair(a,b)
typedef long long ll;
using namespace std;
il void filejudge(){
    freopen(".in","r",stdin);
    freopen(".out","w",stdout);
}
il int read(){
    int x=0;bool f=1;char ch=getchar();
    while(!isdigit(ch)){if(ch=='-') f=0;ch=getchar();}
    while(isdigit(ch)){x=(x<<3)+(x<<1)+(ch^48);ch=getchar();}
    return f?x:-x;
}
/*----- head end -----*/
const int N=2e5+10;
struct Edge{
    int v,nxt;
} e[N<<1];int head[N],tot;
il void add_edge(int u,int v){ e[++tot]=(Edge){v,head[u]};head[u]=tot;}
il void link(int u,int v){ add_edge(u,v);add_edge(v,u);}
int n,k,dep[N],sz[N],a[N];
ll ans;
il void dfs(int u,int f){
    dep[u]=dep[f]+1;
    sz[u]=1;
    repe(i,u){
        int v=e[i].v;
        if(v==f) continue;
        dfs(v,u);
        sz[u]+=sz[v];
    }
    a[u]=dep[u]-sz[u];
}
int main(){
    n=read();k=read();
    rep(i,2,n){ int u=read(),v=read();link(u,v);}
    dfs(1,1);sort(a+1,a+1+n,greater<int>());
    rep(i,1,k) ans+=(ll)(a[i]);
    printf("%lld\n",ans);
    return 0;
}

Problem B

Analysis

憨憨题。考虑如果我们固定了3个值中的最小值$mn$和最大值$mx$，那么根据简单的不等式我们可以知道第三个最佳的值是$\frac{(mn+mx)}{2}$。枚举$mn$，确定$mx$，然后大力二分第三个值就行了。

Attention

（lower_bound在从小到大排序的数组中是找到第一个大于等于的值）

Code

//Code by Enderturtle
#include<bits/stdc++.h>
#define rep(i,a,b) for(register int i=a;i<=b;++i)
#define repe(i,a) for(register int i=head[a];i;i=e[i].nxt)
#define il inline
#define pii pair<int,int>
#define mp(a,b) make_pair(a,b)
typedef long long ll;
using namespace std;
il void filejudge(){
    freopen(".in","r",stdin);
    freopen(".out","w",stdout);
}
il int read(){
    int x=0;bool f=1;char ch=getchar();
    while(!isdigit(ch)){if(ch=='-') f=0;ch=getchar();}
    while(isdigit(ch)){x=(x<<3)+(x<<1)+(ch^48);ch=getchar();}
    return f?x:-x;
}
/*----- head end -----*/
const int N=1e5+10;
const ll INF=LLONG_MAX;
int r[N],g[N],b[N];
int nr,ng,nb;
il ll calc(int x,int y,int z){
    if(x<=0 || y<=0 || z<=0 || x==(nr+1) || y==(ng+1) || z==(nb+1)) return INF;
    ll xx=(r[x]-g[y]),yy=(g[y]-b[z]),zz=(r[x]-b[z]);
    return xx*xx+yy*yy+zz*zz;
}
int main(){
    int T=read();
    while(T--){
        nr=read();ng=read();nb=read();
        rep(i,1,nr) r[i]=read();sort(r+1,r+1+nr);r[nr+1]=INT_MAX;
        rep(i,1,ng) g[i]=read();sort(g+1,g+1+ng);g[ng+1]=INT_MAX;
        rep(i,1,nb) b[i]=read();sort(b+1,b+1+nb);b[nb+1]=INT_MAX;
        int x,y,z;
        ll ans=LLONG_MAX;
        rep(i,1,nr){
            x=i;
            y=lower_bound(g+1,g+1+ng,r[x])-g;
            if(y!=(ng+1)){
                z=lower_bound(b+1,b+1+nb,(r[x]+g[y])/2)-b;
                ans=min(ans,calc(x,y,z));
                ans=min(ans,calc(x,y,z-1));
            }
            y--;
            if(y!=0){
                z=lower_bound(b+1,b+1+nb,(r[x]+g[y])/2)-b;
                ans=min(ans,calc(x,y,z));
                ans=min(ans,calc(x,y,z-1));
            }
            z=lower_bound(b+1,b+1+nb,r[x])-b;
            if(z!=(nb+1)){
                y=lower_bound(g+1,g+1+ng,(r[x]+b[z])/2)-g;
                ans=min(ans,calc(x,y,z));
                ans=min(ans,calc(x,y-1,z));
            }
            z--;
            if(z!=0){
                y=lower_bound(g+1,g+1+ng,(r[x]+b[z])/2)-g;
                ans=min(ans,calc(x,y,z));
                ans=min(ans,calc(x,y-1,z));
            }
        }
        rep(i,1,ng){
            y=i;
            z=lower_bound(b+1,b+1+nb,g[y])-b;
            if(z!=(nb+1)){
                x=lower_bound(r+1,r+1+nr,(g[y]+b[z])/2)-r;
                ans=min(ans,calc(x,y,z));
                ans=min(ans,calc(x-1,y,z));
            }
            z--;
            if(z!=0){
                x=lower_bound(r+1,r+1+nr,(g[y]+b[z])/2)-r;
                ans=min(ans,calc(x,y,z));
                ans=min(ans,calc(x-1,y,z));
            }
        }
        printf("%lld\n",ans);
    }
    return 0;
}

Problem C

Analysis

区间$dp$，将$T$长度补到$len_s$（保证正确性），$dp[l][r]$表示目前已经匹配了$T$中的$[l,r]$的字符串。

Attention

无

Code

//Code by Enderturtle
#include<bits/stdc++.h>
#define rep(i,a,b) for(register int i=a;i<=b;++i)
#define repe(i,a) for(register int i=head[a];i;i=e[i].nxt)
#define il inline
#define pii pair<int,int>
#define mp(a,b) make_pair(a,b)
typedef long long ll;
using namespace std;
il void filejudge(){
    freopen(".in","r",stdin);
    freopen(".out","w",stdout);
}
il int read(){
    int x=0;bool f=1;char ch=getchar();
    while(!isdigit(ch)){if(ch=='-') f=0;ch=getchar();}
    while(isdigit(ch)){x=(x<<3)+(x<<1)+(ch^48);ch=getchar();}
    return f?x:-x;
}
/*----- head end -----*/
const int N=3010,mod=998244353;
int n,m;
ll dp[N][N],ans;
char s[N],t[N];
il void add(ll &x,ll y){ x+=y;if(x>=mod) x-=mod;}
int main(){
    scanf("%s",s+1);n=strlen(s+1);
    scanf("%s",t+1);m=strlen(t+1);
    rep(i,1,n+1) dp[i][i-1]=1;
    rep(i,1,n){
        for(register int l=1,r=i;r<=n;++l,++r){
            if(l>m || t[l]==s[i]) add(dp[l][r],dp[l+1][r]);
            if(r>m || t[r]==s[i]) add(dp[l][r],dp[l][r-1]);
        }
    }
    rep(i,m,n) add(ans,dp[1][i]);
    printf("%lld",ans);
    return 0;
}

Problem D

Analysis

等我想写再写

Attention

实际上是因为我菜

Code

orz