A-求导

Question

求在次导后前的系数。

Solution

Code

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int>P;
const double eps = 1e-8;
const int NINF = 0xc0c0c0c0;
const int INF  = 0x3f3f3f3f;
const ll  mod  = 1e9 + 7;
const ll  maxn = 1e6 + 5;
const int N = 1e5 +5;

ll f[N];

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    ll n;cin>>n;
    ll base=1;
    for(int i=1;i<=n;i++){
        base=base*i%mod;
        f[i]=base;
    }
    cout<<f[n]<<'\n';
    return 0;
}

B-猜数

Question

纸上写了 个数字，牛牛在之前改动了几个数字，他忘了他具体改了些数字了。
但是他记得动之前这些数字的和是 的，求他最少改动几个数字。
注意：这些数字在改之前和改之后均在 ，且为整数。

Solution

贪心，优先从数字最小的开始改，记入每个数字的次数。

  1. 若没改过的最小数字全改还没有则全改，记入该数字的个数。
  2. 若改完当前数字一定可以结束，求最小改当前数字多少个，记入答案。

    Code

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int>P;
const double eps = 1e-8;
const int NINF = 0xc0c0c0c0;
const int INF  = 0x3f3f3f3f;
const ll  mod  = 1e9 + 7;
const ll  maxn = 1e6 + 5;
const int N = 1e6 + 5;

ll a[N],cnt[10];

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    ll n,m;cin>>n>>m;
    ll sum=0,ans=0;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        sum+=a[i];
        cnt[a[i]]++;
    }
    ll ma=0,idx=0;
    while(sum<m){
        ma=(9-idx)*cnt[idx];
        if(sum+ma<m){
            sum+=ma;
            ans+=cnt[idx];
            idx++;
        }else{
            int base=9-idx;
            int t=(m-sum+base-1)/base;
            sum+=t*base;
            ans+=t;
        }
    }
    cout<<ans<<'\n';
    return 0;
}

C-答题卡

Question

求一个的矩阵主对角线对称，且每行每列只有一个为其余均为的方案数。

Solution

DP，我们画图，发现每次扩一行一列的时候，我们可以把新的看做老图的左上角加一个1（原来的变为），剩下的格子个格子由于不在所以选中他的同时，必须要选中他对称的格子的位置，那样的话还剩个格子，我们把选中的那一行一列划掉，剩下的拼在一起就构成了一个的图，这样的拿法有个。
故得到DP关系式：

Code

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int>P;
const double eps = 1e-8;
const int NINF = 0xc0c0c0c0;
const int INF  = 0x3f3f3f3f;
const ll  mod  = 1e9 + 7;
const ll  maxn = 1e6 + 5;
const int N = 1e5 + 5;

ll f[N];

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n;cin>>n;
    f[1]=1;f[2]=2;f[3]=4;
    int base=2;
    for(int i=4;i<=n;i++){
        f[i]=(f[i-1]+(i-1)*f[i-2]%mod)%mod;
    }
    cout<<f[n]<<'\n';
    return 0;
}

D-杀树

Question

给出一棵节点数为 的树，删去一个点 的代价为 ，一条链的长度定义为路径上点的个数。
一棵树死了，满足不存在一条长度 的链，牛牛希望用最少代价杀死这棵树。

Solution

树形背包
设表示第个结点链长不超过的最小花费，令表示删掉第个结点所需要的最小花费。


对于不删这个节点而言，有两种情况:

  1. 该节点子树两边的最长链+该节点
  2. 该节点子树最长链+该节点(该节点为叶子)

两种情况子树的一边取，另一边就只能取

想了很久还是没能想通为什么可以这么转移以及数组在这里的含义

Code

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int>P;
const double eps = 1e-8;
const int NINF = 0xc0c0c0c0;
const int INF  = 0x3f3f3f3f;
const ll  mod  = 1e9 + 7;
const ll  maxn = 1e6 + 5;
const int N = 5e3 + 5;

int n,l,a[N],f[N][N],dp[N][N];
vector<int> G[N];

void dfs(int x,int fa){
    memset(f[x],INF,sizeof(f[x]));
    f[x][0]=a[x];
    f[x][1]=0;
    for(auto c:G[x]){
        if(c==fa) continue;
        dfs(c,x);
        f[x][0]+=f[c][l-1];
        for(int i=1;i<l;i++){
            f[x][i]=min(f[x][i]+f[c][min(l-i-1,i-1)],f[c][i-1]+dp[x][i]);
            dp[x][i]+=f[c][min(l-i-1,i-1)];
        }
    }
    for(int i=1;i<l;i++) f[x][i]=min(f[x][i],f[x][i-1]);
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin>>n>>l;
    for(int i=1;i<=n;i++) cin>>a[i];
    for(int i=1;i<n;i++){
        int u,v;cin>>u>>v;
        G[u].push_back(v);
        G[v].push_back(u);
    }
    dfs(1,0);
    cout<<f[1][l-1]<<'\n';
    return 0;
}