嗯，这次比赛证明了，打得快不一定排名就高。。。qwq大佬们的程序跑得好快啊

A.夹娃娃

狂爆手速拿下一血，成就感++

题目就是给你个数列，让你求若干个区间的和。

直接预处理出前缀和，然后回答完事。。。

代码:

#include <bits/stdc++.h>
using namespace std;
const int N=1e5+1;
int s[N];
int main(){
    int n,k;
    scanf("%d%d",&n,&k);
    for(int i=1;i<=n;++i){
        scanf("%d",&s[i]);s[i]+=s[i-1];
    }
    while(k--){
        int l,r;
        scanf("%d%d",&l,&r);
        printf("%d\n",s[r]-s[l-1]);
    }
    system("pause");
    return 0;
}

哪怕加了快读快写，还是比大佬们的总用时都长

B.莫的难题

做这道题，只需要字典序学得好，懂排列组合初步就行了。。。

我们先预处理出所有的组合数的值（直接递推式，也就是做一遍杨辉三角就好了）

然后，我们现在就只需求最终第k小的字符串即可。

我们先枚举最终字符串的长度。

注意到，长度为1的有5个，长度为2的有25...长度为x的有个。

（每个位置5种选法，乘法原理相乘即可）

于是，我们找到最小的i，满足(也就是所有长度小于等于i的字符串的个数比k大了)

那么，第k小的字符串一定在这里面，又由于i是最小的，所以第k小的字符串长度即为i

然后，我们令(这个的意思是，第k小的字符串在所有长度为i的字符串中的排名)

我们设函数dfs(x,y)的作用是求出长度为y的字符串中排名为x的字符串（think function~）

那么，答案肯定就是dfs(p,i)了

现在，我们只需要实现这个函数即可。

实现dfs(x,y)

现在，我们开始愉快的枚举每一位。

我们由小到大枚举，即按照1,2,3,5,9的顺序枚举。

当我们枚举到1时，我们算下这一位为1时，剩下的位可以凑出几个串（由之前的推导可以知道，一共可以凑出个串）

我们比较下x和的大小关系。

若x小于等于它，那么，很明显的，我们要求的串肯定包含在当前位为1所形成的所有串中。

若x大于它，怎么办呢？很明显，要求的串肯定就不包含在里面了，那么，我们肯定就要枚举另一个数2了。

不过，需要注意的是，我们枚举2时，我们就相当于把开头为1的所有情况都忽视掉了，那么，我们需要求的串在忽略所有1开头的串后的所有串中的排名就会变化，因为舍弃的，以1为开头的串都会比之后的串小，所以，我们要求的串在忽略所有1开头的串后的所有的串的排名即为:,所以我们令即可（其实就是类似于用数据结构求kth）

然后，类似1的方法，我们依次枚举2,3,5,9即可。

那么，如果我们确定了当前位，之后怎么做呢？

肯定就是去枚举下一位辣！

做一遍dfs(x,y-1)即可。

当y=0时，return就好了

代码:

#include <bits/stdc++.h>
using namespace std;
const int mod=1e9+7;
const int N=101;
int C[N][N];int num[6]={0,1,2,3,5,9};
inline int ksm(int x,int y){
    int ans=1;
    while(y){
        if(y&1)ans*=x;
        x*=x;
        y>>=1;
    }
    return ans;
}
inline void print(int x,int lon){
    if(!lon)return;
    for(int i=1;i<=5;++i){
        int tot=ksm(5,lon-1);
        if(x<=tot){
            printf("%d",num[i]);
            print(x,lon-1);
            return;
        }else{
            x-=tot;
        }
    }
}
int main(){
    for(int i=1;i<N;++i){
        C[i][0]=C[i][i]=1;
    }
    for(int i=2;i<N;++i){
        for(int j=1;j<i;++j){
            C[i][j]=(C[i-1][j-1]+C[i-1][j])%mod;
        }
    }
    int T;
    scanf("%d",&T);
    while(T--){
        int n,m;
        scanf("%d%d",&n,&m);
        int tot=C[n][m],lon=0,sum=0,tp=1;
        for(int i=1;;++i){
            tp*=5;
            if(tp>=tot){
                lon=i;
                break;
            }
            tot-=tp;
        }
        print(tot,lon);putchar('\n');
    }
    system("pause");
    return 0;
}

C.不平衡数组

一开始太蠢了，以为是个带后悔的贪心

我们设dp[i][0/1]表示，保证前i个数合法的情况下，第i个数是否+1的最小花费

那么,我们只需要分当前的i是否+1，和i-1是否+1,来转移方程即可。

代码:

#include<bits/stdc++.h>
using namespace std;
const int N=2e5+1;
#define int long long
int a[N],b[N];
int dp[N][2];//前i个数符号，第i个数是否+1的最小代价
signed main(){
    int n;long long ans=0;
    scanf("%lld",&n);
    for(int i=1;i<=n;++i){
        scanf("%lld%lld",&a[i],&b[i]);
    }
    memset(dp,0x3f3f,sizeof(dp));
    dp[1][0]=0,dp[1][1]=b[1];
    for(int i=2;i<=n;++i){
        if(a[i]!=a[i-1]){
            dp[i][0]=min(dp[i][0],dp[i-1][0]);
        }
        if(a[i]!=a[i-1]+1){
            dp[i][0]=min(dp[i][0],dp[i-1][1]);
        }
        if(a[i]+1!=a[i-1]){
            dp[i][1]=min(dp[i][1],dp[i-1][0]+b[i]);
        }
        if(a[i]+1!=a[i-1]+1){
            dp[i][1]=min(dp[i][1],dp[i-1][1]+b[i]);
        }
    }
    printf("%lld",min(dp[n][0],dp[n][1]));
    return 0;
}

D.数列统计

通过打表发现，答案即为x-1维前缀和的第l个数，即C(x+l-2,x-1)

Ps:

0维前缀和的每一项都是1

k维前缀和()就是对k-1维前缀和再做一遍前缀和

咳咳，我们来推导下吧。。。

我们设表示以i()结尾，长度为j的数列的个数。

那么，明显有转移

（因为我们只能放一个i进去）

注意到，dp方程的递推式，和多维前缀和的递推式完全一样，并且，当j=1时，正好即为0维前缀和的值。

所以，我们带公式即可。

注意到T很大，n不是很大，所以我们预处理出所有的阶乘和逆元阶乘，然后回答即可

代码:

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