-
[综合] POJ2184 Cow Exhibition(DP:变种01背包)
题意: 一群奶牛分别有s和f两个值,要求选出一些奶牛使s与f的和最大并且s和f分别的和不能为负数。 要点: 用dp[i]=j表示当s的和为i时f的和为j,这样最后只要求dp[i]+i的最大值即可。注意这题因为有负数,所以引入一个偏移量。这里01背包是用一维表示的,所以要根据s[i]的正负分别处理,遍...
64
热度 -
[综合] POJ1700 Crossing River(贪心)
题意: 经典的过河问题,一群人要过河,只有一艘船,船最多坐两个人,船速为两人中较慢的那个,问把所有人都运到对岸最少要多长时间。 要点: 这题自己想真挺难,看了一下网上的方法,基本上是这样,当人数n=1,2,3时,最小时间是固定的,而n大于3时,可以先考虑把最慢的两个人运过去,有以下两种方法:一:用最...
52
热度 -
[综合] 最大流的Edmonds-Karp算法
最大流一般可以解决像货运这种问题,例如POJ1273,一共n个池塘m条边,给出每条边能通过的最大水流量,给出一个起点和一个汇点,问起点流出的最大水流量是多少。基本算法是Edmonds-Karp算法:循环增加流的值,每次通过BFS寻找一个增长路径(从起点到汇点的简单路径),每次将路径中最小的残余边量(...
22
热度 -
41
热度 -
[综合] POJ1149 PIGS(最大流)
题意: 有m个锁着的猪圈,现在有n个顾客过来买猪,他们手里分别有对应猪圈的钥匙,如果已经开了对应的猪圈,就可以在把这个猪圈的猪赶到其他猪圈去,要求能卖出最多的猪数。 要点: 这题建图比较困难,建完图就是个最大流模板。另设一个源和一个汇,将顾客作为其他节点,将猪圈开启的次数作为边,这样先将源点与每个猪...
34
热度 -
[综合] 例题5-2 UVa101 The Blocks Problem(STL:vector)
题意: 看白书 要点: 学了一下vector中的resize()的用法,就是把resize(n),n及以上的都丢掉。这道题的归位的意思是放回对应的第i个堆。 #include<iostream> #include<vector> #include<algorithm&...
46
热度 -
[综合] 例题5-3 UVa10815 Andy's First Dictionary(STL:setsstream的应用)
题意: 输入一长串字符串,将其中的单词按字典序输出。 要点: STL中的set就像数学中的集合,每个元素最多只出现一次。ssteam可以很简单的将字符串转换为整数或反之。这题注意将所有不是字母的字符变成空格再进行一次出入流操作来除掉空格。 #include<iostream> #inc...
28
热度 -
[综合] 例题5-7 UVa136 Ugly Numbers(STL:priority_queue)
题意: 看白书 要点: 很简单的priority_queue应用题。之所以写个博客是为了总结一下priority_queue的写法。主要问题是VS中greater不是模板,但OJ中可以AC。 需要特殊排序可以有以下两种写法: structnode {intx,y; }; structcmp {bo...
56
热度 -
[综合] POJ2155 Matrix(经典二维树状数组)
题意: 给出一个矩阵,其中的元素要么是0要么是1,现在有两种操作,一种是将一个子矩阵内的元素全部反转,一种是查询元素(x,y)对应的值。 要点: 这题是非常经典的一道二维树状数组题,难点是怎么修改子矩阵内的值,其实只要每次修改(x1,y1),(x1,y2+1),{x2+1,y1},(x2+1,y2+...
5
热度 -
[综合] POJ1236 Network of Schools(强连通分量:Tarjan算法)
题意: 学校之间有网络系统,通过网络可以从一个学校定向的传递文件给另一个学校。现在问最少给几个学校传递文件使所有学校都能收到?最少添加几天网络边可以使整个网络连通? 要点: 就是一个基本的强连通分量,将连通分量缩成一个点,入度和出度如果都不为0说明这个点与其他点连通,所以第一问我们只要算出几个点入度...
77
热度 -
[综合] POJ2186 Popular Cows(强连通分量)
题意: 奶牛A觉得奶牛B流行,奶牛B觉得奶牛C流行,则奶牛A也觉得奶牛C流行,现在要统计被其他所有奶牛觉得流行的奶牛数量。 要点: 先求出强连通分量并缩成点,算出对应入度和出度,统计出度为0的奶牛数即可,一开始我是统计进度为cnt-1的,后来发现WA,错误的地方在题目里也说了,A->B->...
21
热度 -
[综合] HDU1028 Ignatius and the Princess III(整数拆分:母函数||DP)
题意: 给出一个值n,问有几种不同的拆分方法。 要点: 可以用母函数或DP来做,这里说一下母函数,基本思路是:写成(1+x^2+x^3+x^4……x^n)*(1+x^2+x^4+……)*(1+x^3+x^6+……)……这样,然后利用循环从每个括号开始算起,用c1存储前一次算出的所有指数对应的系数,c...
33
热度 -
[综合] HDU3944 DP?(大组合数取模:lucas定理)
题意: 有一个杨辉三角,现在从顶点到第n行第k列,只能向下或向右下,问最短路径和模p的值。 要点: 如果n>2*m,此时一直往斜左上走到边界,再一直向上,这样最短,权值总和为C(n+1,m)+(n-m);如果n<=2*m,就先向上到边界,再斜左上到顶点,这样总和为C(n+1,m+1)+m...
38
热度 -
[综合] UVa11806 Cheerleaders(容斥原理)
题意: 给出一个n*m的棋盘,在上面放k个棋子,求第一行,第一列,最后一行,最后一列每个都有棋子的组合数。 要点: 简单的容斥原理,对第一行,第一列,最后一行,最后一列没有棋子进行容斥,这样最后减去即可。注意进行容斥时如果是相减的可能出现负数,所以在前面+MOD。 #include<iost...
50
热度 -
[综合] POJ2960 S-Nim(博弈论:sg函数)
题意: 给出一系列石子堆,现在每次只能从一个堆中拿出固定石子数,问输赢结果。 要点: 跟Nim博弈很像,但是这次每次只能拿固定个数,所以要用sg函数,下面是sg函数的具体定义: sg(x)=mex(sg(y)|y是x的后继结点)其中mex(x)(x是一个自然是集合)函数是x关于自然数集合的补集中的最...
97
热度 -
[综合] Codeforces Round #366 (Div. 2)
这套div2的题感觉难度比较低 A: 水题 B: 博弈论,但是很简单。最终必须把所有的数分解为1,所以只有考虑每个数要分解a[i]-1次,每次sum累加模2进行判断即可 C: 这题是div2的C题但是div1的A题,一不小心做了div1去了。 题意: 手机的app有通知,现在有n个app,q个操作。...
0
热度 -
[综合] codeforces723E One-Way Reform(欧拉通路)
第一次打线上赛,1456分来着,感觉自己模拟题做的不怎么样,总是想复杂,而且写代码慢的要死,这套题说实话还算简单,但只A了两道,其他的题都很基础,这题欧拉通路我刚好不会,所以写一下。 题意: n个城市之间m条双向道路,现在把双向道路变成单向,求让出入度相同的城市最多的路线图。 要点: 这题就是个欧拉...
3
热度 -
[综合] codeforces723F st-Spanning Tree(连通性t)
题意: 给出一个n个顶点m条边的无向图,并给出两个点s,t和对应的度数,要求将图转变为一颗生成树,并且s,t的度数要满足要求。 要点: 生成树也就是把原图的边减少至n-1条边,并且所有的点都连通。这题的思路是将st除去的图进行连通操作,然后此时这些连通块可以分为二种: 1.只和st其中一个相连 2....
29
热度 -
[综合] 例题27 UVa10635 Prince and Princess(DP:LIS的nlogn算法)
题意: 看白书 要点: 这题本来应该是LCS,但因为时间的要求,可以转化为LIS,而且还得用nlogn的算法,基本思路就是用b数组来存储当前b的值在a数组中对应的位置。LIS的nlogn算法的思路就是,每次用g来存储,并每次在其中进行二分查找,注意这里每次更新是不会改变LIS的性质的,最后g的结果不...
49
热度 -
[综合] 例题29 UVa11825 Hackers' Crackdown(DP:子集)
题意: 看白书二P67 要点: 这题还是有点难度的,思维上比较难想到,具体解析看白书吧。 #include<iostream> #include<cstring> #include<algorithm> usingnamespacestd; constintN=...
52
热度