2023年多校联训NOIP层测试2

0x7f · 2023-08-02 17:58:39 · 个人记录

离谱场。

T1 斐波那契树

原：HDU4786 Fibonacci Tree

结论题。

题意：给 N 个点，M 条边，边权只有 0（黑）或 1（白），问能否用这些边组成的生成树各边权之和属于斐波那契数。

思路：因为边权只有 0 和 1，所以可以组成的生成树的范围一定介于最小生成树与最大生成树之间。举个例子，已经得到了最小生成树，现在需要找第二小的生成树，那么就把最小生成树中的边权为 1 的边换成 0 就可以得到第二小的，第三小的同理。

int mn = 0, mx = 0;
if(!Krus(n, m, mn)) {
    puts("NO");
    continue;
}
reverse(e + 1, e + 1 + m);
if(!Krus(n, m, mx)) {
    puts("NO");
    continue;
}

for(int i = 1; ; i++)
    if(fib[i] >= mn && fib[i] <= mx) {
        puts("YES");
        break;
    } else if(fib[i] > mx){
        puts("NO");
        break;
    }

T2 期末考试

爆搜题。

题意：共 10 道单选，满分 100，每道题从 ABCD 中选择一个正确选项，选对得 10 分，选错得 0 分，给出 n 份答案及其对应分数，求有多少种可能的正确答案（保证一定有合法答案）。

部分分：

设 n 份答案中第 i 位共出现了 c_i 种字符，则有：

设 n 份答案中有 x 份本质不同，则有：

• 这题数据应该锅了，acccoders 上还开了 2 秒，所以放过了 O(n\cdot4^n)爆搜。

void dfs(int now) {
    if (now > 9) {
        bool OK = true;
        for (int i = 1; i <= n; i++) {
            int _v = 0;
            for (int _ = 0; _ < 10; _++) _v += (s[i][_] == ans[_]) * 10;
            if (_v != v[i]) { OK = false; break; }
        }
        cnt += OK;
        return;
    }
    for (int i = 0; i < 4; i++) {
        ans[now] = 'A' + i;
        dfs(now + 1);
    }
}

T3 麻烦的工作

如题。

题意：有 n 项任务，第 i 项任务需要 a_i 个不同的员工共同完成。共有 m 个员工，第 i 个员工每天只能做 b_i 项任务。现进行 q 次调整（改变原数据），具体有如下四种情况：

1. 令 a_i\gets a_i+1
2. 令 a_i\gets a_i-1
3. 令 b_i\gets b_i+1
4. 令 b_i\gets b_i-1

求每次调整后的任务是否可以在一天内完成。