很简单的二分答案,不过要注意一点,题目所说的自然数不包括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 […]
n皇后问题,其中n<=50,而且棋盘上有一些部分已经放置皇后.Dancing Links算法搞掉,另外jl大牛似乎用一个改进的DLX算法(貌似是一个十八向的链表…)用极快的速度AC了这道题…另:C++比Pascal快一倍,真TMD无语…
{ SPOJ 1771; Yet Another N-Queen Problem - sqybi’s code - DLX}//for my winstyprogram nqueen_sqybi; const nn = 50; tt = nn * 6 - 2 + nn * nn * 4;
var n, i, j, k, temp, tot: longint; a: array[1..nn]of longint; col, row, u, d, l, r, size: array[0..tt]of longint; used: […]
水题.求出中位数即可.
根据WindyWinter的blog,有两点注意.
Pascal注意,读入n对数时,应该用read而不是readln,因为虽然样例数据有换行,但题目中的描述是没有换行的.否则会像我一样WA on 14.
C++注意,iostream会TLE on 12.
{ SGU 114; Telecasting station - sqybi’s code}//for my winstyprogram sgu114_sqybi; const nn = 15000;
type rec = record p, v: longint; end;
var s, t, n, i: longint; a: array[1..nn]of rec;
procedure qsort(l, r: longint); var i, j, d: longint; t: rec; begin if l >= r […]
一道很经典的费用流题目,也是第一次写费用流.SPFA写错了一点.另外终于理解上次SGU那道题为啥可以用费用流了…
题目描述懒得写了…建图的方法:s到每个盒子连边,容量为盒子里球的数量,费用0.盒子到t连边,容量为1,费用0.相邻的两个盒子连边,容量为正无穷,费用1.要求的就是最小费用.
{ SPOJ 371; BOXES - sqybi’s code - 最小费用最大流}//for my winstyprogram boxes_sqybi; const nn = 1000; inf = 100000000; mm = nn * 4; tt = nn + 2;
var cases, times, n, m, s, t, i, x, y, qs, ql, temp, now, res: longint; head, dist, go, path, pathEdge: array[1..tt]of longint; q: […]
这道题很神奇…好久没做这么神奇的题目了.
首先对于两个数a,b,如果可以解出的话,一定可以用如下方法解决(一定在500步以内):首先定义minP(x)为x除了1以外最小的因数.如果a是奇数,那么a’<-a+minP(a);如果b是奇数,那么b’<-b-minP(b).这样a和b就都成了偶数.然后假设每次存在最大的k使得a’+2^k<b’,那么让a’<-a’+2^k,直到a’=b’为止.这样就找到了一个解(a, a’, a”, a”’, …, b’, b).
挺神奇的…
{ SGU 330; Numbers - sqybi’s code}//for my winstyprogram sgu330_sqybi; var da, db: double; a, b, pa, pb, t, r: int64; i, l: longint; path: array[1..500]of int64;
begin readln(a, b); if a = 2 then begin writeln(’Impossible’); halt; end; da := a; db := b; pa := 0; […]
Liked it here?
Why not try sites on the blogroll...