首页 > 其他分享 >CF1634D Finding Zero

CF1634D Finding Zero

时间:2024-03-29 15:45:43浏览次数:25  
标签:CF1634D int MAX 最大值 保留 leq Zero Finding include

原题链接 每日一题系列。

在做过 CF1762D GCD Queries 后发现这个题跟那个 trick 一模一样,所以切了,尽管做那道的时候没有想出来。


每次任意选出四个数 \(a,b,c,d\),规定 \(a\leq b\leq c\leq d\)。考虑询问这四个数中所有组合。然后仅保留可能为 \(0\) 的位置,剩下的删掉。

\(f(a,b,c)=c-a,f(a,b,d)=d-a,f(a,c,d)=d-a,f(b,c,d)=d-b\)。

发现 \(d-a\geq c-a\),当 \(c=d\) 时取等;\(d-a\geq d-b\),当 \(a=b\) 时取等;所以这四个结果中会有 \(2\sim 4\) 个最大值。

当最大值个数为 \(2\),此时 \(a\not=b,c\not=d\)。我们的目的是保留 \(a\),因为 \(a\) 最小,只有 \(a\) 有可能是 \(0\)。实际我们无法分辨 \(a\) 和 \(d\),所以均保留,即保留在这两个最大值对应情况中都出现的数。

当最大值个数为 \(3\),此时有两种情况。当 \(a=b,c\not=d\)。因为 \(0\) 只有一个,所以 \(a\) 也不会是 \(0\),我们不需要保留任何数。当 \(a\not=b,c=d\)。我们的目的仍是保留 \(a\),此时 \(a\) 是在三个最大值对应情况中都出现的数。实际我们无法分辨到底是哪两个数相等,所以无论究竟是哪种情况都保留在三个最大值对应情况中都出现的数。

当最大值个数为 \(4\),此时 \(a=b,c=d\),一个都不需要保留。

所以总结起来就是每次保留在每个不为最大值对应情况中出现的数。每次最少删掉两个,最多操作步数为 \(\lceil\dfrac{n-2}{2}\rceil\times 4\),刚好卡上界。

#include<stdio.h>
#include<iostream>
#include<algorithm>
using namespace std;
const int MAXN=3010;
int T,n,p[MAXN],tot;
inline void add(int k)//加回来一些数直到够 k 个
{
    for(int i=1;tot<k;++i)
    {
        bool flag=true;
        for(int j=1;j<=tot;++j)
            flag&=(p[j]!=i);
        if(flag) p[++tot]=i;
    }
}
inline void work()
{
    cin>>n;tot=n;
    for(int i=1;i<=n;++i) p[i]=i;
    while(tot>2)
    {
        int a[5],b[5],MAX=-1;add(4);//不够 4 个要加到 4 个
        for(int i=1;i<=4;++i) a[i]=p[tot--];
        for(int i=1;i<=4;++i)
        {
            cout<<"? ";
            for(int j=1;j<=4;++j)
                if(j!=i) cout<<a[j]<<' ';
            cout<<endl;cin>>b[i];MAX=max(MAX,b[i]);
        }
        for(int i=1;i<=4;++i)
            if(b[i]!=MAX) p[++tot]=a[i];
    }
    add(2);cout<<"! "<<p[1]<<' '<<p[2]<<endl;
}
int main()
{
    cin>>T;while(T--) work();
    return 0;
}

标签:CF1634D,int,MAX,最大值,保留,leq,Zero,Finding,include
From: https://www.cnblogs.com/int-R/p/18103963/CF1634D

相关文章

  • 嵌入式LINUX开发系列之基于Radxa zero的usb_gadgetEthnet功能配置
    LINUX系列文章目录第二章嵌入式linux开发之基于Radxazero的usb_gadgetEthnet功能配置文章目录LINUX系列文章目录第二章嵌入式linux开发之基于Radxazero的usb_gadgetEthnet功能配置前言一、usb_gadgetEthnet是什么?二、具体操作1.开发板上电,查询网络信息2.usb_gadge......
  • 【微前端】微前端的零信任(Zero-trust)机制应用
    【微前端】微前端的零信任(Zero-trust)机制应用目录【微前端】微前端的零信任(Zero-trust)机制应用零信任如何应用于前端将零信任扩展到微前端1\.独立的构建过程2\.微前端隔离3\.用于微前端组件的身份验证结论推荐超级课程:Docker快速入门到精通Kub......
  • go-zero处理本地事务
    go-zero处理本地事务,sqlx.SqlConn提供了基础的事务机制,官方代码varconnsqlx.SqlConnerr:=conn.TransactCtx(context.Background(),func(ctxcontext.Context,sessionsqlx.Session)error{r,err:=session.ExecCtx(ctx,"insertintouser(......
  • linux 中shell脚本中遇到 Runtime error (func=(main), adr=22): Divide by zero
    在Linux中编写Shell脚本时,遇到“Runtimeerror(func=(main),adr=22):Dividebyzero”这样的错误通常是因为在脚本中进行了除以零的操作,类似于编程语言中的除零错误。要解决这个问题,您需要检查Shell脚本中涉及到除法运算的地方,确保分母不为零。下面是一个示例S......
  • 开源模型应用落地-qwen模型小试-Zero/One/Few Shot-进阶篇(九)
    一、前言  Zero-Shot、One-Shot和Few-Shot是机器学习领域中重要的概念,特别是在自然语言处理和计算机视觉领域。通过Zero-Shot、One-Shot和Few-Shot学习,模型可以更好地处理未知的情况和新任务,减少对大量标注数据的依赖,提高模型的适应性和灵活性。这对于推动人工智能在现实......
  • Meta-Learned Attribute Self-Interaction Network for Continual and GeneralizedZer
    目录摘要介绍releatedworkzero-shotlearning零样本持续学习提出的方法bibtex格式参考文献摘要零样本学习(ZSL)是一种有希望的方法,通过利用类别属性将模型推广到训练期间未见过的类别,但仍然存在挑战。最近,利用生成模型来解决对训练期间已见类别的偏见的方法推动了技......
  • 中考英语首字母快速突破010-2021上海浦东英语二模-Living a Fun Zero-Waste Lifestyle
    PDF格式公众号回复关键字:ZKSZM010原文​Canlivingazero-wastelifestylebetrue?OneNewYorkerisprovingit'snotonlypossible,butitlooksfunaswell.​TheNewYorker,Ms.Singerdidn'tgrowupinareally"green"home.&qu......
  • [Paper Reading] DALLE: Zero-Shot Text-to-Image Generation
    DALLE:Zero-ShotText-to-ImageGenerationDALLE:Zero-ShotText-to-ImageGeneration时间:21.02(与CLIP同期论文)机构:OpenAITL;DR提出一个将文本与图像作为token,利用Transformer的自回归机制来生成图像。使用大规模数据(250M图文Pair)与大模型(12B)训练,模型效果达到可与特定......
  • pytorch使用pytorch_wavelets包错误:ValueError: step must be greater than zero 错误
    错误描述在使用pytorch_wavelets包的DWT1DInverse时,发现报错信息如下:Traceback(mostrecentcalllast):File"/work/GDN/test/test_DWT.py",line24,inx_=idwt((YL,YH))File"/opt/conda/lib/python3.6/site-packages/torch/nn/modules/module.py",line550......
  • aspnet zero 12 添加登录 验证码
       aspnetzero自带的验证码是基于Google,国内当前无法使用,只能替换国内的。实现后的界面如下图: PackageManagerInstall-PackageLazy.Captcha.Core验证码后端代码publicinterfaceICaptchaAppService:IApplicationService{///<summary>......