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

2024牛客多校第5场

时间:2024-08-01 23:06:33浏览次数:31  
标签:cnt ch return int 多校 2024 牛客 && true

很神奇的场hh,大家一起坐牢,多好啊!

B

找规律,这种题一般都是多模拟几个数据然后猜出来

#include<bits/stdc++.h>
using namespace std;

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 n,m,a,b;
bool sol(){
    n=read(); m=read();
    a=read(); b=read();
    if (n>m) swap(n,m);
    if ((n&1)&&(m&1)) return false;
    if (n==1&&m==2) return true;
    if (a==0&&b==0) {
        return false;
    }
    if (a==1&&b==1) return true;
    if (a==1&&b==0){
        if (n==1&&m%2==0) return true;
        return false;
    }
    if (a==0&&b==1){
        if (n==1&&m%2==0) return false;
        return true;
    }
    return true;
}
signed main()
{
    int T;
    T=read();
    while(T--) 
        if (sol()) cout << "Yes" << endl;
            else cout << "No" << endl;
    return 0;
}

E

显然如果ai>bi,先手肯定赢

如果ai==bi,如果这个位置谁先操作谁赢

假设有cnt个ai==bi的,cnt为奇数是A能赢cnt/2+1,cnt为偶数时A赢cnt/2

#include<bits/stdc++.h>
using namespace std;
const int N = 2e5+5;
int a[N],b[N];
void solve(){
    int n;cin>>n;
    for(int i=1;i<=n;i++) cin>>a[i];
    for(int i=1;i<=n;i++) cin>>b[i];
    
    int cnt=0,eq=0;
    for(int i=1;i<=n;i++){
        cnt+=(a[i]>b[i]);
        eq+=(a[i]==b[i]);
    }
    cout<<cnt+(eq+1)/2<<'\n';
}
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    
    int t;cin>>t;
    while(t--){
        solve();
    }
}

L

发现如果A[i]> A[I-1],则把A[i]-1,A[i-1]+1不会使答案更差

证明:

1.A[i]原本=A[i-1]+1,减完后相当于A[i]和A[i-1]互换,乘积不变

2.A[i]>A[I-1]+1,减完后更平均了,根据均值不等式,肯定最好

#include<bits/stdc++.h>
using namespace std;
const int N =105;
const int mod = 998244353;
typedef long long ll;
int a[N];
void solve(){
    int n;cin>>n;
    for(int i=1;i<=n;i++) cin>>a[i];
    priority_queue<int,vector<int>,greater<int>>q;
    q.push(a[1]);
    
    for(int i=2;i<=n;i++){    
        while(a[i]>q.top()){
            int u=q.top();
            q.pop();
            a[i]--;
            u++;
            q.push(u);
        }
        q.push(a[i]);
    }
    ll ans=1;
    while(!q.empty()){
        ans*=1ll*q.top();
        ans%=mod;
        q.pop();
    }
    cout<<ans<<"\n";
}
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    
    int t;cin>>t;
    while(t--){
        solve();
    }
}

H

暴搜过的,发现由于是下降的,所以每从u走到一个新的点v,u点的邻点都不能走,ban掉就行

发现图越稠密,每次ban掉的点越多,很快就走到底了

如果图不稠密,那走法很少,也很快就走到底了

比较严格的证明:

 

J

填坑中..

很神奇的dp,赛时一直不知道怎么去完备、不重不漏地数完一棵树

 

标签:cnt,ch,return,int,多校,2024,牛客,&&,true
From: https://www.cnblogs.com/liyishui2003/p/18337761

相关文章

  • 2024.8.1 总结(集训)
    今天和昨天都是学图论。wwlw给我们讲了Tarjan求强连通分量、(有向图)缩点、欧拉路径和欧拉回路、2-SAT和某个奇妙的容斥DP题。感觉有收获,但是没有理解透。感觉lr好强啊,好多题好像都有思路。xwb也好强啊,在洛谷团队里的图论题单里rank1,1200分。我今天的主要问题还是理解......
  • 2024.8.1随笔
    前言今天下午最后的时间不想写题了,于是就准备拿来随便写写什么。上午讲的是一些图论中常见的考点的应用(大概),题目难度都在蓝到紫,感觉也不是完全不可做,或多或少都能有一些想法,有时能想到点子上,但也常常乱整。今天讲了有关连通分量、欧拉路、2-sat等知识的题,其中2-sat我全部遗......
  • 河南萌新联赛2024第(三)场:河南大学
    河南萌新联赛2024第(三)场:河南大学前言这场应该算是比较简单的了,隔壁都有佬ak了,咱只有8t,还是得加训。A-圆周率日挑战_河南萌新联赛2024第(三)场:河南大学(nowcoder.com)思路Python最有用的一集。抄了个500行的浮点高精度代码爆内存了,改了两个小时也没过,崩溃。代码n=in......
  • 2024牛客暑期多校训练营6
    Abstract好难qwqA-CakeIdea全是博弈!首先来解释题目意思。phase1:给出一颗树,根节点为1,树上每一条边的权值为0或者1。初始时刻,根节点处有一只小马,小G和小O依次控制小马移动,每次只能向子节点移动,若当前节点是叶节点,phase1结束。在移动的过程中,需要记录经过的边的......
  • 2024牛客暑期多校训练营6 A Cake
    题目大意详细题目传送门\(A\)和\(B\)要从轮流走,从根到一个叶子节点位置,\(A\)先。树有边权\(0,1\),按照顺序经过的边权按字符串拼接得到一个串\(S\)。现在\(B\)可以把\(1\)拆分成任意个分数(但不能超过\(S\)的长度,且分数可以为空,)两人按照\(S\)串的顺序选取,如果\(S_......
  • 喜报 | 极限科技入选北京市 2024 年第一批科技中小企业名单
    2024年7月24日,北京市科学技术委员会、中关村科技园区管理委员会发布《关于北京市2024年第一批拟入库科技型中小企业名单的公示》。根据《科技型中小企业评价办法》(国科发政〔2017〕115号)和《科技型中小企业评价服务工作指引》(国科火字〔2022〕67号)有关规定,极限数据(北......
  • 2024.8 - 做题记录与方法总结
    2024.8-RecordofQuestionsandSummaryofMethodology先分享一个歌单:永无止境的八月!2024/08/01先来点重量级的P4768[NOI2018]归程题面:[NOI2018]归程题目描述本题的故事发生在魔力之都,在这里我们将为你介绍一些必要的设定。魔力之都可以抽象成一个\(n\)个节......
  • 2024暑假集训测试17
    前言比赛链接。T1没加记忆化莫名原因T飞了,T2没做过IO交互不知道咋测样例干脆没交,T3到现在还不知道为啥爆零了,赛时不知道咋合并背包根本不敢打,离线下来寻思快点结果全死了,T4不可做题。还是老毛病,遇到之前见的不多题型(尤其是T1、T2放)就寄,这次T1倒是没卡住(但是挂分......
  • 2024.8.1 test
    A\(n\)个点的完全图,\(i\toj(i<j)\)的边权是\(u_j-u_i\),问最小生成树。\(n\le3e5\)。考虑boruvka算法。boruvka算法是重复以下过程,直到只有一个连通块。找到所有连通块的连向外面的最小边,并把这些边加入最小生成树。不难发现这是最多做\(\logn\)次的。我们现在考虑......
  • 2024年1月刷题记录
    2024年1月1日【leetcode】1599.经营摩天轮的最大利润题意:你正在经营一座摩天轮,该摩天轮共有4个座舱,每个座舱最多可以容纳4位游客。你可以逆时针轮转座舱,但每次轮转都需要支付一定的运行成本runningCost。摩天轮每次轮转都恰好转动1/4周。给你一个长度为n的......