HAI__嗨I起来-CSDN博客

原创对拍程序

对拍程序，可以用于检查代码，写一个标准程序来生成数据，来检验另一个程序的正确性1.cpp#includeusing namespace std;int main(){ int a,b; cin>>a>>b; cout<<a+b<<endl; return 0;}2.cpp#includeusing namespace std;int ma

2017-03-23 17:20:36 448

原创城市间紧急救援 ,复杂点的最短路，记录路径，记录最短路个数等

5-7 城市间紧急救援 (25分)作为一个城市的应急救援队伍的负责人，你有一张特殊的全国地图。在地图上显示有多个分散的城市和一些连接城市的快速道路。每个城市的救援队数量和每一条连接两个城市的快速道路长度都标在地图上。当其他城市有紧急求助电话给你的时候，你的任务是带领你的救援队尽快赶往事发地，同时，一路上召集尽可能多的救援队。输入格式:输入第一行给出4个正整数NN、M

2017-03-20 21:34:52 996

原创纯拓扑排序，稍加改良时间。

#includeusing namespace std;#define LL long long#define INF 99999999#define put() puts("***********")const int N = 2e3+10;int du[N];int a[N][N];vectorvec[N];queueQ;int main(){ int n;

2017-03-20 20:57:27 376

原创 01背包+记录路径

复习一下#includeusing namespace std;int a[]={0,23,34,113,54,33,65,77,132};int path[110][500];int p[500];int dp[110][500];void solve(int i,int j){ while(i&&j){ //01背包只存在与取与不取两

2017-03-15 16:44:36 1535

原创是否完全二叉搜索树（对一个排序二叉树进行判别是否为完全二叉树）

2 是否完全二叉搜索树 (30分)将一系列给定数字顺序插入一个初始为空的二叉搜索树（定义为左子树键值大，右子树键值小），你需要判断最后的树是否一棵完全二叉树，并且给出其层序遍历的结果。输入格式：输入第一行给出一个不超过20的正整数N；第二行给出N个互不相同的正整数，其间以空格分隔。输出格式：将输入的N个正整数顺序插入一个初始为空的二叉搜索树。在第

2017-03-12 22:11:27 544

原创 centos6.0静态ip VMWare centos6.0静态ip设置

centos6.0静态ip VMWare centos6.0静态ip设置因为使用虚拟机有时候ip会变化，用putty和一些工具不方便，所以就设置成静态ip方法/步骤先获取window的ip地址ipconfig/all按照window的ip地址设置

2017-01-10 21:06:36 303

原创 HDU 5898 数位dp

题意：给出一个区间[l, r]，问其中数位中连续的奇数长度为偶数并且连续的偶数长度为奇数的个数。（1例如 12223333 就不满足条件，因为存在奇数个奇数（1个1）#include#define LL long long#define N 100010#define INF 0x3f3f3f3fusing namespace std;LL dp[25][25][25];i

2016-09-20 20:59:45 1062

原创 HDU 5900 区间dp

题意：给出n对数keyi,vali表示当前这对数的键值和权值，可以操作将连续的两个数合并，如果满足gcd(a[i],a[i+1])>1，得到的价值是两个数的权值和，每次合并两个数之后，这两个数就会消失，然后旁边的数会接上比如1 2 3 4 合并了 2 3 则剩下1 4也可以合并。思路：1：处理出任意区间内的所有数是否可以合并对于当前的[l,

2016-09-19 12:27:54 330

原创 HDU 5726 求gcd=k的区间的个数（二分+RMQ）

题意：给一个数组a，大小为n，接下来有m个询问，每次询问给出l、r，定义f[l,r]=gcd（al，al+1，...，ar），问f[l,r]的值和有多少对（l'，r'）使得f[l',r']=f[l,r]。n思路：　　第一步比较简单，预处理一下，定义f[i][j]为：ai开始，连续2^j个数的最大公约数，所以f[1][0]=a[1],f[1][1]=gcd(a1,a2),f[1]

2016-09-13 21:27:15 399

原创 HDU 5869 求区间中不同连续序列的gcd的个数（树状数组）

题意：长度n的序列, m个询问区间[L, R], 问区间内的所有子段的不同GCD值有多少种.思路：区间GCD收敛的很快，所以直接暴力预处理出到每个数字截至的后缀串有哪些GCD以及它们的位置，就是每个数字向前看有哪些GCD出现，这个数量是很少的。1.枚举区间的右坐标，然后枚举出所有的以这个为右坐标为区间左坐标。2.并求出他们这个连续区间的gcd，去重,（即重复的不再记录）3.

2016-09-13 20:29:46 1697

原创 HDU 5877 dfs+离散化+树状数组（树上维护）

题意：　给出一棵n个结点的树和一个数k, 每个节点上有权值, 问有多少个有序对(u,v) (u,v)满足u是v的祖先, a[u] * a[v] 思路：首先这是在树上进行操作，然后就是找满足祖先关系，并且a[u] * a[v] 找点的a[u] * a[v] 然后这就转化成找树上点有多少个小于某个值得问题了，对于这种问题要转换成树状数组进行维护，时间复杂度就变

2016-09-12 19:29:29 389

原创 POJ 1185 经典状压dp （模板）

炮兵阵地Time Limit: 2000MS Memory Limit: 65536KTotal Submissions: 26096 Accepted: 10072Description司令部的将军们打算在N*M的网格地图上部署他们的炮兵部队。一个N*M的地图由N行M列组成，地图的每一格可能是山地（用"H" 表示），也可

2016-09-10 22:18:07 386

原创 uva 1218 完美服务器树形dp 染色问题

详解见紫书 283页。#include#define INF 10000000using namespace std;const int N= 10010;vectorvec[N];int dp[N][3]; ///int vis[N];void dfs(int u){ int len=vec[u].size(); vis[u]=1; dp[u][0]=

2016-09-09 21:17:11 319

原创 UVA 1220 树形dp 最大独立集+状态标记

题意：公司里n个人形成一个树形结构，即除了boss之外每个员工都有唯一的直属上司。要求选尽量多的人，但不能同时选择一个人和他的直属上司。问最多能选多少人，以及判断人数最多的前提下得方案是否是唯一结果。思路：树形dp，就是求在树上的最大独立集合，加唯一性特判.首先需要明确的一点是：这是一个树形结构。A：然后就是要明确我们要存入两种结果值，一个是最大的独立集合的

2016-09-09 18:41:19 398

原创 POJ 2486 Apple Tree 树形dp+背包

题意：给一棵苹果树，树上有n个结点，每个结点有 ai个苹果，（不存在父子关系），让求最多走k步之后可以吃到的最多的苹果数目，（走动必须在相邻结点之间进行发生，从一个结点到另一个相邻结点是需要消耗一个步数。），每次都先从结点1开始走。思路：首先看到这个题就要先想起树形结构，然后这道题只存在相邻关系，即是一个无向树，此题让求最多走k步可以吃到的苹果数目，所以状态可以先表示成在

2016-09-04 14:20:36 386

原创 POJ 1947 Rebuilding Roads 树形dp+01背包

题意：给了一棵树，树上有n个结点，然后让求最少删去多少条边，可以使剩下的一棵子树中存在p个结点。思路：dp[x][ j ] 表示把x结点当成根时，形成的恰好含有j个结点的子树，至少删除的边数。此时考虑递推式；对于x结点的dp[x][j] 他的状态可以由子结点推出来，对于孩子结点son来说；1）当不需要son时 dp[x][j]= dp[x][j]+1;

2016-09-04 12:42:25 216

原创 POJ 2454 Jersey Politics 分组问题随机化算法

题意：给出3*k个数，将它们分成三分，每份k个数，要求至少存在有两份，使得每一份的k个数的和大于500*k。思路：先从大到小的进行排序，然后只需要将前2*n大的数进行随机的分配成两组就行了。#include #include #include #include #include #include #include #include #define LL long lon

2016-09-03 21:12:39 339

原创 POJ 3318 Matrix Multiplication 随机化算法

题意：给出三个n*n的矩阵A,B,C看是否A*B=C;#include#include#include#include#include#include#include#define bug puts("************")#define INF 0x3f3f3f3f#define LL long longusing namespace std;const in

2016-09-02 21:59:39 325

原创 POJ 3101 Astronomy 轨道相遇问题，求n个分数的最小公倍数

题意：给你一个n，然后给你n个星球的周期。让你求出经过多长时间可以使所有的星球可以在条直线上。思路：求轨道相遇问题,设经过了t个时间星球A转的角度为 (2π/T1)*t 星球B转的角度为(2π/T2)*t 他们在一条直线上所以可得：(2π/T1)*t-(2π/T2)*t=n*π，半圈就相遇，所以n取1。-->t=T1*T2/(2T1-2T2);然后需要求出所有的星球与第

2016-08-26 08:56:38 534

原创 POJ 2891 Strange Way to Express Integers解线性同余方程组(中国剩余定理不互质版)

题意：给出k个模方程组：x mod ai = ri。求x的最小正值。如果不存在这样的x，那么输出-1.题解：由于这道题目里面的ai、ri之间不满足两两互质的性质，所以不能用中国剩余定理直接求解。不过，我们可以模仿中国剩余定理的做法来解决这个问题。如果只有一个方程：x mod a0 = r0。那么，显然x的最小正值为a0+r0。根据模的性质，我们容易得知，x+a0*k

2016-08-25 19:35:11 599

原创 POJ 1061扩展gcd

扩欧的使用，要学会构建方程，首先要先写出等式关系出来，然后再将等式关系进行构建方程。这道题是：假设两只青蛙都跳了t步之后两者相遇。则青蛙A 的位置为x+mt ，青蛙B为 y+nt。则 x+mt-y-nt=pL (p为圈数)所以t*(n-m)+pL=x-y; 套入extend_gcd 既可以得到x1(n-m)+y1L=gcd;之后求出gcd与x-y的倍数关系。

2016-08-25 10:44:43 272

原创 POJ 2947 (高斯消元解同模方程)

公司被吞并，老员工几乎全部被炒鱿鱼。一共有n种不同的工具，编号1-N（代码中是0—N-1），每种工具的加工时间为3—9天，但是现在老员工不在我们不知道每种工具的加工时间，庆幸的是还保留着一些对工人制造工具的记录，对于每个老员工，他的记录包括，他开始工作的时间（在某个星期的星期几），被炒鱿鱼的时间（某个星期的星期几），在第几个星期不知道.....在这段时间里，他正好加工了k件物品，给出了这k件物

2016-08-24 22:04:06 290

原创 POJ 1222 开关问题高斯消元法

一个01矩阵，表示灯的亮灭状态，每次操作可以改变一个十字形状内的五个灯的状态。问能否将所有灯熄灭。最后输出开关的状态。思路：开灯关灯问题，5*6的灯阵，将每一个位置上开关状态看做一个变元，30个变元，而对于30个位置的灯的状态当成开关状态的解，列出30个异或方程，高斯消元解方程即可（增广矩阵）。对于每个状态，影响他的条件与五个位置的开关状态有关，让这五个状态的开关系数为1 ，其

2016-08-24 17:01:25 447

原创 POJ 3270 Cow Sorting (置换群利用) 位置交换问题

题目：有一串数字，要将它排列成升序，每次可以交换两个数，交换一次的代价为两数之和。要求代价最小。所有的数都是唯一的。将原有数列排序之后，得到目标串，这样就与原串形成了置换。1.对于单个循环群来说(大小大于1)，所有的数的位置与目标位置完全不同，所以最理想的交换的情况是需要交换n-1次。例如串 2 3 4 5 1 变成1 2 3 4 5 这是最简单的循环群，需要交换n-1次并且每

2016-08-24 10:43:34 377

原创 POJ 1026 Cipher（置换群）循环节

Bod 和 Alice 计划使用一种全新的编码方案，令人惊讶的是这不是一个公开的公匙密码，但是他们的编码基于密匙，在Philadelphia on February 16th他们的会议中选择了密匙，他们选择的密匙是一个两两不等的整数序列，a1.....an,大于0并且小于等于n，编码基于一下原则。下面的信息是关键，这样关键的人物信息和数字相对齐，一个字符在i位置，编码的时候把他放在ai，a

2016-08-23 21:47:11 387

原创 POJ 1286 polya计数、burnside定理

题目大意：n个珠子串成一个圆，用三种颜色去涂色。问一共有多少种不同的涂色方法。不同的涂色方法被定义为：如果这种涂色情况翻转，旋转不与其他情况相同就为不同。解题思路：Polya定理模版题。burnside定理：对于一个置换f,若一个着色方案s经过置换后不变，称s为f的不动点。将f的不动点为C(f).则等价类数目为所有C(f)的平均值。

2016-08-23 17:10:52 234

原创 HDU 5617 多维dp降维问题，回文串匹配

给你一个n*n的矩阵。求从(1,1)走到(n,n)所组成的回文串个数。只可以向右或者向下走。思路：1.此题的“序” 是这个二维坐标。2.影响决策的因素是前后字符串是否比配。3.状态及其考虑的方案：因为是回文串问题，所以要考虑从首尾两个位置进行枚举看看相对应的位置是否相等，同时再记录他们的对应位置的相匹配的数量。可以设从起点（1,1）和终点（n,n）同时出发，计算分别到达

2016-08-20 10:30:16 331

原创 HDU5616 背包天平平衡问题

题目大意：有一个只能判断两边是否相等的天平，现在给你一些已知重量的砝码，问你是否可以通过这些砝码测量一个任意给定的重量（input），即可以通过在天平两侧放一定数量的砝码，使天平平衡。#include #define INF 0x3f3f3f3fusing namespace std;const int N=1000;char s[N];int a[N];int dp[N][3*N

2016-08-19 19:29:29 599

原创 POJ 1166 枚举或者高斯消元

给出9个钟表的状态，给出九种操作，问最少要操作几次能把所有的钟表调回12点。思路：对于9个钟表分别列方程，然后高斯消元即可。然后用每个未知量表示是否进行此操作。所以取值是1或者0接下来就是枚举每个未知量得系数使得每个等式都成立。#include#include#include#include#define LL long long#define bug p

2016-08-17 21:37:52 250

原创 HDU 5667 矩阵快速幂关于指数的递推

SequenceTime Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)Total Submission(s): 1498 Accepted Submission(s): 505Problem Description Holion Augus

2016-08-16 15:58:08 246

原创 HDU 5833 高斯消元异或方程组

题意：给出n个正整数，从中选出1个或者多个，使得选出来的整数乘积是完全平方数，一共有多少种选法。思路：用01向量表示一个数，再用n个01向量来表示我们的选择，因为完全平方数要求素因子的次数一定要是偶数的，所以我们可以统计的将奇数当作1，偶数当作0，那么就是一组可以变换成oxr的方程组，最后的结果有自由变量f个，答案是2^f-1,f求解就是求n-方程组的秩，（本题不允许一个都不选，所以减

2016-08-16 10:02:11 344

原创 UVA 10870 递推关系矩阵快速幂

题意：f(n) = a1 ＊f(n - 1) + a2 ＊f(n - 2) + a3 ＊f(n - 3) + … + ad＊ f(n - d), n > d.求f(n)见白书 155页。由于n太大，不能直接递推，需要用矩阵快速幂来解决，时间复杂度为O(d^3logn) 举例，d=5的矩阵关系式为： |a1 a2 a3 a4 a5|

2016-08-15 19:48:58 609

原创 POJ 1703 并查集的应用关系并查集l两种方法

/*****************有两个帮派，有两种操作 D a b表示a 和 b不是一个帮派；A a b 表示询问a b是否是一个帮派，若至此还不确定，输出“Not sure yet”。思路：关系并查集；只要两者的关系确定了，就将他们放入同一个集合内，而另外增加一个表示关系的数组r[ ]来表示该节点与其父亲的关系。0表示同一类，1表示不同类。初始时集合只有自己一个元素，r[ ]设置

2016-08-13 21:17:29 200

原创 HDU 5807 分段 dp 将DAG分段进行

给定一个50个点的DAG图每个点有个权值w[i]，给定初始3个特工所在的位置是x,y,z这3个城市，每一时刻每个人都得移动到下一个城市，并且要求每一时刻两两之间都能联系但且仅当任意两个城市之间的权值差思路：注意一点是：输入为有向图，并且输入的数据满足 u /*********************** 对于DAG问

2016-08-12 20:26:06 234

原创 HDU 5821 多校脑洞题贪心

题意：有N个盒子，每个盒子最多装一个球. 球的颜色不一定相同.现在要进行m次区间操作：每次操作 [l, r] 后可以随意将区间内的球重新分配回去.问经过上述操作后是否有可能达到给定的状态. 思路贪心.首先应该明白待操作数据与目标数据是一一对应的关系，然后接下来就去想，如何可以判断是否可以匹配上。为每个球记录它在最终结果中的序号. 对

2016-08-12 11:44:54 318

原创 HDU 5719 贪心，脑洞题

点击打开链接题意：这儿共有nn堆稻谷，编号为11到nn。Psyche需要将这些谷堆以某种顺序排列，设最终排在第ii位的谷堆是A_iAi。她得知了一些该排列的要求： 1. 对于任意整数i \in [1,n]i∈[1,n]，A_1, A_2, ..., A_iA1,A2,...,Ai的最小值为B_iBi。 2. 对于任意整数i \in [1,n]

2016-08-11 10:30:18 381

原创 HDU 5750 数学题

随便推导下, 令y=xdy=xd, 如果dd是yy的maximum positive proper divisor, 显然要求xx是yy的最小质因子. 令mp(n)mp(n)表示nn的最小质因子, 那么就有x \le mp(d)x≤mp(d), 同时有y yn, 那么x \le \lfloor \frac{n-1}{d} \rfloorx≤⌊dn−1⌋.

2016-08-10 10:05:58 367

原创 HDU 5818 2016多校赛第七场数组模拟链表，来模拟栈

http://acm.hdu.edu.cn/showproblem.php?pid=5818比较简单巧妙的一个做法是引入一个新的栈C，每次合并的时候就把A和B合并到C上，然后把A和B都清空. push还是按正常做，pop注意当遇到要pop的栈为空时，因为题目保证不会对空栈进行pop操作，所以这时应直接改为对C栈进行pop操作. 这样做因为保证每个元素最多只在一次合并中被处理到，pop和push

2016-08-09 22:22:03 315

原创 sg函数应用多校 HDU5795A Simple Nim 与其他题 NIM变形

点击打开链接题意：一个n堆的取石子游戏，每次可以取一堆中的任意个，或者将当前堆分为三个非空堆。求先手/后手必胜。思路：根据sg定理，游戏和的sg函数等于各个游戏的sg函数的nim和。所以需要把各个状态的sg函数打表打出来，找找规律。该题有两种操作方式，一种是任意一堆拿任意数量，另一种是将任意的一堆分成三等份。其他题目链接http://acm.hust.edu.cn/vjud

2016-08-09 18:42:19 349

原创 POJ 3468 A Simple Problem with Integers 区间和更新，区间和查找

点击打开链接#include#include#include#include#include#include#include#define LL long long#define bug puts("***********");#define lson L,mid,ind<<1#define rson mid+1,R,ind<<1|1#define lind ind<<1

2016-08-08 14:11:21 210

空空如也

空空如也