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

A 夹娃娃

```#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]);
}
}```

B 莫的难题

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");
}

}```

C 不平衡数组

dp[0][i]表示到i位子,不使用+1,使得前i个相邻不相等的代价
dp[1][i]表示到i位子,使用+1,使得前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;
}```

D 数列统计

x\y 1 2 3 4 5 6 7 8 9 10 11 12
0 1 1 1 1 1 1 1 1 1 1 1 1
1 1 2 3 4 5 6 7 8 9 10 11
2 1 3 6 10 15 21 28 36 45 55
3 1 4 10 20 35 56 84 120 165
4 1 5 15 35 70 126 210 330
5 1 6 21 56 126 252 462
6 1 7 28 84 210 462
7 1 8 36 120 330
8 1 9 45 165
9 1 10 55
10 1 22
11 1

```#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;
}```

# 近期热帖

• 回复(25) 发表于 今天 10:45:52
• 回复(4) 发表于 今天 11:52:13
• 回复(0) 发表于 今天 16:30:02
• 回复(0) 发表于 今天 10:46:30

# 等你来战

• 报名截止时间：2020-08-13 00:00
• 报名截止时间：2020-08-13 00:00
• 报名截止时间：2020-08-14 23:55
• 报名截止时间：2020-08-14 00:00
• 报名截止时间：2020-08-14 00:00
• 报名截止时间：2020-08-13 22:00
• 报名截止时间：2020-08-13 22:00
• 报名截止时间：2020-08-13 22:00
• 报名截止时间：2020-08-14 22:00
• 报名截止时间：2020-08-16 18:00
• 报名截止时间：2020-08-18 21:30
• 报名截止时间：2020-08-21 22:00
• 报名截止时间：2020-08-22 22:00
• 报名截止时间：2020-08-25 22:00

# 热门推荐

• 扫描二维码，关注牛客网

• 下载牛客APP，随时随地刷题