首页 > 其他分享 >2024牛客多校第三场

2024牛客多校第三场

时间：2024-07-24 11:44:15浏览次数：7  
标签：ch return int mid else 2024 牛客 第三场 first

磨合上升期，爽！

B

队友做的

#include<bits/stdc++.h>
using namespace std;
#define int long long
inline int read()
{
    int x=0;bool f=1;char ch=getchar();
    for(;ch<'0'||ch>'9';ch=getchar())f^=(ch=='-');
    for(;ch>='0'&&ch<='9';ch=getchar())x=(x<<1)+(x<<3)+(ch^48);
    return f?x:-x;
}
const int N=105;
int n,d,p,res;
int h[N];
int gcd(int x,int y){
    if (y==0) return x;
    return gcd(y,x%y);
}
signed main()
{
    cin >> n >> d;
    for (int i=1;i<=n;i++)
        cin >> h[i];
    p=h[n];
    for (int i=1;i<n;i++)
        p=gcd(p,h[i]);
    res=d%p;
    if (res>p/2) res=p-res;
    cout << res << endl;
    return 0;
}

L

#include<bits/stdc++.h>
using namespace std;
const int N=9;
char ch[N+5][N+5];
void Kafka()
{
    for(int i=1;i<=N;++i) scanf("%s",ch[i]+1);
    bool flag=1;
    for(int i=1;i<=N;putchar('\n'),++i) for(int j=1;j<=N;++j)
    {
        if(i>1&&i<N&&j>1&&j<N&&ch[i][j]=='8'&&flag) putchar('8'),flag=0;
        else putchar('*');
    }
}
signed main()
{
    Kafka();
    return 0;
}

J

对于这类 "每个点都是1出度，指向的点可以确定" 的题，经典做法是倍增跳

23年的杭电多校也有一道类似的，问走x步在环上走到哪里，那题想到倍增直接做完

这题比较麻烦的地方在于要先预处理出f[i]表示i到的点才能进行倍增

预处理可以用二分/倍增实现

#include<bits/stdc++.h>
using namespace std;
const int N=1e5;
int n,a,b;
char s[N+5];

//PART 1:
int sum[N+5];
pair<int,bool> f[N+5];
void Get_Prefix()
{
    sum[1]=s[1]^48;
    for(int i=2;i<=n;++i) sum[i]=sum[i-1]+(s[i]^48);
}
inline int QueryA(int L,int R){return L<=R?sum[R]-sum[L-1]:0;}
inline int QueryB(int L,int R){return L<=R?R-L+1-QueryA(L,R):0;}
int check(int L,int R,int A,int B)
{
    if(A+QueryA(L,R)>=a) return 1;
    else if(B+QueryB(L,R)>=a) return 0;
    return -1;
}
int check(int A,int B)
{
    if(A>=a) return 1;
    else if(B>=a) return 0;
    return -1;
}
int Find_Len(int L,int R,int A,int B)
{
    int l=1,r=R-L+1;
    for(int mid=l+r>>1;l<r;check(L,L+mid-1,A,B)>-1?r=mid:l=mid+1)mid=l+r>>1;
    return l;
}
int Find_Nums(int A,int B)
{
    int l=0,r=(2*a-1)/n+1,tmpA=QueryA(1,n),tmpB=QueryB(1,n);;
    for(int mid=l+r+1>>1;l<r;check(A+mid*tmpA,B+mid*tmpB)>-1?r=mid-1:l=mid) mid=l+r+1>>1;
    return l;
}
void Kafka()
{
    cin>>n>>a>>b;
    cin>>s+1;
    Get_Prefix();
//    for(int i=1;i<=n;++i) printf("sum[%d]=%d\n",i,sum[i]);
    for(int i=1;i<=n;++i)
    {
        if(~check(i,n,0,0))
        {
            int tmp=Find_Len(i,n,0,0);
            f[i]=make_pair(i+tmp,check(i,i+tmp-1,0,0));
            if(f[i].first>n) f[i].first-=n;
        }
        else
        {
            int nums=Find_Nums(QueryA(i,n),QueryB(i,n));
            int A=QueryA(i,n)+nums*QueryA(1,n),B=QueryB(i,n)+nums*QueryB(1,n);
            if(A>=a) f[i]=make_pair(1,1);
            else if(B>=a) f[i]=make_pair(1,0);
            else 
            {
                int tmp=Find_Len(1,n,A,B);
                f[i]=make_pair(1+tmp,check(1,tmp,A,B));
                if(f[i].first>n) f[i].first-=n;    
            }
        }
    } 
//    for(int i=1;i<=n;++i) printf("f[%d]=%d and %d\n",i,f[i].first,f[i].second);
}

//PART 2:
const int LIMIT=18;
pair<int,int> g[LIMIT+5][N+5];
int Gcheck(int A,int B)
{
    if(A>=b) return 1;   
    else if(B>=b) return 0;
    return -1;
}
int Ans(int x)
{
    int A=0,B=0;
    for(int i=LIMIT-1;~i;--i)
    {
        int Len=1<<i,tmpA,tmpB;
        tmpA=g[i][x].second,tmpB=Len-tmpA;
        if(~Gcheck(A+tmpA,B+tmpB)) continue;
        x=g[i][x].first,A+=tmpA,B+=tmpB;
    }
    A+=g[0][x].second;
    if(A>=b) return 1;
    else return 0;
}
void Himeko()
{
    for(int i=1;i<=n;++i) g[0][i]=f[i];
    for(int i=1;i<LIMIT;++i) for(int j=1;j<=n;++j)
    {
        g[i][j].first=g[i-1][g[i-1][j].first].first;
        g[i][j].second=g[i-1][j].second+g[i-1][g[i-1][j].first].second;
    }
//    for(int i=0;i<LIMIT;++i) for(int j=1;j<=n;++j) printf("g[%d][%d]:%d and %d\n",i,j,g[i][j].first,g[i][j].second);
    for(int i=1;i<=n;++i) cout<<(char)(Ans(i)^48);
}
signed main()
{
    Kafka();
    Himeko();
    return 0;
}

A

思路一直假了，在那边用一种求得出方案的nlog做法写模拟，挂了两发后实在找不到返利，开始贪心

贪心的实质就是算供给，运过去需要的最少次数S为 (n-r)/(r-l) ，能提供的总次数为 Σ min( (h[i]-1)/2, S)

 Σ min( (h[i]-1)/2, S) >= S*L 即可

证明还是很妙的，数学归纳法

#include<bits/stdc++.h>
using namespace std;
#define int long long
inline int read()
{
    int x=0;bool f=1;char ch=getchar();
    for(;ch<'0'||ch>'9';ch=getchar())f^=(ch=='-');
    for(;ch>='0'&&ch<='9';ch=getchar())x=(x<<1)+(x<<3)+(ch^48);
    return f?x:-x;
}
const int N=5e5+505;
int n,l,r;
int h[N],d[N];

bool sol(){
    if (n<l) return false;
    for (int i=1;i<=n;i++){
        int x=(h[i]-1)/2;
        d[1]++;
        d[x+1]--;
    }
    for (int i=1;i<=n;i++)
        d[i]+=d[i-1];
    int cnt=0,sum=0,k=r-l;
    for (int i=1;i+r<n+1;i+=k){
        cnt++;
        sum+=d[cnt];
        if (sum<cnt*l) return false;
    }
    return true;
}

signed main()
{
    cin >> n >> l >> r;
    for (int i=1;i<=n;i++)
        h[i]=read();
    
    if (sol()) cout << "Yes" << endl;
        else cout << "No" << endl;
    return 0;
}

J

给定n块两端都有数字的骨牌，要求排列它们使得任意相邻的两端都不相等，排列时可以指定某个骨牌左右顺序

本来想到了奇怪的图论优化建图去，在那边网络流流了半天没网出来

首先注意到如果两端都不相等，假设有x个，那么这x个怎么排都可以，如果撞了反一下就好  ........①

如果两端都相等，假设有y个，问题转化为给定长度为y的数组a[i]（其中a[i]表示第i个数出现的次数）

 每次都可以挑两个出来对消，问要怎么构造使得剩下的最少？

经典结论是：每次挑众数和随便一个数去删，只要众数<=sum/2，偶数能消完，奇数剩一个。否则众数>sum/2，一定会有剩余

实现时我用了小根堆，每次pop两次堆头对消

到这里处理完了两端都相同的，不妨假设剩下的为(1,1)

还没用上的骨牌里如果有（2，1） (3，1)（4，1）这种一端相同的也全部可以接上去

最后还剩两端不一样 && 两端都≠1的，这就和 ① 一样了

#include<bits/stdc++.h>
using namespace std;
const int N = 2e5+5;
int n;
inline int read()
{
    int x=0;bool f=1;char ch=getchar();
    for(;ch<'0'||ch>'9';ch=getchar())f^=(ch=='-');
    for(;ch>='0'&&ch<='9';ch=getchar())x=(x<<1)+(x<<3)+(ch^48);
    return f?x:-x;
}
int xid[N<<1],tot[N<<1],x[N],y[N];
int cntx=0,flag=1;
struct node{
    int c,v;
    /*
    
    
    bool operator
    */
    bool operator <(const node &b)const{return v==b.v?c<b.c:v>b.v;}
    bool operator >(const node &b)const{return v==b.v?c>b.c:v<b.v;}
};
priority_queue<node,vector<node>,greater<node>>q;
void solve(){
    n=read();
    for(int i=1;i<=n;i++){
        x[i]=read(),y[i]=read();
        xid[++cntx]=x[i];
        xid[++cntx]=y[i];
    }
    sort(xid+1,xid+1+cntx);
    cntx=unique(xid+1,xid+1+cntx)-(xid+1);
    
    int sum=0;
    vector<pair<int,int>>a;
    for(int i=1;i<=n;i++){
        int idx=lower_bound(xid+1,xid+1+cntx,x[i])-(xid);
        int idy=lower_bound(xid+1,xid+1+cntx,y[i])-(xid);
        if(x[i]==y[i]){
            tot[idx]++;
        }
        else a.push_back({idx,idy});
    }
    int most=0,val=-1;
    for(int i=1;i<2*N;i++){
        if(!tot[i]) continue;
        q.push((node){i,tot[i]});
        sum+=tot[i];
        if(tot[i]>most){
            most=tot[i],val=i;
        }
    }
    int flag=0;
    int last=-1;
    vector<pair<int,int>>out;
    if(!most){
        flag=1;
        for(auto v:a){
            if(v.first==last){
                out.push_back({v.second,v.first}); last=v.first;
                continue;
            }
            if(v.second==last){
                out.push_back({v.first,v.second}); last=v.second;
                continue;
            }
            out.push_back({v.first,v.second});
            last=v.second;
        }
    }
    else {
        if(most<=sum/2){ // 1.clear
            int left=0;
            flag=1;
            while(!q.empty()){
                auto u=q.top();
                q.pop();
                if(q.empty()==true) {
                    left=u.c;
                    break;    
                }
                auto v=q.top();
                q.pop();
                out.push_back({u.c,u.c});
                out.push_back({v.c,v.c});
                last=v.c;
                u.v--;v.v--;
                if(u.v) q.push(u);
                if(v.v) q.push(v);     
            }
            if(left) {
                out.push_back({left,left});
                last=left;
            }
            
            
            
            for(auto v:a){
                if(v.first==last){
                    out.push_back({v.second,v.first}); last=v.first;
                    continue;
                }
                if(v.second==last){
                    out.push_back({v.first,v.second}); last=v.second;
                    continue;
                }
                out.push_back({v.first,v.second});
                last=v.second;
            }
        }
        else {
            node tmp;
            while(!q.empty()){
                auto u=q.top();
                q.pop();
                if(q.empty()==true) {
                    tmp=u;
                    break;    
                }
                auto v=q.top();
                q.pop();
                out.push_back({u.c,u.c});
                out.push_back({v.c,v.c});
                last=v.c;
                u.v--;v.v--;
                if(u.v) q.push(u);
                if(v.v) q.push(v);     
            }
            
            out.push_back({tmp.c,tmp.c});
            last=tmp.c;
            tmp.v--;
            int cnt=0;
            for(int i=1;i<=n;i++){
                if(x[i]==y[i]) continue;
                int idx=lower_bound(xid+1,xid+1+cntx,x[i])-(xid);
                int idy=lower_bound(xid+1,xid+1+cntx,y[i])-(xid);
                if(idx==tmp.c){
                    out.push_back({idy,idx});
                }
                else if(idy==tmp.c){
                    out.push_back({idx,idy});
                }
                else cnt++;
            }
            
            if(cnt>=tmp.v) {
                flag=1;
                for(int i=1;i<=n;i++){
                    if(x[i]==y[i]) continue;
                    int idx=lower_bound(xid+1,xid+1+cntx,x[i])-(xid);
                    int idy=lower_bound(xid+1,xid+1+cntx,y[i])-(xid);
                    if(tmp.v&& idx!=tmp.c&&idy!=tmp.c){
                        out.push_back({idx,idy});
                        out.push_back({tmp.c,tmp.c});
                        last=tmp.c;
                        tmp.v--;
                    }
                    else {
                        if(idx==tmp.c || idy==tmp.c ) continue;
                        
                        if(idx!=last){
                            out.push_back({idx,idy});
                            last=idy;
                        }
                        if(idy!=last){
                            out.push_back({idy,idx});
                            last=idx;
                        }
                    }
                }
            }
        }        
    }
    
    if(!flag){
        cout<<"NO"<<"\n";
    }
    else {
        cout<<"YES"<<"\n";
        for(auto v:out){
            cout<<xid[v.first]<<" "<<xid[v.second]<<"\n";
        }
    }
}
signed main()
{
    solve();
    return 0;
}

 

标签：ch,return,int,mid,else,2024,牛客,第三场,first
From： https://www.cnblogs.com/liyishui2003/p/18320495

相关文章

  • 2024-07-24 想法记录，关于 可以准点睡觉 和 拖延寄快递
    2024-07-24     昨天晚上可以及时睡觉，比原来早，12点以前睡下来，11点半闭上的眼。之前的晚睡，怎么突然在这一会就可以变回来了呢？ 我思考了一下，最重要的原因，我看见自己下巴和两鬓的白胡子，白发了。我才人到中年而已，年纪不大就已经头发胡子都变白了，不敢再熬夜了。再仔细感受......
  • 源代码加密软件，2024年企业常用的五款源代码加密软件推荐
    在当今高度数字化和竞争激烈的商业环境中，保护源代码的安全性对于企业来说至关重要。源代码不仅是企业的核心资产，也是创新和竞争优势的关键所在。一旦源代码泄露，可能导致知识产权的丧失、商业机密的暴露，甚至对企业的声誉造成不可挽回的损害。因此，选择一款可靠的源代码加密软件......
  • 2024 暑假集训
    树状数组&线段树线段树合并，主席树等知识点是第一次接触。同时对扫描线能解决的问题有了些更好的认知。毕竟是之前学过的东西，还是比较好的。掌握程度：\(85\%^+\)离线分治算法具体是：线段树分治\(80\%^+\)就是个线段树上二分。CDQ分治基于时间的分治\(75\%^+\)基本......
  • 【稳定检索|投稿优惠】2024年金融创新与当代贸易国际会议(ICFICT 2024)
    2024年金融创新与当代贸易国际会议2024InternationalConferenceonFinancialInnovationandContemporaryTrade【1】大会信息会议名称：2024年金融创新与当代贸易国际会议会议简称：ICFICT2024大会时间：请查看官网大会地点：中国·南京截稿时间：请查看官网审稿通知：投稿......
  • [2024JZYZ暑期集训]知识点总结
    前言第三次暑期集训了，与前两次不同，这次没有前两次的激动了，所以也能够更深入地学习算法。闲话宿舍挺好，有空床能住。捡了三块钱，史上最灵异事件。R班好热闹。认识了几个郑州那边的大佬知识点Day1讲了几个基础数据结构（树状数，线段树），作业里面的题目很多之前都做过，就当复习了。......
  • 2024/7/23 测试小结
    突然听说要考试捏（没有复习（T1是P1434[SHOI2002]滑雪。草这不一眼......等下好像不太会写。一开始脑抽了。暴力建图给每个点跑spfa最长路。明显地，不是正解。直接跳掉了。T2是P4170[CQOI2007]涂色。草这真的是一眼题。10min秒掉。T3是CF161DDistanceinTree。一眼淀......
  • 【保奖思路】2024年华为杯研究生数学建模D题解题思路分享（点个关注，后续会更新
    您的点赞收藏是我继续更新的最大动力！一定要点击如下的卡片链接，那是获取资料的入口！点击链接加入群聊【2024华为杯研赛资料汇】：http://qm.qq.com/cgi-bin/qm/qr?_wv=1027&k=MwNruKbEvR9aZns1l7xXBWmQQKYAEh-F&authKey=igaBN79pz6BhNlDQ6TIZ5YFAbn71aDcYL77uANPquLF%2FTVgeSAhEZ......
  • 2024.7.23 c语言学习笔记
    复习:什么是指针？   也叫地址address，就是内存块的首位置，英文名叫painter。他是一个常量，指针不能被赋值，不能自增自减，例如：数组名就是内存块首地址，他就是一个指针常量。Inta=10，&a就是首地址，是指针常量；什么是指针变量?顾名思义，存放指针（地址）数据的变量，也叫地址变量。就......
  • 2024.7.22每日笔记，有错望指出
    //5、求125之内自然数中偶数之和。#include<stdio.h>intmain(){inti=0;intsum=0;for(i=0;i<=125;i++){if(i%2==0){sum=sum+i;printf("%d\n",sum);}}return0;}//7、编程计算1......
  • NOI2024 游记 | 如果这只是梦
    NOI2024游记|如果这只是梦省流：HBA类打铜，内含很多个人想法，可能更像对这一赛季想说的鲜花我终于站在了国赛场上，这也是第一次站在赛场上。第一天考试的时候我无法抑制紧张的心情，看到T2居然是真的交互题当时顿时心凉了半截，我开场前1h心跳一直很快，后面都有些喘不过气来，花了......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99