牛客IOI周赛16-普及组

A、求导

题意

思路：

真的就是对 求导直到 x 的系数为1，求导 次后 x 的系数就是 ，阶乘比较大，开ll算阶乘问题不大。
Code：

#include <bits/stdc++.h>
#define ll long long
using namespace std;
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;
}
ll n,ans=1;
int main() {
    read(n);
    for(ll i=2;i<=n;++i)    ans=(ans*i)%1000000007;
    printf("%lld\n",ans);
}

B、猜数

题意：

题目描述
纸上写了 n 个数字，牛牛在之前改动了几个数字，他忘了他具体改了些数字了。
但是他记得动之前这些数字的和是 \ge m≥m 的，求他最少改动几个数字。
注意：这些数字在改之前和改之后均在 0 ~ 9 之间，且为整数。
输入描述:

第一行给出 n,m
第二行给出 n 个 0 ~ 9 的整数

输出描述:
输出最少改动了几个数字(保证答案 )
备注
对于 50% 数据有
对于 100% 数据有
思路：

一道思维题，我刚开始就是直接计算每个数字的贡献，就是并用m减去 ，然后将贡献从大到小排序，统计将m减到小于等于0需要几个数字去贡献。但是现在想起来太蠢了。
之前思路的复杂度为 ，这个复杂度主要是排序带来了，而每个数使总和增加的贡献只能是0 ~ 9，也就是说记录可以贡献多少个 ，然后遍历 9 ~ 1 用除法判断需要多少次贡献就可以了。
Code：

#include <bits/stdc++.h>
#define ll long long
using namespace std;
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;
}
int n,m,x,b[10],ans;
int main() {
    read(n),read(m);
    for(int i=1;i<=n;++i) {
        read(x);
        m-=x;
        ++b[9-x];
    }
    for(int i=9;i&&m>0;--i) if(m>i*b[i]) {
        ans+=b[i];
        m-=i*b[i];
    }
    else {
        ans+=m/i+(m%i!=0);
        printf("%d\n",ans);
        return 0;
    }
}

C、求导

思路：

每行每列只能涂一个格子，判断这样涂的时候，对称矩阵的情况的种数。
打表找规律，前面是1，2，4，10，26。
得递推公式是 。
Code：

#include <bits/stdc++.h>
#define ll long long
using namespace std;
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;
}
ll n,a,b,c;
int main() {
    read(n);
    b=2,c=1;
    for(int i=3;i<=n;++i) {
        a=(b+c*(i-1))%1000000007;
        c=b; b=a;
    }
    printf("%lld\n",a);
}

D、杀树

题意：

题目描述
牛牛学习了树。
给出一棵节点数为 n 的树，删去一个点 i 的代价为 aia_iai​，一条链的长度定义为路径上 点 的个数。一棵树死了，满足不存在一条长度 ≥l\geq l≥l 的链，牛牛希望用最少代价杀死这棵树。
输入描述:

第一行给出 n,l
第二行给出 n 个整数分别代表 aia_iai​
接下来 n-1 行，每行给出 u,v 表示有一条 u 到 v 的边。

输出描述:

输出一个整数，表示最小的代价。

思路：

看了一下午还是。。。想不出来。
树状dp， 表示以 i 为根的子树，向下传 j 个长度的最小值，特别的dp[i][0]表示删除子树的根i。
1.首先，初始状态 表示去掉了自己，还要保证子树剩余的点满足题目意思。就将子树中 中的最小花费加上 给 。
2.保留点： ，便于下面更新 找最小值。
3. 。
Code：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int INF = 0x3f3f3f3f;
const int maxn=5e3+7;
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;
}
int head[maxn],Next[maxn<<1],to[maxn<<1],tot;
void add(int u,int v) {
    to[++tot]=v;
    Next[tot]=head[u];
    head[u]=tot;
}
int a[maxn],f[maxn][maxn],tmp[maxn],n,m;
void dfs(int u,int fa) {
    f[u][0]=a[u];
    for(int i=head[u];i;i=Next[i]) {
        int v=to[i]; if(v==fa) continue;
        dfs(v,u);
        f[u][0]+=*min_element(f[v],f[v]+m);
        for(int i=1; i<m; ++i)
            tmp[i]=f[u][i],f[u][i]=INF;
        for(int i=1; i<m;++i){
            for(int j=0; j<m; ++j){
                if(i+j<m)
                    f[u][max(i,j+1)]=min(f[u][max(i,j+1)],tmp[i]+f[v][j]);
                else
                    break;
            }
        }
    }
}
int main(){
    read(n),read(m);
    for(int i=1;i<=n;++i)    read(a[i]);
    for(int i=1;i<n;++i){
        int u,v;
        read(u),read(v);
        add(u,v),add(v,u);
    }
    dfs(1,0);
    printf("%d\n",*min_element(f[1],f[1]+m));
    return 0;
}