01的世界-CSDN博客

原创 Codeforces 620E New Year Tree

http://codeforces.com/problemset/problem/620/E题意：给以一棵树，每个结点刚开始的时候都有一个颜色，现在有查询1 u col：给这个结点及其子树染上col这种颜色，2 u：查询以u为根节点的子树的所有颜色种类分析：显然是到线段树的题目，要把每个节点的子树放到一个区间上，并且记录首尾位置，这样就可以更新颜色的时候成段更新，查询颜色种类的时候区间查询。

2016-03-18 13:06:31 610

原创 Codeforces 620D STL+二分

题目：620D - Professor GukiZ and Two Arrays题意：交换两数组中的元素最多两次，使两数组差值最小分析：对于0次和1次的情况，元素2000个，暴力枚举就行，但是对于交换两次的，因为交换方案也有很多种情况，预测也是暴力，但怎么暴力呢？看了题目的标签是二分，也往这方面考虑。想了很久，不会啊（囧），看了大神的博客：http://www.cnblo

2016-03-18 00:27:33 613

原创 poj 2135 最小费用最大流模板题

题目：http://poj.org/problem?id=2135题意：给出一个无向图，找两条不同的路从1到n。分析：对于此题,拿过来一看，想了一下，因为来回不可以走相同的边，所以可以做两次最短路，中间记录最短路径，做完第一次后把最短路径删掉，然后再做一次最短路，这不就可以了吗？于是很快敲完，然后交WA，然后反复看代码，以为代码出错了，但是找了半天bug，代码绝对没错啊！画了一

2016-03-16 10:37:54 993

原创 hdu 1532 最大流入门题

题目：http://acm.hdu.edu.cn/showproblem.php?pid=1532题意：农田在1点，河流在n点，中间有一些通路，问从1到n的最大流量分析：最大流的入门题#include#include #include#include#include#includeusing namespace std;const int INF=1000

2016-03-15 22:52:54 554

原创 627A - XOR Equation 数学

题目：627A - XOR EquationTwo positive integers a and b have a sum of s and a bitwise XOR of x. How many possible values are there for the ordered pair(a, b)?InputThe first line of the

2016-03-15 12:49:50 577

原创 Codeforces 627B Factory Repairs 线段树

题目：627B - Factory RepairsInputThe first line contains five integers n,k, a,b, and q (1 ≤ k ≤ n ≤ 200 000,1 ≤ b a ≤ 10 000, 1 ≤ q ≤ 200 000) — the number of days, the length of the repa

2016-03-15 12:31:40 412

原创 UVa 247 电话圈 floyd找环

题意：有n个人m通电话，如果有两个人相互打电话(直接或间接)则在同一个电话圈里。输出所有电话圈的人的名单。分析：用floyd求出两点之间是否有边，然后如果g[i][j]==g[j][i]==1，那么就放入一个连通分量，最后依次输出每个连通分量的所有边，注意输入输出格式，这地方坑了几次。放入一个连通分量用并查集做。每条边对应一个ID号用map去重。找连通分量lrj是用的dfs

2016-03-14 12:32:54 415

原创 UVa 1395 最小生成树

题意：给出一个n节点的图，求苗条度(最大边减最小值）尽量小的最小生成树分析：把边按权值排序，然后就要找一个区间【l，r】,可以构成最小生成树，然后最大边减去最小边的权值，这样一次枚举区间左侧，更新最小值。#include#include#include#include#include#includeusing namespace std;const int N=109

2016-03-13 17:38:31 352

原创 hdu 3555 含有49的数数位dp

题目：http://acm.hdu.edu.cn/showproblem.php?pid=3555题意：给定任意n，计算从1~n中有多少数包含49分析：今天看到群里有个人问这道题，我就做了一下，dfs就搞定了。。看了一下题解，大部分是递推，找规律求解。但是做题还是dfs#include#includeusing namespace std;typedef lo

2016-03-13 17:22:33 374

原创 BC #75 hdu 5642 数位dp/ 递推

这次的BC题目不难，01最大公约数，02模拟，只是没看清数据范围坑了几次，03dp，04如果做过约瑟夫问题的，那就是一道大水题题目：http://acm.hdu.edu.cn/showproblem.php?pid=5642题意：数一个长度为 nnn 的序列，并且序列中不能出现长度大于 333 的连续的相同的字符，这玩意就是一个数位DP嘛。定义 d[i][

2016-03-13 17:22:09 457 2

原创 HOJ 1017 模拟约瑟夫问题

题目：http://acm.hit.edu.cn/hoj/problem/view?id=1017题意：前K个是好人，后K个是坏人，要求在杀掉第一个好人之前，已经杀掉所有坏人分析：模拟一下约瑟夫问题的过程，枚举m，看看是否前K次会杀掉好人，如果会，那么m就不行。#includeint f[15];bool solve(int k,int m){ int s

2016-03-13 09:12:13 383

原创 UVa 1393 问题抽象

题目：uva 1393 - Highways题意：给定一个m∗n的矩阵，将矩阵上的点两两相连，问有多少条直线至少经过两点。分析：自己想了好久，不知道怎么做，看了篇题解：http://www.cnblogs.com/zhexipinnong/archive/2013/05/07/3064893.html写的很好。这种解法不知道怎么想出来的，可能是找规律吧。

2016-03-12 16:53:59 360

原创 UVa 1363 约瑟夫的数论问题

题目：题目链接题意：给定n, k,求出∑ni=1(kmod i )分析：这题不难，但是我一直WA了七次，我的思路跟书上的是一样的，一直找错误，一直WA，但一直找不到我哪里错了，后来无奈，看了刘汝佳的代码，他实现起来没有讨论k和n谁小谁大，直接比较的，而我先讨论了，n>=k的情况（因为这时候，对于所有的i>k，ans都要加上k)，然后再用等差公式求解n

2016-03-12 10:27:00 431

原创 Codeforces 623A 623B dp

题目：623AGraph and String题意：题目要求a,b,c,三个字母，如果相邻或者相等就连一条边，现在给你边，问是否存在这样的数组。分析：可以反着考虑，可见，如果没边，那么一定是a和c相邻，b无论跟谁相邻都会有边，所以O(n^2)遍历找到没边的两点，分别给这两点填上a或者c，这是如果a，c已经填上了同一种颜色，那么肯定

2016-03-11 16:54:41 660

原创 Educational Codeforces Round 7 Codeforces 622D Codeforces 622E

题目：622CNot Equal on a Segment分析：对于这题，对于连续相等数字做一下压缩处理，如果相等的直接跳到下一个不等的位置在比较就好了，O（N)的时间压缩预处理，查询O(1)。题目：622DOptimal Number Permutation分析：这是道找规

2016-03-11 09:41:28 357

原创 poj 1251 最小生成树基础

题目：点击打开链接题意：分析：就是给一个图，求最小生成树。prime算法：#include #include#include#include#include#includeusing namespace std;const int N=50;int g[N][N],dis[N];char op[2];int n;bool vis[N];i

2016-03-09 19:28:59 299

原创 poj 1639 Picnic Planning 最小k度生成树

题目：点击打开链接题意：就是求最小限度生成树，不会做，我是参考这篇http://www.cnblogs.com/jackge/archive/2013/05/12/3073669.html博客做的分析：要求最小 k 度生成树，我们可以按照下面的步骤来做：设有度限制的点为 V0 ，V0称为根节点1，把所有与 V0 相连的边删去，图会分成多个子图（假设为 m 个，显然的

2016-03-08 23:26:38 341

原创 poj 3259 最短路判负环 spfa算法和Bellman_ford算法

题目：http://poj.org/problem?id=3259题意：有个人在一个图上旅行，当它从一点出发后，可能会经过一些虫洞边，然后时光倒流，回到原点，看到自己，看了好久样例一才看清题意，他必须要看到“自己”，也就是要有个负环回路，所以这就是个求负环回路的问题分析：spfa算法和Bellman_ford算法都可以spfs代码：#include #include

2016-03-08 23:20:32 466

原创 Bestcoder #74 hdu 5635 hdu 5636 hdu 5637 hdu 5638

hdu 5635题意：Peter有一个字符串s=s1s2...sns=s_{1}s_{2}...s_{n}令suffi=sisi+1...snn是ss第ii字符开头的后缀. Peter知道任意两个相邻的后缀的最长公共前缀ai=lcp(suffi,suffi+1)(1≤in).现在给你数组aaa, Peter有多少个仅包含小写字母的字符串满足这个数组. 答案

2016-03-06 15:56:07 533

原创 Uva 1262 密码

题意：给出两个6行5列的字母矩阵，一个密码满足：密码的第i个字母在两个字母矩阵的第i列均出现。然后找出字典序为k的密码，如果不存在输出NO分析：自己的做法就是书上说的那样一位一位的处理，先把两个矩阵一样的字母找出来，但要注意，一列中相同的字母只找一个就行，如果重复了就WA了。然后对于每一位，求出这一位的权重（就像加法那样的位权），然后就一位位处理。#includ

2016-03-06 11:24:48 350

原创 Codeforces 527C 线段树 /set

题目：http://codeforces.com/problemset/problem/527/C题意：给出矩形的长和高，然后给出一些操作，水平或者竖直切割矩形，每切割一次，求出剩下的面积最大的矩形分析：看到题目，就想到是如何维护区间的最大值，第一想到的就是线段树，可以把还可以划线点的用1表示，划了线的用0表示，然后求最大长度就是如何求连续的1的最大个数，那么这题的变成了一

2016-03-05 22:52:45 392

转载大学

装载于：http://blog.csdn.net/ljfbest/article/details/7079998每个安慰你挂科算什么的人，　　最后都默默拿了奖学金；　　每个夸你肥嘟嘟的脸好可爱的人，　　最后都瘦成了万人迷；　　每个在你面前说自己前途渺茫的人，　　最后都身家过亿；　　只有你，　　在满床的薯片袋和电脑荧光照射下，　　淬炼成一朵SB 。　　你要

2016-03-05 10:11:53 263

原创 Codeforces 533B 树上的dp（求最大偶数个节点的权重和）

题目：点击打开链接题意：给你n个节点,每个节点已知父亲和权值,1节点为根必选,你从中挑选节点,以每个节点为父亲的子节点个数和必须为偶数,问最大的权值和分析：从叶子结点，更新他的父节点，直到跟新到树根。f[i][0]表示以i节点为树根的节点数为偶数个的最大权值和f[i][0]表示以i节点为树根的节点数为奇数个的最大权值和状态转移方程就是，如果是奇数个再加上一个节点

2016-03-01 20:40:26 1059

原创 Codeforces 628D 偶数位全是某个数数位dp

题目：点击打开链接题意：d magic number（0题目问，给a,b,m,d(a分析：一道简单的数位dp题，也没什么好说的。就是bit下标是从0开始的，奇偶换一下就可以了。#include#include#include#include#includeusing namespace std;typedef long long ll;const int

2016-03-01 18:11:21 330

原创 AC自动机的初步学习 hdu2222 AC自动机入门题

本来KMP和trie树就不太熟悉，但是就是想弄明白AC自动机是什么东东，所以就找了一些博客学习了一下，用hdu2222练了一下手。推荐几篇很好的博客：http://www.cppblog.com/menjitianya/archive/2014/07/10/207604.html这篇博客绝对是良心之作，尤其是那些图片，可以很好地讲述AC自动机的失败指针和trie图构造。还有几篇不错

2016-02-29 23:12:56 589

原创 UVa 11732 strcmp函数 trie树左儿子右兄弟表示法

题意：给出n个字符串, 计算两两比较的次数. 每次比较都需要比较(str1[i] == str2[i])和 (str1[i]== '\0'各一次).分析：边插入边统计，这样就刚好是两两比较一次的结果。如果先建树再深搜，那么就多比较了一次，/2就可以。#include#includetypedef long long ll;const int N=4000*1000+10;

2016-02-29 10:02:57 506

原创 LA 3942 背单词 trie树+dp

题目：题意：给定一个字符串和给定一个单词集合。问从给定单词集合中选取单词，有多少种选取方法刚好拼接成字符串。例如:abcd4abcdab有两种a-b-cdab-cd分析：刘汝佳书上入门经典的题目，看了他的模板敲了下，不错，我原先是用链表来存储的，以后就按这种形式了。对于这题,要求的是有多少种方法，一看就是dp，其中d(i)表示从字符i开始

2016-02-28 21:22:51 560

原创 poj 3630 找重复前缀 trie树

题目：点击打开链接题意：给你一些电话号码，如果其中一个电话号码是另一个电话号码的前缀，那么输出NO，否则YES分析：这题就是找最小前缀问题，以前我都是用string然后排序，然后取相等的一段判断就行。今天主要是学习一下trie树。如果是动态节点的话，会TLE，只能初始化数组，但是别忘了一开始trie数组清0.思路是在建树的时候，在单词的最后一个节点标记一些结尾，然后查询

2016-02-28 17:49:14 849

原创 hdu 1075 翻译火星文 trie树 / map

题目：点击打开链接题意：给你一段火星文对应的英文，再给你几句火星话，让你翻译成英文。分析：先把火星文建成一颗字典树，在翻译的时候，查找每个单词块，看是否这个串在字典树中能否找到，因为在建树的时候id存储了对应单词的英文，所以查找的时候返回id就可以，找不到就返回-1. 对于这题，如果简单的做做，可以用map，很简单。#include#include#includeusing

2016-02-28 13:59:18 370

原创 hdu 1247 trie树入门题

题目：http://acm.hdu.edu.cn/showproblem.php?pid=1247题意：给你一些单词，输出是由两个其他的单词组成的单词。分析：trie树的入门题，很简单，这题的数据很水，每个单词的长度不会超过26.#include#include#includeusing namespace std;const int N=50005;char word[N]

2016-02-28 11:08:38 90

原创 hdu1693 Eat the Trees 插头DP

题目：点击打开链接题意：一个棋盘上有0,1.需要找一些回路把1全部串起来，问总方法数分析：插头dp第一题，果然有点难度，用了我一天的时间，还是自己太菜了。。。。我是看了这个图才恍然大悟的，这就对应下面的三种可以联通的情况。对于为什么 f[i][0][s可参考文档：http://www.docin.com/p-741918386.html图片来

2016-02-27 22:06:35 315

原创 poj 2411 骨牌覆盖问题状压dp

题目：点击打开链接题意：用1*2 的矩形通过组合拼成大矩形，求拼成指定的大矩形有几种拼法分析：这题的关键在于什么状态是合法的，可以这样想，用1表示有骨牌覆盖，用0表示空着。在覆盖第i行的时候，那么如果覆盖的状态是合法的，覆盖完后第i-1行必须没有空格了（全是1111），所以可以看出，每一行的状态必须要有偶数个1相连，为什么？由于在做第i行dp时必须完全覆盖第i-1行，只

2016-02-27 00:04:25 1810

原创 zoj 3471 Most Powerful 状压dp(简单）

题目：点击打开链接题意：有n种原子，原子i和j相撞，如果j消失，会产生能量a[i][j]，如果i消失，会产生a[j][i]能量，问产生的最大能量。分析：这题很简单，本没必要写，但这是我第一道独立做出来的状压dp题，于是写出来了。f[i]表示状态是i的最大能量，i是一个二进制数，1表示原子还存，0表示已经消失了，所以状态转移就明显了f[s]=min{ f[s-{j} ] }.

2016-02-26 20:09:04 284

原创 poj 2288 哈密顿路状压dp

题目：http://poj.org/problem?id=2288题意：给出了n个地点和m座桥（连接顶点的），画出哈密尔顿圈并求出最大值，他们的最大值由三部分决定，1：n个地点的value值之和，2：顶点之间连接之积，3：三个（连续的）顶点之积；要求输出最大值，并且存在最大值的情况总数，同时，对于两个完全逆向的路径可以认为是同一条路径；分析：发现每个点的状态由前面两个点确定，用DP（S

2016-02-26 17:36:08 361

原创 hdu 3001 Travelling 状压dp TSP变形

题目：点击打开链接题意：给定n 个城市已经 m 条路以及对应路费c，要求遍历所有城市最少的路费，每个城市不能超过2次分析：要求每个点最多走两边，不是只可以走一次，所以要用三进制的状态压缩解决这个问题。可以预处理每个状态的第k位是什么。状态的表示 f[st][i],表示现在在i点，状态是st的最短路程。那么状态转移显而易见：f[st][i]=min( f[{st}-i][j]+

2016-02-26 15:20:27 289

原创几道数学问题（未完成）

知识点：判断三角形是否为非退化三角形。方法：判断三点是否在一条直线上，看斜率。但不能直接求斜率，会有精度损失而且还要分情况处理。解决如下：bool ok(point a,point b,point c){ return (a.y-b.y)*(c.x-b.x)==(c.y-b.y)*(a.x-b.x);}如果ok函数放回true，表示三点共线，否则可以构成三角形例题：Code

2016-02-26 11:04:40 368

原创 TSP问题动态规划实现

货郎担问题（TSP）。有n个城市，两两之间均有路直接连接，求一条经过每个城市一次且仅一次，最后返回起点的最短路线。这是刘汝佳书上的一道题，他给出了思路，我实现了一下。用动态规划解决，可以假设从0点出发，然后回到0点。那么用 f(i,S)表示现在处在i点，要去访问剩余的在集合S中的点，集合S可以用二进制数st。那么状态转移方程就是：f(i,S)=min{d(j,S-{j})+dist

2016-02-25 20:33:10 3678

原创 poj 3311 送披萨状压dp

题木：点击打开链接题意：位于0点小伙计给n个点送披萨，每个点可以经过多次，问送完n个点回到0的最短路程。类似于TSP问题，不过TSP每个点只可以经过一次。分析：对于这题，因为一个点可以经过多次，所以可以预处理两个点的最短距离，这个距离可以经过多次。处理完之后，就好办了，可以枚举n个点的全排列，找出最小的就好，比较简单。对于这题，当然也可以用dp，状态的表示 f[st][i]

2016-02-25 16:33:02 404

原创 poj 1185 炮兵阵地状压dp

题目：点击打开链接题意：如图，大炮可以放在p处，黑色区域是可以攻击的范围，问怎么放大炮可以不会误伤，求出最大数？分析：和上一篇poj3254一样，这是这题多加了一个判断，就是还要考虑上上行的情况，其实跟上一题差不多，具体参考代码。【状态表示】dp[i][j][k] 表示第i行状态为k，第i-1状态为j时的最大炮兵个数。【状态转移方程】dp[i][k][t] =

2016-02-25 09:50:30 248

原创 poj 3254 Corn Fields 状压dp入门题

题目：点击打开链接题意：一个矩阵里有很多格子，每个格子有两种状态，可以放牧和不可以放牧，可以放牧用1表示，否则用0表示，在这块牧场放牛，要求两个相邻的方格不能同时放牛，即牛与牛不能相邻。问有多少种放牛方案(一头牛都不放也是一种方案)分析：状压dp的入门题，这题就是把每一行等效成一个数，由于是由01表示的，所以很容易想到整行用一个二进制来等价，因为1表示可以选，0表示不可以选，那么这

2016-02-24 19:48:02 360

空空如也

空空如也