牛客IOI周赛17-普及组 题解
嗯，这次比赛证明了，打得快不一定排名就高。。。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;
}
