竞赛讨论区 > 【题解/标程】2022牛客寒假算法基础集训营 1 题解+标程
头像
FriedChicken
编辑于 2022-02-05 23:40
+ 关注

【题解/标程】2022牛客寒假算法基础集训营 1 题解+标程

题解pdf现在在群(477641458)的群文件中(更新:群满了,现在进975214176),过几天也会把题解挂到这个帖子里。

更新:题解pdf

更新:B站讲题视频

这里主要给出一些标程,来自于我或某位验题人(有的题我的代码太丑陋了,就放验题人的了),欢迎对照题解查看。

A 九小时九个人九扇门

#include<bits/stdc++.h>
#define fors(i,a,b) for(int i = a; i < b; ++i)
#define ll long long
#define mid ((l+r)>>1)
#define lson rt<<1, l, mid
#define rson rt<<1|1, mid+1, r
#define all(x) x.begin(),x.end()
#define pb push_back
using namespace std;
const int maxn = 1e5+5;
int f[maxn][9];
const int mod = 998244353;
int main(){
    int n; cin>>n;
    f[0][0] = 1;
    fors(i,1,n+1){
        int x; scanf("%d", &x); x %= 9;
        fors(j,0,9){
            f[i][(j+x)%9] = (f[i][(j+x)%9] + f[i-1][j])%mod;
            f[i][j] = (f[i][j]+f[i-1][j])%mod;
        }
    }
    fors(i,1,9) cout<<f[n][i]<<" "; cout<<f[n][0]-1<<endl;
    return 0;
}

DP数组含义与题解中相同。

B 炸鸡块君与FIFA22

#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,n) for(int i=a;i<=n;i++)
#define per(i,a,n) for(int i=n;i>=a;i--)
#define pb push_back
#define SZ(v) ((int)v.size())
#define fs first
#define sc second
typedef long long ll;
typedef double db;
typedef pair pii;
int n,q,st[3][200010][21];
char s[200010];
int mod3(int x){
    return (x%3+3)%3;
}
int main(){
    cin>>n>>q;
    scanf("%s",s+1);
    rep(j,0,20){
        rep(i,1,n){
            if(j==0){
                if(s[i]=='W'){
                    st[0][i][j]=st[1][i][j]=st[2][i][j]=1;
                }
                if(s[i]=='L'){
                    st[1][i][j]=st[2][i][j]=-1;
                    st[0][i][j]=0;
                }
                if(s[i]=='D'){
                    st[0][i][j]=st[1][i][j]=st[2][i][j]=0;
                }
            }
            else{
                int p1=i,p2=i+(1<<(j-1));
                if(p2>n){
                    st[0][p1][j]=st[0][p1][j-1];
                    st[1][p1][j]=st[1][p1][j-1];
                    st[2][p1][j]=st[2][p1][j-1];
                }
                else{
                    st[0][p1][j]=st[0][p1][j-1]+st[mod3(0+st[0][p1][j-1])][p2][j-1];
                    st[1][p1][j]=st[1][p1][j-1]+st[mod3(1+st[1][p1][j-1])][p2][j-1];
                    st[2][p1][j]=st[2][p1][j-1]+st[mod3(2+st[2][p1][j-1])][p2][j-1];
                }
            }
        }
    }
    int l,r,ans;
    rep(_,1,q){
        scanf("%d%d%d",&l,&r,&ans);
        int pos=l;
        while(pos<=r){
            int j=0;
            while(pos+(1<<j)-1<=r)    j++;
            j--;
            ans+=st[ans%3][pos][j];
            pos+=(1<<j);
        }
        printf("%d\n",ans);
    }
    return 0;
}

st数组含义与题解相同,rep是上面宏定义的for()循环简写(希望你不是很讨厌这种写法)。

C Baby's first attempt on CPU

#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,n) for(int i=a;i<=n;i++)
#define per(i,a,n) for(int i=n;i>=a;i--)
#define pb push_back
#define SZ(v) ((int)v.size())
#define fs first
#define sc second
typedef long long ll;
typedef double db;
typedef pair<int,int> pii;
int n,le[110],a[110][5],res[1010],p;
int main(){
    cin>>n;
    rep(i,1,n){
        le[i]=4;
        rep(j,1,3){
            scanf("%d",&a[i][j]);
            if(a[i][j])    le[i]=min(le[i],j);
        }
    }
    rep(i,1,n){
        if(le[i]!=4){
            int j=p;
            while(res[j]!=i-le[i])    j--;
//            printf("%d %d\n",i,j);
            int add=3-(p-j);
            rep(j,1,add)    res[++p]=0;
        }
        res[++p]=i;
    }
    printf("%d\n",p-n);
    return 0;
}

res[]数组维护新的程序,res[i]=0表示这是一条空语句,否则res[i]=x表示这是源程序中第x条语句。

D 牛牛做数论

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll prime[20]={0,2,3,5,7,11,13,17,19,23,29,31,37,41};
ll n,t;
inline bool isP(int x){
    if(x<=3)    return true;
    for(int i=2;i*i<=n;i++){
        if(n%i==0)    return false;
    }
    return true;
}
int main(){
    cin>>t;
    while(t--){
        cin>>n;
        assert(n!=0);
        ll now=1,i=1;
        if(n==1){
            puts("-1");
            continue;
        }
        while(now*prime[i]<=n){
            now*=prime[i];
            i++;
        }
        printf("%lld ",now);
        while(!isP(n)){
            n--;
        }
        printf("%lld\n",n);
    }
    return 0;
}

E 炸鸡块君的高中回忆

#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,n) for(int i=a;i<=n;i++)
#define per(i,a,n) for(int i=n;i>=a;i--)
#define pb push_back
#define SZ(v) ((int)v.size())
#define fs first
#define sc second
typedef long long ll;
typedef double db;
typedef pair<int,int> pii;
int T,n,m;
int main(){
    cin>>T;
    while(T--){
        scanf("%d%d",&n,&m);
        if(m==1){
            if(n==1)    puts("1");
            else    puts("-1");
        }
        else{
            printf("%d\n",((n-1)/(m-1)+((n-1)%(m-1)!=0))*2-1);
        }
    }
    return 0;
}

F 中位数切分

#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,n) for(int i=a;i<=n;i++)
#define per(i,a,n) for(int i=n;i>=a;i--)
#define pb push_back
#define SZ(v) ((int)v.size())
#define fs first
#define sc second
typedef long long ll;
typedef double db;
typedef pair<int,int> pii;
int T,n,m;
int a[100010];
int main(){
    cin>>T;
    while(T--){
        scanf("%d%d",&n,&m);
        int ans=0;
        rep(i,1,n){
            scanf("%d",&a[i]);
            if(a[i]>=m)    ans++;
            else    ans--;
        }
        if(ans>0)    printf("%d\n",ans);
        else    puts("-1");
    }
    return 0;
}

↑题解中的简单方法;

#include<bits/stdc++.h>

using ll = long long;
using ld = long double;

namespace GTI
{
    char gc(void)
       {
        const int S = 1 << 16;
        static char buf[S], *s = buf, *t = buf;
        if (s == t) t = buf + fread(s = buf, 1, S, stdin);
        if (s == t) return EOF;
        return *s++;
    }
    ll gti(void)
       {
        ll a = 0, b = 1, c = gc();
        for (; !isdigit(c); c = gc()) b ^= (c == '-');
        for (; isdigit(c); c = gc()) a = a * 10 + c - '0';
        return b ? a : -a;
    }
    int gts(char *s)
       {
        int len = 0, c = gc();
        for (; isspace(c); c = gc());
        for (; c != EOF && !isspace(c); c = gc()) s[len++] = c;
        s[len] = 0;
        return len;
    }
    int gtl(char *s)
       {
        int len = 0, c = gc();
        for (; isspace(c); c = gc());
        for (; c != EOF && c != '\n'; c = gc()) s[len++] = c;
        s[len] = 0;
        return len;
    }
}
using GTI::gti;
using GTI::gts;
using GTI::gtl;

const int inf = 0x3f3f3f3f;
struct BIT
{
    std::vector<int> f;
    int n;
    void init(int n)
    {
        this->n = n;
        f.resize(n);
        std::fill(f.begin(), f.end(), -inf);
    }
    void insert(int loc, int val)
    {
        if (loc == 0) f[0] = std::max(f[0], val);
        else
            for (int i = loc; i < n; i += i & -i)
                f[i] = std::max(f[i], val);
    }
    int query(int loc)
    {
        if (loc < 0) return -inf;
        int ret = f[0];
        for (int i = loc; i; i -= i & -i)
            ret = std::max(ret, f[i]);
        return ret;
    }
}tr;

const int N = 1e5 + 500;
int a[N], f[N];
int main(void)
{
    for (int T = gti(); T; T--)
    {
        int n = gti(), m = gti();
        for (int i = 1; i <= n; i++)
            a[i] = (gti() >= m ? 1 : -1) + a[i - 1];

        {
            std::vector<int> val;
            for (int i = 0; i <= n; i++)
                val.push_back(a[i]);
            std::sort(val.begin(), val.end());
            val.erase(std::unique(val.begin(), val.end()), val.end());
            for (int i = 0; i <= n; i++)
                a[i] = lower_bound(val.begin(), val.end(), a[i]) - val.begin();
            tr.init(val.size());
        }

        tr.insert(a[0], 0);
        for (int i = 1; i <= n; i++)
        {
            f[i] = tr.query(a[i] - 1) + 1;
            tr.insert(a[i], f[i]);
        }
        if (f[n] < 0) puts("-1");
        else printf("%d\n", f[n]);
    }
    return 0;
}

↑题解中树状数组优化dp的麻烦方法。

G ACM is all you need

#include<bits/stdc++.h>
#define fors(i,a,b) for(int i = a; i < b; ++i)
#define ll long long
#define mid ((l+r)>>1)
#define lson rt<<1, l, mid
#define rson rt<<1|1, mid+1, r
#define all(x) x.begin(),x.end()
#define pb push_back
using namespace std;
int sg(int x){
    if(x == 0) return 0;
    if(x<0) return -1;
    return 1;
}
int main(){
    int T; cin>>T; assert(T <= 1e4 && T > 0);
    int sumn = 0;
    while(T--){
        int n; scanf("%d", &n); sumn += n;
        assert(n <= 1e5 && n > 0);
        vector<int> f(n);
        fors(i,0,n) scanf("%d", &f[i]);
        vector<int> t1, t2;
        vector<int> cc;
        int cnt = 0;
        fors(i,1,n-1){
            if(f[i]>f[i-1] && f[i]>f[i+1]){
                int d = f[i]-max(f[i-1], f[i+1]);
                int up = max(f[i-1],f[i+1]) + d/2+1;
                t1.pb(up); cc.pb(up); 
            }
            else if(f[i] < min(f[i-1], f[i+1]) ) {
                int d = min(f[i-1], f[i+1])-f[i];
                int up = f[i]+(d+1)/2;
                t2.pb(up); cc.pb(up);
                cnt++;
            }else if(min(f[i-1], f[i+1]) < f[i] && max(f[i-1], f[i+1]) > f[i] ){
                int l = min(f[i-1], f[i+1]);
                int r = max(f[i-1], f[i+1]);
                int L = l+ (f[i]-l)/2 + 1;
                int R = f[i]+(r-f[i]+1)/2;
                if(L <= R) {t1.pb(L), t2.pb(R);}
            }
        }
        for(int x:t1) cc.pb(x); for(int x:t2) cc.pb(x);
        sort(all(cc)); cc.erase(unique(all(cc)), cc.end());
        vector<int> d(cc.size());
        for(int x:t1){
            // cout<<"x1:"<<x<<endl;
            int p = lower_bound(all(cc), x)-cc.begin(); d[p]++;
        }
        for(int x:t2){
            // cout<<"x2:"<<x<<endl;
            int p = lower_bound(all(cc), x)-cc.begin(); d[p]--;
        }
        int ans = cnt;
        fors(i,1,d.size()) d[i]+=d[i-1];
        for(int x:d) ans = min(ans, cnt+x);
        cout<<ans<<endl;
    }
    assert(sumn <= 1e6 && sumn > 0);
    return 0;
}

这里是将题解中提到预处理出来的所有区间放到中、放到中,然后解区间覆盖问题。

H 牛牛看云

#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,n) for(int i=a;i<=n;i++)
#define per(i,a,n) for(int i=n;i>=a;i--)
#define pb push_back
#define SZ(v) ((int)v.size())
#define fs first
#define sc second
typedef long long ll;
typedef double db;
typedef pair<int,int> pii;
int n;
int a[1000010];
ll cnt[1010];
int main(){
    cin>>n;
    rep(i,1,n){
        scanf("%d",&a[i]);
        cnt[a[i]]++;
    }
    ll ans=0;
    rep(i,0,1000){
        rep(j,i,1000){
            ll add;
            if(i==j)    add=(cnt[i]+cnt[i]*(cnt[i]-1ll)/2ll);
            else    add=cnt[i]*cnt[j];
            ans=ans+add*(ll)abs(i+j-1000);
        }
    }
    printf("%lld\n",ans);
    return 0;
}

add表示当前的(i,j)对儿贡献了多少次。

I B站与各唱各的

#include<stdio.h>
#include<algorithm>
#include<vector>
#include<cmath>
using namespace std;
const int P = 1000000007;
int ksm(int x,int k) {
    int ans=1;
    while (k) {
        if (k&1) ans=1ll*ans*x%P;
        x=1ll*x*x%P;
        k>>=1;
    }
    return ans;
}
int inv(int x) {
    return ksm(x,P-2);
}
void solve()
{
    int n,m;
    scanf("%d%d",&n,&m);
    printf("%lld\n",1ll*(ksm(2,n-1)-1)*inv(ksm(2,n-1))%P*m%P);
}
int main()
{
    int t;
    scanf("%d",&t);
    while (t--) solve();
}

J 小朋友做游戏

#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,n) for(int i=a;i<=n;i++)
#define per(i,a,n) for(int i=n;i>=a;i--)
#define pb push_back
#define SZ(v) ((int)v.size())
#define fs first
#define sc second
typedef long long ll;
typedef double db;
typedef pair<int,int> pii;
int T,A,B,n;
int va[10010],vb[10010];
bool cmp(int xx,int yy){
    return xx>yy;
}
int suma[10010],sumb[10010];
int main(){
    cin>>T;
    while(T--){
        cin>>A>>B>>n;
        rep(i,1,A)    scanf("%d",&va[i]);
        rep(i,1,B)    scanf("%d",&vb[i]);
        int mxb=min(n/2,B);
        if(A+mxb<n){
            puts("-1");
            continue;
        }
        sort(va+1,va+1+A,cmp);
        sort(vb+1,vb+1+B,cmp);
        rep(i,1,A)    suma[i]=suma[i-1]+va[i];
        rep(i,1,B)    sumb[i]=sumb[i-1]+vb[i];
        int ans=-1;
        rep(ia,0,A){
            int ib=n-ia;
            if(ib>mxb||ib<0)    continue;
            ans=max(ans,suma[ia]+sumb[ib]);
        }
        assert(ans!=-1);
        printf("%d\n",ans);
    }
    return 0;
}

K 冒险公社

简约美版本:

#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,n) for(int i=a;i<=n;i++)
#define per(i,a,n) for(int i=n;i>=a;i--)
#define pb push_back
#define SZ(v) ((int)v.size())
#define fs first
#define sc second
typedef long long ll;
typedef double db;
typedef pair<int,int> pii;
int n;
// 0G 1B 2R
int dp[100010][27];
const int inf=-1e6;
char s[100010];
int cnt(int x){
    int g=(x%3==0)+(x/3%3==0)+(x/9%3==0);
    int r=(x%3==2)+(x/3%3==2)+(x/9%3==2);
    return g-r;
}
int main(){
    scanf("%d%s",&n,s+1);
    rep(i,0,n+5){
        rep(j,0,26)    dp[i][j]=inf;
    }
    rep(j,0,26){
        if(s[3]=='G'&&cnt(j)<=0)    continue;
        if(s[3]=='B'&&cnt(j)!=0)    continue;
        if(s[3]=='R'&&cnt(j)>=0)    continue;
        dp[3][j]=(j%3==0)+(j/3%3==0)+(j/9%3==0);
    }
    rep(i,4,n){
        rep(j,0,26){
            if(s[i]=='G'&&cnt(j)<=0)    continue;
            if(s[i]=='B'&&cnt(j)!=0)    continue;
            if(s[i]=='R'&&cnt(j)>=0)    continue;
            rep(k,0,26){
                if(k%3==j/3%3&&k/3%3==j/9%3){
                    dp[i][j]=max(dp[i][j],dp[i-1][k]+(j%3==0));
                }
            }
        }
    }
    int ans=inf;
    rep(j,0,26)    ans=max(ans,dp[n][j]);
    if(ans<0)    puts("-1");
    else    printf("%d\n",ans);
    return 0;
}

暴力美学版本:

#include<iostream>
#include<string.h>
using namespace std;
int f[100010][4][4][4];//在i前三个为j k p的绿色个数
int main()
{
    int n;
    string s;
    cin>>n;
    cin>>s;
    s=" "+s;
    // hei hong lv
    memset(f,-1,sizeof f);
    if(s[n]=='G')
        {
            f[n][1][1][1]=3;
            f[n][1][1][3]=2;
            f[n][1][3][1]=2;
            f[n][3][1][1]=2;
            f[n][1][1][2]=2;
            f[n][1][2][1]=2;
            f[n][2][1][1]=2;
            f[n][1][3][3]=1;
            f[n][3][1][3]=1;
            f[n][3][3][1]=1;
        }
        if(s[n]=='R')
        {
            f[n][2][2][2]=0;
            f[n][2][2][3]=0;
            f[n][2][3][2]=0;
            f[n][3][2][2]=0;
            f[n][2][2][1]=1;
            f[n][2][1][2]=1;
            f[n][1][2][2]=1;
            f[n][2][3][3]=0;
            f[n][3][2][3]=0;
            f[n][3][3][2]=0;
        }
        if(s[n]=='B')
        {
            f[n][3][3][3]=0;
            f[n][3][1][2]=1;
            f[n][3][2][1]=1;
            f[n][1][3][2]=1;
            f[n][2][3][1]=1;
            f[n][2][1][3]=1;
            f[n][1][2][3]=1;
        }
    for(int i=n-1;i>=3;i--)
    {
        if(s[i]=='G')
        {
            for(int j=1;j<=3;j++)
            {
            if(f[i+1][1][1][j]!=-1)f[i][1][1][1]=max(f[i][1][1][1],f[i+1][1][1][j]+1);
            if(f[i+1][1][3][j]!=-1)f[i][1][1][3]=max(f[i][1][1][3],f[i+1][1][3][j]+1);
            if(f[i+1][3][1][j]!=-1)f[i][1][3][1]=max(f[i][1][3][1],f[i+1][3][1][j]+1);
            if(f[i+1][1][1][j]!=-1)f[i][3][1][1]=max(f[i][3][1][1],f[i+1][1][1][j]);
            if(f[i+1][1][2][j]!=-1)f[i][1][1][2]=max(f[i][1][1][2],f[i+1][1][2][j]+1);
            if(f[i+1][2][1][j]!=-1)f[i][1][2][1]=max(f[i][1][2][1],f[i+1][2][1][j]+1);
            if(f[i+1][1][1][j]!=-1)f[i][2][1][1]=max(f[i][2][1][1],f[i+1][1][1][j]);
            if(f[i+1][3][3][j]!=-1)f[i][1][3][3]=max(f[i][1][3][3],f[i+1][3][3][j]+1);
            if(f[i+1][1][3][j]!=-1)f[i][3][1][3]=max(f[i][3][1][3],f[i+1][1][3][j]);
            if(f[i+1][3][1][j]!=-1)f[i][3][3][1]=max(f[i][3][3][1],f[i+1][3][1][j]);    
            }
        }
        if(s[i]=='R')
        {
            for(int j=1;j<=3;j++)
            {
            if(f[i+1][2][2][j]!=-1)f[i][2][2][2]=max(f[i][2][2][2],f[i+1][2][2][j]+0);
            if(f[i+1][2][3][j]!=-1)f[i][2][2][3]=max(f[i][2][2][3],f[i+1][2][3][j]+0);
            if(f[i+1][3][2][j]!=-1)f[i][2][3][2]=max(f[i][2][3][2],f[i+1][3][2][j]+0);
            if(f[i+1][2][2][j]!=-1)f[i][3][2][2]=max(f[i][3][2][2],f[i+1][2][2][j]+0);
            if(f[i+1][2][1][j]!=-1)f[i][2][2][1]=max(f[i][2][2][1],f[i+1][2][1][j]);
            if(f[i+1][1][2][j]!=-1)f[i][2][1][2]=max(f[i][2][1][2],f[i+1][1][2][j]);
            if(f[i+1][2][2][j]!=-1)f[i][1][2][2]=max(f[i][1][2][2],f[i+1][2][2][j]+1);
            if(f[i+1][3][3][j]!=-1)f[i][2][3][3]=max(f[i][2][3][3],f[i+1][3][3][j]+0);
            if(f[i+1][2][3][j]!=-1)f[i][3][2][3]=max(f[i][3][2][3],f[i+1][2][3][j]+0);
            if(f[i+1][3][2][j]!=-1)f[i][3][3][2]=max(f[i][3][3][2],f[i+1][3][2][j]+0);    
            }
        }
        if(s[i]=='B')
        {
            for(int j=1;j<=3;j++)
            {
            if(f[i+1][3][3][j]!=-1)f[i][3][3][3]=max(f[i][3][3][3],f[i+1][3][3][j]);
            if(f[i+1][1][2][j]!=-1)f[i][3][1][2]=max(f[i][3][1][2],f[i+1][1][2][j]);
            if(f[i+1][2][1][j]!=-1)f[i][3][2][1]=max(f[i][3][2][1],f[i+1][2][1][j]);
            if(f[i+1][3][2][j]!=-1)f[i][1][3][2]=max(f[i][1][3][2],f[i+1][3][2][j]+1);
            if(f[i+1][3][1][j]!=-1)f[i][2][3][1]=max(f[i][2][3][1],f[i+1][3][1][j]);
            if(f[i+1][1][3][j]!=-1)f[i][2][1][3]=max(f[i][2][1][3],f[i+1][1][3][j]);
            if(f[i+1][2][3][j]!=-1)f[i][1][2][3]=max(f[i][1][2][3],f[i+1][2][3][j]+1);
            }
        }
    }
    int ans=-1;
    for(int i=0;i<=3;i++)
        for(int j=0;j<=3;j++)
            for(int p=0;p<=3;p++)
                ans=max(ans,f[3][i][j][p]);
    cout<<ans<<endl;
}

L 牛牛学走路

#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,n) for(int i=a;i<=n;i++)
#define per(i,a,n) for(int i=n;i>=a;i--)
#define pb push_back
#define SZ(v) ((int)v.size())
#define fs first
#define sc second
typedef long long ll;
typedef double db;
typedef pair<int,int> pii;
int T,n;
char s[1010];
int main(){
    cin>>T;
    while(T--){
        scanf("%d%s",&n,s+1);
        int x=0,y=0;
        db ans=0;
        rep(i,1,n){
            if(s[i]=='U')    y++;
            if(s[i]=='D')    y--;
            if(s[i]=='L')    x--;
            if(s[i]=='R')    x++;
            ans=max(ans,hypot(x,y));
        }
        printf("%.12lf\n",ans);
    }
    return 0;
}

全部评论

(7) 回帖
加载中...
话题 回帖

等你来战

查看全部

热门推荐