const_qiu的专栏

Drainage Ditches题意：给出n条水管，m个节点（0~n-1），以及每天水管的最大流量，问从节点0到节点n-1某时刻的最大流量思路：最大流问题解题方法：初学，参考大神的博客题解，详细点这里   我的理解就是从开始节点开始通过dfs找到去终点的路，然后会发现中途会有交叉口，这时你先选一条继续走，直到找到终点。 注意：当找到终点你会发现之前的流量可能有些是没

注：这题似乎有bug， two odd prime numbers 不应该是奇素数吗，所以若输入7，应该是不可以拆的，可是输出“7 = 2 + 5”和"Goldbach's conjecture is wrong.\n"都可以AC，有知道的希望能解答下疑惑Goldbach's ConjectureTime Limit: 2 Seconds      Memory Limit: 65

原谅我就只会这两水题了，其他题没怎么看~估计看了也是无奈OlympiadTime Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/65536 K (Java/Others)Total Submission(s): 234    Accepted Submission(s): 171Problem

Semi-PrimeTime Limit: 2 Seconds      Memory Limit: 65536 KBPrime Number Definition An integer greater than one is called a prime number if its only positive divisors (factors) are one and it

注：题意纠结了半天，后来看了很多大牛的博客，才理解透，最后发现就是匈牙利，纯暴力~还有就是字典序总觉得难透~Blue and Red题意：有两个对，红队（0）和蓝队（1）。然后有n个人属于这两个队的某一只队，既然有人，那么肯定会有两两是朋友的，一共m对。但是现在有一个测试，某某不希望有不在同一个队的两个人是朋友关系，说什么会影响测试，所以需要把某些人删掉使这个条件成立，而且删人的话还要按字

注：只看了1005&&1007，个人水平比较low，1005 - The shortest problem乍看一眼，有点像前几天水的一道数论水题，说求一个数（2*10^9）的每位数之和，然后与此题无关系，其实题目就是不断求各位数的和然后补充上去，执行t次后判断得到的数时候能被11整除，很明显是有规律的，此数已经十几万位的数，不能直接%11，所以就会发现其实被11整除的数（只需判断奇数位的和

Minimum Cost题意：给出： n个客户，m个仓库，k种商品 每个客户对每种商品的需求书每个仓库里每种商品的数目对于每种商品，每个客户在各个仓库的进价（具体可以见输入代码注释）求所有客户购买需要的所有商品的最小费用，如果某个客户不能购买到某种商品那么输出-1思路：最小费用最大流解题方法：对每种商品算一次最小费用最大流主要是建图：对于每次

注：每个功能在代码中有注释，具体详解可自己输出测试1：区间更新与区间求和#include#include#includeusing namespace std;#define N 400010#define LL long longLL sum[N],lazy[N];///向上更新求和void pushUp(int root){ sum[root]=sum[

Chessboard题意：一个n*m的矩阵方格，其中有k个1*1的小方格不能使用，问剩下的是否能恰好用1*2的方格铺满思路：二分图的最大匹配 匈牙利算法解题方法：要点1：一个1*2的方块可分成两个1*1的小方块，这两个小方块的横纵坐标和必定一个为奇数一个为偶数要点2：将奇数的小方块作为二分图的左边，然后去找能够与它组成1*2的方块（也就是与它相邻的）构成二分图的右边

Power Network题意：n个点（0~n-1），m条边，np个源点，nc个汇点，有各自的流量限制，问同一时刻所有源点到汇点的最大流思路：最大流，建图，EK解题方法：新增起始点n，与所有源点相连通；新增终点n+1，与所有汇点相连通，此时就变成求结点n到结点n+1的最大流注意：这里用的是理解矩阵存的边，刚开始用了vector的邻接表发现超时了代

注：还是推公式，类似zoj2277，打表超内存（话说才10^7数组就爆了），默默暴力计算930ms险过Big NumberTime Limit: 10 Seconds      Memory Limit: 32768 KBIn many applications very large integers numbers are required. Some of

注: 第一想法就是矩阵快速幂，还有一想法是maybe有规律可循，这里用的是矩阵快速幂解法Number SequenceTime Limit: 2 Seconds      Memory Limit: 65536 KBA number sequence is defined as follows:f(1) = 1, f(2) = 1, f(n) = (A * f(

注：将数字转换为二进制比较就可，主要是细节问题Binary NumberTime Limit: 2 Seconds      Memory Limit: 65536 KBFor 2 non-negative integers x and y, f(x, y) is defined as the number of different bits in the bi

Nearest Common Ancestors题意：求两个节点的最近公共父节点思路：LCA tarjan代码如下：#include#include#includeusing namespace std;#define N 10010struct Edge{ int v; int len; int next;}edge[N*2];int e

How far away ？题意：建一棵树，n个点，n-1条边，有权值，然后q次询问，每次求两个节点的连线最短距离。思路：LCA解题方法:(还有待理解，怕说错)注意:vector会爆栈，需要加第一行代码然后C++可过，据说是服务器略坑，不过手写栈（代码待更新）就不用担心了参考AC代码:#pragma comment(linke

Connections between cities题意：求连接两城市的最短距离题目思路:LCA Tarjan解题方法:通过Tarjan求距离需注意的问题：存在森林，所以对于每棵树都得进行计算    存在未连通，只需先判断节点的根节点（并查集find）是否相同即可    内存29432K险过，需用邻接表模拟，vector会爆AC代码：

Design the city题意：求三个节点到他们最近公共父节点的距离和思路：对于三个节点两两求到最近公共父节点的距离，然后加起来除以二就是答案参考代码：#include#include#include#includeusing namespace std;#define N 100010#define NN 500010struct Edg

2007/2008 ACM International Collegiate Programming Contest University of Ulm Local ContestProblem F: Frequent valuesYou are given a sequence of n integers a1 , a2 , ... , an in non-decreasin

Assignment题意：一个公司有n个与员工，编号依次1~n，每个员工有对应能力值a[i],现在有多少个不同的区间(l,r)满足区间内任意两个员工的能力值差不能超过k，求满足条件的区间个数题目思路:RMQ+二分，RMQ不了解可以先看下这里，二分就不多说了，详细见如下代码：#include#include#include#includeusing namespace s

Balanced Lineup题目大意:一群牛，编号依次1-n，每头牛都有一个高度height，现在会有Q次询问（A，B），求编号A~B的牛中最高与最低牛高度的差值。题目思路 :RMQ(Range Minimum/Maximum Query),即区间最值查询解题方法：类似DP，mm[i][j]表示从 第i个位置 开始到 第（2^j）个位置的最大值，由2^j=

注：怎么都说是个水题~~TTTT~~怪我方向感太差Crazy Tea PartyTime Limit: 2 Seconds      Memory Limit: 65536 KBn participants of "crazy tea party" sit around the table. Each minute one pair of neighbors can cha

The Gate to FreedomTime Limit: 2 Seconds      Memory Limit: 32768 KBBackgroundIt is dark at night.It is silence at night.It is she in the dark.It is she in the silence.Then a light

ShoppingTime Limit: 10000/5000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)Total Submission(s): 2126    Accepted Submission(s): 712Problem DescriptionEvery girl likes

Instrction Arrangement题目链接: http://acm.hdu.edu.cn/showproblem.php?pid=4109~~第一道关键路径问题，留下代码纪念，题目大意就是要完成n个任务（0~n-1），每个任务单独最快要1s，而有些任务是需要在某些任务完成后耗时**才能完成的，可多线程进行任务，问完成所有任务需要的最短时间。拓扑排序、关键路径

题目链接：http://poj.org/problem?id=1269题目mians

初期:一.基本算法:     (1)枚举. (poj1753{bfs+位二进制} ,poj2965{bfs 或者一种很巧妙的解法} )    (2)贪心(poj1328,poj2109,poj2586)    (3)递归和分治法.     (4)递推.     (5)构造法.(poj3295)    (6)模拟法.(poj1068,poj26

Minimum Inversion Number题目连接：http://acm.hdu.edu.cn/showproblem.php?pid=1394

Just a Hook题目连接：http://acm.hdu.edu.cn/showproblem.php?pid=1698

KMP

#include#include#includeusing namespace std;#define N 105char map[N][N];int go[4][2]={0,1,0,-1,1,0,-1,0};///四个方向判断int m,n;void dfs(int s,int t){    if(map[s][t]=='.') return ;///碰到不是

A Simple Problem with Integers题目连接：http://poj.org/problem?id=3468题目大意：给出一个数组，要求对一个区间所有的值加某一个数或者计算某一区间所有值的和。题目思路：利用线段树处理，具体见代码代码如下：#include#include#includeusing namespace std;#define N 10

敌兵布阵Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others)Total Submission(s): 43628    Accepted Submission(s): 18510Problem DescriptionC国的死对头A国这段时间正在进行军事演

深度优先搜索一、深度优先搜索DFS(Depth First Search)（一）深度优先搜索遍历类似于树的先根遍历，是树的先根遍历的推广。（二）假设初始状态是图中所有顶点未曾访问，则深度优先搜索可从图中某个顶点V出发，访问此顶点，然后依次从V的未被访问的邻接点出发深度优先遍历图，直到图中所有和V有路径相通的顶点都被访问到；若此时图中尚有顶点未被访问，则另选图中一个未曾被访问

题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=2108

题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=4709题目大意：给出n个点，

题目链接:

Heavy Transportation题目链接：http://poj.org/problem?id=1797题目大意: 一个城市有n个街道（1~n），每两个街道有些是相通的，可容纳一些物品流通，但是这个通路是有大小的，因此可流通的物品大小不一，现在要从街道1流通一些物品去街道n，问一次可以流通多大的物品。通俗的讲就是求1->n所有路径中最小距离最大的那段。题目思路

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=2647RewardTime Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)Total Submission(s): 4397    Accepted Submission

Frogger题目链接：http://poj.org/problem?id=2253题目大意:青蛙，两只青蛙，是的就是两只青蛙，池塘里有些石块，两只青蛙各自站在一块石块上，其中有一只青蛙想去找另一只青蛙，估计是寂寞了，然后因为池塘也有其他的石块，所以这只青蛙就有很多路径可以选择了，但是因为从一块石块到另一石块是有距离的，所以每条路径都存在一段最大的距离是这只青蛙需要跳过

Til the Cows Come Home~~~~题目大意就不多说了，果果的最短路问题，给出n的点，t条路径和路径的权值，要求出从n点到1点的最小权值。思路：将路径和权值存入map[][]中，没有的就用INF，然后使用一个vis[]数组去标记哪些点的最短路已经确定好了的，没有确定的可以继续通过其他点进行更新。。最后也是最重要的就是dis[]数组了，首先要明白dis[]数组存的是什么。