【Atcoder】AGC 020 B - Ice Rink Game 递推
2024-09-21 06:37:39
【题意】n个人进行游戏，每轮只保留最大的a[i]倍数的人，最后一轮过后剩余2人，求最小和最大的n，或-1。n<=10^5。
【算法】递推||二分
【题解】令L(i),R(i)表示第i轮过后的最小人数和最大人数。
令X(i)和Y(i)表示区间[L(i),R(i)]中最小的a[i]倍数和最大的a[i]倍数。
L(i-1)=X(i)，R(i-1)=Y(i)+a[i]-1。
X(i)=L(i)/a[i]（上取整），Y(i)=R(i)/a[i]（下取整）。
答案为L(0),R(0)。
#include<cstdio>
int n,a[];
long long L=,R=;
int main(){
scanf("%d",&n);
for(int i=;i<=n;i++)scanf("%d",&a[i]);
for(int i=n;i>=;i--){
L=((L-)/a[i]+)*a[i];
R=R/a[i]*a[i]+a[i]-;
}
if(L>R)printf("-1");else printf("%lld %lld",L,R);
return ;
}
所以，求什么设什么，还是有道理的O_O……
最新文章
- CentOS yum 源的配置与使用
- Sublime Text使用配置介绍
- 学习Python的第一课(简单的单元测试)
- python在linux上的GUI无法弹出界面
- Centos7 打开80端口防火墙命令
- JavaScript之Ajax
- require.js学习笔记
- Using F2 to Rename Open Files
- 关于多台机器之前session共享，sessionState mode="StateServer" 问题的困扰
- 积极参与开源项目，促进.NET Core生态社区发展
- GlusterFS 安装 on centos7
- pyqt5-定时器
- 解决：error LNK2026: 模块对于 SAFESEH 映像是不安全的
- SQL Server CTE 递归查询全解
- Validation in jQuery
- day44 数据库学习 索引 引用自egon 老师博客
- Working routine CodeForces - 706E (链表)
- pytest使用笔记（二）——pytest+allure配置使用
- Spring Boot 学习笔记 - 01
- JavaScirpt(JS)——js介绍及ECMAScript