当前位置: 首页 > news >正文

洛谷月赛T1 P14081 「CZOI-R7」炸弹游戏

竟然做了一晚上才AC
发题解警示自己犯糖
一道思维题,推公式即可


首先手玩一下样例发现 m=1,m=2均无法成功,直接输出
如果大于2一定存在范围[L,R]可以胜利
对于最小值,不难想到对于完全图可以使n最小,且完全图的合法炸弹数一定小于一个m条边的m元环(在环内连接边一定不会更劣嘛)
所以根据公式可知 n*(n-1)>=m,暴力时间复杂度 O(nT) 太劣了,考虑预处理+二分优化,时间复杂度 O(Tlogn+n),比较优

再考虑最大值,注意到对于一条边,让它的贡献最大必然是连接两个孤立点,这样它的贡献是两个点,发现连成链或者环每个边的贡献都不如它优,这样我们每一条边获得了两个点的贡献,同时会有一个炸弹合法,我们只能让m-1个炸弹合法,所以最大有2*(m-1)个点,最后一条边随意连接两个孤立的连通块即可。


火花真可爱awa

代码:

#include<bits/stdc++.h>
#define int long long 
using namespace std;
int m;
const int N=4e5+10;
int f[N]; 
void init()
{for(int i=1; i<=1e5;i++) { f[i]=i*(i-1);}
}int check(int x)
{int l=1,r=1e5;while(l<r){int mid=(l+r)>>1;if(f[mid]>=x) r=mid;else l=mid+1;}return r;
}
signed main(){int T;cin>>T;init(); while(T--){cin>>m;if(m<=2) cout<<"Lose!";else{cout<<check(2*m)<<" ";cout<<2*(m-1);}cout<<endl;}
}
http://www.hskmm.com/?act=detail&tid=22573

相关文章:

  • VMware NSX 4.2.3.1 发布,新增功能概览
  • Claude Code V2集成KAT-Coder
  • Ubuntu 软件源
  • Ceph 分布式存储学习笔记(一):介绍、部署与集群设置(上)
  • 数学学习总结
  • VMware Aria Suite Lifecycle 8.18 Patch 5 发布,新增功能概览
  • P3977 [TJOI2015] 棋盘题解
  • 03. 基本元素
  • 基础整理01:Bode图、PM、GM、极点零点 - 教程
  • [已解决]CUDA error: CUBLAS_STATUS_EXECUTION_FAILED when calling cublasSgemmStridedBatched
  • VMware vCenter Server 7.0U3w 发布 - 集中管理 vSphere 环境
  • VMware Aria Operations 8.18.5 发布,新增功能概览
  • VMware Aria Operations for Logs 8.18.5 发布,新增功能概览
  • 专题:2025医药行业数智赋能与AI应用全景研究报告|附200+份报告PDF、数据仪表盘汇总下载
  • 喵之勇者败北录
  • Windows 作为 Ansible 节点的完整部署流程(含 Docker 部署 Ansible) - 实践
  • 软工
  • 10.1考试T4(swap)题解
  • 基本分段存储管理方式
  • 专题:2025零售数字化与即时零售竞争洞察报告|附130+份报告PDF、数据仪表盘汇总下载
  • 2025/10/1图论
  • 详细介绍:Python 豆瓣TOP250 爬虫类讲解
  • springboot用jar启动能访问,但是打成war,部署到tomcat却访问不到 - 详解
  • 用AirPods控制的创新iPhone游戏:RidePods技术解析
  • oppoR9m电话号码盘对应工程模式
  • 常量
  • Index of /ubuntu-releases/25.10/
  • P10364 [PA 2024] Dzielniki 题解
  • 20251001 之所思 - 人生如梦
  • 25普及联考day6爆炸记