牛客IOI周赛16-普及组 (ABC题解)

A:
很容易发现求的就是一个N!
代码：

#include<bits/stdc++.h>
using namespace std;

typedef long long int ll;
const int maxn = 1e5 + 10;
const ll mod = 1e9 + 7;
void solved(){
    int n;cin>>n;
    ll ans = 1;
    for(int i = n; i >= 2; i--){
        ans = ans * i % mod;
    }
    cout<<ans<<endl;
}
int main(){
    solved();
    return 0;
} 

B:
贪心。
可以先求一波所有数的和，然后从小到大修改，sum - 这个数 + 9，一直循环，直到sum >= m退出循环输出答案即可。
代码：

#include<bits/stdc++.h>
using namespace std;

typedef long long int ll;
const int maxn = 1e6 + 10;
ll a[maxn];
void solved(){
    ll n,m;cin>>n>>m;
    for(int i = 1; i <= n; i++)cin>>a[i];
    sort(a + 1, a + 1 + n);
    ll sum = 0;
    for(int i = 1; i <= n; i++)sum += a[i];
    int pos = 1;
    int cnt = 0;
    while(sum < m){
        sum -= a[pos++];
        sum += 9;
        cnt ++;
    }
    cout<<cnt<<endl;
}
int main(){
    solved();
    return 0;
} 

C:
场上没想出来，但是也89不离十了，最后没出有点可惜。
这题不会做的情况下可以写一个暴力骗分。
代码：

#include<bits/stdc++.h>
using namespace std;

typedef long long int ll;
const int maxn = 1e5 + 10;
ll mod = 1e9 + 7;
ll n;
bool g[100][100];
bool vis[maxn];
int path[100];
int cnt ;
void dfs(int dep){
    if(dep >= n){
        for(int i = 0 ; i < dep; i++){
        //  cout<<path[i]<<" ";
            g[i + 1][path[i]] = 1;
        }
        //cout<<endl;
        bool flag = false;
        for(int i = 1; i <= n; i++){
            for(int j = 1; j <= n; j++){
                if(g[i][j] && !g[j][i]){
                    flag = true;
                }
            }
        }
        memset(g,false,sizeof(g));
        if(!flag)cnt++;
    }
    for(int i = 1; i <= n; i++){
        if(!vis[i]){
            vis[i] = true;
            path[dep] = i;
            dfs(dep + 1);
            vis[i] = false;
        }
    }
}
void solved(){
    cin>>n;
    dfs(0);
    cout<<cnt<<endl;   
}
int main(){
    solved();
    return 0;
}

如果擅长找规律的大佬，根据前面几项就可以推出公式，然后弱菜的我并不能。
接下来是这题的正解：
注意到要使得横竖都相等，只能45度直线斜对角线填，当我们填在(1,1)那么第一行第一列不能再填写任何数，那么就是要在(n-1,n-1)填，填法与刚才一样。当我们不填在(1,1),我们还有(n-1)个选择去填写(一次填两，对称)，但是每当我们填完两个还剩下(n-2,n-2)个格子要填写(填完两损失两行两列)，然后这(n-2,n-2)格子填法与之前一样，所以我们能够得到递推式：f(n) = f(n - 1) + (n - 1) * f(n - 2)。
这里偷个图

代码：

#include<bits/stdc++.h>
using namespace std;

const int mod = 1e9 + 7;
typedef long long int ll;
const int maxn = 1e5 + 10;
ll f[maxn];
void solved(){
    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) % mod;
    cout<<f[n]<<endl;
}
int main(){
    solved();
    return 0;
}