题解

noip半年集训day8

写在前面

开学了,咕咕咕了好久的题解我终于想起来写了QAQ

A.猜单词

日常送分题, 我的思路是按照 $K$ 进制拆分一下。

Source Code

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
const int MAXN = 500 + 7;
int n, m, k, x;
char str[MAXN];
char sub[MAXN][MAXN];
int ans[MAXN];
bool cmp(char a, char b) {
    return a < b;
}
int main(int argc, char *argv[]) {
    scanf("%d %d %d %d", &n, &m, &k, &x);
    scanf("%s", str + 1);
    for (int i = 1; i <= m; i++) {
        scanf("%s", sub[i] + 1);
        std::sort(sub[i] + 1, sub[i] + k + 1);
    }
    if (m == 1) {
        for (int i = 1; i <= n; i++) {
            printf("%c", str[i] == '#' ? sub[1][x] : str[i]);
        }
        puts("");
        return 0;
    }
    int pos = m;
    while (x) {
        ans[pos--] = x % k;
        x /= k;
    }
    int tot = m;
    for (; tot; tot--) {
        if (!ans[tot]) ans[tot] = k;
        else {
            tot--;
            break;
        }
    }
    for (; tot; tot--) ans[tot]++;
    for (int i = 1; i <= n; i++) {
        if (str[i] == '#') {
            tot++;
            printf("%c", sub[tot][ans[tot]]);
        } else printf("%c", str[i]);
    }
    puts("");
    return 0;
}

B.树的权

首先化简成既约分数大家都会吧,除以 $gcd$ 就可以了。
通过手玩各种数据可知(手动滑稽),最优的方案只有三种情况。
1.选择一条点权全是 $1$ 的链。
2.选择一条点权为若干个 $1$ 和一个 $2$ 的链。
3.选择点权最小的一个点。
其实也可以简单证明一下。
只要证明这个式子成立就可以了。
$$\frac{a}{b} \leq \frac{2a}{b+1}$$
十字相乘一下
$$ab+a \leq 2ab$$
$$a \leq ab$$
因为 $$b$$ 是正整数,所以这个不等式成立。
那这个式子是在说什么呢?
考虑如果当前选了一条全是 $1$ 的长度为 $l$ 的路径,现在再选一个权值是 $2$ 的点,然后可以走过这个点再选择一条长度为 $l$ 的权值都是 $1$ 的路径,那么就可以求得更优的方案。这样相当于是在不亏的情况下选了 $2$ 然后再拓展就得到更小的答案了。至于为什么不能选别的,考虑这个很写出来之后就很显然的式子
$$\frac{a}{b} \leq \frac{na}{b+1},(n > 2)$$
前两种情况归在一起就是说最多有一个点的权值是 $2$ 。那么我们考虑 $dp$ 解决。第三种情况很好处理,取一下最优值就可以。
设 $f_{i,1/2}$ 表示编号为 $i$ 的点的子树内选一条点权都是 $1$ $/$选一条仅含有一个点的点权为 $2$, 其余点权都是 $1$ 的最大长度。
转移和树形背包是一模一样的,具体见代码。
然后再注意合并的时候更新一下答案。

Source Code

#include 
#include 
#include 
#include 
#include 
#include 
#define rep(i, a, b) for (int i = a; i <= b; i++);
typedef long long ll;
const int MAXN = 1e6 + 7;
struct Edge {
    int t, next;
} edge[MAXN << 1];
int head[MAXN], cnt;
ll f[MAXN][3], a1 = INT_MAX, a2 = 1, w[MAXN];
inline ll gcd(ll a, ll b) {
    return !b ? a : gcd(b, a % b);
}
inline void update(ll a, ll b) {
    if (a * a2 < b * a1) a1 = a, a2 = b;
}
inline void add(int u, int v) {
    edge[++cnt] = (Edge){v, head[u]}; head[u] = cnt;
}
void dfs(int u, int pre) {
    if (w[u] <= 2) f[u][w[u]] = 1;
    for (int e = head[u]; e; e = edge[e].next) {
        int v = edge[e].t;
        if (v == pre) continue;
        dfs(v, u);
        for (int i = 1; i <= 2; i++) {
            for (int j = 1; j <= 2 / i; j++) {
                update(i * j, f[u][i] + f[v][j]);
            }
        }
        for (int i = 1; i <= 2 / w[u]; i++) {
            f[u][i * w[u]] = std::max(f[u][i * w[u]], f[v][i] + 1);
        }
    }
}
int main(int argc, char *argv[]) {
    int n, u, v;
    scanf("%d", &n);
    for (int i = 1; i < n; i++) {
        scanf("%d %d", &u, &v);
        add(u, v);
        add(v, u);
    }
    for (int i = 1; i <= n; i++) {scanf("%d", w + i); a1 = std::min(a1, w[i]);}
    if (a1 > 1) printf("%lld/%lld\n", a1, a2);
    else {
        dfs(1, 0);
        ll c = gcd(a1, a2);
        printf("%lld/%lld\n", a1 / c, a2 / c);
    }
    return 0;
}

C.丢手绢

先考虑下 $40 \%$ 的部分分。
如果对于任意的$i$,都有 $A_i=1$,也就是起点都是 $1$ 的话,那么显然就是如下问题:

给定两个长度为 $n$ 的序列 $a,b$ 使其两两配对,求满足 $a_i>b_i$ 的对数。

那就挺显然的,有两种做法
第一种,对两个序列升序排序,然后两个指针从末尾往前指,如果可以造成贡献就把两个指针都往前移动一位,然后 $ans++$;否则把指向序列 $b$ 的指针向前移动一位。
第二种,开一个 $set$维护当前可以用的手绢的权值,从前往后扫,看看可不可以造成贡献,可以就把能造成贡献的权值最小的手绢放下,否则就放 $set$ 中权值最小的手绢。
那么现在如果有限制怎么办呢?
可以发现一点,按照题目中给的游戏规则,一定存在一个位置是不会被跨越的,比如说没有从 $1$ 传到 $2$。
那么只要枚举这个断点就可以用上面说的第二种做法做了。
但是时间复杂度不够优秀,而上述算法时间复杂度瓶颈在于枚举断点,考虑怎么快速找到最优的那个断点。
设 $pref_i$ 表示有多少手绢的起点在 $1 \rightarrow i$,这个数组可以通过前缀和处理出来,并且可以通过差分求出任意一个区间有多少手绢的起点。
考虑对于一段区间 $[l,r]$,若无法跨越 $r \rightarrow r+1$,那么必然有
$$r-l \leq pref_r - pref_l$$
说白了就是这段区间内的手绢数小于区间长度。
这个式子变一下就是
$$r - pref_r \leq l - pref_l$$
那么说白了就是找 $r - pref_r$ 最小的位置就可以了。

Source Code

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
const int MAXN = 5e5 + 7;
int n, pos[MAXN], pref[MAXN];
std::vector v[MAXN];
int p[MAXN];
int solve(int start) {
    std::set set;
    int ret = 0;
    for (int i = start, j = 0; j < n; j++, i = (i + 1) % n) {
        for (int it = 0; it < (int)v[i].size(); it++) {set.insert(v[i][it]);}
        for (std::vector::iterator it = v[i].begin(); it != v[i].end(); it++) set.insert(*it);
        std::set::iterator it = set.upper_bound(p[i]);
        if (it == set.end()) {
            if (!set.empty()) set.erase(set.begin());
        } else {
            set.erase(it); ret++;
        }
    }
    return ret;
}
int main(int argc, char *argv[]) {
    memset(pref, -1, sizeof pref);
    scanf("%d", &n);
    for (int i = 0; i < n; i++) {
        scanf("%d", pos + i);
        pos[i]--;
    }
    for (int i = 0; i < n; i++) {
        scanf("%d", p + i);
    }
    int w;
    for (int i = 0; i < n; i++) {
        scanf("%d", &w);
        pref[pos[i]]++;
        v[pos[i]].push_back(w);
    }
    std::pair min = std::make_pair(INT_MAX, INT_MAX);
    for (int i = 0; i < n; i++) {
        if (i) pref[i] += pref[i - 1];
        min = std::min(min, std::make_pair(pref[i], i));
    }
    printf("%d\n", solve((min.second + 1) % n));
    return 0;
}

D.Trie

最小化Trie 上的节点数,那么只要尽可能最大化公共前缀就可以了。
考虑 $dp$。
用 $pref_s$ 表示集合 $S$ 的最长前缀子串的长度。
对于给定的一个字符串的真子集 $S$,枚举它的一个子集 $S'$,则有
$f_s = \min(f_{s'}+f_{s-s'})-pref_s$。
就是说对于一个子集,显然先把能排成公共前缀的字母排成公共前缀,然后再划分开分别求最小的值,就可以了。
记忆化搜索很容易实现。

Source Code

#include 
#include 
#include 
#include 
#include 
#include 
const int MAXN =  16 + 1;
int f[1 << MAXN];
int n, cnt[MAXN][30];
char str[MAXN][1 << 20];
int calc(int mask) {
    int tmp[26], ret = 0;
    memset(tmp, 0x7f, sizeof tmp);
    for (int i = 0; i < n; i++) {
        if (mask & (1 << i))
        for (int j = 0; j < 26; j++) {
            tmp[j] = std::min(tmp[j], cnt[i][j]);
        }
    }
    for (int i = 0; i < 26; i++) ret += tmp[i];
    return ret;
}
int solve(int mask) {
    int &ret = f[mask];
    if (ret != -1) return ret;
    int pref = calc(mask);
    if ((mask & -mask) == mask) return ret = pref;
    ret = INT_MAX;
    for (int i = mask & (mask - 1); i > 0; i = mask & (i - 1)) {
        ret = std::min(ret, solve(i) + solve(mask ^ i) - pref);
    }
    return ret;
}
int main(int argc, char *argv[]) {
    scanf("%d", &n);
    memset(f, -1, sizeof f);
    for (int i = 0; i < n; i++) {
        scanf("%s", str[i]);
    }
    for (int i = 0; i < n; i++) {
        for (int j = 0; str[i][j]; j++) {
            cnt[i][str[i][j] - 'a']++;
        }
    }
    printf("%d", solve((1 << n) - 1) + 1);
    return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注