投稿
  1. 首页
  2. 随笔

2022牛客寒假算法基础集训营1 L E J H F C D A I

高音质音乐下载 • 2022-12-17 • 随笔 • 阅读 38

2022牛客寒假算法基础集训营1 L E J H F C D A I,第1张

2022牛客寒假算法基础集训营1 L E J H F C D A I 2022牛客寒假算法基础集训营1 L E J H F C D A I L 牛牛学走路

思路： 模拟，用一个 M A X MAX MAX存储。

参考代码： 

#include
using namespace std;
#define mp make_pair
#define int long long 
#define re register int
#define pb emplace_back
#define lowbit(x) (x&-x)
#define fer(i,a,b) for(re i = a ; i <= b ; i ++)
#define der(i,a,b) for(re i = a ; i >= b ; i --)
#define snow ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
int gcd(int a,int b){return b?gcd(b,a%b):a;}
int lcm(int a,int b){return a*b/gcd(a,b);}
typedef pairPII;
typedef pairPIS;
signed main(){
    int t;
    cin>>t;
    while(t--){
        double MA=0;
        int n;
        cin>>n;
        string s;
        cin>>s;
        int x=0,y=0;
        int x1=x;
        int y1=y;
        for(int i=0;i 
E 炸鸡块君的高中回忆 

 
 
思路： 非常简单的推公式，不能暴力因为数据范围很大。需要特判
     
      
       
        
         n
        
        
         =
        
        
         1
        
        
         ,
        
        
         m
        
        
         =
        
        
         1
        
       
       
        n=1,m=1
       
      
     n=1,m=1和
     
      
       
        
         n
        
        
         !
        
        
         =
        
        
         1
        
        
         ,
        
        
         m
        
        
         =
        
        
         1
        
       
       
        n!=1,m=1
       
      
     n!=1,m=1的情况。贪心做法，一直让一个人带着最多
     
      
       
        
         (
        
        
         m
        
        
         −
        
        
         1
        
        
         )
        
       
       
        (m-1)
       
      
     (m−1)个人进去，直到所有人全部进入校园。
 

 

参考代码： 

#include
using namespace std;
#define mp make_pair
#define int long long 
#define re register int
#define pb emplace_back
#define lowbit(x) (x&-x)
#define fer(i,a,b) for(re i = a ; i <= b ; i ++)
#define der(i,a,b) for(re i = a ; i >= b ; i --)
#define snow ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
int gcd(int a,int b){return b?gcd(b,a%b):a;}
int lcm(int a,int b){return a*b/gcd(a,b);}
typedef pairPII;
typedef pairPIS;
signed main(){
    int t;
    cin>>t;
    while(t--){
        int n,m;
        cin>>n>>m;
        if(m==1&&n==1){
            cout<<1< 
J 朋友做游戏 

 
 
思路： 双指针模拟，贪心。
 

 

参考代码： 

#include
using namespace std;
#define mp make_pair
#define int long long 
#define re register int
#define pb emplace_back
#define lowbit(x) (x&-x)
#define fer(i,a,b) for(re i = a ; i <= b ; i ++)
#define der(i,a,b) for(re i = a ; i >= b ; i --)
#define snow ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
int gcd(int a,int b){return b?gcd(b,a%b):a;}
int lcm(int a,int b){return a*b/gcd(a,b);}
typedef pairPII;
typedef pairPIS;
const int N=1e4+10;
int a[N],b[N];
bool cmp(int a,int b){
    return a>b;
}
signed main(){
    int t;
    cin>>t;
    while(t--){
        int x,y,n;
        cin>>x>>y>>n;
        for(int i=1;i<=x;i++)cin>>a[i];
        for(int i=1;i<=y;i++)cin>>b[i];
        sort(a+1,a+1+x,cmp);
        sort(b+1,b+1+y,cmp);
        for(int i=1;i<=x;i++)a[i]+=a[i-1];
        for(int i=1;i<=y;i++)b[i]+=b[i-1];
        int ans=-1;
        for(int i=1;i<=n;i++){
            if(i>=1&&i<=x&&n-i<=y&&i>=n-i){
                ans=max(ans,a[i]+b[n-i]);
            }
        }
        cout< 
H 牛牛看云 

 
 
思路： 本题虽然
     
      
       
        
         n
        
       
       
        n
       
      
     n很大，具有迷惑性，但是
     
      
       
        
         a
        
       
       
        a
       
      
     a的范围很小最多只有
     
      
       
        
         1000
        
       
       
        1000
       
      
     1000，所以可以通过记录
     
      
       
        
         0
        
       
       
        0
       
      
     0~
     
      
       
        
         1000
        
       
       
        1000
       
      
     1000中各个数出现的次数，跑一遍
     
      
       
        
         1
        
        
         e
        
        
         6
        
       
       
        1e6
       
      
     1e6的复杂度。当然也可以使用二分来做，时间复杂度
     
      
       
        
         O
        
        
         (
        
        
         n
        
        
         l
        
        
         o
        
        
         g
        
        
         n
        
        
         )
        
       
       
        O(nlogn)
       
      
     O(nlogn)。
 

 

二分参考代码： 

#include
using namespace std;
#define mp make_pair
#define int long long 
#define re register int
#define pb emplace_back
#define lowbit(x) (x&-x)
#define fer(i,a,b) for(re i = a ; i <= b ; i ++)
#define der(i,a,b) for(re i = a ; i >= b ; i --)
#define snow ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
int gcd(int a,int b){return b?gcd(b,a%b):a;}
int lcm(int a,int b){return a*b/gcd(a,b);}
typedef pairPII;
typedef pairPIS;
const int N=1e6+10;
int a[N];
int s[N];
signed main(){
    int n;
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    sort(a+1,a+1+n);
    for(int i=1;i<=n;i++){
        s[i]=a[i]+s[i-1];
    }
    int res=0;
    for(int i=1;i<=n;i++){
        int x=1000-a[i];
        int l=i,r=n;
        while(l>1;
            if(a[mid]>=x)r=mid;
            else l=mid+1;
        }
        int sum=l-i;
        if(l>i)
        res+=1000*sum-(s[l-1]-s[i-1]+(sum)*a[i]);
        int sum2=n-l+1;
        res+=(s[n]-s[l-1]+(sum2)*a[i])-sum2*1000;
    }
    cout< 

映射+暴力参考代码： 

#include
using namespace std;
#define mp make_pair
#define int long long 
#define re register int
#define pb emplace_back
#define lowbit(x) (x&-x)
#define fer(i,a,b) for(re i = a ; i <= b ; i ++)
#define der(i,a,b) for(re i = a ; i >= b ; i --)
#define snow ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
int gcd(int a,int b){return b?gcd(b,a%b):a;}
int lcm(int a,int b){return a*b/gcd(a,b);}
typedef pairPII;
typedef pairPIS;
const int N=1010;
int a[N];
signed main(){
    int n;
    cin>>n;
    for(int i=1;i<=n;i++){//映射
        int x;
        cin>>x;
        a[x]++;
    }
    int sum=0;
    for(int i=0;i<=1000;i++)//1e6暴力
        for(int j=i;j<=1000;j++){
            int dapei=0;
            if(i==j)dapei=a[i]+(a[i]*(a[i]-1))/2;
            else dapei=a[i]*a[j];
            sum+=dapei*abs(1000-(i+j));
        }
    cout< 
F 中位数切分 

 
 
思路： 结论题，
     
      
       
        
         1
        
       
       
        1
       
      
     1个小于
     
      
       
        
         m
        
       
       
        m
       
      
     m的数需要至少
     
      
       
        
         2
        
       
       
        2
       
      
     2个大于等于
     
      
       
        
         m
        
       
       
        m
       
      
     m的数来维护，
     
      
       
        
         2
        
       
       
        2
       
      
     2个小于
     
      
       
        
         m
        
       
       
        m
       
      
     m的数需要至少
     
      
       
        
         3
        
       
       
        3
       
      
     3个大于等于
     
      
       
        
         m
        
       
       
        m
       
      
     m的数来维护，以此推类，但
     
      
       
        
         0
        
       
       
        0
       
      
     0个小于
     
      
       
        
         m
        
       
       
        m
       
      
     m的数不需要维护。因为要求最多段，所以一旦遇到小于
     
      
       
        
         m
        
       
       
        m
       
      
     m的数花最小代价去维护它即可。剩余的不用维护的皆可单独成段。
 

 

参考代码： 

#include
using namespace std;
#define mp make_pair
#define int long long 
#define re register int
#define pb emplace_back
#define lowbit(x) (x&-x)
#define fer(i,a,b) for(re i = a ; i <= b ; i ++)
#define der(i,a,b) for(re i = a ; i >= b ; i --)
#define snow ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
int gcd(int a,int b){return b?gcd(b,a%b):a;}
int lcm(int a,int b){return a*b/gcd(a,b);}
typedef pairPII;
typedef pairPIS;
const int N=1e5+10;
int a[N];
signed main(){
    int t;
    cin>>t;
    while(t--){
        int n,m;
        cin>>n>>m;
        int sum=0;//统计>=m的数量
        for(int i=1;i<=n;i++){cin>>a[i];if(a[i]>=m)sum++;}
        if(n%2==0){
            if(sum<=n/2){cout<<"-1"< 
C Baby’s first attempt on CPU 

 
 
思路： 阅读理解，模拟+贪心。我们只需要依次执行下来，哪里缺空格补哪里，并且需要考虑补了空格之后对接下去两行的影响。因为我们最多会影响三行。
 

 

参考代码： 

#include
using namespace std;
#define mp make_pair
#define int long long 
#define re register int
#define pb emplace_back
#define lowbit(x) (x&-x)
#define fer(i,a,b) for(re i = a ; i <= b ; i ++)
#define der(i,a,b) for(re i = a ; i >= b ; i --)
#define snow ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
int gcd(int a,int b){return b?gcd(b,a%b):a;}
int lcm(int a,int b){return a*b/gcd(a,b);}
typedef pairPII;
typedef pairPIS;
const int N=110;
struct node{
    int a,b,c;
}nodes[N];
signed main(){
    int n;
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>nodes[i].a>>nodes[i].b>>nodes[i].c;
    }
    int res=0;
    for(int i=1;i<=n;i++){
            if(nodes[i].a==1){
                res+=3;
                nodes[i].a=nodes[i].b=nodes[i].c=0;
                nodes[i+1].b=nodes[i+1].c=0;
                nodes[i+2].c=0;
            }
            else if(nodes[i].b==1){
                res+=2;
                nodes[i].b=nodes[i].c=0;
                nodes[i+1].c=nodes[i+1].b=0;
                nodes[i+2].c=0;
            }
            else if(nodes[i].c==1){
                res+=1;
                nodes[i].c=0;
                if(nodes[i+1].b==1){
                    nodes[i+1].b=0;
                    nodes[i+1].c=1;
                }
                else if(nodes[i+1].c==1){
                    nodes[i+1].c=0;
                }
                nodes[i+2].c=0;
            }
    }
    cout< 
D 牛牛做数论 

 
 
思路： 比较好看出来的数学题，除了
     
      
       
        
         n
        
       
       
        n
       
      
     n等于
     
      
       
        
         1
        
       
       
        1
       
      
     1的情况，其余的
     
      
       
        
         n
        
       
       
        n
       
      
     n的最小
     
      
       
        
         X
        
        
         o
        
       
       
        Xo
       
      
     Xo为不超过
     
      
       
        
         n
        
       
       
        n
       
      
     n的所有素数连积，最大
     
      
       
        
         X
        
        
         o
        
       
       
        Xo
       
      
     Xo为不超过
     
      
       
        
         n
        
       
       
        n
       
      
     n的最大素数。由于素数的连积小于
     
      
       
        
         1
        
        
         e
        
        
         9
        
       
       
        1e9
       
      
     1e9只需要
     
      
       
        
         10
        
       
       
        10
       
      
     10个数所以打表即可。求不超过n的最大素数只需要暴力即可，因为
     
      
       
        
         1
        
        
         e
        
        
         9
        
       
       
        1e9
       
      
     1e9内最大两个数的间隔是282。
 

 

参考代码： 

#include
using namespace std;
#define mp make_pair
#define int long long 
#define re register int
#define pb emplace_back
#define lowbit(x) (x&-x)
#define fer(i,a,b) for(re i = a ; i <= b ; i ++)
#define der(i,a,b) for(re i = a ; i >= b ; i --)
#define snow ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
int gcd(int a,int b){return b?gcd(b,a%b):a;}
int lcm(int a,int b){return a*b/gcd(a,b);}
typedef pairPII;
typedef pairPIS;
int prime[15]={0,2,3,5,7,11,13,17,19,23,29};
int get_prime(int x){
    for(int i=2;i*i<=x;i++){
        if(x%i==0)return false;
    }
    return true;
}
signed main(){
    int t;
    cin>>t;
    while(t--){
        int n;
        cin>>n;
        if(n==1){
            cout<<"-1"<=1;i--){
            if(get_prime(i)){
                r=i;
                break;
            }
        }
        cout< 
A 九小时九个人九扇门 

 
 
思路： 简单
     
      
       
        
         D
        
        
         P
        
       
       
        DP
       
      
     DP 
     
      
       
        
         01
        
       
       
        01
       
      
     01背包的变形。一个非常有用的结论：任何一个数
     
      
       
        
         m
        
        
         o
        
        
         d
        
        
         9
        
       
       
        mod9
       
      
     mod9即使其数字根。注意：
     
      
       
        
         m
        
        
         o
        
        
         d
        
        
         =
        
        
         0
        
       
       
        mod=0
       
      
     mod=0的话数字根为
     
      
       
        
         9
        
       
       
        9
       
      
     9，然后
     
      
       
        
         1
        
        
         e
        
        
         5
        
       
       
        1e5
       
      
     1e5个人就变成了
     
      
       
        
         1
        
       
       
        1
       
      
     1~
     
      
       
        
         9
        
       
       
        9
       
      
     9的值，然后进行01背包，选或者不选。然后算出最后的方案数。
 

 

参考代码： 

#include
using namespace std;
#define mp make_pair
#define int long long 
#define re register int
#define pb emplace_back
#define lowbit(x) (x&-x)
#define fer(i,a,b) for(re i = a ; i <= b ; i ++)
#define der(i,a,b) for(re i = a ; i >= b ; i --)
#define snow ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
int gcd(int a,int b){return b?gcd(b,a%b):a;}
int lcm(int a,int b){return a*b/gcd(a,b);}
typedef pairPII;
typedef pairPIS;
const int N=1e5+10;
const int mod=998244353;
int a[N];
int f[N][10];
int get(int x){
    if(x%9==0)return 9;
    else return x%9;
}
signed main(){//DP
    int n;
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        a[i]=get(a[i]);
    }
    f[0][0]=1;//注意入口，都不选的情况下也是一种方案。
    for(int i=1;i<=n;i++){
        for(int j=0;j<=9;j++){
            f[i][j]=(f[i][j]+f[i-1][j])%mod;
            int temp=get(j+a[i]);
            f[i][temp]=(f[i][temp]+f[i-1][j])%mod;
        }
    }
    for(int i=1;i<=9;i++)cout< 
I B站与各唱各的 

 
 
思路：
 

 

参考代码： 

#include
using namespace std;
#define mp make_pair
#define int long long 
#define re register int
#define pb emplace_back
#define lowbit(x) (x&-x)
#define fer(i,a,b) for(re i = a ; i <= b ; i ++)
#define der(i,a,b) for(re i = a ; i >= b ; i --)
#define snow ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
int gcd(int a,int b){return b?gcd(b,a%b):a;}
int lcm(int a,int b){return a*b/gcd(a,b);}
typedef pairPII;
typedef pairPIS;
const int mod=1e9+7;
int qmi(int a,int b){
    int res=1;
    while(b){
        if(b&1)res=(res*a)%mod;
        a=(a*a)%mod;
        b>>=1;
    }
    return res;
}
signed main(){
    int t;
    cin>>t;
    while(t--){
        int n,m;
        cin>>n>>m;
        int fenzi=qmi(2,n)-2;
        int fenmu=qmi(2,n);
        fenmu=qmi(fenmu,mod-2);
        cout<<(m*fenzi%mod*fenmu%mod)<					
										


					

						
欢迎分享，转载请注明来源：内存溢出
原文地址: http://outofmemory.cn/zaji/5713698.html
赞 (0)
打赏 微信扫一扫 微信扫一扫 支付宝扫一扫 支付宝扫一扫
高音质音乐下载 高音质音乐下载 一级用户组
0 0
上一篇 2022-12-17
下一篇 2022-12-17

发表评论

登录后才能评论

评论列表（0条）

保存