很简单的二分答案,不过要注意一点,题目所说的自然数不包括0(也就是说,如果输入是0,需要输出1.这里WA了2次).
{ SGU 154; Factorial - sqybi’s code - 二分答案}//for my winstyprogram sgu154_sqybi; var n, l, r, mid, i, t, ans: int64;
begin readln(n); ans := 0; l := 1; r := n * 5; while l <= r do begin mid := (l + r) div 2; i := 5; t := 0; while […]
求最大值最小,快排+二分答案.水题,不写题解.
1Y了,比较兴奋.
此题正好练习二分答案.发现在SPOJ上看别人AC哪道就做哪道也不是难事…不过这道题才0.1分…
{ SPOJ 297; Aggressive Cows; AGGRCOW - sqybi’s code - 快排+二分答案}//for my winstyprogram aggrcow_sqybi; const nn = 100000;
var cases, times, n, m, max, l, r, mid, ans, i: longint; a: array[1..nn]of longint;
procedure qsort(l, r: longint); var i, j, d, t: longint; begin i := l; j := r; d := a[(l+r) […]
要求你维护一个序列,支持两种操作:一种是查询某一个区间上的第k小值,一种是将序列中的某个数更改.经典的线段树套平衡树+二分答案.太困了,不想多说为什么这样做,想知道的自己查阅资料.
300行程序,对于我来说其实并不多,可是这是没有用Object的行数.那么估计如果用了object,350行是最少的了.这个东西也不好用object啊,除非写动态的平衡树.
其实挺惊讶于自己今天晚上的准确度,状态奇佳,这么长的程序竟然只出了两个小错(用注释//forgot!标记出来了).不过这两个小错也让我用对拍等手段调了一个多小时…
题目其实还不是很恶心的.Todo List又少了一道题了…不过同时每天也都在多题…
P.S.终于知道正确的二分答案该怎么写了…以前自己写的都太恶心了.
{ZOJ 2112; Dynamic Rankings- sqybi’s code- 线段树+平衡树+二分答案- Interval Tree, Splay}//for my winstyprogram zju2112_sqybi; const nn = 50000; mm = 10000; kk = (mm + nn) * 25; tt = 1000000000;
var cases, times, n, m, i, num, x, y, z, l, r, mid, ans: longint; ch: char; a: array[1..nn]of longint; father, data: array[1..kk]of […]
Liked it here?
Why not try sites on the blogroll...