- 博客(69)
- 收藏
- 关注
RSS订阅原创 Qt试玩::flyEditor
昨天经过向总的指示+自己心血来潮，如是乎准备去研究一个跨平台的应用程序框架。经过LYP的指点得知了这么两个玩意：QT、GTK+ ；去网上查了一下发现QT和GTK+这两个东西觉不亚于VIM和Emacs之争，各有各的强大。但由于GTK+是纯C风格的，QT是纯C++风格的（类简直用得天昏地暗），最后摇摆不定的选择了QT，当然现在只是玩玩，以后必定是都要学的
2011-10-23 20:23:50
1135
原创 在windows右键菜单中加入“新建CPP”并创建模板
1.首先写好模板文件，随便保存在一个地方，比如我是“E:\mb.cpp”;2.打开注册表（regedit），找到 [HKEY_CLASSES_ROOT] -> [.cpp] （没有的话，自己新建项.cpp）;3.在 [.cpp] 下新建项 [ShellNew] （已经有的
2011-10-08 19:26:22
3767
4
原创 C++果然还是有一个模板写起来要舒服点
#include #include #include #include #include #include #include #include #include #include #include #define PB push_back#define M
2011-10-08 18:51:40
1174
1
原创 TC SRM520 div1
好悲惨啊。。。俺爆0了。。还好没有去cha错别人，要不然就负分了。。第一题暴力枚举吧，暴力枚举都写错了，被一哥们cha掉了~~第二题我打算用荣斥原理做比较方便，先不考虑有从1~ P[X]的限制，令cal(I)=C(I-1,2)，G[I]=cal(i
2011-10-05 01:02:21
1248
原创 光线追踪——最终版
今天又泡了一天的时间在光线追踪上，不过显然，收获颇多。首先是花了半个小时推球体反射折射的式子，然后改了改光源的位置，画出的第一幅图是这样的：完全被吓了一跳，为什么突然变得这么好了？（可以对比昨天的图）唧唧提醒了我，因为我把光源往下拉了，所以导致上方墙壁
2011-10-01 00:16:09
3181
9
原创 光线追踪试玩
经过LRJ大大的指点，我今天花了一天时间写成了我第一个光线追踪！！先暂时上点成果演示，因为我还想继续添加一点新元素，比如加入球体，贴图什么的。首先上一个有镜子的：然后，再上一个有折射的（还有全反射现象哦！）呃 ~~~锯齿是不
2011-09-29 23:03:06
1254
原创 Codeforces Beta Round #88
做CF被血虐。。。下次要扳回来！AB题就pass吧，现在直接切入正题（A掉AB题我都花了1个小时啊，混蛋。。）C给你一个竞赛图，要你找一个三元环。solution竞赛图的意思就是 Aij≠Aji ，一直都忘记用这个性质，悲催。。下面讲一个我翻别人代
2011-09-24 14:54:32
1332
2
原创 TC srm519 div1
第一次做div1，比div2激情多啦250： 在二进制位上从高到低，找到A，B之间第一个不相同的位置，把这一位与后面的所有位改为1输出即可。RPM太低加上英语水平太差，只有180分600： AC自动机+状态压缩DP，这种题很多了。
2011-09-20 17:04:28
817
原创 痛苦的转VIM+GDB+GPP中
最近初学VIM，写了个很丑陋的vimrc，贴出来看看。。set nocompatiblesource $VIMRUNTIME/vimrc_example.vimsource $VIMRUNTIME/mswin.vimbehave mswin "刚学vim，这配置文件以后慢慢加（XP） colorscheme eveningset cursorlineset shift
2011-08-23 23:33:47
1163
1
原创 【重口味。。】CTSC2011杀菌计划
在奋战了7个小时后才AC了这道题的人只能瞻仰在考场上AC的FHQ了。。。代码很恐怖，写了350行8KB，最可恶的是一页草稿纸的伪代码和各种特殊情况。 涉及的几个关键字：三维叉积、半平面交、梯形剖分 三维叉积的一个核心操作就是：三维旋系，另外还需要用来写：面面交，面线交，判三维空间上下左右，二维投影。 具体做法是： 一束光线首先在每一个面上投一个影，然后这个
2011-06-26 19:25:00
2113
原创 组合计数小启发
<br />在DP的领域中还有的很大一部分就是组合计数。<br /> <br />以前做了FHQ在集训队作业中的《连边》这道题，大概就是要你给一个图连边是的若干个点度数为奇数。<br />比较容易发现是一道DP题，但是怎样保证状态不重不漏？<br /> <br />常用的方法就是增维，比如按照排序大小扩展啦，按照字典序扩展啦从而使得状态不重，但是还有两种方法可以使得状态不重不漏，那就是除法和减法！<br /> <br />除法可能大家用的多，比如最常见的组合数就是利用的除法，从排列数除以N!，但是减法就比较
2011-05-20 21:04:00
1123
1
原创 在Ubuntu下一个很棒的对拍程序 for pascal
<br />大家应该都知道如何在windows下面对拍程序，唧唧发明了个在任意平台都试用的对拍程序，详见代码:<br />program comp;uses crt,dos;var a,b:string;procedure rd(f:string;var a:string);//用来读入的程序，这里是读第一行begin assign(input,f);reset(input); readln(a); close(input);end;begin repe
2011-05-07 17:31:00
3048
2
原创 正则二分图匹配
<br />正则二分图根据Hall定理（怎么证？）一定存在完美匹配。<br /> <br />当度数正好为2^k时有O(E)的完美匹配算法，那就是每次做一遍欧拉回路然后把欧拉回路上的边隔一条删一条，最后只剩下N/2条边时就是完美匹配。。。。<br /> <br />真是搞笑。。。
2011-04-27 20:14:00
6581
4
原创 【容斥原理+状态压缩】zjoi2009 多米诺骨牌
<br /><br />转送门：zjoi2009 多米诺骨牌<br /> <br /> <br />彻彻底底的被这道题虐了，想了一个月没想出来，最后和宇宙大总统一起强肯了2个小时标程算是看懂了。。<br />首先抛开这道题的那个奇怪的限制（没行列没有骨牌跨过），一个赤裸裸的骨牌覆盖我都不不知道怎么做啊！！<br />先看下赤裸裸的骨牌覆盖怎么做：<br />一般人的反映就会想到状态压缩DP，没错<br />状态为F【I，J】表示第i行的状态为J的方案数>>空间复杂度O（N*2^N），转移O（2^N），写的好
2011-04-19 22:50:00
3466
5
原创 单旋SPLAY的优化
单旋splay的优点是好写，缺点就是太慢了。经过以前大量的正版splay和单旋splay之间的对比发现单旋splay大概要慢50%。。。加上如下几个优化后单旋SPLAY绝对可以媲美正版SPLAY，是PNOI,NOI，居家旅行，哔~~~~~~，必备良数据结构关于单旋splay有如下几个优化（不会加大代码量，要不然还要单旋splay干嘛）：1.对于大量插入操作，写一个过程：buildtree，建议一颗完全二叉树插入树中，很多题目一开始就需要buildtree，所以不会增加代码，在NOI05 sequence中加
2011-04-17 23:38:00
3754
9
原创 OJ记录（11.4.8）
<br />鄙人在h8oj上玩了几天，难题是一道也没有做出来。。。。<br /> <br />大概的总结下，一共有14道：<br /> <br />1.神题A+B problem（代码最短奖）<br />/************************************************************** Problem: 1000 User: ImSB Language: Pascal Result: Accepted Time:0
2011-04-08 22:50:00
3075
原创 【Baby-step giant-step Algorithm】poj3243，hdu2815
等下来填坑。。。program poj3243;const mom=1>1))mod mo; if odd(b) then fmul:=fm
2011-04-03 22:24:00
1590
原创 【单纯形】线性规划的神器
<br />看了Nehzilrz神牛无比风骚的单纯形：POJ 1755 单纯形判定不等式是否成立，骤然对单纯形产生了浓厚的兴趣，遂苦苦钻研算导上的单纯性加上Nehzilrz神牛漂亮的代码，由此生成了我的第一道单纯形算法：<br /> <br />Nehzilrz神牛把目标函数，约束矩阵之类的全都塞到一个矩阵里了，整个代码行云流水，一气呵成！<br /> <br />这道题是poj1273，一道裸网络流，原usaco ditch。<br /> <br />code：<br />program dcx;co
2011-03-24 14:53:00
2345
2
原创 【快速傅里叶变换】FFT高精乘法
<br />比较优美的算法，虽然我至今还推倒不出那个定理（多项式差值的唯一性还有逆运算的公式），嘛，记住算了。<br /> <br />可以用来优化高精度乘法，做到NlogN,不过这个NlogN真的很蛋疼，我四位一压才可以做到300000一秒出，因为涉及复数和实数运算，常数太大了。<br /> <br />基本上是照着算导写的，常数小优化就是那些复数根可以预先处理出来，代码小优化就是DFT和DFT-1可以写在一起，只要把单位复根的y取反即可。<br /> <br />看了一下h8oj发现rank1的神牛比我
2011-03-22 13:51:00
6675
4
原创 【带模的除法】poi2008 per
<br />这道题的难点在于带模的除法，可恶的是模还不是质数，更可恶的是还没办法约分。。<br /> <br />看了标程才知道原来还可以这样做：<br />把取模的数进行分解质因数，对于你要乘或者要除以某一个数的时候，将这个数和模的gcd额外处理（其实直接把质因数的几次幂记下来就可以了），对于不是gcd的部分直接乘法逆元即可。<br /> <br />我是参考的标程的写法（ps：标程跑得非常慢），加略微的改进，感觉我应该不会写丑啊。。。但是交到h8oj上面去的时候果断被虐了。。估计是还有更优美的算法，那位
2011-03-18 23:32:00
1858
1
原创 【二维线段树】poi2006 tet
<br />题目大意<br />给你一个1000*1000的矩阵，支持两种操作：<br />1.查询一个子矩阵的最大值；<br />2.把一个子矩阵的值全部改为某一个值；<br />ps：矩阵内所有值递增；<br /> <br />一开始没有什么好idea，以前就想过关于二维线段树标记下放的问题，后来才明白了二维线段树在第一维上是不能下方标记的。<br />写了个很挫的四分树，TLE了。。<br />program ex1;{$inline+}const mm=2100;var f,s:a
2011-03-15 09:43:00
1623
1
原创 【数位统计】poi2006 kry
<br />题目大意：<br />给定N个数a1，a2，a3...<br />问有多少组Xi满足<br />1.0<=xi<=ai<br />2.x1 xor x2 xor ... xor xn =0<br /> <br />因为是异或，所以第一时间冒出来的想法就是分位统计，因为xor各位之间没有联系，但是小于号各位之间是有联系的，所以最初的想法就是用状态压缩来表示这种大小关系，F[i,x]表示在第i为，状态为x（若x的第j位为1就表示a[j]的第i位可以为1）xor为0的方案数。<br /> <br />
2011-03-04 22:58:00
1024
原创 带标记非递归的动态树
<br />有时候splay如果需要带标记的话会必须递归从上至下的释放标记，这里是一个比较漂亮的非递归版本，为了优化常数。<br />以后他就是模板了吧，我可是苦苦调了一天才把所有细节扣了出的。。。<br /> <br />某题：<br />program t4;{$inline+}const o=50001;var root:array[0..o] of boolean; l,r,f,c,z,s,fa:array[0..o] of longint; i,q,g,t,n,m,x,y
2011-02-26 16:03:00
1135
原创 【计算几何】zjoi2008 risk
<br />题目大意：给你一个平面图，平面被分成了若干个区域，求出每个区域与之相邻的区域，数据保证区域数不超过500；<br /> <br />有数据范围可以看出要求是低于N3的算法。<br /> <br />我的做法是：<br /> 1.将每一条线段AB拆成两条有向线段AB与BA，然后将所有有向线段AB与从B点引出的线段中位于AB顺时针方向的第一条线段连有向边(BA与AB的夹角为2PI，而不是0)。这样对所有的线段做一次DFS之后就能将图中的封闭区域全部求出来，这样出了某个区域包含的区域，其他相邻的区域
2011-02-25 20:30:00
1915
原创 最近做的几道恶心题
<br />noi08糖果雨：<br />program ex2;const mlen=1001;var a:array[0..mlen*4,0..mlen*4] of longint; l,r:array[0..1000000] of longint; b:array[0..mlen*2] of longint; n,i,j,q,t,s,ll,rr,tt,len,ans,len2:longint;procedure ins2(x,y,o:longint);beg
2011-02-13 21:54:00
1113
原创 【增量算法】三维凸包
<br />很长一段时间没有写总结了，随着冬令营的结束，最近对大幅度的总结。<br /> <br />最后一天LRJ讲了下计算几何我才发现3D凸包原来如此简单。<br /> <br />主要讲了两个算法：包裹法和增量算法。<br /> <br />个人感觉增量法比较好，整个过程只用到了+-*这集中运算，不涉及实数运算。<br /> <br />包裹法：首先确定一条一定为凸包上的线段，然后由这条线段为轴，像包纸一样的往顺时针（逆时针）包，碰到的第一个点就是凸包上的点，这时候又可以确定两条直线，递归操作；<br
2011-01-23 18:30:00
4330
3
原创 数位统计小结
<br /> “在信息学竞赛中，有这样一类问题：求给定区间中，满足给定条件的某个D 进制数或此类数的数量。所求的限定条件往往与数位有关，例如数位之和、指定数码个数、数的大小顺序分组等等。题目给定的区间往往很大，无法采用朴素的方法求解。此时，我们就需要利用数位的性质， 设计log(n)级别复杂度的算法。 解决这类问题最基本的思想就是 “逐位确定”的方法。下面就让我们通过几道例题来具体了解一下这类问题及其思考方法。”——09集训队论文《浅谈数位类统计问题》by 刘聪<br /> <br />以前碰到过一些
2010-11-21 17:41:00
2766
2
原创 【计算几何】圆的面积并
<br />总之，圆的面积并是一个非常漂亮的算法，虽然说好像没有很强的扩展性以及实用性，但确实训练自己计算几何代码能力的好题目。<br />一下皆蒯自栗师《圆的并》解题报告:<br /> 试想，如果人来做此题，而不使用计算机计算，那么，人会采取什么样的方法呢？<br /><br /><br />首先要做一些预处理，如果一个圆完全被另一个圆包围，那么这一个圆可以删除。删除后，如果一个圆是孤立的圆，不与其它任何圆相交，就可以把这个圆的面积现算出来，也将它删去。剩下的工作就是求交点了。<br /><br /
2010-11-15 20:12:00
8497
7
原创 【欧拉回路+高斯消元】超级翻转
<br />一道非常好的综合题！<br />因为有多组数据，要注意的是数组清零。<br />利用欧拉回路优美的性质构造异或方程组，详见刘书。<br /> <br />program ex1;var l,u,a,b:array[0..20,0..20] of longint; f:array[0..600,0..600] of boolean; p,next,d,o,g,ans:array[-2000..2000] of longint; t,n,i,j,k,v,sx,sy,ss,
2010-11-10 21:53:00
1144
原创 【后缀数组，RMQ】poj3693
<br />非常恶心的一道题目，看了罗的论文，其中并没有说最小的字典序怎么处理，我整整写了3个RMQ，哎哟~~<br /> <br />总之就是先枚举单个循环节的长度，然后再枚举，找公共前缀（后缀），关于字典序还要写另外一个RMQ。。<br /> <br />100行的代码对于我这种喜欢缩行的人已经很恐怖了。。<br />program ex3;const ln2=1/ln(2);type arr=array[0..100001] of longint;var x,y,r,sa,c:arr;
2010-11-09 22:16:00
1782
2
原创 【有限制的 Pólya+矩阵快速幂】poj2888
<br />神题神题~~被他折磨了一下午，不过大大加深了我对 Pólya 和 Burnside 的理解。<br /> <br />初学 Pólya 和 Burnside 的时候发现数学太重口味了，背了个公式草草走人，今天为了做这道题可是费了血本把组合数学的书翻出来看，哎，都怪组合数学课上YY去了。<br /> <br /> 花了1个小时的时间强啃，总算是有了些收获，小小的总结下。<br /> <br />首先是几个名词：<br />1.着色方案；<br />2.置换，置换群；<br />3.不动置换，对于某
2010-11-07 17:54:00
1904
1
原创 线段树一个漂亮的实现
<br />以前一直误解线段树了，看了莫队的线段树发现我以前一直写丑了。。。<br /> <br />这是hnoi03的一道题：<br />program ex4;uses math;var d,next,x,y,z,s,f:array[0..30000] of longint; n,r,i,a,b,c,t,ans:longint;procedure new(l,r,w,o:longint);begin inc(t);next[t]:=d[o];d[o]:=t; x[
2010-11-07 13:10:00
1094
原创 判定性统计问题的启发
<br />今天看见这样一道题目：<br />一个N*N的矩阵（N＜2000），满足下列两个操作：<br />1.添加一个子矩形；2.查询某个点被多少个矩形覆盖，并销毁这些矩形。<br /> <br />如果没有后面这句“销毁”的话，这就是个水题了，直接用二维树状数组维护点事件即可，但是需要销毁，怎么办？<br /> <br />尽然不能直观的查询某个点会被多少个矩形覆盖，那么不防换一个角度：查询这个矩形是被哪个点销毁的，首先我们可以知道，每个矩形只会被一个点销毁，那么是满足什么条件的点才可以满足呢？我们相
2010-11-06 23:20:00
601
1
原创 【Pólya计数】hnoi2009图的同构计数
<br />题目的简单描述：计算出含有n（n＜60）个点的无向图的本质不同的个数。<br />这里面本质不同的概念是一个图通过改变一些点的序号可以变成其他的图。<br /> <br />刚开始看这道题是晕的，60的范围很让人蛋疼，搜索？DP？记得以前在LTC男人八题里有一道有N个点的连通图的个数，但是这道题所有点是一样的，就涉及到了同构的问题。是通过非常巧妙的状态DP？还是通过等价类的搜索？<br /> <br />后来问了道长是Pólya计数。。比较无语的是，我看见这道题第一个排除的算法就是Pólya，他
2010-11-06 16:05:00
2168
原创 【费用流算法：ZKW】
先上代码，等下再写~~program ex3;{$inline+}var o:array[0..10000] of boolean; d,s,f,a,st:array[0..10000] of longint; c,w,next,p,q:array[-200000..200000] of longint; i,j,k,n,m,t,tt,s1,t1,c1,w1,ans,flow,imp:longint;procedure link(i,j,k,l:longint);be
2010-10-28 19:54:00
8470
1
原创 【KM算法小结】
<br />最近学习了下KM算法，发现异常的好编，而且思想非常巧妙，通过顶标，相当于是迭代最优解再验证可行性的算法。<br /> <br />百度百科上写的非常通俗：<br /> <br /> 初始时为了使A[ i ]+B[j]>=w[i,j]恒成立，令A[ i ]为所有与顶点Xi关联的边的最大权，B[j]=0。如果当前的相等子图没有完备匹配，就按下面的方法修改顶标以使扩大相等子图，直到相等子图具有完备匹配为止。 <br /> 我们求当前相等子图的完备匹配失败了，是因为对于某个X顶点，我们找不到一条从它
2010-10-28 08:47:00
1659
原创 【网络流专题】
<br />最近做了两道网络流神题，里面用了几个非常巧妙的技巧，在今后很多题目中都可以使用得到。<br />第一题：WC2007石头剪刀布<br /> 这题是网络流，简直太难想到了，总之这道题有几个非常巧妙的转化。<br /> 首先是补集转化，我要统计一个完全有向图中的三元环的个数，就等于所有环的个数-非三元环的个数。非三元环的个数怎么统计呢？观察三元环的特点，发现一个三元环必然有一个点在这个环中入度为二（出度为二），由此我们便可以得到一个计算三元环的公式（设d[i]为i的入度）<br
2010-10-24 23:49:00
1117
原创 【基于归并排序的分治】统计问题
题目是这样的：给你一个N*N的矩阵，可以完成两个操作 1.修改某个格子的权值；2.查询某个矩形的权值。看到题目以后很快想到的是二维树状数组，但是N不过既然有这种题目，那么就一定是有解决办法的，在线算法不行，可以考虑离线算法，这个离线算法应该怎么做呢？深入考虑这道题，发现他相当于是要满足在3个偏序集的基础上进行统计---时间、x坐标、y坐标，怎样才可以满足条件呢？对于2个偏序集，我们常用的方法是对其中某一个偏序集进行排序使其成为全序集，再用数据结构统计另一个偏序集。3个应该怎么办？（看了题解后）应该
2010-10-24 19:27:00
1404
3
原创 【带除法的取模运算】hnoi2009有趣的数列
<br />题目本身很简单，有意识的人会打个表轻易地可以发现是个卡特兰数列。<br /> 众所周知卡特兰数列的最普通的递推式是O(N^2)的，数据规模是1000000，很显然过不了，卡特兰数列第i项还有另外一个公式就是C(n,2n)/(n+1),这个除法怎么办？我们所知的取模运算是不满足除法的，那应该怎么办？一个最直观的想法就是分解质因数，然后对于每一个质数分别求出它的指数。通过对每个数进行质因数分解是不现实的，复杂度高达O(N^1.3),1000000的数据显然过不了。<br />
2010-10-18 20:42:00
5640
3
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人