牛客IOI周赛17-普及组

A.夹娃娃

Solution

前缀和裸题

Code

#include<bits/stdc++.h>
#define fi first
#define se second
#define mp make_pair
using namespace std;
typedef long long ll;
typedef pair<int,int>P;
const double eps = 1e-8;
const int NINF = 0xc0c0c0c0;
const int INF  = 0x3f3f3f3f;
const ll  mod  = 1e9 + 7;
const ll  N = 1e5 + 5;

int w[N],pre[N],n,k;

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin>>n>>k;
    for(int i=1;i<=n;i++){
        cin>>w[i];
        pre[i]=pre[i-1]+w[i];
    }
    for(int i=1;i<=k;i++){
        int l,r;cin>>l>>r;
        cout<<pre[r]-pre[l-1]<<'\n';
    }
    return 0;
}

B.莫的难题

Solution

容易发现 $cnt_{len_i}=5\times cnt_{len_{i-1}}$
虽然答案是由 $1、2、3、5、9$ 构成的，但是本质是五进制的数， $0→4$ 分别对应 $1→9$ 。
假设答案长度为 $n$ ，则 $C_n^m-\sum_{i=1}^{n-1}cnt_i-1$ 之后转换为五进制的数，对应输出即可。
下面的代码预处理了 $C[n][m]$ 和 $f[n]$ (长度贡献值的前缀和)。

Code

#include<bits/stdc++.h>
#define fi first
#define se second
#define mp make_pair
using namespace std;
typedef long long ll;
typedef pair<int,int>P;
const double eps = 1e-8;
const int NINF = 0xc0c0c0c0;
const int INF  = 0x3f3f3f3f;
const ll  mod  = 1e9 + 7;
const ll  N = 1e2 + 5;

ll f[20],C[N][N];
int u[6]={1,2,3,5,9};

void init(){
    for(int i=0;i<=100;i++){
        for(int j=0;j<=i;j++){
            if(j==0 || j==i) C[i][j]=1;
            else C[i][j]=(C[i-1][j-1]+C[i-1][j])%mod;
        }
    }
    ll base=5;
    for(int i=1;i<=15;i++){
        f[i]=f[i-1]+base;
        if(f[i]>mod) break;
        base=base*5;
    }
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    int T;cin>>T;
    init();
    while(T--){
        ll n,m;
        cin>>n>>m;
        ll k=C[n][m];
        int id=0;
        for(int i=1;i<=13;i++) if(f[i]<k) id=i;
        k-=f[id]+1;
        ll t=k;
        int a[15]={0},cnt=0;
        while(t>0){
            a[++cnt]=t%5;
            t/=5;
        }
        for(int i=id+1;i>=1;i--) cout<<u[a[i]];
        cout<<'\n';
    }
    return 0;
}

C-不平衡数组

Solution

01dp
考虑取和不取两种情况。 $f[i][0/1]$ 表示第i位不加1和加1的情况。

$a[i]=a[i-1]:\quad f[i][0]=f[i-1][1] \quad f[i][1]=f[i-1][0]+b[i]$
$a[i]+1=a[i-1]:\quad f[i][0]=min(f[i-1][0],f[i-1][1])\quad f[i][1]=f[i-1][1]+b[i]$
$a[i]=a[i-1]+1):\quad f[i][0]=f[i-1][0]\quad f[i][1]=min(f[i-1][1],f[i-1][0])+b[i]$
其他情况 $:\quad f[i][0]=min(f[i-1][0],f[i-1][1])\quad f[i][1]=min(f[i-1][0],f[i-1][1])+b[i]$

Code

#include<bits/stdc++.h>
#define fi first
#define se second
#define mp make_pair
using namespace std;
typedef long long ll;
typedef pair<int,int>P;
const double eps = 1e-8;
const int NINF = 0xc0c0c0c0;
const int INF  = 0x3f3f3f3f;
const ll  mod  = 1e9 + 7;
const ll  N = 1e6 + 5;

ll n,a[N],b[N],f[N][2];

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin>>n;
    for(int i=1;i<=n;i++) cin>>a[i]>>b[i];
    f[1][0]=0,f[1][1]=b[1];
    for(int i=2;i<=n;i++){
        if(a[i]==a[i-1]){
            f[i][0]=f[i-1][1];
            f[i][1]=f[i-1][0]+b[i];
        }
        else if(a[i]+1==a[i-1]){
            f[i][0]=min(f[i-1][0],f[i-1][1]);
            f[i][1]=f[i-1][1]+b[i];
        }
        else if(a[i]==a[i-1]+1){
            f[i][0]=f[i-1][0];
            f[i][1]=min(f[i-1][1],f[i-1][0])+b[i];
        }else{
            f[i][0]=min(f[i-1][0],f[i-1][1]);
            f[i][1]=min(f[i-1][0],f[i-1][1])+b[i];
        }
    }
    cout<<min(f[n][0],f[n][1])<<'\n';
    return 0;
}

D-数列统计

Solution

设 $f[x][l]$ 表示以x结尾，长度为l的数列个数。

$l=1:f[x][l]=1$
$l\ge 1:f[x][l]=f[x-1][l]+f[x][l-1]$

数据量较大:预处理组合数前缀积和逆元的前缀积。(这里方法是参考Lskkkno1的

由递推式打表找规律得到答案为 $C_{l+x-2}^{x-1}$ 。
顺便问下有没有数学方法，就稍微严谨一点的方法可以由递推式推出结论的？

Code

#include<bits/stdc++.h>
#define fi first
#define se second
#define mp make_pair
using namespace std;
typedef long long ll;
typedef pair<int,int>P;
const double eps = 1e-8;
const int NINF = 0xc0c0c0c0;
const int INF  = 0x3f3f3f3f;
const ll  mod  = 911451407;
const ll  N = 2e6 + 5;

ll fac[N+5],ifac[N+5];

ll qpow(ll a,ll b){
    ll res=1;
    while(b>0){
        if(b&1) res=res*a%mod;
        a=a*a%mod;
        b>>=1;
    }
    return res;
}

inline ll perm(ll x,ll y){return fac[x]*ifac[x-y]%mod;}
inline ll comb(ll x,ll y){return perm(x,y)*ifac[y]%mod;}

void init(){
    fac[0]=1;
    for(int i=1;i<=N;i++) fac[i]=1ll*i*fac[i-1]%mod;
    ifac[N]=qpow(fac[N],mod-2);
    for(int i=N;i;i--) ifac[i-1]=1ll*i*ifac[i]%mod;
}

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