- 博客(174)
- 资源 (3)
- 收藏
- 关注
RSS订阅
原创 收集整理威尔逊定理的证明
在求解BNUOJ 1093 YAPTCHA时，用到了威尔逊定理。在这里收集整理一下证明威尔逊定理的方法。先说从题意出发吧。这道题是给定一个式子再给若干个n，让你求出Sn的值。(1暴力肯定是不行的。所以考虑数论的方法。 当3k+7不是素数时，可以得到((3k+6)!+1)/(3k+7)=[(3k+6)!/(3k+7)]，此时括号内的值为0. 当
2013-03-06 16:02:49
10344
原创 java在ACM竞赛中的使用
java简单功能强大，高精度类可以帮队员轻松地实现对大数操作，而不用C/C++手写高精度。使用java做题，不容易犯一些低级的错误，如: if (a = b)。刚刚接触acm的时候，笔者还不会使用java，为此还特地花了一个月时间学习了一下java语言。现在回过头来发现，学会在比赛中熟练地使用java其实根本不需要花很长时间......所以在这里小结一下java在acm比赛中的使用。
2013-01-21 22:04:28
4292
5
原创 Lua脚本语言学习笔记
什么是脚本语言？1.一种解释运行而非编译的计算机语言。2.以文本的形式保存，在被调用时进行解释或编译。为什么要使用LUA脚本语言？1.提高工作效率。项目规模扩大，编译源代码所需时间变长。为了不因为一些小的改动（改变几个常量的值），就去编译整个项目，所以使用脚本语言。2.提高创造性。使用lua脚本，不仅可以帮你初始化变量，还可以帮你创建游戏逻辑甚至是游戏对象。3.增加扩展
2013-01-21 11:49:37
2167
原创 Linux系统下的OpenGL图形程序框架
Linux系统下的OpenGL图形程序框架 说到图形界面编程，想到的大多是Windows下的多种多样的应用程序。Linux是一个基于命令行的操作系统，在Linux下的工作大多是在命令行里完成的，而并非像Windows那样。图形界面虽然并不是Linux的一部分，我们通过一些工具，依然可以编写一些在Linux下的图形应用程序。 OpenGL是一个工业标准的三维计算机
2013-01-15 12:03:28
7277
原创 POJ 2849 brainf*ck
#include #include #include #include using namespace std;int cao[32768],pa[130000],stack[130000];int p,ls;void caonima(int v){ v=cao[p]+v; if (v == -1) v=255; if (v == 256)
2013-12-17 17:03:48
1238
原创 【总结】2013年，再见ACM/ICPC
【总结】2013年，再见ACM/ICPCplusplus7发表于 2013-11-23在整理旧博客的文章时，偶然翻到了去年这个时候写的总结【总结】2012年，很水的一年，于是便想也写个今年的总结。去年的那篇总结是写于去年打完ACM/ICPC亚洲区域赛成都赛区后。那时，我和Aikilis，小灯组队，队名叫3dmin/三弟马克思，满怀希望，以为能拿下学校的第一块亚洲区域赛奖牌.
2013-11-23 23:27:48
1285
原创 川大校赛总结
对于这次四川大学的结果，我感到挺意外。 比赛开始时，我们3人分工很明确。随后我很快读出了一道题，然后和tuber交流了题意，确认了以后就开始敲。此时Aikilis继续看题。随后，很顺利地AC了此题。然后我们暂时没有发现简单的题，只找到一道BFS的题，但是实现起来比较复杂，于是决定让我敲此题，他们继续看题。后来tuber读到了E题，发现是一道DP题，于是Ai
2013-05-02 20:16:06
1231
原创 SGU 249 Matrix
格雷码。。#include #include #include #include using namespace std;int grayCode[10000000];int main(){ int s,n,m,pn,pm,t,i,j; scanf("%d%d",&n,&m); s=pow(2,(n+m)); pn=pow(2,n); pm=p
2013-04-22 21:28:44
794
原创 LA 3618 Cubic Eight-Puzzle
立体的八数码问题。 普通的DFS和BFS就别想了，迭代加深TLE，而用启发式搜索又想不到合适的启发函数。可发现目标状态有固定的2^8种，而状态转移的方式最多只有4种......所以用双向bfs，应该能解决问题。因为会产生很多重复的状态，所以用hash表判断一下重复的状态。stl的hash会TLE，所以还是手写静态链表哦。#include #include #include
2013-04-22 21:22:29
1294
原创 UVa 11212 Editing a Book
黑书P207 例题IDA* 搜索，估价函数设计得很经典。#include #include #include using namespace std;class Board{public: int a[16]; int h; int n; bool readIn() { int i; scanf("%d",
2013-04-22 21:03:16
1954
原创 POJ 3856 deltree
模拟题。deltreeTime Limit: 1000MS Memory Limit: 65536KTotal Submissions: 58 Accepted: 33DescriptionYou have just run out of disk space and decided to delete some
2013-04-22 21:00:05
731
原创 POJ 2870 Light Up
题意简述：在n*m的格子中放置灯泡。其中格子中有些障碍，灯光可以照亮上下左右的格子，光线会被障碍挡住。题目解法：搜索。 每个状态的转移会产生很多状态，而目标状态有是不固定的，所以不能BFS或双向BFS。但是DFS又很容易陷入搜索到很深但是却又是错误的状态，而最优解的深度又是不深。所以考虑使用迭代加深搜索。 剪枝：搜到每个障碍时，发现上面的格子是空的，剪枝。
2013-04-22 20:55:10
1616
原创 POJ 3852 String LD
简单题，第一次提交居然TLE了。然后以为暴力不行，所以写了个Trie树，汗...赛后和别人讨论发现是可以暴力的。#include #include #include using namespace std;int ans;struct Trie{ int dep; int next[26]; bool init(int d) { d
2013-04-22 19:54:36
950
原创 LA 5506 Eight
同样是South Central USA 1998的题，POJ和HDU上的数据比较水，用BFS不加任何优化都可以AC，时间一般是三位数左右。而用A*或IDA*则可以把时间控制在10ms左右，甚至0ms！ 然而UVa Live上的这道题是多数据的，用IDA*不加优化都会超时。除此之外题目输入输出很严格，case和case之间必须有空行，在最后一组case之后不能有空行，否则会Wr
2013-04-17 13:07:28
764
原创 LA 3211 Now or later
训练指南 P325 例题2-SAT问题+二分。题目的数据范围小，所以用朴素的算法解2-SAT能过。tarjan的SCC算法判2-SAT#include #include #include #include #define MAXN 2200#define MAXN_2 4400using namespace std;int min(int a,int b){
2013-04-11 17:34:28
1055
原创 UVa 11235 Frequent Values
训练指南 P198 例题在一个非降序数组中寻找区间内出现次数最多的值的出现次数。用线段树和RMQ都能AC。RMQ解法#include #include #include #define INF 0x7fffffffusing namespace std;int n;int a[120000];int nb[120000],b[120000],bv[120000],l[
2013-04-11 17:31:44
1160
原创 LA 3027 Corporative Network
并查集的应用。在压缩路径的时候维护一个dist数组，保存其到祖先的长度。#include #include #include using namespace std;int uset[21000],dist[21000];int abs(int a){ return a>0?a:-a;}bool init(){ int i; for (i=0; i
2013-04-11 17:28:25
865
原创 LA 4329 Ping pong
训练指南 P197 例题 扫描一下所有的i，计算出从1到i-1有多少个数比它大，和从i+1到n有多少个数比它大。 然后就是交叉相乘算出总的方案数。#include #include #include #define INF 120000using namespace std;long long a[21000];long long l[21000],r[2100
2013-04-11 17:25:14
1609
原创 LA 3942 Remember the Word
训练指南 P209 例题用trie树使得每次寻找递推的下一步。#include #include #include #define MOD 20071027using namespace std;struct Trie{ bool tag; int next[26]; bool init() { tag=false;
2013-04-11 17:21:50
1613
原创 POJ 3164 Command Network
朱刘算法模板题#include #include #include #include #define eps 1e-8#define INF 0x7fffffffusing namespace std;struct point{ double x; double y;};struct edge{ int u; int v; doub
2013-03-31 20:51:01
1117
原创 POJ 1442 Black Box
题意：给你n个数的数列，然后再给你m次查询，第i（i题解：根据Discuss说的，这题可以用各种数据结构AC...为了练习一下红黑树，我写了个红黑树求解的。240行代码，结果居然1Y了,,,这...解法：红黑树//不想说什么了#include #include #include using namespace std;int m,n;int a[60000]
2013-03-28 13:38:06
1788
原创 POJ 1325 Machine Schedule
建图+Dinic=Accept#include #include #include #include using namespace std;int sta,end;int val[300][300];int tag[300];int min(int a,int b){ return a>b?b:a;}int bfs(){ int u,v; qu
2013-03-27 00:33:14
784
原创 CodeForces 1B Spreadsheet
字符串处理+计算吧用python，使用正则表达式来读取数据更方便一些。import redef convert(d): s='' while (d > 0): t=d%26 d/=26 if (t == 0): s+=('Z') d-=1 else:
2013-03-27 00:31:20
1087
原创 CodeForces 266E More Queries to Array...
因为k最大只有5，所以我建六个线段树，分别用于保存ai*i^k的值，这样就能在logn内算出值，所以此题总复杂度nlogn。#include #include #include #include using namespace std;struct Segment{ int l; int r; int mid; long long v; bo
2013-03-27 00:28:22
1067
原创 CodeForces 268A Games
水题一枚。。。#include #include #include using namespace std;int main(){ int n,i,ans,j,cnt[200],a[200],b[200]; scanf("%d",&n); memset(cnt,0,sizeof(cnt)); for (i=0; i<n; i++) {
2013-03-27 00:25:49
1281
原创 POJ 3308 Paratroopers
最大流最小割模型。把问题转化成最小点权覆盖问题，就能用最小割求解。而最小割又和最大流是对偶问题，所以此题用dinic可解。#include #include #include #include #include#define INF 1000007#define eps 1e-8using namespace std;int sta,end;double val[200]
2013-03-27 00:24:52
836
原创 POJ 1236 Network of Schools
强连通分量问题一，缩点后，求出所有入度为0的点的个数；问题二，缩点后，求出入度为0的点的个数和出度为0的点的个数中的最大值 #include #include #include #include #include using namespace std;vector g[120];int tg[120];int dfn[120];int low[
2013-03-19 15:19:36
1080
原创 POJ 2942 Knights of the Round Table
双连通分量Tarjan+交叉染色#include #include #include using namespace std;struct edge{ int u; int v;};int n;int g[1010][1010];int tg[1010][1010],lt[1010];bool flag[1010];int dfn[1010],low[10
2013-03-13 18:07:50
539
原创 POJ 2165 Going Home
题意：给定一个地图（n*m），地图上有若干个man和house（最小费用最大流的模板题。（但是也可以看做是求二分图的带权匹配问题，用KM算法解决，这里先贴最小费用最大流的代码）#include #include #include #include #define INF 0x7fffffffusing namespace std;struct point{
2013-03-08 17:17:52
615
原创 POJ 2516 Minimum Cost
n个店主，m个经销商，k个商品。不同经销商可以提供不同数量的商品，不同店主需求不同数量的商品，不同的商品从不同的店主手中发货给不同的店主需要花费不同的价钱。题目输入格式是这样的： 第一行n m k 接下来是一个n*k的矩阵，表示不同店主需求不同数量的商品； 然后是一个m*k的矩阵，表示不同经销商可以提供不同数量的商品；
2013-03-08 17:14:46
599
原创 POJ 3281 Dining
题意是有F种食物，D种饮料，N个人，每个人决定吃或喝，现在让你去分配，使得吃喝都得到的人最多（占便宜）。每种吃喝的东西只能招待一头牛最大流的题，建图是关键。源点与每个食物连一条容量为1的边，汇点与每个饮料连一条容量为1的边。牛要拆点，入点与对应的食物连容量为1的边，出点和对应的饮料连一条容量为1的边。用的dinic算法。 #include #include #include
2013-03-07 22:42:37
647
原创 BNUOJ 1392 Drainage Ditches
和前面那个POJ 1273是一样的，这里用的是Dinic算法，所以当做一个模板保存一下。#include #include #include #include #define INF 0x7fffffffusing namespace std;int val[300][300];int lev[300];int n,m;bool bfs(){ int u,v;
2013-03-07 22:38:20
660
原创 OpenGL织梦之旅【第四章】第2节．简单的3D动画
上一小节中，我们已经成功地搭建好了一个“小剧场”，“观众席”已经设置好了，但是“演员”还没有到位。所以这一小节，我们就来请一些“演员”，让他们做一些“动作”。 还记得读取纹理那章的内容吧~2D纹理在这里同样是可以使用的。为了方便，我把LoadBitmap函数放到了"bmpLoader.h"中，这样方便调用。 在bmpLoader.h中：#include #
2013-03-04 15:36:03
1432
原创 POJ 1106 Transmitters
给定一些点，和一个圆心坐标，求一个以这个点为圆心的半圆能最多能圈下多少点。#include #include #include #include using namespace std;#define hPI 1.5707963267949#define eps 1e-8struct point{ double x; double y;};double cr
2013-03-02 23:08:22
545
原创 POJ 1201 Intervals
差分约束系统。如果一个系统由n个变量和m个约束条件组成，其中每个约束条件形如xj-xi求解差分约束系统，可以转化成图论的单源最短路径问题。观察xj-xi<=bk，会发现它类似最短路中的三角不等式d[v] 原点（s,s）与所有定点相连，边权均为0。对这个图以s为原点运行Bellman-ford算法（或SPFA算法），最终{d[i]}即为一组可行解。#include #inc
2013-03-01 17:28:38
519
原创 OpenGL织梦之旅【第四章】第1节.设置视点函数gluLookAt
在做所有的事情之前，我们必须要了解怎么在3D的世界中绘图。这也是为了帮助我们调整视点，不然调来调去都是黑框... 3D世界中的坐标系也是笛卡尔坐标系，y轴就像是现实世界中的“高低”，而x和z像是地面的坐标。 我们写一个DrawBox函数，这函数负责绘制一个正方体。void DrawBox(){ glBegin(GL_POLYGON);
2013-03-01 00:04:45
4321
1
原创 OpenGL织梦之旅【第四章】编写一个自己的小剧场
先来解释一下这个标题，在这一章我们要掌握一些OpenGL 3D的基本要点。在这一章中，我们进入3D世界，制作一些简单的3D动画，然后实现可以自由调节位置和视角，类似于在剧场中观看动画的感觉。 在现实生活中，我们通过眼睛观察事物，然而也有可能我们是歪着头在看这件事物。如果把现实世界坐标化，我们的眼睛有个坐标eyeX,eyeY,eyeZ,我们观察的事物有个坐标viewX,viewY,
2013-02-28 23:53:26
838
原创 Python 之 BNUOJ代码抓取器
经过Wireshark抓包，我发现要抓取BNU上提交过的代码，访问http://www.bnuoj.com/bnuoj/get_source.php?runid=%d&randomid=0.19548853184096515这个链接，其中runid=%d，%d填代码执行的id号。那个randomid不知道是干嘛的。。然后这个页面就会返回包含代码信息的html页面。如图：用pytho
2013-02-06 19:19:04
912
原创 Python 之 BNUOJ代码提交器
FLUYY包工头用bash shell 写了个bnuoj代码提交器。传送门：http://fluyy.net/post/linux/20130119-bnuposter/ 他说，用python可能会更方便一些，让我去试试。于是我查了下资料，用python也写了一个代码提交器。用起来感觉还是挺方便的。 使用方法，先是要登录一下，获取到cookie。
2013-02-03 21:56:11
1268
1
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人