博客部分乱码，符号改为html的转义字符

A 夹娃娃

水题 前缀和
数据量过大 会T

#include
using namespace std;
typedef long long ll;
inline ll read() {
    ll s = 0, w = 1;
    char ch = getchar();
    while (ch  57) {
        if (ch == '-') w = -1;
        ch = getchar();
    }
    while (ch >= 48 && ch <= 57) s = (s << 1) + (s << 3) + (ch ^ 48), ch = getchar();
    return s * w;
}
const int N = 1e5 + 7;
const ll mod = 1e9 + 7;
ll w[N], n, k, l, r;
int main() {
    ll n = read(), k = read();
    for( int i = 1; i <= n; ++i) w[i] = read(); 
    for( int i = 2; i <= n; ++ i) w[i] += w[i-1];
    while (k--) {
        ll l = read(), r = read();
        printf("%lld\n",w[r]-w[l-1]);
    }
    return 0;
}

B 莫的难题

题意：给了五个数 1 、 2 、 3 、 5 、 9
这五个数任选几个任意位置组合，在所有组成数中，找出第 小的数
有10%的数据 n=m 就可以得到 ，所以直接输出1 就可水10分

思路：对组合数从小到大排序，对应的一位数有5个，二位数有25个，三位数有125个，以此类推 每增加一位数 对应的组成数的个数指数增长，而从小到大排序能够恰好对应于五进制的每一位对应的1 2 3 5 9这几个数
（语文太差，以上句子可能存在语病，难以理解还请见谅）
举个栗子：
五进制： 0 1 2 3 4 10 11 12
对应的组成数：1 2 3 5 9 11 12 13
即 个一位数，个两位数，个三位数，个四位数。
（有一个坑，10 的时候对应的并不是 21 而是 11，这里的每次进位 都会有类似的问题 ， 进位会导致错误， 消除进位可以用自减的方式）
来自大佬的一句很绕的话：五进制，但是起点是1，而不是0。

还有一个求组合数的过程 -> 套板子

（比赛想出来，但很可惜有一段时间没写过代码 五进制bug百出

代码

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

inline ll read() {
    ll s = 0, w = 1;
    char ch = getchar();
    while (ch < 48 || ch > 57) {
        if (ch == '-') w = -1;
        ch = getchar();
    }
    while (ch >= 48 && ch <= 57) s = (s << 1) + (s << 3) + (ch ^ 48), ch = getchar();
    return s * w;
}
const ll mod = 1e9 + 7;
const int maxn = 2e5+7;

//组合数 C(n,m)if (m < 0) return 0;
ll qkpow(ll a, ll b) {
    ll ans = 1;
    while (b) {
        if (b & 1) ans = ans * a % mod;
        a = a * a % mod;
        b >>= 1;
    }
    return ans;
}
ll getInv(ll a) {
    return qkpow(a, mod - 2);    //求一个数的逆元
}
ll C(ll n, ll m) {
    if (n < m) return 0;
    if (m > n - m) m = n - m;
    ll up = 1, down = 1;
    for (ll i = 0; i < m; i++) {
        up = up * (n - i) % mod;
        down = down * (i + 1) % mod;
    }
    return up * getInv(down) % mod;
}

char a[5]={'1','2','3','5','9'};

int main() {
    ll t = read();
    while(t--) {
        ll n = read(),m=read();
        ll tmp = C(n,m);
        string s="";
        while(tmp>0){
            --tmp;
            s+=a[tmp%5];
            tmp/=5;
        }
        reverse(s.begin(),s.end());
        cout<<s<<endl;
    }
}

C 不平衡数组

数据没卡到，假算法过了(

题意，一个长度为n的数组，相邻两个数相同，考虑将其中一个数+1，数+1 会付出一定的代价，每个数只能加一次，问在使数组中所有的数都不同的情况下所需消耗的最小代价

思路：dp，考虑 a[i] 与 a[i-1] 之间的关系
+1 与 不+1 的情况
dp[0] 不+1 的代价
dp[1] +1 的代价

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

inline ll read() {
    ll s = 0, w = 1;
    char ch = getchar();
    while (ch < 48 || ch > 57) {
        if (ch == '-') w = -1;
        ch = getchar();
    }
    while (ch >= 48 && ch <= 57) s = (s << 1) + (s << 3) + (ch ^ 48), ch = getchar();
    return s * w;
}
const int N=200005;
ll a[N],b[N];
ll dp[2][N];//考虑两种状态即使+1或者不+1对其的影响
int main() {
    ll n = read(),t;
    fill(dp[0]+1,dp[0]+n,0);
    fill(dp[1]+1,dp[1]+n,0);
    for(ll i=1; i<=n; i++) 
        a[i]=read(),b[i]=read();
    for(ll i=2; i<=n; i++)
        if(a[i-1] == a[i]) {             
            dp[0][i] = dp[1][i-1];       // a[i-1]+1 的代价作为 a[i] 不 +1 的代价 
            dp[1][i] = dp[0][i-1]+b[i];  // a[i] +1 
        }                                //之后类推 
        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;
}

D 数列统计

题意 一个非降序的以值为x结尾的序列
打表找规律（太菜了 没看出来， 参考大佬代码）
预处理

#include<bits/stdc++.h>
using namespace std;
const int N=2e6+1,mod=911451407;
int num[N],fac[N];
inline int C(int x,int y){
    int res=(1LL*num[x]*fac[y])%mod;
    res=(1LL*res*fac[x-y])%mod;
    return res;
}
int main(){
    num[0]=num[1]=fac[0]=fac[1]=1;
    for(int i=2;i<N;++i){
        num[i]=(1LL*num[i-1]*i)%mod;
        fac[i]=(1LL*fac[mod%i]*(mod-mod/i))%mod;
    }
    for(int i=2;i<N;++i){
        fac[i]=(1LL*fac[i-1]*fac[i])%mod;
    }
    int T=read();
    while(T--){
        int l=read(),x=read();
        printf("%d\n",C(x+l-2,x-1));
    }
    return 0;
}