- 博客(42)
- 资源 (2)
- 收藏
- 关注
RSS订阅原创 BZOJ1296: [SCOI2009]粉刷匠 DP
http://www.lydsy.com/JudgeOnline/problem.php?id=1296
2014-04-11 09:22:47
933
原创 BZOJ1036:[ZJOI2008]树的统计Count 树链剖分 / LCT
树链剖分网上的资料比较详细了。上代码：#include #include #define rep(i,l,r) for (int i=l;i<=r;++i)#define per(i,r,l) for (int i=r;i>=l;--i)#define feh(k,v) for (int k=first[v];k;k=next[k])#define gt getchar()in
2014-04-09 20:06:48
711
1
原创 SPOJ5153 Compressed String
题目简述定义字符串的压缩表示[S]N，它等价于N 个S 串从左向右依次连接起来的新串。压缩表示可以嵌套，即S 本身可以是压缩过的字符串。 如“[a]2”代表“aa”，“[[ab]2c]2”代表“ababcababc”。 给出两个压缩以后的字符串S1 和S2，判断它们在哪一位开始不相同。 对于每组字符串，如果S1 和S2 完全相同，输出“Yes”，否则输出它们第一个不相同的位
2014-04-09 14:27:13
544
原创 ax+by=c 且X∈[x1,x2] Y∈[y1,y2] 可行解组数 exgcd
#include #include #include #define rep(i,l,r) for (int i=l;i<=r;++i)typedef long long LL;const int INF=~0U>>2;typedef std::pair PII;int exgcd(int a,int b,int &x,int &y){ if (!b){x=1,y=0;return
2014-04-04 11:26:01
761
原创 BZOJ 3323: [Scoi2013]多项式的运算
Description某天，mzry1992 一边思考着一个项目问题一边在高速公路上骑着摩托车。一个光头踢了他一脚，摩托车损坏，而他也被送进校医院打吊针。现在该项目的截止日期将近，他不得不请你来帮助他完成这个项目。该项目的目的是维护一个动态的关于x 的无穷多项式F(x) = a0 * x^0 + a1 * x^1 + a2 * x^2 + ... ，这个多项式初始时对于所有i有ai =
2014-04-02 17:02:05
1202
原创 BZOJ1770: [Usaco2009 Nov]lights 灯
BZOJ繁体字看着很。。不爽啊。。异或方程组。最开始没有考虑自由元。我想每一个地方都有个1，那肯定没有自由元...囧然后由于自由元的存在，枚举自由元的选择方法。#include #include #define rep(i,l,r) for (int i=l;i<=r;++i)#define per(i,r,l) for (int i=r;i>=l
2014-04-02 11:56:53
1064
原创 高斯消元\高斯约当 模板
实数版：O（n^3)解方程：#include #include #define rep(i,l,r) for (int i=l;i<=r;++i)const double EPS=1e-8;int sign(const double &x){return xEPS;}const int MAX_N=105,MAX_M=1005;double a[MAX_N][MAX_M+MAX
2014-04-02 11:54:39
669
原创 CQOI2014
CQOI每年都这样啦。。半水不水的。。我要在大CQ多好啊~~T1:第一题深搜水水的骗了55分...弱爆啊。。ORZ深搜90分。。搜第一行就可以确定下面的行。。第一行还可以折半搜索在对称过去。。!然后就是2^(m/2)*nm。。 然后还是要T两三个点 。。囧不过不要紧的，BZOJ算总时间能过。。HAHAHAHA正解：异或方程组。。待我研究研究。。DFS
2014-04-02 08:51:27
976
原创 古代文明
古代人类文明逐渐发展，但不是所有的原始人都互相认识。你得到了一份古代的城市文明表a[i]，表示在i时刻，a[i]这个城市有人。城市的地图也会给出，这是一个无向图，每两个城市间有且只有一条路径，就是说这是一棵树。你的任务是，若i时刻到j时刻的所有城市都存在，那么他们分为多少个大部落。即ai到aj这些结点后在原图中构成的联通集数（一个节点重复出现只算出现一次）。对于结点i,结点j，
2014-03-26 21:10:39
828
1
原创 因果的锁链
因果循环，报应不爽。世间的一切都在这因果的操控下，缓缓运作。本来，这一切都不为人所知，直到默默无名的科学家凤凰院凶魔，偶然进入了世界的里端。在那里，他看到的是在空中飞舞的具现化成锁链的因果律。作为科学狂人，他马上开始研究因果律锁链，全然不顾他现在所处的异常空间。凶魔发现因果律锁链是由4种不同的锁环环环相扣而成的。他将它们编号为a~d。凶魔认为这4个环的不同排列方式中，蕴含着因果律本质。
2014-03-26 21:03:14
834
原创 送信
有一群无聊的人，共n个，编号1-n，他们互相发信，共有m个发信请求，每个请求ai,bi表示标号为ai希望将1封信发给bi，每个人有且只有一次到达邮筒的机会，到达邮筒时，他们先接收邮箱中发给自己的信，然后他们会将自己要发的信放在邮筒里。每个人在(pi,qi)之间随机一个时间到达，这之中每个时间被选中的概率均等，此时间为0,100之间的实数。收到信的总数的期望是多少。输入格式：
2014-03-26 20:49:18
869
原创 鸡腿の游戏
题目描述：给出一个无向图，求图中每个点是多少对点对的必经点。输入格式：第一行输入两个正整数n，m，含义同题目描述。接下来m行，每行两个整数a，b表示a，b两个通讯基站能够直接通讯。输出格式：输出n行，每行一个整数，第i行表示通讯基站i是多少对不同的通讯基站的必经点。样例输入：7 91 21 31 41 51 61 7
2014-03-24 21:08:49
10136
原创 割点、桥、双连通分量
推荐一篇感觉写得比较好的，内容很全面，定义、求法都囊括在内：http://blog.csdn.net/tsaid/article/details/6877404然后我就没什么要说的了。。放个点双模板。//当fa==0,就是第一次进入时，割点不能是叶子节点（要特判，本代码不能搞） void tar(int v,int fa){ dfn[v]=low[v]=++Time
2014-03-24 20:58:22
510
原创 鸡腿の花园
给出两棵二叉树，求这两棵树上有多少相同的子树。相同的子树指树A中的子树a和树B中的子树b完全相同，二叉树的相同定义为树上总节点个数相同，根节点孩子数相同，而且两棵子树分别相同。当然，孩子节点是有先后顺序的！输入格式：第一行输入两个正整数N，M表示两棵二叉树的节点个数。第2到N+1行每行两个整数X、Y，第i+1行表示树A上节点i的左孩子和右孩子分别是谁。若没有
2014-03-24 17:51:32
577
原创 计数
给定一个n*m的网格图，图上有一个起点和一个终点（起点和终点处没有障碍），以及若干障碍，对于每个数字0-9都将会给出一对数(ai,bi)。对于一个数t，我们从高位到低位扫一遍，对于t的每一个数字i将当前位置行加上ai列加上bi，若从起点开始在模拟过程中能不走出边界且不走到障碍最终到达终点，就说数t对于当前网格图合法。问区间[L,R]内合法的数t个数有多少，答案对1,000,000,007取模。
2014-03-21 17:00:54
714
原创 异或路径
有一棵n个结点的树，每个点都有一个点权，定义一条异或路径的权值为该路径上所有点权的异或值，问该棵树的最大异或路径权值。输入格式：第一行1个整数n，表示树的结点数。接下来1行n个数ai表示每个结点点权。接下来n-1行每行2个整数x、y，结点x和y之间有连边。输出格式：输出一个整数ans表示最大异或路径权值。样例输入：
2014-03-21 16:08:49
2021
原创 BZOJ1876: [SDOI2009]SuperGCD
题目链接：http://www.lydsy.com/JudgeOnline/problem.php?id=1876题目简述：求Gcd(A,B) 0 这尼玛..如果还是Gcd(a,b)=Gcd(b,a%b) 那这就难写了。。换种求法，数学书上的。更相减损术。g是个计数器若A%2==0 && B%2==0 则 g++,A/=2,B/=2若A%2==0 &
2014-03-08 16:01:05
1735
原创 APIO2007：风铃（Mobiles） 数据备份（Backup） 动物园(Zoo)
这套题比较水..风铃->乱搞即可形状最多有三种。数据备份-> DP 60% 网络流之后乱搞 100%退流思想。。高端！神堆。动物园->一个人看到的只有5个，状压。问题的关键是开头和结尾怎么处理。枚举开头前四个的选择方法。然后结尾就好搞了。第一次WA3个点，，一直没找到问题啊我艹。找一下午，f数组赋0 没 -INF !!!!!
2014-03-06 11:16:39
1673
原创 APIO2010 信号覆盖
高清图片，新窗口打开吧。BZOJ持续阵亡。我写个暴力把外心的通式算出来了。。何必。。联立解两条直线就行了嘛。手推还容易错。..题解上说的还是比较清楚了。。极角排序不能直接用叉乘。。 atan2吧，就是速度比较慢。先预处理出来atan2值，不要在cmp里面算。#include #include #include #define rep(i,l,
2014-03-04 13:24:32
716
原创 论OJ集体阵亡。
首先，CF挂了。 回档到2月7日。（听说我还能涨分 嘘...）其次，BZOJ挂了。这不说了，已习以为常了。第三，contesthunter也挂了....我还想看看3月8日妇女节的比赛呢。。..Bless All....愿OI不灭，OJ长存。2014年3月3日21:05:35
2014-03-03 21:04:06
569
原创 APIO2010:巡逻 树中最长K条链
。。。无语BZOJ挂了，CF也挂了。Bless All..题目链接： （木有） APIO2010题目描述：求一颗树里的边不相交的K条链，使得K条链经过的边数之和最大。( 本题K首先：http://blog.sina.com.cn/s/blog_61034ad90100ii8r.htmlhttp://www.cnblogs.com/procedure2012/archive/
2014-03-03 20:59:12
1025
原创 BZOJ1345: [Baltic2007]序列问题Sequence
http://www.lydsy.com/JudgeOnline/problem.php?id=1345Description对于一个给定的序列a1, …, an，我们对它进行一个操作reduce(i)，该操作将数列中的元素ai和ai+1用一个元素max(ai，ai+1)替代，这样得到一个比原来序列短的新序列。这一操作的代价是max(ai，ai+1)。进行n-1次该操作后，可以得到一个长度
2014-02-28 14:56:13
763
原创 BZOJ1801: [Ahoi2009]chess 中国象棋
http://www.lydsy.com/JudgeOnline/problem.php?id=1801Description在N行M列的棋盘上，放若干个炮可以是0个，使得没有任何一个炮可以攻击另一个炮。 请问有多少种放置方法，中国像棋中炮的行走方式大家应该很清楚吧./*递推，有点像扫雷Mine每一行每一列最多放两个炮 考虑状压记录每一列已经放了几个炮了N M
2014-02-28 13:48:10
1235
原创 BZOJ3240: [Noi2013]矩阵游戏
http://www.lydsy.com/JudgeOnline/problem.php?id=3240Description婷婷是个喜欢矩阵的小朋友,有一天她想用电脑生成一个巨大的n行m列的矩阵(你不用担心她如何存储)。她生成的这个矩阵满足一个神奇的性质：若用F[i][j]来表示矩阵中第i行第j列的元素，则F[i][j]满足下面的递推式:F[1][1]=1F[i,j]=a
2014-02-28 12:14:36
1173
2
原创 BZOJ3450: Tyvj1952 Easy
http://www.lydsy.com/JudgeOnline/problem.php?id=3450Description某一天WJMZBMR在打osu~~~但是他太弱逼了，有些地方完全靠运气:(我们来简化一下这个游戏的规则有n次点击要做，成功了就是o，失败了就是x，分数是按comb计算的，连续a个comb就有a*a分，comb就是极大的连续o。比如ooxx
2014-02-28 12:07:04
1226
原创 BZOJ1025: [SCOI2009]游戏
http://www.lydsy.com/JudgeOnline/problem.php?id=1025Descriptionwindy学会了一种游戏。对于1到N这N个数字，都有唯一且不同的1到N的数字与之对应。最开始windy把数字按顺序1，2，3，……，N写一排在纸上。然后再在这一排下面写上它们对应的数字。然后又在新的一排下面写上它们对应的数字。如此反复，直到序列再次变为1，2，3，…
2014-02-28 11:59:08
1102
1
原创 BZOJ3444: 最后的晚餐
【问题背景】高三的学长们就要离开学校，各奔东西了。某班n人在举行最后的离别晚餐时，饭店老板觉得十分纠结。因为有m名学生偷偷找他，要求和自己暗恋的同学坐在一起。【问题描述】饭店给这些同学提供了一个很长的桌子，除了两头的同学，每一个同学都与两个同学相邻（即坐成一排）。给出所有信息，满足所有人的要求，求安排的方案总数（这个数字可能很大，请输出方案总数取余989381的值，也可能为0）
2014-02-28 11:09:09
1649
1
原创 BZOJ2303: [Apio2011]方格染色
题目链接：http://www.lydsy.com/JudgeOnline/problem.php?id=2303题目简述：有一个包含n × m个方格的表格，每个方格可以涂红色或蓝色，他们想要表格中每个2 × 2的方形区域都包含奇数个（1 个或 3 个）红色方格。有些格子已经被确定颜色，剩下的格子可以自行染色。求满足条件的方案数MOD(10^9)。哎这数据太弱了，，考试随便写了个。
2014-02-28 10:02:36
2101
转载 向量偏移并查集
只是填个坑而已。。。转自：http://blog.163.com/i_oi/blog/static/202956070201210641828692/http://poj.org/problem?id=1182这道食物链题目是并查集的变型，很久以前做的一次是水过的，这次仔细地研究了这“食物链”，无非就是运用向量偏移，从以前节点与节点转化成向量与向量的关系。我们可以把
2014-02-27 18:26:09
969
原创 BZOJ1833: [ZJOI2010]count 数字计数
题目连接：http://www.lydsy.com/JudgeOnline/problem.php?id=1833题目简述：给定两个正整数a和b，求在[a,b]中的所有整数中，每个数码(digit)各出现了多少次。zjoi算是比较水的题了吧。。虽然感觉用循环好想好写些，但一直就在想dfs怎么写，太傻了。。太傻了。。不是一样吗。。！！！1-9都很好搞，0的话dfs再传一位状态
2014-02-26 22:47:36
811
原创 Codeforces 55D Beautiful numbers
题目链接：http://codeforces.com/contest/55/problem/D题目简述：求[a,b]区间内整数n，n能被他所有非零数位上的数整除。看见整除，肯定想的就是%i=0，所以要记他%1~9的余数，但这明显是不科学的。。于是乎，只需要记下1~9的LCM，LCM=2520，这样状态就小了很多了，到最后再分开模。但是我怎么知道他有1~9中的哪些？。。可以考
2014-02-26 14:27:08
637
原创 数位DP/数位统计 初探
一点废话：本沙茶从昨天上午下午到现在一直看这鬼东西。。恶心死了啊有木有！！以前做过一次windy数，代码调了一亿年...经过两天的专题训练，数位dp一点从不会到入了一点门了吧。以前是什么都不会，不会想也不会写。现在至少稍微能写一些大水题了。。（其实还是什么都不会）好了不说废话了。 先说写法：最开始我是写的预处理再循环，前几道题那样写挺不错，个人认为挺好的，后
2014-02-26 08:06:45
1262
原创 Codeforces 392C Yet Another Number Sequence
题目链接：http://codeforces.com/problemset/problem/392/C题目简述：F1 = 1, F2 = 2, Fi = Fi - 1 + Fi - 2 (i > 2).We'll define a new number sequence Ai(k) by the formula:Ai(k) = Fi × ik (i ≥ 1).
2014-02-24 17:14:28
1113
原创 set.cpp/c/pas
set.cpp/c/pas时间限制1s，内存限制256MB。题目描述据说大主任认识一个自认为很聪明的人。有一天，大主任问那个人：“你能告诉我一个集合的表示法吗？”“当然，我这么聪明！”他回答说，“那是一组在两个大括号包围的元素，但括号里也可以为空，这些元素可以是一个新的集合，也可以是一个字母，他们之间用','隔开。”“那么，”大主任说，“如果我给你一个表示，你能告诉
2014-02-24 16:17:15
871
原创 mm.cpp/c/pas
题目简述：时间限制：1s 内存限制：256MB题目描述：看了题目名称不要乱想，mm是MemoryManage的缩写。内存一共有N个单元，有M次内存操作。请你编写一个程序模拟内存的管理过程，有如下几个操作：Reset：将所有在使用中的内存释放。New x：申请新的一段长度为x的，没有被使用过的内存，如果有多段就找左端点地址最小的那段。Free x：将第x个单元的内存所在的
2014-02-24 16:06:05
844
2
原创 矩阵优化递推的总结(不定期更新，最后更新20140321)
定义矩阵：struct Matrix{ LL a[MAX_K][MAX_K],n,m;//n行 m列 Matrix(int _n = 0,int _m = 0):n(_n),m(_m){rep(i,1,n)rep(j,1,m) a[i][j]=0;} void dw(int _n,int _m){n=_n,m=_m;rep(i,1,n)rep(j,1,m) a[i][j]=(i==j
2014-02-23 19:41:15
1953
原创 ContestHunter #26 B 玩骰子
CH转移服务器上不去了，链接就不贴了。题目简述：掷N枚骰子，若掷到点数分别为A1,A2,An的[有序]集合，若该集合有一个子集之和为m，则称该集合为好集，问在N枚骰子的所有有序集合中取到一个好集的概率。 N官方题解：爆搜+打表 = =以下题解，虽然不是我想出来的。 (BY：diamondlx)令n个骰子投出来的数为 A1,A2..AnA集合的子集能组合出来
2014-02-22 23:55:46
893
五子棋AI代码 启发式搜索+算杀 内置禁手 mac/windows通用
2017-01-19
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人