2021-08-20 22:03 门头沟学院 C++

关注

题解 | 牛客练习赛87

中位数

设 ${a_1,a_2,...,a_n}$ 是升序的，若 ${k=n-1}$ ，则 ${m=1}$ ，答案为 ${\sum\limits_{i=1}^na_i}$ 。
否则，无论如何第 ${\lfloor\frac{m+1}{2}\rfloor}$ 小的数都不会是最后得到的数组中第 ${m}$ 小的数，此时只需把所有操作都加到第 ${m}$ 个。
时间复杂度 ${O(nlogn)}$ 。

#include<bits/stdc++.h>
#define inf 0x3f3f3f3f
using namespace std;
typedef long long ll;
const int N=2e5+5;
void ast(ll x,ll l,ll r){assert(x>=l&&x<=r);}
int n,k;
ll a[N];
int main()
{
    int t;scanf("%d",&t);
    ast(t,1,5);
    while(t--)
    {
        scanf("%d%d",&n,&k);
        ast(n,2,200000);
        for(int i=1;i<=n;i++) scanf("%lld",&a[i]),ast(a[i],1,200000);
        ast(k,1,n-1);
        sort(a+1,a+1+n);
        for(int i=n-k+1;i<=n;i++) a[n-k]+=a[i];
        n-=k;
        int m=(n+1)/2;
        printf("%lld\n",a[m]);
    }
}

k小数查询

由于 ${a_1,a_2,...,a_n}$ 是 ${1,2,...,n}$ 的排列，所以 $x$ 只出现一次。
设 ${x}$ 所在的位置为 ${pos}$ ，令 $l_i$ 为 ${[i,pos-1]}$ 中小于 ${x}$ 的数的个数， ${r_i}$ 为 ${[pos+1,i]}$ 中小于 ${x}$ 的个数。
答案为 ${\sum\limits_{i=1}^{pos-1}\sum\limits_{j=pos+1}^n[l_i+r_j=k-1]}+\sum\limits_{i=1}^{pos-1}[l_i==k]+\sum\limits_{i=pos+1}[r_i==k]$
用一个桶来计数 ${r_i}$ ，枚举 ${l_i}$ 即可。
时间复杂度 ${O(n)}$ 。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=2e5+5;
int n,x,k,a[N];
int vis[N];
ll sol(int x,int k)
{
    k--;
    ll ans=0;
    for(int i=1;i<=n;i++)
        if(a[i]==x)
        {
            int r=0;
            for(int j=i+1;j<=n;j++)
            {
                r+=a[j]<x;
                ans+=r==k;
                vis[r]++;
            }
            int l=0;
            for(int j=i-1;j>=1;j--)
            {
                l+=a[j]<x;
                ans+=l==k;
                if(l<=k) ans+=vis[k-l];
            }
        }
    return ans;
}
int main()
{
    scanf("%d%d%d",&n,&x,&k);
    assert(n>=1&&n<=200000);
    assert(x>=1&&x<=n);
    assert(k>=1&&k<=n);
    for(int i=1;i<=n;i++) scanf("%d",&a[i]),assert(a[i]>=1&&a[i]<=n);
    printf("%lld\n",sol(x,k));
}

牛老板

记忆化搜索，当 ${n}$ 较小时直接暴力。
当 ${n}$ 比较大时，设 ${f(n)}$ 为恰好凑出 ${n}$ 元需要的纸币数量，此时优先用面值为 ${6^x,9^y(6^x\le n,6^{x+1}>n,9^{y}\le n,9^{y+1}>n)}$ 的纸币，因为相对于用面值 ${6^t(t<x)}$ 的纸币，我们省了 ${6^{x-t}-1}$ 张纸币，对 ${9^t}$ 同理。

#include<bits/stdc++.h>
#define inf 0x3f3f3f3f
using namespace std;
typedef long long ll;
unordered_map<ll,int>f;
vector<ll>v6,v9;
int F(ll n)
{
    if(n==0||f[n]) return f[n];
    f[n]=inf;
    int pos=upper_bound(v6.begin(),v6.end(),n)-v6.begin()-1;
    if(pos>=0)
        f[n]=min(f[n],F(n-v6[pos])+1);
    pos=upper_bound(v9.begin(),v9.end(),n)-v9.begin()-1;
    if(pos>=0)
        f[n]=min(f[n],F(n-v9[pos])+1);
    if(n<=5) f[n]=min(f[n],F(n-1)+1);
    return f[n];
}
int main()
{
    for(ll x=6;x<=1000000000000ll;x*=6) v6.push_back(x);
    for(ll x=9;x<=1000000000000ll;x*=9) v9.push_back(x);
    int t;scanf("%d",&t);
    while(t--)
    {
        ll n;scanf("%lld",&n);
        printf("%d\n",F(n));
    }
}

小G的排列-加强版

可以发现 ${m\ge \lfloor\frac{n}{2}\rfloor}$ 这个条件非常耀眼。
考虑用总排列数减去含有大于等于 ${m+1}$ 的连续段的排列的数量。
可以发现长度大于等于 ${m+1}$ 的连续段在序列中最多只会出现一次。
记 ${sol(n,m)}$ 为所有长度为 ${n}$ 的排列中长度为 ${m}$ 的连续段的出现的总次数，有 ${sol(n,m)=(n-m+1)*(n-m+1)!*(1+(m>1))}$ 。
考虑一个排列 ${P}$ 中有一个长度为 ${k(k>\lfloor\frac{n}{2}\rfloor)}$ 的连续段，他恰好含有 $k-(m+1)+1$ 个长度为 ${m+1}$ 的连续段，含有 $k-(m+2)+1$ 个长度为 ${m+2}$ 的连续段（比长度为 ${m+1}$ 的连续段少一个），因此 ${sol(n,m+2)-sol(n,m+1)}$ 恰好为长度大于等于 ${m+1}$ 的连续段的个数。
因此答案为 ${n!-sol(n,m+1)+sol(n,m+2)}$ ，预处理阶乘后，可以 ${O(1)}$ 回答每个查询，时间复杂度 ${O(T)+O(n)}$ 。

#include<bits/stdc++.h>
#define inf 0x3f3f3f3f
using namespace std;
typedef long long ll;
const int N=10000005,mod=1e9+7;
ll f[N];
int n,m;
ll sol(int n,int m)
{
    if(m>n) return 0;
    return (n-m+1)*f[n-m+1]%mod*(m>1?2:1)%mod;
}
int main()
{
    f[0]=f[1]=1;
    for(int i=2;i<N;i++) f[i]=f[i-1]*i%mod;
    int t;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d%d",&n,&m);
        ll ans=f[n]-sol(n,m+1)+sol(n,m+2);
        ans=(ans%mod+mod)%mod;
        printf("%lld\n",ans);
    }
}

贪吃蛇

设 ${n}$ 条蛇的长度为 ${L_1,L_2,...,L_n}$ ，不妨蛇 ${L_1\le L_2\le...\le L_n}$ 。
我们看看在一瞬能发生什么： ${n-1}$ 条蛇被吃掉，剩下 ${1}$ 条蛇存活。
此时存活这条的蛇由于没蛇可吃，实际上也进入了冷却。
考虑如何吃蛇能让所有蛇变得尽可能的长。
第 ${n-1}$ 条吃掉第 ${n}$ 条，随后第 ${n-2}$ 条吃掉第 ${n-1}$ 条，...，最后第 ${1}$ 条吃掉第 ${2}$ 条。
这个时候第一条蛇变为最长，第二条第二长，...，第 ${n}$ 条第 ${n}$ 长。
模拟这个策略 ${\lfloor\frac{M}{L}\rfloor}+1$ 次即可得出答案。
但是这样复杂度太高，但这个过程可以通过构造一个矩阵来解决：
图片说明
这个矩阵乘法得到的 ${T}$ 仍然升序。
构造出矩阵后进行矩阵快速幂即可。

#include<bits/stdc++.h>
#define inf 0x3f3f3f3f
using namespace std;
typedef long long ll;
const int N=55,mod=1e9+7,MS=55;
int n,x,M,L[N];
struct Mat
{
    ll a[MS][MS];
    int n,m;
    Mat(int n=0,int m=0):n(n),m(m) {memset(a,0,sizeof(a));}
    Mat operator*(const Mat&B)const
    {
        Mat C(n,B.m);
        for(int i=1;i<=n;i++)
            for(int j=1;j<=B.m;j++)
                for(int k=1;k<=m;k++)
                C.a[i][j]=(C.a[i][j]+a[i][k]*B.a[k][j])%mod;
        return C;
    }
};
Mat qpow(Mat a,int n)
{
    Mat ans(a.n,a.n);
    for(int i=1;i<=a.n;i++) ans.a[i][i]=1;
    for(;n;n>>=1,a=a*a)
        if(n&1) ans=ans*a;
    return ans;
}
void ast(int x,int l,int r){assert(x>=l&&x<=r);}
int main()
{
    int t;scanf("%d",&t);
    ast(t,1,50);
    while(t--)
    {
        scanf("%d%d%d",&n,&x,&M);
        ast(n,1,50);
        ast(x,1,1000000);
        ast(M,1,1000000);
        for(int i=1;i<=n;i++) scanf("%d",&L[i]),ast(L[i],1,1000000);
        sort(L+1,L+1+n);
        reverse(L+1,L+1+n);
        M=M/x+1;
        Mat A(n,n);
        for(int i=1;i<=n;i++)
            for(int j=1;j<=n-i+1;j++)
            A.a[i][j]=1;
        A=qpow(A,M);
        ll ans=0;
        for(int i=1;i<=n;i++) ans=(ans+1ll*A.a[i][1]*L[i]%mod)%mod;
        printf("%lld\n",ans%mod);
    }
}

简洁的题面

对于一个固定的 ${d}$ ，考虑这个式子的组合意义：有 ${n}$ 个木板和 ${k}$ 种颜色，每个木板可以从 ${k}$ 种颜色里选一种颜色进行染色，或者不染色，有多少种方案使得每种颜色的出现次数都是 ${d}$ 的倍数 ${(\mod d=0)}$ 。 ${d}$ 和 ${k}$ 都比较小，于是可以用一个 ${d}$ 进制来表示染色状态，在各种状态之间建立转移边，再用矩阵快速幂加速计算。
具体的，设 $dp_{i,st_1,st_2,...,st_k}$ 为已经对第 ${1,2,...,i}$ 块木板染色，第 ${j(1\le j\le k)}$ 种颜色出现的数量 ${\mod d=st_j}$ ， $dp_{i,st_1,st_2,...,st_k}$ 可以转移到 $dp_{i+1,st_1,st_2,...,st_k}$
$dp_{i+1,(st_1+1)\mod d,st_2,...,st_k}$
$dp_{i+1,st_1,(st_2+1)\mod d,...,st_k}$
$...$
$dp_{i+1,st_1,st_2,...,(st_k+1)\bmod d}$
把 ${st_1,st_2,...,st_k}$ 压缩成 ${d}$ 进制状态，在转移之间建立有向边，问题等价于求图中状态 ${0}$ 到状态 ${0}$ 长度为 ${n}$ 的路径的数量。

#include<bits/stdc++.h>
#define inf 0x3f3f3f3f
using namespace std;
typedef long long ll;
int n,k,mod,g;
struct node
{
    ll a[27][27];
    int n;
    node(int n):n(n){memset(a,0,sizeof(a));}
    node operator*(const node&o)const
    {
        node ans(n);
        for(int i=0;i<n;i++)
            for(int j=0;j<n;j++)
            for(int k=0;k<n;k++)
            ans.a[i][j]=(ans.a[i][j]+a[i][k]*o.a[k][j])%mod;
        return ans;
    }
};
ll qpow(ll a,ll n)
{
    ll ans=1;
    for(;n;n>>=1,a=a*a%mod)
        if(n&1) ans=ans*a%mod;
    return ans;
}
node mqpow(node a,int n)
{
    node ans(a.n);
    for(int i=0;i<a.n;i++) ans.a[i][i]=1;
    for(;n;n>>=1,a=a*a)
        if(n&1) ans=ans*a;
    return ans;
}
int main()
{
    int t;scanf("%d",&t);
    while(t--)
    {
        scanf("%d%d%d%d",&n,&k,&mod,&g);
        ll ans=0;
        for(int d=1;d<=g;d++)
        {
            if(d==1) ans=(ans+qpow(k+1,n))%mod;
            else
            {
                int st=1;
                for(int i=1;i<=k;i++) st*=d;
                node A(st);
                for(int i=0;i<st;i++)
                {
                    A.a[i][i]=1;
                    for(int j=0,h=1;j<k;j++,h*=d)
                    {
                        int s=i/h%d;
                        int sst=i-s*h;
                        s=(s+1)%d;
                        sst+=s*h;
                        A.a[i][sst]=1;
                    }
                }
                A=mqpow(A,n);
                ans=(ans+A.a[0][0])%mod;
            }
        }
        printf("%lld\n",ans);
    }
}