Code

#include <stdio.h>
#include <string.h>

#define N 100

/*
这道题的输入要比较小心的处理, 由于字符是按顺序给的,所以我们不需要保存字符

-----------------基本思路------------
n = read()
f[n] = read()

best = 最优权值和

m = read()

循环 m 次:
    读方案, 计算当前方案 cost
    计算有无前缀关系

    if ok:
        print("Yes")
    else:
        print("No")
-------------------------------------
*/


/*
f 是频率, rf 是 f 的副本, 因为在计算最优权值和的时候 f 已经被改变

str 保存编码方案
*/


int f[N], rf[N];
char str[N][N];
int vis[N];
int n, m;


int getMinCost(){
    //所有非叶子结点的和

    int T = n - 1; //合并 n - 1 次
    int cost = 0;

    while(T--){
        int m1, m2; //两个最小的值
        int idx1, idx2; //两个最小值对应的下标

        /*
            每次找最小的两个值 m1, m2
            把 m1 的 vis 标记置 1, m2 标记不动
            然后把 m1 的权值加到 m2 上

            实现合并操作
        */

        //find m1
        m1 = 1e8; //一个很大的数
        for(int i = 1;i <= n;i++){
            if(!vis[i] && f[i] < m1){
                m1 = f[i];
                idx1 = i;
            }
        }
        vis[idx1] = 1;

        //find m2
        m2 = 1e8;
        for(int i = 1;i <= n;i++){
            if(!vis[i] && f[i] < m2){
                m2 = f[i];
                idx2 = i;
            }
        }
        f[idx2] += f[idx1];
        cost += f[idx2];
    }

    return cost;
}

/*
计算两个串是否存在前缀关系
'\0' === 0, 所以可以用 *s 来当判断
*/
int isprefix(char* s, char* t){
    while(*s && *t){
        if(*s != *t) return 0;
        s++;t++;
    }
    return 1;
}
int main(){
    scanf("%d ", &n); //注意加了一个空格, 吸收空白符
    char tmp;
    for(int i = 1;i <= n;i++){
        scanf("%c%d ",&tmp, &f[i]); //注意加了一个空格, 吸收空白符
        rf[i] = f[i];
    }

    int best = getMinCost();

    scanf("%d ", &m); //注意加了一个空格, 吸收空白符

    while(m--){
        int cost = 0;
        for(int i = 1;i <= n;i++){
            scanf("%c%s ", &tmp, str[i]); //注意加了一个空格, 吸收空白符
           
            cost += rf[i] * strlen(str[i]);
        }
        if(cost != best){
            puts("No");
            continue;
        }
        int ok = 1;
        for(int i = 1;i <= n;i++){
            for(int j = i + 1;j <= n;j++){
                if(isprefix(str[i], str[j])){
                    ok = 0;
                }
            }
        }
        if(ok) puts("Yes");
        else puts("No");
    }

}
上一篇:浅谈满足四边形不等式的序列划分问题的答案凸性


下一篇:Linux如何保证系统安全 看这里