IOI周赛16题解

A: 传送门：https://ac.nowcoder.com/acm/contest/5389/A

思路：根据求导法则，可知道答案要求的是n的阶乘，只要进行简单的模拟，一步一步的求出即可
注意：开longlong
代码：

#include<bits/stdc++.h> 
using namespace std;
const int mod=1e9+7;
typedef long long ll;
int main(){
    ll n;
    scanf("%ld",&n);
    ll ans=1;
    for(int i=2;i<=n;++i){
        ans=ans*i%mod;
    }
    printf("%ld\n",ans);
    return 0;
}

B: 传送门：https://ac.nowcoder.com/acm/contest/5389/B

思路：贪心，既然要变化最少，那么我们就尽量让他的每个数变动最大，所以进行一个排序，然后从最小的开始变化，将每个数变化到最大，即为9，每个数变化后可以使总和sum增加了多少，每变化一次就进行检查sum是否已经满足条件，输出即可。
特判：一个都不要变化，即ans=0，不变化总和也大于等于m
代码：

#include<bits/stdc++.h>
using namespace std;
int a[1000010];
int main(){
    int n,m;
    cin>>n>>m;
    int sum=0;
    for(int i=0;i<n;i++){
        cin>>a[i];
        sum+=a[i];  //先求出总和sum
    }
    if(sum>=m)  cout<<"0"<<endl;  //特判0
    else{
        sort(a,a+n);
        int k=0;
        for(int i=0;i<n;i++){
            int temp=9-a[i];  //计算离9差多少
            sum+=temp;  //总和加sum
            k++;
            if(sum>=m){  //每次进行一个检查
                cout<<k<<endl;
                return 0;
            }
        }
    }
    return 0;
}

C: 传送门：https://ac.nowcoder.com/acm/contest/5389/C

思路：dp+数学，想到了用dp求，但一直没有找到规律，orz。关键是要找出他其实是在找一个关于左上到右下的斜对角线进行对称的涂法，注意这里每行每列只能涂一个，也就是在每个吐涂了的位置的同一行，同一列不能再有被涂的位置了。接下来，介绍一下如何dp。
首先，我们令dp[i]表示的是i阶矩阵的涂法有dp[i]种，假设当前的方阵为n阶，然后，一种情况是在之前的n-1阶的所有涂法的基础上涂左上角那个位置，因为之前的n-1阶的涂法都一定是满足对称的，这是条件，则dp[n-1]就是dp[n]当中的一部分。
然后就是假如我们不涂左上角那个位置，我们涂第一行第二列的那个位置，那么对应就一定要涂第二行第一列的那个位置，然后我们将这两个位置而这一行这一列都删去，就只剩下n-2阶矩阵了；同样，我们也可以涂第一行第三列的那个位置，第一行第四列的那个位置...第一行第n列的那个位置（这里都要对应的涂关于斜对角线对称的那个位置。一共是n-1种涂法，对应每种涂法有dp[n-2]种情况，总的就有（n-1）dp[n-2]
综上，我们得到dp[n]=dp[n-1]+dp[n-2](n-1)
注意：对dp开longlong即可
代码：

#include<bits/stdc++.h>
using namespace std;
const int mod=1e9+7;
typedef long long ll;
ll dp[1000010];
int main(){
    ll n;
    cin>>n;
    dp[1]=1,dp[2]=2;
    for(int i=3;i<=n;++i){
        dp[i]=(dp[i-1]+dp[i-2]*(i-1))%mod;
    }
    cout<<dp[n]<<endl;
    return 0;
} 

D: 传送门：https://ac.nowcoder.com/acm/contest/5389/D

待填！！！