5 01的世界

尚未进行身份认证

有时,失去了才懂得珍惜

等级
TA的排名 1w+

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

Codeforces 620D STL+二分

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

2016-03-18 00:27:33

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

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

2016-03-16 10:37:54

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

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

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

UVa 247 电话圈 floyd找环

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

2016-03-14 12:32:54

UVa 1395 最小生成树

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

2016-03-13 17:38:31

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

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

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

UVa 1393 问题抽象

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

2016-03-12 16:53:59

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

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

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

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

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

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

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

2016-03-08 23:20:32

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知道任意两个相邻的后缀的最长公共前缀a​i​​=lcp(suff​i​​,suff​i+1​​)(1≤in).现在给你数组aaa, Peter有多少个仅包含小写字母的字符串满足这个数组. 答案

2016-03-06 15:56:07

Uva 1262 密码

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

2016-03-06 11:24:48

查看更多

勋章 我的勋章
    暂无奖章