A-咪咪游戏

Solution

需要满足以下条件：

字符串长度为偶数。
奇数位是 $m$ ，偶数位是 $q$ 。

从前到后扫描一遍即可。

时间复杂度 $O(n)$ 。

Code

#include <iostream>
#include <cstdio>
#include <cstring>
const int maxn=1e5+10;
using namespace std;
int n,q;
char ch[maxn];
int main(){
    ios::sync_with_stdio(false);
    cin>>q;
    int x;
    while(q--){
        cin>>(ch+1);
        n=strlen(ch+1);
        if(n%2==1){
            cout<<"No"<<endl;
            continue;
        }
        x=1;
        for(int i=1;i<=n;i++)
            if((i%2==1&&ch[i]!='m')||(i%2==0&&ch[i]!='q')){
                x=0;
                break;
            }
        if(x)
            cout<<"Yes"<<endl;
        else
            cout<<"No"<<endl;
    }
    return 0;
}

B-三角形

Solution

依次处理每个序列。若当前处理到第 $i$ 个序列，在所有可能的和中只有前 $k$ 小的可能会对最终答案产生贡献。那么就可以及时剔除其他情况。此过程可以使用大根堆来维护，每次将当前序列和合并成一个大小为 $k$ 的数组即可。

关于合并两个数组得到新的和，使用的是经典的双指针法。

时间复杂度： $O(nk \log k)$ 。

Code

#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
const int maxn=1e6+10;
int ans,n,m,k,tot,a[maxn],b[maxn],c[maxn];
struct node{
    int x,y,z;
}heap[maxn<<1];
void up(int u){
    while(u>1){
        if(a[heap[u].x]+b[heap[u].y]<a[heap[u>>1].x]+b[heap[u>>1].y])
            swap(heap[u],heap[u>>1]);
        else
            break;
        u>>=1;
    }
}
void down(int u){
    int v=u<<1;
    while(v<=tot){
        if(v<tot&&a[heap[v+1].x]+b[heap[v+1].y]<a[heap[v].x]+b[heap[v].y])
            v++;
        if(a[heap[v].x]+b[heap[v].y]<a[heap[u].x]+b[heap[u].y])
            swap(heap[u],heap[v]);
        else
            break;
        u=v;
        v=u<<1;
    }
}
void insert(int i,int j,int q){
    heap[++tot].x=i;
    heap[tot].y=j;
    heap[tot].z=q;
    up(tot);
}
void extract(){
    heap[1]=heap[tot--];
    down(1);
}
int main(){
    ios::sync_with_stdio(false);
    cin>>n>>k;
    m=1;
    int len,cnt;
    for(int i=1;i<=n;i++){
        cin>>len;
        cnt=0;
        for(int j=1;j<=len;j++)
            cin>>b[j];
        sort(b+1,b+len+1);
        if(i==1)
            for(int j=1;j<=len;j++)
                a[j]=b[j];
        else{
            for(int j=1;j<=m;j++)
                for(int h=1;h<=len;h++)
                    c[++cnt]=a[j]+b[h];
            for(int j=1;j<=cnt;j++)
                a[j]=c[j];
            sort(a+1,a+cnt+1);
        }
        m*=len;
        if(m>=k){
            m=k,len=i;
            break;
        }
    }
    int u,v;
    for(int i=len+1;i<=n;i++){
        cin>>cnt;
        tot=0;
        for(int j=1;j<=cnt;j++)
            cin>>b[j];
        sort(b+1,b+cnt+1);
        insert(1,1,0);
        for(int j=1;j<=k;j++){
            u=heap[1].x;
            v=heap[1].y;
            c[j]=a[u]+b[v];
            if(v+1<=cnt)
                insert(u,v+1,1);
            if(!heap[1].z)
                insert(u+1,v,0);
            extract();
        }
        for(int j=1;j<=k;j++)
            a[j]=c[j];
    }
    for(int i=1;i<=k;i++)
        ans+=a[i];
    cout<<ans;
    return 0;
}

C-区间加

Solution

序列问题还是先想差分。设 $a_i$ 为第 $i$ 位还差多少到 $m$ ， $b$ 为 $a$ 的差分数组。之后依次考虑 $b_i$ ：

若 $b_i=-1$ ，则表明此处比上一处所需要的少 $1$ 。那么可以在 $i-1$ 处放置一个区间右端点。
若 $b_i=1$ ，则表明此处比上一处所需要的多 $1$ 。那么可以在 $i$ 处放置一个区间左端点。
若 $b_i=0$ ，则表明此处和上一处所需要的相等。那么可以在 $i-1$ 处放置一个区间左端点，在 $i$ 处放置一个区间右端点，也可以都不放。
若 $b_i<-1$ 或 $b_i>1$ ，显然不可能成功。

所以只需要维护一个变量记录当前未匹配的左端点个数，再根据乘法原理更新答案即可。

时间复杂度： $O(n)$ 。

Code

#include <iostream>
#include <cstdio>
#include <algorithm>
#define ll long long
using namespace std;
const int mod=998244355;
const int maxn=2e3+10;
int n,m,sum,a[maxn],b[maxn];
ll ans=1;
int main(){
    ios::sync_with_stdio(false);
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        a[i]=m-a[i];
    }
    for(int i=1;i<=n+1;i++)
        b[i]=a[i]-a[i-1];
    for(int i=1;i<=n+1;i++){
        if(b[i]>1||b[i]<-1){
            ans=0;
            break;
        }
        else if(b[i]==1)
            sum++;
        else if(!b[i])
            ans=(ans*(sum+1))%mod;
        else
            ans=(ans*sum)%mod,sum--;
    }
    cout<<ans;
    return 0;
}

D-多元组

Solution

显然是一道 $dp$ 题。设 $f_{i,j}$ 表示前 $i$ 个数组成 $j$ 元组的方案数，那么有

$f_{i,j}= \sum\limits_{k=1}^{i-1} f_{k,j-1} (a_k<a_i)$

然后发现这个前缀可以用树状数组维护：设 $c_{i,j}$ 为小于 $i$ 的数所能组成的 $j$ 元组的数量。将数据离散化即可。

时间复杂度： $O(mn \log n)$ 。

Code

#include <iostream>
#include <cstdio>
#include <algorithm>
#define ll long long
using namespace std;
const ll maxn=1e5+10;
const ll mod=1e9+7;
ll n,m,len,a[maxn],b[maxn],c[maxn],ans[maxn][52],t[maxn][52];
ll gtid(ll x){
    ll l=1,r=len,mid;
    while(l<r){
        mid=(l+r)>>1;
        if(c[mid]<x)
            l=mid+1;
        else
            r=mid;
    }
    return l;
}
ll lowbit(ll x){
    return x&(-x);
}
ll ask(ll x,ll y){
    ll sum=0;
    for(;x>0;x-=lowbit(x))
        sum=(sum+t[x][y])%mod;
    return sum;
}
void add(ll x,ll y,ll z){
    for(;x<=len;x+=lowbit(x))
        t[x][y]=(t[x][y]+z)%mod;
}
int main(){
    ios::sync_with_stdio(false);
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        b[i]=a[i];
    }
    sort(b+1,b+n+1);
    for(int i=1;i<=n;i++)
        if(b[i]!=b[i-1]||i==1)
            c[++len]=b[i];
    for(int i=1;i<=n;i++)
        ans[i][1]=1;
    ll x;
    for(int i=1;i<=n;i++){
        x=gtid(a[i]);
        add(x,1,1);
        for(int j=2;j<=m;j++){
            ans[i][j]=(ans[i][j]+ask(x-1,j-1))%mod;
            add(x,j,ans[i][j]);
        }
    }
    ll sum=0;
    for(int i=1;i<=n;i++)
        sum=(sum+ans[i][m])%mod;
    cout<<sum;
    return 0;
}

【比赛】牛客OI周赛15-普及组

A-咪咪游戏

Solution

Code

B-三角形

Solution

Code

C-区间加

Solution

Code

D-多元组

Solution

Code