[BJWC2008]秦腾与教学评估
2024-08-28 09:40:06
二分好题。
怎么二分呢?反正我是没想出来。
看了题解。
因为只有一个为奇数的点,所以对于一个位置x,求出区间[0, x]的教总和,如果为奇数,说明x取大了;否则x取小了(妙啊)。
虽然答案在int内,但是L + R可能会爆int,导致有几个点TLE了,所以还是都开long long 吧。
#include<cstdio>
#include<iostream>
#include<cmath>
#include<algorithm>
#include<cstring>
#include<cstdlib>
#include<cctype>
#include<vector>
#include<stack>
#include<queue>
using namespace std;
#define enter puts("")
#define space putchar(' ')
#define Mem(a, x) memset(a, x, sizeof(a))
#define rg register
typedef long long ll;
typedef double db;
const int INF = 0x3f3f3f3f;
const db eps = 1e-;
const int maxn = 2e5 + ;
inline ll read()
{
ll ans = ;
char ch = getchar(), last = ' ';
while(!isdigit(ch)) {last = ch; ch = getchar();}
while(isdigit(ch)) {ans = ans * + ch - ''; ch = getchar();}
if(last == '-') ans = -ans;
return ans;
}
inline void write(ll x)
{
if(x < ) x = -x, putchar('-');
if(x >= ) write(x / );
putchar(x % + '');
} int n;
struct Node
{
ll s, e, d;
}t[maxn]; ll calc(ll x)
{
ll ret = ;
for(int i = ; i <= n; ++i)
{
if(t[i].s > x) continue;
ret += (min(x, t[i].e) - t[i].s) / t[i].d + ;
}
return ret;
} int main()
{
int T = read();
while(T--)
{
n = read(); ll Max = ;
for(int i = ; i <= n; ++i) t[i].s = read(), t[i].e = read(), t[i].d = read(), Max = max(Max, t[i].e);
ll L = , R = Max;
if(!(calc(R) & )) {puts("Poor QIN Teng:( "); continue;}
while(L < R)
{
ll mid = (L + R) >> ;
if(calc(mid) & ) R = mid;
else L = mid + ;
}
write(L), space, write(calc(L) - calc(L - )), enter;
}
return ;
}
最新文章
- jQuery系列:DOM操作
- 耿丹CS16-2班第六次作业汇总
- 【转载】latch: cache buffers chains
- Unity 碰撞检测中碰撞器与触发器的区别
- .net下Ueditor配置(主要讲解上传功能配置)
- [经验][JS]如何观察网站,进而模仿
- c signal
- bzoj 2330: [SCOI2011]糖果
- wpf 调用线程必须为sta 因为许多ui组件都需要
- 9月19号-9月21号丰宁坝上草原行 - 营销系统 - 京东内部论坛 - Powered by Discuz!
- win32api大全
- 使用Python-iGraph绘制贴吧/微博好友关系图
- python——序列 &; 集合 &; 映射
- 【Netty源码解析】NioEventLoop
- .Net Core跨平台应用研究-HelloDDNS(动态域名篇)
- 银盒子智慧餐厅硬件尺寸规格&;推荐机型
- PAT A1113 Integer Set Partition (25 分)——排序题
- [Windows Azure] Windows Azure SQL Database library
- DataTables实现rowspan思路
- 重构 demo篇