省常中 Day 2

由于家里的床睡起来比较舒服决定在家只因训。

昨天睡得太香忘写blog了，114514年后补。

以及那个启瑞智慧树居然没有文件读写，赛时带着文件读写的代码交上去会爆炸。

T1

水，还需要说思路吗（

首先很显然形如 999999 的数字肯定是字典序最大的，又因为前面都相同的情况下位数越多字典序越大，直接在 <n 的情况下凑最多位数即可。

需要特判除个位以外都是 9 的数字，原因还用说吗（凑位数）。

code：

#include
using namespace std;
const int N=1010;
int len;
bool lim=true;
char s[N];
int main()
{
    scanf("%s",s+1);
    len=strlen(s+1);
    for (int i=1;i<len;i++){
        if (s[i]!='9'){
            lim=false;
            break;
        }
    }
    for (int i=2;i<=len;i++){
        printf("9");
    }
    if (lim){
        printf("%c",s[len]);
    }
    return 0;
}

T2

很明显要让树的深度尽量小。

观察到数据范围不大，可以用我唯一会打的算法暴力求解。

枚举每个节点为根的情况并bfs建出深度最小的树，然后直接dfs求花费即可。

code：

#include
using namespace std;
const int N=2e3+10,K=5e3+10,INF=0x3f3f3f3f;
int n,h[N],to[K],nxt[K],cnt=-1;
int k,c[N];
bool vis[N];
int numvis,h1[N],to1[K],nxt1[K],cnt1,mon[N];
int ans=INF;
void add(int x,int y){
    nxt[++cnt]=h[x];
    h[x]=cnt;
    to[cnt]=y;
    return;
}
void add1(int x,int y){
    nxt1[++cnt1]=h1[x];
    h1[x]=cnt1;
    to1[cnt1]=y;
    return;
}
void dfs(int u){
    mon[u]=1;
    for (int i=h1[u];~i;i=nxt1[i]){
        int v=to1[i];
        dfs(v);
        mon[u]+=mon[v];
    }
    return;
}
void bfs(int rt){
    memset(vis,false,sizeof vis);
    memset(h1,-1,sizeof h1);
    cnt1=-1;
    numvis=1;
    queue q;
    q.push(rt);
    vis[rt]=true;
    while (!q.empty()){
        int u=q.front();
        q.pop();
        for (int i=h[u];~i;i=nxt[i]){
            int v=to[i];
            if (vis[v]){
                continue;
            }
            vis[v]=true;
            numvis++;
            add1(u,v);
            q.push(v);
        }
    }
    if (numvis<n){
        return;
    }
    dfs(rt);
    int sum=0;
    for (int i=1;i<=n;i++){
        sum+=mon[i];
    }
    ans=min(ans,sum);
    return;
}
int main()
{
    memset(h,-1,sizeof h);
    scanf("%d",&n);
    for (int i=1;i<=n;i++){
        scanf("%d",&k);
        for (int j=1;j<=k;j++){
            scanf("%d",&c[j]);
            add(c[j],i);
        }
    }
    for (int rt=1;rt<=n;rt++){
        bfs(rt);
    }
    printf("%d",ans);
    return 0;
}

T3

观察到 k=1 的情况下一定会被吃（其他史莱姆都比它大），因此直接输出 0 即可，期望得分 5 ，但由于数据过水拿了 10pts 。

DP，赛时由于智力过低刷题又过少没打出来。

大概思路是令 dp_i 表示考虑前 i 个史莱姆的合法方案，分类讨论。

智力不够，没完全搞懂，回放还没发，待会再改。