【题解】牛客IOI周赛17-普及组

这次比赛没被爆破，高兴.jpg
官方题解写的可能不如民间题解，害怕.jpg

A 夹娃娃
本题很明显的考察前缀和。将数组预处理，记录sum[i]为a[1]...a[i]的总和。
那么sum[r]-sum[l]就是l...r的和了。时间复杂度O(n)。

#include<bits/stdc++.h>
using namespace std;
const int maxn=1e5+10;
const int mod=1e9+7;
int w[maxn], n, k, sum[maxn];

int main()
{
    scanf("%d%d", &n, &k);
    for (int i=1; i<=n; i++)
    {
        scanf("%d", &w[i]);
        sum[i] = w[i] + sum[i-1];
    }
    while (k--)
    {
        int l, r; scanf("%d%d", &l, &r);
        printf("%d\n", sum[r]-sum[l-1]);
    }
}

出题人&题解编写人：Aurora

B 莫的难题
本题主要考察组合数打表以及进制处理。
首先，题目问所有组合中第C(n, m)%1e9+7 (n>=m) 个数有多大；那么我们得先处理C(n, m)%1e9+7。因为原本的组合数公式中是有除号的，所以直接模肯定是不行的。那么就要用逆元。而且因为有多次询问，所以如果在数据极限的情况下可能还要用逆元预处理。这种方法太麻烦了，这里建议使用杨辉三角。首先，杨辉三角若查询C(n, m)，只需要O(1)的复杂度( 预处理复杂度为O(n²) )。其次，杨辉三角递推式中仅含有加法，所以可以直接取模，省事很多。
处理完C(n, m)%1e9+7的值，就来思考如何算出第k大的组合。估计一下，每次n/=5，最多可以到达14位，可以发现答案的位数会很大，用long long都存不下。那么可以首先将数据进行类似离散化的操作，将{1, 2, 3, 5, 9}变为{0, 1, 2, 3, 4}。那就变成了一个五进制的问题了。要注意的是，五进制，但是起点是1，而不是0。那么只需要将C(n, m)%1e9+7转换为5进制，并且将第i位转换为a[i]就好了。

PS：感觉这样写很不清楚，这里向大家推荐Bernard5的博客，写的很清楚：https://blog.nowcoder.net/n/10142a8b912e4de39147675915a0e526
呜呜呜，数据出的不够强，没有卡掉普通组合数的做法，这里向大家致歉。

#include<bits/stdc++.h>
using namespace std;
const int maxn=1e7+10;
const int mod = 1e9+7;
long long tgl[110][110], t, k;
int a[5] = {1, 2, 3, 5, 9};
int pt[maxn];


int main()
{
    tgl[1][1] = 1;
    for (int i=2; i<=110; i++)
    {
        for (int j=1; j<=i; j++) tgl[i][j] = (tgl[i-1][j] + tgl[i-1][j-1])%mod;
    }
    cin>>t;
    while (t --)
    {
        int n, m, in=0; cin>>n>>m;
        k = tgl[n+1][m+1];
        while (k)
        {
            k -= 1;
            pt[in++] = a[(k)%5];
            k /= 5;
        }
        for (int i=in-1; i>=0; i--) printf("%d", pt[i]);
        printf("\n");
    }

}

出题人&题解编写人：Aurora

C 不平衡数组
考虑dp，先考虑状态, 考虑两种状态即使+1或者不+1对其的影响.
dp[0][i]表示到i位子,不使用+1,使得前i个相邻不相等的代价
dp[1][i]表示到i位子,使用+1,使得前i个相邻不相等的代价
那么就只要考虑四种情况了.
第一种 if(a[i-1]==a[i]) 前面的值等于后面
dp[0][i]=dp[1][i-1];上一个状态a[i-1]+1了,那我就不要改变,直接转移
dp[1][i]=dp[0][i-1]+b[i];上一个转态a[i-1]没+1，那我要不相等必须+1。
其他情况以此类推,但是注意取相同效果下代价最低的就好了.

#include<bits/stdc++.h>
#define ios ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0)
#define pb push_back
#define inf 1329103910
typedef long long ll;
const ll mod=1e9+7;
const ll N=3e5+5;
const double eps=1e-7;
using namespace std;
ll gcd(ll a,ll b) {return b==0?a:gcd(b,a%b);}
ll lcm(ll a,ll b) { return a*b/gcd(a,b);    }
ll qp(ll a,ll b, ll p){ll ans = 1;while(b){if(b&1){ans = (ans*a)%p;--b;}a = (a*a)%p;b >>= 1;}return ans%p;}
ll Inv(ll x){ return qp(x,mod-2,mod);}
ll C(ll n,ll m){if (m>n) return 0;ll ans = 1;for (int i = 1; i <= m; ++i) ans=ans*Inv(i)%mod*(n-i+1)%mod;return ans%mod;}
ll a[N];
ll b[N];
ll dp[2][N];//考虑两种状态即使+1或者不+1对其的影响
int main()
{
        ios;
        ll n,t;
        cin>>n;
        for(ll i=1;i<=n;i++) dp[0][i]=0,dp[1][i]=0;
        for(ll i=1;i<=n;i++) cin>>a[i]>>b[i];
        for(ll i=1;i<=n;i++)
        {
            if(a[i-1]==a[i])
            {
                dp[0][i]=dp[1][i-1];
                dp[1][i]=dp[0][i-1]+b[i];
            }
            else if(a[i-1]+1==a[i])
            {
                dp[0][i]=dp[0][i-1];
                dp[1][i]=min(dp[0][i-1],dp[1][i-1])+b[i];
            }
            else if(a[i-1]==a[i]+1)
            {
                dp[0][i]=min(dp[0][i-1],dp[1][i-1]);
                dp[1][i]=dp[1][i-1]+b[i];
            }
            else
            {
                dp[0][i]=min(dp[0][i-1],dp[1][i-1]);
                dp[1][i]=min(dp[0][i-1],dp[1][i-1])+b[i];
            }
        }
        cout<<min(dp[0][n],dp[1][n]);
        return 0;
}

出题人&题解编写人：shyyhs

D 数列统计
设 表示最大数为 , 长度为 的不下降正整数数列的个数。

由

看出 是杨辉三角的第 行，第 列

而杨辉三角第 行，第 列代表

易得出

而原问题可转为最大数为 , 长度为 的不下降正整数数列。

故原问题的公式为 。

#include <cstdio>
#include <cstdlib>
#include <iostream>
using namespace std;
typedef long long LL;
const int maxn = 2e6, mod = 911451407;

int re[maxn + 10], inv[maxn + 10], fac[maxn + 10];

inline void init(int n) {
    re[0] = inv[1] = fac[0] = re[1] = fac[1] = 1;
    for (int i = 2; i <= n; ++i) {
        fac[i] = (LL)fac[i - 1] * i % mod;
        inv[i] = (LL)(mod - mod / i) * inv[mod % i] % mod;
        re[i] = (LL)re[i - 1] * inv[i] % mod;
    }
}

inline int C(int a,int b) {
    if (a < 0) return 0;
    return (LL)fac[a] * re[b] % mod * re[a - b] % mod;
}

int main() {
    ios::sync_with_stdio(false), cin.tie(NULL), cout.tie(NULL);
    init(2e6);
    int T;
    cin >> T;
    int l, x;
    do {
        cin >> l >> x;
        --l;
        cout << C(l + x - 1, x - 1) << '\n';
    } while (--T);
    return 0;
}

出题人&题解编写人：情不知所起，一往而深 （巨佬%%%）