还记得一个月以前那个牛逼逼的暑假计划

现在又到暑假结束的时候了......

我想日历个8.28变成7.28。

一位靓女同学如是说.

不过我挺想快点开学的,在学校是压抑,在家里也是压抑的,orz

那么这个暑假干了点什么呢?先来检查一下:

• 0.早睡早起

• 间歇性,有选择性的做到...

• 1.OI方面继续搜索和DP的学习,

• 在DP深渊杯具中...

• 2.多去切题,希望USACO能做到3

好吧,3是3,是2.3

• 3.把研究性学习的网站重写

Done!

• 4.配置好ubuntu(麻痹,ibus真是垃圾啊)

用着还好,没有弄出什么大问题

• 5.多看几本书,多看几部电影

看了25部左右吧...

• 6.听听VOA,学学英语

别提了...掩面ing

---------------------------------------------------------------------------------
检查完毕,再次掩面
这是一个让我变宅的暑假,基本就在家待着,待着,待着,待着......当然,生活还不是那么闷的,还有妈妈的无厘头责骂,老爸的间歇性冷漠,然后还有强烈反应的生成物:吵架.

看到别人那个壮观而又温馨的Fifty happy things.,哦,天哪,怎么你(们)的暑假能过得这样欢乐这可令我想起了大雄(他还有叮当)和菊次郎之夏里的那个内向小孩(他还能去徒步轻狂一下),而我呢,就是坐在家里,等,killing time at home,get busy living, or get busy dying.

妈妈一直都说我懒,我笨,确实是啊,洗了一个暑假的碗,怕了额；叫我煮一顿饭,我确实不会；让我弄点其他什么的吧,基本都是拖后腿的,可怜的妈妈,劳碌了一个夏季......
最近真的很害怕待在家,先不说像什么社会青年的问题,而最迫切的是这个家让我感觉到高压(当然,我爸高血压了),别人是多么牛逼牛逼,而我们家,能少点冷战和吵闹就好了,没有尝试过如此恐怖,如此无助,当你体会到这种不可言喻(显然我是没解释吧)的感觉的时候,你会明白的.我也明白家家有本难念的经,我希望我家能变得温馨点就好,希望如此......
我一直很讨厌拉家常的.

普希金写过

假如生活欺骗了你，
不要忧郁，也不要愤慨！
不顺心时暂且克制自己，
相信吧，快乐之日就会到来。

不知道他这首诗是写给谁的呢?也希望能有一点用处吧.

还有一件令人伤心的事:我近视加深了,可恶的发光的耀眼的19寸的宽屏的电脑显示器,可怜的可怜的可怜的可怜的可怜的眼睛；再次对干涩到不能流眼泪的双眼表示抱歉.

----------------------------------------------------------------------------------
说了一大堆(其实是冰山一角)的郁闷,该谈点开心的吧(对fifty happy things感到压力),
最令我开心的是:和几个女孩的关系好点了；
还有认识了河南的几个同龄人,都是可爱的娃,哈哈
还有什么么?貌似真的没有了,orz

-----------------------------------------------------------------------------------
有时半夜这么辗转难眠,却一点也想不出自己在想什么,当人们在谈论失眠的时候他们在谈论什么?或许就是为生活一点苦闷而感到踌躇吧；白云苍狗,多少人生历险尚待我去探索；长路漫漫,走马观花；或是心里还有一点自留地,给予这个曾经疲倦过,疯狂过,快活过,放荡过的自己；时运不齐，命运多舛，冯唐易老，李广难封；没有朋友,没有欢呼,没有搀扶,人生就是这样跌跌宕宕中过去；如同走过一片沙滩,只留下自己的38号的脚印.

这就是我的夏天了,一个简简单单的夏天.
我的夏天结束了.

贴两张这个假期写的代码行数,还没有算上一些html,shell脚本的杂货

题目描述

就是一个双线程DP,可以选择以斜线为状态或者以坐标和为状态(其实都一样,坐标和就可以减少一点判断,斜线在速度上却占优,orz)
显然可以将四维降到三维了

f[k,x1,x2]=max{f[k-1,x1,x2],f[k-1,x1-1,x2-1],f[k-1,x1-1,x2],f[k-1,x1,x2-1]}

这里对应着四种状态:

• 路线1,2都向下走
• 路线1,2都向右走
• 路线1向右,2向下
• 路线1向下,2向右

不过有个问题,我在开始写的时候把答案写成了 f[m+n,n,m] 结果就傻冒了很久......最近人品差啊
[cc lang="pascal"]const
maxn=51;
var
map:array[0..maxn,0..maxn] of longint;
f:array[-10..maxn*2,0..maxn,0..maxn] of longint;
m,n,k,x1,x2:longint;

procedure Init;
var
i,j:longint;
begin
readln(n,m);
for i:=1 to n do
begin
for j:=1 to m do
read(map[i,j]);
readln;
end;

fillchar(f,sizeof(f),0);
end;

function whoMax(a,b,c,d:longint):longint;
var
t:longint;
begin
t:=a;
if b>t then t:=b;
if c>t then t:=c;
if d>t then t:=d;
exit(t);
end;

begin
Init;

for k:=3 to n+m do
for x1:=1 to k-1 do
for x2:=1 to k-1 do
begin
if (kn+m)and(x1=x2) then continue;
f[k,x1,x2]:=whoMax(f[k-1,x1,x2],f[k-1,x1-1,x2-1],f[k-1,x1-1,x2],f[k-1,x1,x2-1]);
inc(f[k,x1,x2],map[x1,k-x1]+map[x2,k-x2]);
end;

writeln(f[n+m,n,n]);
end.
[/cc]

多重背包介绍

不过纳闷的是,里面那个:

将第i种物品分成若干件物品，其中每件物品有一个系数，这件物品的费用和价值均是原来的费用和价值乘以这个系数。使这些系数分别为1,2,4,...,2^(k-1),n[i]-2^k+1，且k是满足n[i]-2^k+1>0的最大整数。例如，如果n[i]为13，就将这种物品分成系数分别为1,2,4,6的四件物品。

摊分方法让我想了好久都不明白什么意思,上网搜索基本都是照搬dd的chapter 3......

不过突然恍然大悟:

用13为例子,我们按照上面的方法可以分成系数:1 2 4 6的四件物品,那么,从1..13的序列我们就可以用这4个数字来表示了,这样既可以减少了逐个枚举的复杂度,又能转化为0,1背包来做了,这里用到了化整为零的方法.

--------------------------------类似题目----------------------------------
逃亡的准备@rqnoj(题目数据描述有点问题,尽量将数组开大比较好)
公路乘车@tyvj

---------------------------------------------------------------------------
我数学太差了,轻拍......最近学DP真够痛苦啊,果然陷入了一个看得懂,可就是不会做的尴尬处境......反正补课推迟了,多出来的假期继续学下去吧......

杜甫

蒋兆和画过的《杜甫像》让人记忆尤深:杜甫端坐在青石上,抬头仰望苍天,是长息过后,还是对落魄河山的概叹呢?尽管已经年迈体衰,但他心中的那份责任却永不褪色,在历史长河洗刷出一道光亮。
尽管他年少就尽显才华,但却一生仕途惨淡,纵有"一览众山小"的壮志却难以兑现.而后生活被拖进战乱之中,纷飞战火使他发出"家书抵万金"的哀叹；三吏、三别的深情控诉。战火终于在他的后半程人生中结束，但生活的窘困以及现实的残酷，迫使他劳碌奔波，不断变迁的生活使他体会到更多的世态炎凉。最终只能在一叶小舟上结束匆匆的人生。
但这只是在长度上的匆匆而过，而他的人生的宽度以及思想的深度却远远大于目之所及：他的一生留下无数写实诗篇就是最好的见证。
杜甫是一个敢言直白的人，立志要扬忠言，却屡次被贬。但他始终把社会安危放在第一位。不管他是在河山中放荡游历，还是在纷乱战火中为生存奔波，抑或是退隐草堂，都离不开对人间的关注。他愤怒写下的《丽人行》；绝望中写下的《春望》；无奈中挥出的《三吏》、《三别》；以及在愤懑中谱出的《茅屋为秋风所破歌》，都饱含着对迂腐统治、惨淡民生的关注。
而放眼当下，又有多少人能够像老杜一样事事总关情呢？太多的物质追求把现代人的贪婪本性展现出来；畏言忌弊的风气仍然充斥于生活之中。所谓的“作家大师”，莫不是都患上了“真话缺失症”?终日沉浸在虚幻的名衔当中，写的是空中楼阁，丝毫没有一种立足于现实的思想。难道中国人缺的是墨水么？不，缺乏的是像杜甫一样的责任感，勿论老杜给后世带来多少的文学影响，单是他那份热枕的忧世情怀就足以让后人所景仰。
纵使安史之乱让杜甫劳碌于战火之中，即使君主昏庸无道，偏听小人让杜甫落寂于官半夜凉初透场之上，尽管生活的穷困潦倒令杜甫饱受艰苦，但是那颗责任之心却继续在历史长河中闪亮，恰似他的一句诗：“千秋万岁名，寂寞身后事”，这是他一生最好的诠释。

--------------------------------------------------

高一上学期写的一篇读后感,居然被老师拿去校刊发表了...

题目描述

额,一道背包问题的变形,我开始还想用搜索去做呢,结果显而易见,会爆掉的...

[cc lang="pascal"]{
ID:bcxx
PROG:subset
LANG ASCAL
}
const
maxn=40*39 shr 1;
var
f:array[0..maxn] of int64;
n,half,i,j:longint;

begin
assign(input,'subset.in');reset(input);
assign(output,'subset.out');rewrite(output);
readln(n);
half:=(1+n)*n shr 1;
if odd(half)or(n=1)or(n=5) then
begin
writeln(0);halt;
end;
half:=half shr 1;

fillchar(f,sizeof(f),0);
f[0]:=1;
for i:=1 to n do
for j:=half downto i do
f[j]:=f[j]+f[j-i];

writeln(f[half] shr 1);
close(input);close(output);
end.
[/cc]

Executing...
Test 1: TEST OK [0.000 secs, 216 KB]
Test 2: TEST OK [0.000 secs, 216 KB]
Test 3: TEST OK [0.000 secs, 216 KB]
Test 4: TEST OK [0.011 secs, 216 KB]
Test 5: TEST OK [0.000 secs, 216 KB]
Test 6: TEST OK [0.000 secs, 216 KB]
Test 7: TEST OK [0.000 secs, 216 KB]

All tests OK.
YOUR PROGRAM ('subset') WORKED FIRST TIME! That's fantastic
-- and a rare thing. Please accept these special automated
congratulations.

其实也是很好想方程的:
f[i,j]=f[i-1,j]+f[i-1,j-i];
其中 i表示前i个数,j表示由前i个数组成的和

然后我们可以先有一点优化:
显然如果 1..n的和是奇数的话就是无解了,不过显然用爆搜还是会爆掉的；
然后我们就可以将问题转化为:

一个容量为1..n的和的一半的背包(拗口不?),用1..n的n件物品去填充,问能恰好填满的结果有多少种?

这样我们就能够从0,1背包转变到一个统计结果的递推问题上来,然后再使用滚动数组,就能得到以下降了一维的方程:

f[j]=f[j]+f[j-i] {1<=i<=n,i<=j<=(n+1)*n/2}

现在觉得做动规关键就是要将问题转化......

---------------------------------
话说这两天腰好痛啊...

最近用GAE折腾了两个静态站点,一个是研究性学习的,一个是个人首页

嗯,先上图吧

话说现在这个研究性学习的网站和原来的设计稿有很大出入了......

感谢国家还保留这像GAE那样好的东西......

以后有空再继续完善吧,不过暂时还不想在python+django上太深入,毕竟也准备开学了......

好吧,希望这个标题能够帮我吸引注意......

题目描述

一眼看穿是背包的题目,一道一点都不会做的题目,oh yeah!

后来看了题解,其实就是一个二维背包,只要再加一维就ok了
[cc lang="pascal"]
for i:=1 to n do
for j:=rmb downto grmb[i] do
for k:=rp downto grp[i] do
[/cc]

但是有个不同点就是他有两个价值:

他想知道,自己泡到最多的MM花费的最少时间是多少.

所以呢,需要改变一下决策来保证两个价值都达到最优
[cc lang="pascal"]
if (g[j,k]f[j-grmb[i],k-grp[i]]+gtime[i])and(g[j-grmb[i],k-grp[i]]+1=g[j,k])) then
begin
f[j,k]:=f[j-grmb[i],k-grp[i]]+gtime[i];
g[j,k]:=g[j-grmb[i],k-grp[i]]+1;
end;
[/cc]

现在的决策就变为:

• 1.当前人数可以增加
• 2.当前人数不变,但是花费时间更少

最后结果还是f[rmb,rp](用g记录人数,f记录时间)
[cc lang="pascal"]
var
gtime,grmb,grp:array[1..1000] of longint;
f,g:array[1..1000,1..1000] of longint;
rmb,rp,n,i,j,k:longint;

procedure Init;
var
i:integer;
begin
readln(n);
for i:=1 to n do
readln(grmb[i],grp[i],gtime[i]);
readln(rmb,rp);
end;

begin
Init;

fillchar(f,sizeof(f),0);
fillchar(g,sizeof(g),0);

for i:=1 to n do
for j:=rmb downto grmb[i] do
for k:=rp downto grp[i] do
if (g[j,k]f[j-grmb[i],k-grp[i]]+gtime[i])and(g[j-grmb[i],k-grp[i]]+1=g[j,k])) then
begin
f[j,k]:=f[j-grmb[i],k-grp[i]]+gtime[i];
g[j,k]:=g[j-grmb[i],k-grp[i]]+1;
end;
if f[rmb,rp]=3 then writeln(2) else
writeln(f[rmb,rp]);
end.

[/cc]

当然,可以将泡妞时间转化为剩余时间,我们只需要用一个很大的时间maxtime-time[i]来作为花费,把决策变为剩余时间最多,显然就能泡到最多的妞了......(邪有暗香盈袖恶啊)

以上都是基于其他大牛们的题解而写出的.

容易得让人发指...纯暴力搜索题......

题目描述
[cc lang="pascal"]{
ID:bcxx
PROG:hamming
LANG ASCAL
}
const
maxn=64;
maxb=8;
maxd=7;
var
N,B,D,upperlimit,count,i,j:integer;
flag:boolean;
ans:array[1..maxn] of integer;

procedure Init;
begin
assign(input,'hamming.in');reset(input);
assign(output,'hamming.out');rewrite(output);
readln(N,B,D);
upperlimit:=2 shl (B-1);
end;

function isLegal(k,m:integer):boolean;
var
i,c,temp:integer;
begin
temp:=k xor m;
c:=0;

for i:=1 to B do
begin
if temp and 1=1
then inc(c);
temp:=temp shr 1;
end;
if c>=D
then exit(true)
else exit(false);
end;

begin
Init;

ans[1]:=0;count:=1;i:=1;

while (count<=N) and (i<=upperlimit) do
begin
flag:=true;
for j:=1 to count do
if isLegal(i,ans[j])=false then
begin
flag:=false;
break;
end;
if flag then
begin
inc(count);
ans[count]:=i;
end;

inc(i);
end;

for i:=1 to N-1 do
if i mod 10=0
then writeln(ans[i])
else write(ans[i],' ' ;
writeln(ans[N]);
close(input);close(output);
end.

[/cc]

Compiling...
Compile: OK

Executing...
Test 1: TEST OK [0.011 secs, 208 KB]
Test 2: TEST OK [0.000 secs, 208 KB]
Test 3: TEST OK [0.000 secs, 208 KB]
Test 4: TEST OK [0.011 secs, 208 KB]
Test 5: TEST OK [0.000 secs, 208 KB]
Test 6: TEST OK [0.011 secs, 208 KB]
Test 7: TEST OK [0.011 secs, 208 KB]
Test 8: TEST OK [0.011 secs, 208 KB]
Test 9: TEST OK [0.011 secs, 208 KB]
Test 10: TEST OK [0.011 secs, 208 KB]
Test 11: TEST OK [0.011 secs, 208 KB]

All tests OK.
Your program ('hamming') produced all correct answers! This is your
submission #2 for this problem. Congratulations!

不过第一次还是忘记了最后的空格问题......

------------------------------wiki-----------------------------
虽然题目很水,不过hamming (汉明码)真的是一样很牛逼的东西......wiki
总之现在就是看不懂......

典型的DFS......当然用枚举+位运算也可以

题目描述
[cc lang="pascal"]{
ID:bcxx
PROG:holstein
LANG ASCAL
}
const
maxV=30;
maxG=20;
type
uu=array[1..maxG] of boolean;
rr=array[1..maxV] of integer;
var
require:rr;
used,ans:uu;
feed:array[1..maxG] of rr;
V,G:integer;
a:int64;

procedure Init;
var
i,j:integer;
begin
assign(input,'holstein.in');reset(input);
assign(output,'holstein.out');rewrite(output);
readln(V);
for i:=1 to V-1 do
read(require[i]);
readln(require[V]);

readln(G);
for i:=1 to G do
begin
for j:=1 to V do
read(feed[i,j]);
readln;
end;

fillchar(used,sizeof(used),false);
a:=2 shl 40;
end;

function isEnough(t:uu):boolean;
var
i,j:integer;
temp:rr;
begin
fillchar(temp,sizeof(temp),0);
for i:=1 to G do
if t[i] then
for j:=1 to V do
inc(temp[j],feed[i,j]);

for i:=1 to V do
if temp[i]<require[i] then exit(false);
exit(true);
end;

procedure whoBetter(t:uu);
var
i:integer;
temp:int64;
begin
temp:=0;
for i:=1 to G do
if t[i] then
temp:=temp*10+i;
if tempG
then exit
else begin
used[depth]:=true;
if isEnough(used) then
whoBetter(used);
DFS(depth+1,used);
used[depth]:=false;
DFS(depth+1,used);
end;
end;

begin
Init;
DFS(1,used);
PrintANS;
end.
[/cc]

Compiling...
Compile: OK

Executing...
Test 1: TEST OK [0.000 secs, 208 KB]
Test 2: TEST OK [0.011 secs, 208 KB]
Test 3: TEST OK [0.011 secs, 208 KB]
Test 4: TEST OK [0.011 secs, 208 KB]
Test 5: TEST OK [0.000 secs, 208 KB]
Test 6: TEST OK [0.000 secs, 208 KB]
Test 7: TEST OK [0.011 secs, 208 KB]
Test 8: TEST OK [0.011 secs, 208 KB]
Test 9: TEST OK [0.119 secs, 208 KB]
Test 10: TEST OK [0.086 secs, 208 KB]

All tests OK.
YOUR PROGRAM ('holstein') WORKED FIRST TIME! That's fantastic
-- and a rare thing. Please accept these special automated
congratulations.

PS1:不过用DFS这种对比方法速度真的是很慢啊.....一开始还把数据范围开小了,杯具啊.

PS2:看来晚上写代码是不行的,还是早上写吧.....

PS3:下面插播一个非常慢,非常恶心的位运算+枚举的方法:
[cc lang="pascal"]{
ID:bcxx
PROG:holstein
LANG ASCAL
}
const
maxV=25;
maxG=15;
var
require:array[1..maxV] of integer;
feed:array[1..maxG,1..maxV] of integer;
G,V,i,j,ans,ans_count:integer;
a:int64;

procedure isEnough(b:integer);
var
i,j,t,count:integer;
temp_require:array[1..maxV] of integer;
c:int64;
begin
t:=b;c:=0;count:=0;
fillchar(temp_require,sizeof(temp_require),0);
for i:=1 to G do
begin
if (t and 1)=1 then
begin
for j:=1 to V do
inc(temp_require[j],feed[i,j]);
c:=c*10+i;
inc(count);
end;
t:=t shr 1;
end;

for i:=1 to V do
if temp_require[i]<require[i]
then exit;
if c<a then
begin
a:=c;
ans:=b;
ans_count:=count;
end;
end;

begin
assign(input,'holstein.in' ;reset(input);
assign(output,'holstein.out' ;rewrite(output);
readln(V);
for i:=1 to V do
read(require[i]);
readln;
readln(G);
for i:=1 to G do
begin
for j:=1 to V do
read(feed[i,j]);
readln;
end;

a:=2 shl 40;
for i:=1 to (2 shl (G-1))-1 do
isEnough(i);

write(ans_count);
for i:=1 to G do
begin
if ans and 1=1 then write(' ',i);
ans:=ans shr 1;
end;
writeln;
close(input);close(output);
end.
[/cc]

关键还是对比那里太慢了,得想想办法加快一点,话说要重新看看M67的位运算了......

PS4:看了nocow上的位运算标程,他们也不过8,9ms左右,我的DFS是9ms,位运算是8ms......但是为什么sznoi上的神牛们能1ms就过了呢?难道是打表cheat过去的?

天哪,好简单的一道题目......

题目描述

[cc lang="pascal"]{
ID:bcxx
PROG:frac1
LANG ASCAL
}
type
node=record
d,m:integer;
end;
var
num:array[1..maxint] of node;
n,a,b,count:integer;

function gcd(a,b:integer):integer;
begin
if a mod b=0
then exit(b)
else exit(gcd(b,a mod b));
end;

function gtr(a,b:node):boolean;
begin
if a.d*b.m>b.d*a.m
then exit(true)
else exit(false);
end;

procedure qsort(l,r:integer);
var
i,j:integer;
k,t:node;
begin
i:=l;j:=r;
k:=num[(i+j) div 2];

repeat
while gtr(k,num[i]) do inc(i);
while gtr(num[j],k) do dec(j);
if ij;

if il then qsort(l,j);
end;

begin
assign(input,'frac1.in');reset(input);
assign(output,'frac1.out');rewrite(output);
readln(n);

count:=1;
for a:=1 to n do
for b:=n downto a+1 do
if gcd(a,b)=1 then
begin
num[count].d:=a;
num[count].m:=b;
inc(count);
end;
dec(count);
qsort(1,count);

writeln(0,'/',1);
for a:=1 to count do
writeln(num[a].d,'/',num[a].m);
writeln(1,'/',1);
close(input);close(output);
end.[/cc]

Compiling...
Compile: OK

Executing...
Test 1: TEST OK [0.000 secs, 336 KB]
Test 2: TEST OK [0.011 secs, 336 KB]
Test 3: TEST OK [0.000 secs, 336 KB]
Test 4: TEST OK [0.011 secs, 336 KB]
Test 5: TEST OK [0.011 secs, 336 KB]
Test 6: TEST OK [0.011 secs, 336 KB]
Test 7: TEST OK [0.000 secs, 336 KB]
Test 8: TEST OK [0.011 secs, 336 KB]
Test 9: TEST OK [0.011 secs, 336 KB]
Test 10: TEST OK [0.011 secs, 336 KB]
Test 11: TEST OK [0.032 secs, 336 KB]

All tests OK.
Your program ('frac1') produced all correct answers! This is your
submission #3 for this problem. Congratulations!

不过有个插曲就是我把writeln输出看作一行输出......囧

再看看题解居然还有个数学方法来递归找的...牛啊
其实代码里在求gcd还可以优化下的...