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: […]
一道很经典的费用流题目,也是第一次写费用流.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: […]
给出c个数,判断它们能不能表示成两个定义在正整数集中的完全平方数的和.看<什么是数学>看多了=.=…
传说中的A7大牛的强力解法,1.8x秒过掉,zch的纯暴力(带sqrt的)就挂了…见程序,l和r的应用是经典…加上下面的while循环和if判断,就是整个算法了…好神奇…没有sqrt所以常数小得多.
{SPOJ 91; Two squares or not two squares; TWOSQRS- sqybi’s code- swc}//for my winstyprogram twosqrs_sqybi; const fin = ‘twosqrs.in’; fout = ‘twosqrs.out’; mm = 1000000;
var i, times, cases: longint; n, l, r: int64; f: array[0..mm]of int64;
begin assign(input, fin); assign(output, fout); reset(input); rewrite(output);
for i:=1 to mm do f[i] := int64(i) […]
题意见下:
Killa.sqybi 20:01:20就是说Killa.sqybi 20:01:21有n个任务Killa.sqybi 20:01:24m个限制条件Killa.sqybi 20:01:37每个限制条件都这样描述:t0 k t1 t2 .. tkKilla.sqybi 20:01:46表示t0的完成需要他Killa.sqybi 20:01:52需要t1..tk的完成Killa.sqybi 20:02:03让你输出一个完成序列Killa.sqybi 20:02:12保证靠前的数越小越好Killa.sqybi 20:02:16没了
就这样…建立个有向图随便写个n^2的topsort就AC了.注意如果当前有多个点入度为0,那么选择编号最小的.
{ SPOJ 1846; Project File Dependencies; PFDEP - sqybi’s code - Topsort}//for my winstyprogram pfdep_sqybi; const nn = 100;
var n, m, i, j, k, x, y, t: longint; ind: array[1..nn]of longint; d: array[1..nn, 1..nn]of boolean;
begin readln(n, m); […]
给出一个无向图,问是不是树.一个DFS完事,竟然0.4分…POJ 1308和这个只有输入格式不同.
不多解释.
{ SPOJ 1436; Is it a tree; PT07Y - sqybi’s code - DFS}//for my winstyprogram pt07y_sqybi; const nn = 10000;
var n, m, i, x, y, tot: longint; f, head, adj, next: array[1..nn*2]of longint;
procedure addEdge(x, y: longint); begin inc(tot); adj[tot] := y; next[tot] := head[x]; head[x] := tot; end;
function […]
Liked it here?
Why not try sites on the blogroll...