woshitanwei-CSDN博客

原创 Index for WC Solution

这是目录以下是本人认为WC的可做题(即有意义的)OK表示已经做完的题,还要努力啊。。。2002:fence(OK) happy(OK)2003:star2004:twins(OK)airpig(OK)2005:species(OK)dface(OK)2006:tube(OK)2007:jsb(OK) racing(OK) repeat&POI 2003 CIA(OK

2012-02-22 19:41:26 903 1

原创 AC自动机小试 POJ2778

http://poj.org/problem?id=2778题目翻译：给定m个异常基因片段，在所有长度为N的DNA序列中如‘AAAAA....’,'ATTTTT....','ATCG...','CGTA...',.....中不包含异常序列的DNA个数mod 100000(

2011-08-23 12:03:33 2041

题目：http://poj.org/problem?id=1739 这种题新手必须仔细钻研大牛们的代码！！！！这一点很重要 大体上与陈丹琪的例题差不多，就是n*m的矩阵求从左下角到右下角的一条满足遍历除障碍外的所有格点的路的方案数。 首先膜拜陈丹琪的论文：http://wenku.baidu.com/view/f49801155f0e7cd18425368e.html 定义dp[l,i,j]为l行以上(包括l行[1,1]到[l,i])中已构成的所有连通块构

2011-05-21 18:49:00 1799

原创 SGU 333 Random Shooting +数据加强版

首先吐槽各种奇葩情况导致的错误...还有,此题是sgu上万里挑一的弱数据强思考题,点数只有8....啊啊啊啊啊啊啊啊啊啊是要推公式么...不会公式...直接做了...当然首先膜拜金斌题解(虽有错误)...以下为题解,,,不是抄的...在自己做这题时发现其实有很多细节要处理...首先将所有点都缩放在一个单位正方形(0,0)->(1,1)内设p[i]为任取两点与凸包上第i条边相交的概率,那

2012-03-15 12:16:58 1145

原创 WC 2008 password

很好的一道题。。。抽出模型是这题关键的一步。。。其实可以作为传统类题的。。。但是如果有任何关于连通性的描述就会彻底破坏这题的价值。。。所以它就成了提交答案式。。。我只做了欧拉回路的测试点。。。因为木有时间了。。。构图很简单。。。将入度大于出度的作为A类，入度小于出度的为B类。。。源向A连边，流量为in-out，B向汇连边,流量为out-in。。。中间的为oo，费用分情况讨论。。。(abc)->

2012-03-08 14:41:54 703

原创 WC 2011 relation

明显的NPC或NP-hard，因为它是要在一个图中寻找一个K个点的导出子图，使其边权最大。。。如果这都可以在多项式中解决。。。那么寻找一个图中的k阶团就可解了。。。point 3,4,5:明显的树形DP。。。三个维度F[i,j,s]表示i号点及其兄弟儿子。。。还剩j个点未选择。。。i的父亲选取状况为s(0为未选,1为已选)的最大权值。。。DFS记忆化搜索实现。。。吐槽一句。。。由于5号点K有1

2012-03-08 14:18:24 587

原创 WC 2011 joy

此题神矣。。。一开始我先想的第二问。。。想到一个线段树做法。。。对于最优子序列的下标序列，i[2k]~i[2k+1]这段区间选一个最小值位置为pos再在pos~i[2k+1]选一个最大值，更新答案。。。再同样处理剩下的区间i[2k]~pos-1。。。数据随机的话O(lognlogn)但是。。。第一问的更新就成了瓶颈。。。后来看了题解才知道。。。不能把i[2k]~i[2k+1]分为一组。。。要把

2012-03-08 11:44:14 665

原创 WC 2011 xor

这篇题解我是来除草的。。。具体题解请见莫涛神犇的题解。。。以及APIO上他的讲题#include#include#include#includeint n=0,m=0,e=1,maxt=0,s=0;long long sum[50005],x=0,a[100005],choose=0,w[200005];int head[50005],link[200005],next[20000

2012-03-08 11:19:50 765

原创 WC 2010 efield 能量场

首先吐槽WC2010：完全毁了“WC不可做”的神奇形象。。。。。。首先是本弱菜被误导了，以为是个动态规划。。。。。。废话少说，首先mamb(ca-cb)化成maca*mb-mbcb*ma。。。这告诉我们关于两者相关的式子，要往把单体信息化到一起，可能会发现很神奇的东西。。。令xa=maca ya=ma，上式就成了叉积。。。所以原题就成了给定在第一象限的n个点，求两两最大叉积的方案，

2012-02-29 19:31:51 1309

原创 WC 2010 rebuild 重建计划

题目描述就不说了。要题目的请往百度NOI吧。经典的树的分治，首先，对于答案是分数形式的基本上要使用二分答案，这不是胡扯，详情请见胡伯涛的论文。那么对于这个题，由于不好估计边分治复杂度(其实边分治是可以过的，好像比点分治要快)，对于答案，化成如下形式sigma{e}-ans*s=0，对于一个可行的ans设为val，必然满足sigma{e}-val*s>=0，所以二分。点分治时，将每个节点

2012-02-29 19:12:39 726

翻译 POI 2003 CIA sequence without stammers 题解波兰文翻译

定义1：一个字符串被认为是square-free的，当且仅当它不包含形如xx的子串，其中，x为有限非空字符串。你很快发现，两个字符(a,b)组成的字母表，在长度大于3时无法构造出square-free的字符串，因为长度为4的字符串总会包括形如aa,bb,baba,abab的子串，所以要构造这样一个square-free的字串，所需字母表元素个数要在3个及以上。挪威数学家Axel Thue证明了

2012-02-28 16:27:15 1363

原创 WC 2009 opt 优化设计

这个题其实就是sat问题，是个NPC，所以做这题基本上是休闲。但其实分析数据可以发现每个数据都是有目的，并不完全是混乱的boolean表达式。首先对于第一、二两个点数据其实质就是枚举，让我想到了NOIP04年的等价表达式。。。囧。。。point 3、4、5、6就是2-sat问题，本弱菜写2-sat的题目不多，基本上中规中矩除读入140几行。构图什么的几乎木有，裸的2-sat问题，345

2012-02-25 09:54:34 722

原创 WC 2009 voice

这题我觉得就是实现和卡常数！！！不会后缀数组的或者背模板的请先去好好研究后缀数组，至少要有自己的版本，当然，自己的版本至少要经过各大OJ洗礼后才能出炉。由于不会SpareTable算法，直接zkw线段树。还是一样，将所有串连起来后缀排序，对于每个字，枚举匹配的位置，O(logn)zkw或O(1)ST的查询匹配长度，按照查询结果跳指针，最多K次不匹配，最多跳K次，然后就统计即可。这一步O

2012-02-22 17:08:37 651

原创 WC 2007 racing jsb 两题

关于石头剪刀布和Racing那题题解很清晰，所以就不多说了。但是，racing这一题竟然卡SPFA，吐槽不能。。。。。。还有关于racing为什么是从赛道上一点走到另一赛道端点而不是中间某点的证明请看题解PPT的第11张(相信很多人都木有认真看题解)Codejsb racing(SPFA 60分,懒得改了)#include#include#include#include

2012-02-22 16:37:07 595

原创 WC 2004 airpig

虽然是提交答案的题目，但还是硬着头皮做了一下，想法其实也不是我的，很老很老的某位神犇的题解这题是一个双启发函数+随机搜索的题，看上去程序应该很慢，实际上竟然最大数据秒解，而且第一次运行就可找到比标准答案优的解，无不让人佩服(我是说佩服写题解的神犇)贪心的想，每个小猪要飞向猪圈必定找最短路，那么每个小猪向当前所有猪圈连边，km算法最优匹配算权值作为当前操作的启发函数值，但是每一步都做km就会

2012-02-22 15:43:38 675

原创 WC 2004 twins

这个题的亮点就是”它竟然是WC的题！！！！“第二问的DP木有什么好说的很裸的f[i]=(1，剩下的就是高精度的事了然后关于第一问，首先本弱菜想了很久木有想出来原因竟然是我以为是要找前驱。。。。。。。好吧，它是要找后继的说。。。。。那么直接进入正题，对于一个合法序列a，说它合法有三个条件，没有后继0、没有循环节或循环长度为序列长度、然后就是对于连续的0的个数的最大值，就是前导0的

2012-02-22 15:22:36 673

原创 WC 2006 species

这是一道很奇怪的题，说它奇怪就是一旦想出来就会觉得自己被侮辱了智商，但想不出来更觉得自己智商低其实是一个比较奇特的想法。首先对于|a-b|的绝对值符号特别的“厌恶“，怎么让它变得好看呢？注意到题目中的k那。。。。。又有什么用？注意到假设a对于任意两个物种的k个属性，若用0,1表示属性值的正负，选择最小的属性值减去更新答案就可以了细节，注意第k号属性不可以改符号，所以要按第k

2012-02-22 14:43:01 496

原创 WC 2005 dface 双面棋盘

其实就是个线段树+并查集维护，原来的每行看做线段树的一个底层节点，线段树每个节点2*n的空间建立一个并查集，两个节点合并时维护块的个数信息，然后舍弃中间部分保留外围部分重建并查集就可以了。我写的是zkw线段树，用这方法就算不是黑白双色也可以的吧。本人弱菜。#include#include#include#includeint sum[517][5],a[517][517],ll

2012-02-22 14:23:08 1027

原创动态树专题 WC 2006 Tube 还有范浩强的“动态树好题”

虽然是O(Qn)的算法可过水题，但是既然是练手的话，就不得不维护一下动态MST了。还是倒着做，删边改为加边，利用环切性质直接找出切点，再将其切开、反向、连边就成了但是反向是这题最蛋疼的一个操作，标记维护限于水平木有在splay中维护(反正我调不出来)，直接在外维护了。做了一天半啊，中途怒删6KB的代码重打，终于。。。。。内牛满面。裸代码题，无需多说50 1000 2000#

2012-02-21 11:32:01 2903

原创 NOI 冬令营 WC 2008 Trip 旅行计划题解

题意就不多说了显而易见，所求的定为一棵树首先，这个题可以用连通性状态压缩动态规划来写，但感觉思路清晰，实现复杂（较于第二种方法），所以果断写了树结构状态压缩dp假设f[i][j][s]为已知景点连通性为s集合，其中每一二进制位1表示已连接，0表示未连接转移显然有两种（以下省略取最小的min）第一：将两个同根树合并，f[i][j][s]=f[i][j][t]+f[i][j][s^

2012-02-10 09:06:50 909

原创 POJ PKU 3028 Nordic 2006

第一次写C++，手生导致此题耗了两个晚上总计6个小时（好在是自己做出来的）（391ms）题意：有n个人，站成一个圈。每个人开枪击中别人的概率是固定的（设数组P[i]表示第i个人的命中率），从第一个人开始轮流开枪，求每个人的生还的概率是多少？（假设每人都以最有利自己的方式选择射击对象，并且当有多个目标都一样好时，随机选择其中一个（即m个好对象时，每个对象被他选中的概率为1/m）。并且，每轮都

2011-12-23 21:43:12 1398

原创 POJ3245 神题二分+DP+单调队列+堆/线段树/平衡树

未做POJ3017Cut the Sequence者请先忽略此文首先膜拜杜神犇：http://hi.baidu.com/billdu/blog/item/215a8defcbc8a43c2df53498.html若有不懂再看本文题目大意：给定长度为n的序列对A，B，将序列对分为若干连续子段使其满足以下性质1：任意两对元素(Ap,Bp)和(Aq,Bq)若p,q不在同一段中且有pAq

2011-11-05 19:17:00 1140

原创容斥原理 POJ3904

题意：给你n个数，求GCD(gcd(a,b),gcd(c,d))=1的方案数，注意a,b,c,d并不一定两两互质，有多组数据本来这个题的题解有一大把，但没有讲题解的只有贴代码的。本来一直在做题，没有什么时间发题解，但这个题加深了我对容斥原理的理解，所以讲一下这个题的算

2011-10-05 19:30:33 1427 2

原创 break VS 平衡树

圆锥玩具问题描述xqz小朋友家中堆积了好多好多种玩具，其中一种便是圆锥玩具。他经常将这类玩具混乱的摆在地上，欣赏内在的排列美。他先把圆锥垂直放在地面上。这些圆锥都有一个特点，就是它的半径等于高度，且内部是空心的，底面也是空的。xqz小朋友有时会将其中的一些小的圆锥玩具放到比它大的圆锥玩具里，如果一个圆锥玩具不被另外任意一个圆锥完全包裹着，xqz就会格外喜欢它(…)。你的任务便是帮助xqz小朋友找出所有他格外喜欢的玩具。(特别的，如果两个圆锥的底面相切，小的圆锥也算被包裹着)为了简化模型，我们将地面抽象成二维

2011-05-20 15:04:00 715

原创 Tarjan强连通(自学版)

强连通分量　　首先我们把强连通分量看做一个齿轮或环（他会转啊），不考虑其他的限制则可认为分量结点可以互换（就是转一下）不会影响分量中包含的结点（为什么这么想呢？你理解tarjan时中的low值有帮助）Tarjan算法是基于对图深度优先搜索的算法，每个强连通分量为搜索树中的一棵子树。搜索时，把当前搜索树中未处理的节点加入一个堆栈，回溯时可以判断栈顶到栈中的节点是否为一个强连通分量。定义DFN(u)为节点u搜索的次序编号(时间戳)，Low(u)为u或u的子树能够追溯到的最早的栈中节点的次序号。由定义可以得出，L

2011-05-17 20:59:00 650

原创 POJ2453

题目来源： http://poj.org/problem?id=2453 An Easy ProblemTime Limit: 1000MS Memory Limit: 65536KTotal Submissions: 6224 Accepted: 3655 DescriptionAs we known, data stored in the computers is in binary form. The problem we discuss now is a

2011-05-17 20:34:00 523

woshitanwei的专栏