求逆序对个数,很经典了.可以归并排序求,可我不喜欢归并,所以我的做法是离散化之后用树状数组维护一下.复杂度一样,离散化也不是很难写,树状数组也巨简单.强烈推荐.
这题极其bt的是,答案是int64的…用longint存答案就WA on 14(还是12?)…
{ SGU 180; Inversions - sqybi’s code - 逆序对}//for my winstyprogram sgu180_sqybi; const nn = 65537;
type rec = record v, p: longint; end;
var n, i, t, r: longint; s: int64; a: array[1..nn]of rec; b, c: array[1..nn]of longint;
procedure qsort(l, r: longint); var i, j, d: longint; t: rec; […]
给出n个数,判断它们的m次方能不能被k整除.对每个数和k分解质因数即可(注意对于每个数只需要分解k的因子).
{ SGU 117; Counting - sqybi’s code}//for my winstyprogram sgu117_sqybi; const nn = 10000;
var i, j, k, kk, l, n, m, s, t: longint; a, b, p: array[1..nn]of longint; f: boolean;
begin readln(n, m, k); kk := k; l := 0; for i:=2 to kk do begin if k = 1 then […]
可以发现,一个数平方的最后9位只和这个数的最后9位有关.对1~9位数随便写个小程序枚举一下,就可发现:对于1位数到8位数,没有任何符合条件;对于9位数,有8个数符合条件;对于n位数(n>9),最高位有9种(1~9),后9位有8种,剩余n-10位每位10种(0~9),总共72*10^(n-10)种.
{SGU 107; 987654321 Problem- sqybi’s code}//for my winstyprogram sgu107_sqybi; var i, n: longint;
begin readln(n); if n <= 8 then writeln(0) else if n = 9 then writeln(8) else begin write(72); for i:=1 to n-10 do write(0); end; end.
阅读(111 次)
找到最靠后的一个满足它左边的’(’比’)’数量多的’(’,改成’)’,然后在后面补(…()…)和)…).好久以前就写过的题.刚才写错了一点,在最后填括号的时候先填(…()…),再填)…).
{ SGU 179; Brackets light - sqybi’s code}//for my winstyprogram sgu179_sqybi; var i, l, r, tr, t: longint; s: ansistring;
begin readln(s); l := length(s); t := 0; r := 0; for i:=1 to l do begin if (t > 0) and (s[i] = ‘(’) then begin tr := t; r := i; end; […]
这道题WindyWinter牛给出的算法是并查集,实际上可以DFS解决(感谢alft…).
每个人选的两个课程之间连无向边,然后DFS时进行黑白染色,DFS树上每个结点和他的父亲节点不同色.然后考虑横向边和返祖边,如果有一条边两边的结点颜色相同则说明无解,否则将白色的考试放在一天,黑色的放在另一天就可以了…并查集当然也没错…
注意会是一个森林,需要多次DFS…
{ SGU 172; eXam - sqybi’s code - DFS}//for my winstyprogram sgu172_sqybi; const nn = 200; mm = 30000;
var n, m, tot, i, x, y, t: longint; flag: boolean; head, p: array[1..nn]of longint; adj, next: array[-mm..mm]of longint;
procedure addEdge(x, y: longint); begin inc(tot); adj[tot] := y; next[tot] := head[x]; head[x] := tot; […]
Liked it here?
Why not try sites on the blogroll...