2024牛客寒假算法基础集训营1

$A.DFS搜索$
$双指针即可$

def solve():
    n=int(input())
    s=input();t='DFS'
    j=0
    for i in range(n):
        if s[i]==t[j]:
            j+=1
            if j==3:
                print(1,end=' ')
                break
    else:
        print(0,end=' ')
    t='dfs'
    j=0
    for i in range(n):
        if s[i]==t[j]:
            j+=1
            if j==3:
                print(1)
                break
    else:
        print(0)
    return

test=1
test=int(input())
for _ in range(test):
    solve()

$B.关鸡$
$分类讨论被左边、右边、零点封住的情况。（代码写的一坨，过了就行）$

def solve():
    n=int(input())
    p=[]
    for i in range(n):
        r,c=map(int,input().split())
        p.append([r,c])
    p.sort(key=lambda x:x[1])
    fl=fr=fld=frd=False
    fz=fzl=fzr=False
    for i in range(n):
        if p[i][1]<0:
            fl=True
            if p[i]==[1,-1]:
                fzl=True
            if i+1<n and p[i+1][1]-p[i][1]<=1 and p[i+1][0]!=p[i][0]:
                fld=True
        elif p[i][1]>0:
            fr=True
            if p[i]==[1,1]:
                fzr=True
            if i and p[i][1]-p[i-1][1]<=1 and p[i][0]!=p[i-1][0]:
                frd=True
        else:
            fz=True
    if fld and frd:
        print(0)
    elif fld:
        if fr or fz:
            print(1)
        else:
            print(2)
    elif frd:
        if fl or fz:
            print(1)
        else:
            print(2)
    else:
        if fz:
            print(2)
        else:
            if fzl and fzr:
                print(1)
            elif fzl or fzr:
                print(2)
            else:
                if fl and fr:
                    print(2)
                elif fl or fr:
                    print(3)
                else:
                    print(3)
    return

test=1
test=int(input())
for _ in range(test):
    solve()

C.按闹分配
$S_c​−S_{min}​≤M->kt_c≤M(k为排在鸡后面的人数，注意不要大于n)，预处理前缀和，每次询问O(1)$

def solve():
    n,q,tc=map(int,input().split())
    t=[0]+list(map(int,input().split()))
    t.sort()
    for i in range(1,n+1):
        t[i]+=t[i-1]
    for i in range(q):
        M=int(input())
        k=min(n,M//tc)
        print(t[n-k]+tc)
    return

$D.数组成鸡$
$询问的范围是±1e9，将除0外不同的数相乘，最大16个就超过1e9了(-8*-7*-6……-1*1*……*8)=1,625,702,400，所以只有不同的数个数小于16的时候才需要考虑。$
$n最小为2，那么必定要有一个数绝对值在\sqrt{10^9}内，否则前两个数相乘就爆1e9了。$
$枚举每个不同的数，令其为-\sqrt{10^9}到\sqrt{10^9}，得到它的偏移量，给整个数组加上这个偏移量，得到乘积，不超过1e9就加到答案集合中。$
$时间复杂度O(2*15\sqrt{10^9}n)$

#include <bits/stdc++.h>

constexpr int K=4e4,inf=1e9;

void solve(){
    int n,Q;
    std::cin>>n>>Q;

    std::vector<int> a(n);
    std::map<int,int> cnt;
    for(int i=0;i<n;i++){
        std::cin>>a[i];
        cnt[a[i]]++;
    }

    std::set<int> S{0};
    int N=cnt.size();
    if(N<=15){
        for(auto it=cnt.begin();it!=cnt.end();it++){
            int x=(*it).first;
            for(int i=-K;i<=K;i++){
                int z=i-x;
                long long res=1;
                for(int j=0;j<n;j++){
                    res*=1ll*a[j]+z;
                    if(std::abs(res)>inf)
                        break;
                }
                if(std::abs(res)<=inf)
                    S.insert(res);
            }            
        }
    }

    while(Q--){
        int m;
        std::cin>>m;
        if(S.count(m)){
            std::cout<<"Yes\n";
        }else{
            std::cout<<"No\n";
        }
    }
    return;

}

int main(){
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    int test=1;
    // std::cin>>test;
    while(test--){
        solve();
    }

    return 0;
}

$E.本题又主要考察了贪心$
$数据范围很小，直接dfs$

def solve():
    def dfs(x):
        nonlocal ans
        if x==m:
            res=1
            for i in range(n):
                if a[i]>a[0]:
                    res+=1
            ans=min(ans,res)
            return
        for i in range(3):
            a[u[x]]+=d[i][0]
            a[v[x]]+=d[i][1]
            dfs(x+1)
            a[u[x]]-=d[i][0]
            a[v[x]]-=d[i][1]
    n,m=map(int,input().split())
    a=list(map(int,input().split()))
    u=[0]*m;v=[0]*m
    for i in range(m):
        u[i],v[i]=map(int,input().split())
        u[i]-=1;v[i]-=1
    d=[[3,0],[0,3],[1,1]]
    ans=n
    dfs(0)
    print(ans)
    return


test=1
test=int(input())
for _ in range(test):
    solve()

$F.鸡数题$
$第二类斯特林数通项公式$

def qmi(a,k,p):
    res=1
    while k:
        if k&1:res=res*a%p
        a=a*a%p
        k>>=1
    return res

def init():
    fact[0]=infact[0]=1
    for i in range(1,N):
        fact[i]=fact[i-1]*i%mod
        infact[i]=infact[i-1]*qmi(i,mod-2,mod)%mod

def C(a,b):
    return fact[a]*infact[b]*infact[a-b]%mod

n,m=map(int,input().split())
mod=1000000007;N=100010
fact=[0]*N;infact=[0]*N
init()
S=0;sign=-1
for k in range(m+1):
    sign*=-1
    S=(S+sign*C(m,k)*qmi(m-k,n,mod)%mod)%mod
for i in range(1,m+1):
    S=S*qmi(i,mod-2,mod)%mod
print(S)

$G.why买外卖$
$按a_i排序，小于等于该价格的满减都用上，能小于等于m就更新ans$

import sys
# sys.setrecursionlimit(1000000)
input=lambda:sys.stdin.readline().strip()
write=lambda x:sys.stdout.write(str(x)+'\n')

from decimal import Decimal
# from datetime import datetime,timedelta
from random import randint,shuffle
# from copy import deepcopy
# from collections import deque,Counter,namedtuple
# from heapq import heapify,heappush,heappop
# from bisect import bisect_left,bisect,insort
from math import inf,sqrt,gcd,ceil,floor,e,log,log2,log10,pi,sin,cos,tan,asin,acos,atan
# from functools import cmp_to_key,reduce
# from operator import or_,xor,add,mul
# from itertools import permutations,combinations,accumulate



def solve():
    n,m=map(int,input().split())
    c=[]
    for i in range(n):
        a,b=map(int,input().split())
        c.append([a,b])
    c.sort()
    s=[0];res=[m]
    for i in range(n):
        s.append(s[i]+c[i][1])
        res.append(c[i][0]-s[i+1])
    ans=m
    for i in range(n+1):
        if i and res[i]<=m:
            ans=max(ans,m-res[i]+c[i-1][0])
    print(ans)

test=1
test=int(input())
for _ in range(test):
    solve()

$H.01背包，但是bit$
$or起来要小于等于m，若最终重量就是m，则选中的重量的二进制里的1必须严格是m的子集。$
$若小于m，可以枚举m二进制的每个1位，令其为0，后面的都为1，再去找所有是其自己的物品。$

#include <bits/stdc++.h>

void solve(){
    int n,m;
    std::cin>>n>>m;
    std::vector<int> v(n),w(n);
    for(int i=0;i<n;i++)
        std::cin>>v[i]>>w[i];
    long long ans=0;
    auto check=[&](int x){
        long long res=0;
        for(int i=0;i<n;i++){
            if((x&w[i])==w[i])
                res+=v[i];
        }
        ans=std::max(ans,res);
    };
    for(int i=27;i>=0;i--){
        if(m>>i&1)
            check(m^(1<<i)|((1<<i)-1));
    }
    check(m);
    std::cout<<ans<<"\n";
    return;

}

int main(){
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    int test=1;
    std::cin>>test;
    while(test--){
        solve();
    }

    return 0;
}

$I.It's bertrand paradox. Again!$
$随便找一个使两种方法有明显差异的统计量即可。$

#include <bits/stdc++.h>

void solve(){
    int n;
    std::cin>>n;
    int sum=0;
    for(int i=0;i<n;i++){
        int x,y,r;
        std::cin>>x>>y>>r;
        sum+=std::abs(x)+abs(y);
    }
    if(sum>90*n){
        std::cout<<"bit-noob\n";
    }else{
        std::cout<<"buaa-noob\n";
    }
    return;
}

int main(){
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    int test=1;
    // std::cin>>test;
    while(test--){
        solve();
    }

    return 0;
}

$J.又鸟之亦心$
$最大值最小，考虑二分答案。$
$二分最大距离d，进行check：枚举每个新的点，若原有两人所在的点中某些点到此距离大于d,则删去。若删完后为空集，则该距离过小，否则过大。$

#include <bits/stdc++.h>

void solve(){
    int n,x,y;
    std::cin>>n>>x>>y;

    std::vector<int> a(n);
    for(int i=0;i<n;i++)
        std::cin>>a[i];

    auto check=[&](int d){
        std::set<int> S;
        if(std::abs(x-y)>d)
            return false;
        int last=y;
        S.insert(x);
        for(int i=0;i<n;i++){
            if(!S.empty()&&std::abs(last-a[i])<=d)
                S.insert(last);
            while(!S.empty()&&std::abs(a[i]-*S.begin())>d)
                S.erase(*S.begin());
            while(!S.empty()&&std::abs(a[i]-*S.rbegin())>d)
                S.erase(*S.rbegin());
            last=a[i];
            if(S.empty())
                return false;
        }
        return true;
    };

    int l=0,r=1e9;
    while(l<r){
        int mid=l+r>>1;
        if(check(mid)){
            r=mid;
        }else{
            l=mid+1;
        }
    }
    std::cout<<l<<"\n";
    return;

}

int main(){
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    int test=1;
    // std::cin>>test;
    while(test--){
        solve();
    }

    return 0;
}

$K.牛镇公务员考试$
$每个题的答案都被另一个题所约束，即每个点出度为1，则必定会形成一棵基环内向树。所有的题形成一座基环内向森林。$
$对于每棵基环树，选取环上一点，枚举这道题答案，沿着环得到环上每个点答案，最终回到该点，若答案与最开始选择一致，则答案加一。$
$最终将每棵基环树的答案数量相乘。$

#include <bits/stdc++.h>

constexpr int mod=998244353;

void solve(){
    int n;
    std::cin>>n;
    std::vector<int> a(n);
    std::vector<std::string> s(n);
    for(int i=0;i<n;i++){
        std::cin>>a[i]>>s[i];
        a[i]--;
    }
    long long ans=1;
    std::vector<int> vis(n,-1);
    for(int i=0;i<n;i++){
        int j=i;
        while(vis[j]==-1){
            vis[j]=i;
            j=a[j];
        }
        if(vis[j]==i){
            int len=0,k=j;
            do{
                len++;
                k=a[k];
            }while(k!=j);
            int res=0;
            for(int x=0;x<5;x++){
                int v=x;
                for(int i=0;i<len;i++){
                    v=s[k][v]-'A';
                    k=a[k];
                }
                res+=v==x;
            }
            ans=ans*res%mod;
        }
    }
    std::cout<<ans<<"\n";
    return;
}

int main(){
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    int test=1;
    // std::cin>>test;
    while(test--){
        solve();
    }

    return 0;
}

$L.要有光$
$中学简单几何，答案为3cw$

def solve():
    c,d,h,w=map(int,input().split())
    print(3*w*c)
    return

test=1
test=int(input())
for _ in range(test):
    solve()

$M.牛客老粉才知道的秘密$
$n为6的倍数，则为n/6,否则n/6*2$

def solve():
    n=int(input())
    if n%6==0:
        print(n//6)
    else:
        print(n//6*2)
    return

test=1
test=int(input())
for _ in range(test):
    solve()