【牛客IOI周赛16-普及组】

假装很菜，实则菜的一批orz

A 求导

这道题，高中数学，求阶层嘛~

代码

#include <iostream>
using namespace std;
typedef long long ll;
#define js ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
const int MOD = 1e9 + 7;
int main() {
    js;
    int n; cin >> n;
    ll mul = 1;
    for (int i = 2; i <= n; i++) mul = (mul * i) % MOD;
    cout << mul << endl;
    return 0;
}

B 猜数

这道题其实也是一道思考题吧。（至少我觉得是）

怎么写呢？

首先我们要知道，我们现在有的一组数是改动后的。我们已知他改动前至少有的总和。
那么我们就有两种情况，其一就是改动以后的和比已知的大，另一个就是改动以后比已知的小。
首先其一，如果改动以后的比已知的还大，说明：即使我不变也没事。所以就是0。
那么我们只要考虑小的情况就好了：我一开始想的是排个序然后一个数一个数删掉计数就好了嘛，对吧。
转念一想，这玩意儿不都可以用除法把时间复杂度降到O（1）嘛。棒棒哒~（咋用除法看下面）

所以代码也很简单：

首先一共就九个数，想想就知道没必要都存下来呀，每个数字计个数不就好了嘛？所以我们把他简单散列在数组里面。
然后判断大小，当前和比改动大就输出0。小的话就考虑删数。
那怎么删呢？我们现在的情况是，作者肯定是把某些数变小了。（变大的话就可能不是最少能删的数了）
所以我们从变少了最多的（加回去就是最多的）给一个个加上去。这里阔以用(m - sum) / (9 - i)简化计算，但是要注意，非整除要+1。
好了，题目简单，详情看代码~

代码

#include <iostream>
#include <cstring>
using namespace std;
//代码预处理区

template<class T>inline void read(T& res);//整型快读函数
//函数预定义区

int main() {
    int cnt[10];
    memset(cnt, 0, sizeof cnt);
    int n, m; read(n); read(m);
    for (int i = 0; i < n; i++) {
        int x; read(x);
        cnt[x]++;
    }
    int sum = 0;
    for (int i = 1; i <= 9; i++) sum += i * cnt[i];
    if (sum >= m) {
        printf("0\n");
        return 0;
    }
    int ans = 0;
    for (int i = 0; i < 9; i++) {
        if (sum + (9 - i) * cnt[i] >= m) {
            ans += (m - sum) / (9 - i);
            if ((m - sum) % (9 - i)) ans++;
            printf("%d\n", ans);
            return 0;
        }
        else {
            sum += (9 - i) * cnt[i];
            ans += cnt[i];
        }
    }
    return 0;
}
template<class T>inline void read(T& res) {
    char c; T flag = 1;
    while ((c = getchar()) < '0' || c > '9')
        if (c == '-')
            flag = -1;
    res = c - '0';
    while ((c = getchar()) >= '0' && c <= '9')
        res = res * 10 + c - '0';
    res *= flag;
}
//函数区

C 答题卡

感觉规律就是

每行每列只能涂一个格子，判断这样涂的时候，对称矩阵的情况的种数。

但是这道题我其实没有推出来，对前几个的规律有印象，所以就把记得的公式套上去打表了。

前面是1，2，4，10，26。递推公式是f[i] = f[i - 1] + (i - 1) * f[i - 2]。

代码

#include <iostream>
using namespace std;
typedef long long ll;
#define js ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
//代码预处理区

const int MOD = 1e9 + 7;
const int MAX = 1e5 + 7;
ll f[MAX];
//全局变量区

int main() {
    js;
    int n; cin >> n;
    f[1] = 1, f[2] = 2;
    for (int i = 3; i <= n; i++)
        f[i] = (f[i - 1] + (i - 1) * f[i - 2]) % MOD;
    cout << f[n] << endl;
    return 0;
}

D 杀树

这道题我想了很久才。。。发现我真的想不出来，大佬答案都看不懂orz

首先这道题是一个树形dp。

算法简介：

这道题范围不是很大，用二维dp可。
我们建立dp数组，dp[i][j]表示为dp[根位置][树直径长度] = 当前情况的总花费。
首先我们来讲删除结点的情况：dp[x][0]为删除本节点时子树的方案最小花费。
（因为当子树直径长度为0的时候连根都没有了嘛，所以就是删掉自己了咯）。
（这里表示：我们用第二维为0的时候表示方案的花费，而不为0的时候就是单纯的递推计算）。
那删除自己时的最小花费等于什么呢？当然是子树里面所有子树里面删除的所有节点所带来的花费加上自己本身的节点花费呀。
所以就有 $dp[x][0]=(\Sigma_{i∈son_{x}}{dp[i][l−1]}) + w_{x}$ _。
（为什么第二维_{（子树长度）}是l - 1呢？因为l是最大长度啊。当前长度没到最大长度也没事，我们算的是最小花费，较大长度代表的花费会直接继承较小长度的。-1是要减掉自己呀）
上面已经讲了删除点的情况，那保留点的情况呢？保留点的话，我们用一个tmp数组储存我们的dp数组所算出来的最小值。
保留点的时候，我们假设有现在的直径长度为len，也就是说，我们要找出比len小的最小花费情况。
给出我们的转移方程：
```
dp[u][j] = min(dp[u][j] + dp[v][min(l - j - 1, j - 1)], tmp[u][j] + dp[v][j - 1]);
tmp[u][j] += dp[v][min(l - j - 1, j - 1)];
```
补充：我们单纯把该删除的节点算作需要花费，而不实际上删除。包括在dp中，被删除的点仍然存在并参与节点计数。
你要问我转移方程的意义是什么？比大小的两项是啥？为啥要min(j−1,l−j−1)？我真的不知道。。。orz（真的就是最后一点点不懂。。这树杀我。。）

打代码：

前向星输入哦。
然后按照上面的操作dfs一遍就好了：我们这里用了一个tmp数组用来暂存某一节点子树最长链。
最后选出最小值输出。
看代码吧看代码~

代码

#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
//代码预处理区

const int INF = 0x3f3f3f3f;
const int MAX = 5e3 + 7;
int head[MAX], tot = 0;//前向星变量
struct Node {
    int v, next;
} edge[MAX << 1];
int n, l, w[MAX];//节点数，最大长度，边权
int dp[MAX][MAX], tmp[MAX][MAX];//dp[根位置][树直径长度] = 当前情况的总花费 //全局变量区

template<class T>inline void read(T& res);
void dfs(int x, int fa);

int main() {
    read(n); read(l);
    for (int i = 1; i <= n; i++) read(w[i]);
    memset(head, -1, sizeof(head));
    for (int i = 1; i < n; i++) {
        int u, v; read(u); read(v);
        edge[tot] = Node{ v, head[u] }, head[u] = tot++;
        edge[tot] = Node{ u, head[v] }, head[v] = tot++;
    }
    //前向星初始化
    memset(dp, INF, sizeof(dp));
    dfs(1, 0);
    //遍历递推
    int ans = INF;
    for (int i = 0; i < l; i++) ans = min(ans, dp[1][i]);
    printf("%d\n", ans);
    //找出最大输出
    return 0;
}
template<class T>inline void read(T& res) {
    char c; T flag = 1;
    while ((c = getchar()) < '0' || c > '9')
        if (c == '-')
            flag = -1;
    res = c - '0';
    while ((c = getchar()) >= '0' && c <= '9')
        res = res * 10 + c - '0';
    res *= flag;
}
void dfs(int u, int fa) {
    dp[u][0] = w[u]; dp[u][1] = 0;
    for (int i = head[u]; ~i; i = edge[i].next) {
        int v = edge[i].v;
        if (v == fa) continue;
        dfs(v, u);
        dp[u][0] += dp[v][l - 1];
        for (int j = 1; j < l; j++) {
            dp[u][j] = min(dp[u][j] + dp[v][min(l - j - 1, j - 1)], tmp[u][j] + dp[v][j - 1]);
            tmp[u][j] += dp[v][min(l - j - 1, j - 1)];
        }
    }
    for (int i = 1; i < l; i++) dp[u][i] = min(dp[u][i], dp[u][i - 1]);
}

比赛文章被收录于专栏

憨憨的专栏