ACM

URAL1416 题意：次小生成树模板题 思路：用Kruskal求最小生成树，标记用过的边。求次小生成树时，依次枚举用过的边，将其去除后再求最小生成树，得出所有情况下的最小的生成树就是次小的生成树。复杂度o(m2)。。。貌似有其他优化。。。

1681: [Usaco2005 Mar]Checking an Alibi 不在场的证明 # Time Limit: 5 Sec Memory Limit: 64 MB Submit: 250 Solved: 178 [Submit][Status][Discuss] Description # A crime has been comitted: a load of grain has been taken from the barn by one of FJ’s cows. FJ is trying to determine which of his C (1 <= C <= 100) cows is the culprit. Fortunately, a passing satellite took an image of his farm M (1 <= M <= 70000) seconds before the crime took place, giving the location of all of the cows. He wants to know which cows had time to get to the barn to steal the grain. Farmer John’s farm comprises F (1 <= F <= 500) fields numbered 1..F and connected by P (1 <= P <= 1,000) bidirectional paths whose traversal time is in the range 1..70000 seconds (cows walk very slowly). Field 1 contains the barn. It takes no time to travel within a field (switch paths). Given the layout of Farmer John’s farm and the location of each cow when the satellite flew over, determine set of cows who could be guilty. NOTE: Do not declare a variable named exactly ’time’. This will reference the system call and never give you the results you really want.

题目链接 题意：n个人的上下级关系形成一棵树..每一个人有一个val（可正可负），要选若干个人参加一个party，要求是一个人和他的直接上级不能同时在场。问参加party的人最大的val之和。

noip 初赛加强版既视感… 自己手动整理的 第二章 机器数：正负符号数码化后的数据称为机器数。 BCD 码：用二进制编码的十进制数称为 BCD 码。 有权码：每位二进制数码元都有确定权值的编码。 校验码：为了发现或纠正数据传送中出现错误的编码。 浮点数的精度由尾数的位数决定。 第三章 溢出：运算结果超出了机器能表示的数据范围。 溢出的特征：结果的符号与操作数的符号不同。 变形补码：两个符号位的补码（用来检测溢出，00,11说明没有溢出，10,01说明有溢出） 对阶：使阶码相等的过程（原则是小阶码向大阶码看齐） 结果规格化：将非规格化数处理为规格化形式。

cf660C solution:ruler.1A 代码实现 1/* *********************************************** 2Author :111qqz 3Created Time :2016年06月08日 星期三 23时43分18秒 4File Name :code/cf/problem/660C.cpp 5************************************************ */ 6 7#include <cstdio> 8#include <cstring> 9#include <iostream> 10#include <algorithm> 11#include <vector> 12#include <queue> 13#include <set> 14#include <map> 15#include <string> 16#include <cmath> 17#include <cstdlib> 18#include <ctime> 19#define fst first 20#define sec second 21#define lson l,m,rt<<1 22#define rson m+1,r,rt<<1|1 23#define ms(a,x) memset(a,x,sizeof(a)) 24typedef long long LL; 25#define pi pair < int ,int > 26#define MP make_pair 27 28using namespace std; 29const double eps = 1E-8; 30const int dx4[4]={1,0,0,-1}; 31const int dy4[4]={0,-1,1,0}; 32const int inf = 0x3f3f3f3f; 33const int N=3E5+7; 34int n,k; 35int sum[N],a[N]; 36 37void ruler() 38{ 39 int head = 1; 40 int tail = 1; 41 int l,r; 42 int res = -1; 43 int cnt = 0 ; 44 45 while (tail<=n) 46 { 47 while (a[tail]==1) tail++; 48// cout<<"head:"<<head<<" tail:"<<tail<<endl; 49 if (a[tail]==0&&tail<=n) cnt++; 50 51 while (sum[tail]-sum[head-1]<=k&&tail<=n) tail++; 52// cout<<"head:"<<head<<"tail:"<<tail<<endl; 53 if (tail-head>res) 54 { 55 res = tail-head; 56 // cout<<"res:"<<res<<endl; 57 l = head; 58 r = tail-1; 59 } 60 61 while (head<=tail&&sum[tail]-sum[head-1]>k) head++; 62// cout<<"head::"<<head<<" tail:"<<tail<<endl; 63 if (tail<=n&&tail-head+1>res) 64 { 65 res = tail-head+1; 66 l = head; 67 r = tail; 68 } 69 70 71 } 72 73 74 for ( int i = l ; i <= r ; i++) a[i] = 1; 75 76 cout<<res<<endl; 77 for ( int i = 1 ; i <= n ; i++) cout<<a[i]<<" "; 78} 79int main() 80{ 81 #ifndef ONLINE_JUDGE 82 freopen("code/in.txt","r",stdin); 83 #endif 84 85 cin>>n>>k; 86 87 sum[0] = 0; 88 for ( int i = 1; i <= n ; i++) 89 { 90 scanf("%d",&a[i]); 91 sum[i] = sum[i-1] +(1-a[i]); 92 } 93 94 ruler(); 95 96 97 #ifndef ONLINE_JUDGE 98 fclose(stdin); 99 #endif 100 return 0; 101}

树，一种十分优美的数据结构，因为它本身就具有的递归性，所以它和子树间能相互传递很多信息，还因为它作为被限制的图在上面可进行的操作更多，所以各种用于不同地方的树都出现了，二叉树、三叉树、静态搜索树、AVL树，线段树、SPLAY树，后缀树等等.. 枚举那么多种数据结构只是想说树方面的内容相当多，本专辑只针对在树上的动态规划，即树形DP.做树形DP一般步骤是先将树转换为有根树，然后在树上进行深搜操作，从子节点或子树中返回信息层层往上更新至根节点。这里面的关键就是返回的信息部分，这个也没一般性的东西可讲，因为每道题目要求做的事都不尽相同。

学完了km..感觉匈牙利真是非常的。。easy… 匈牙利算法学习链接 有一种题目会用1*2的小格子填充大的，问能不能填满之类的，可以用匈牙利搞。hdu 4185解题报告 poj2446解题报告

km算法我的理解 刷了不到20道题。。。回来总结一发。。 如果题目求的是最小权值匹配，比较好的做法是将权值取取值，最后res再取负就好。需要注意的是初始化的时候w和lx要比所有值都小，所以要ms(lx,0xc0)

hdu 3523 题目链接 题意：有m个排列，每个排列有n个，然后要找一个长度为n的排列（1..n每个数字恰好出现一次），使得这个排列到其他m个排列的距离之和最小。 两个排列之间的距离是对应位置上数字差的绝对值的和。

hdu 3315 题目链接 题意：两个人分别各有 n 个怪物。进行 n 场 pk。每只怪物必须恰好进行一场 pk。如果先手的第 i 只怪物赢，会获得 v[i] 的 val，输会减少 v[i] 的 val。给出两个人 n 只怪物的血量和攻击力。先手的初始战斗顺序为 1,2,3..n（后手的战斗顺序一直都是 1,2,3..n）现在问能否通过调整顺序使得先手获得的 val 最大，如果这个 val 大于 0，表示先手可以赢。如果可以赢，那么还要求调整后的顺序和原始顺序的相似度，并且使得相似度尽可能大（If there are multiple orders, you should choose the one whose order changes the least from the original one）

hdu 2853 题目链接 题意：n 个公司，m 个任务（m>=n)，一个公司只能对应一个任务，一个任务也只能对应一个公司。给出一个 n*m 的 mat，表示每个公司对应每个任务产生的 val。然后给出 n 个数，表示初始钦定（雾）这 n 个公司分别做哪些任务。但是可能初始的安排得到的 val 不是最大的。我们现在想得到最大的 val，并且保证改变的安排数最少。求安排后得到的 val 比初始安排大多少，以及需要改变的安排数量。

hdu2448 题目链接 题意：n 艘船 n 个港口，一个港口只能承接一艘船，m 个油田，给出 n 艘船各自在哪个油田，然后给出 m 个油田之间的无向图，然后给出油田和港口之间的有向图。求 n 艘船到达港口的最小距离之和。

hdu 3718题目链接 题意：东西分类作业，有n个东西，k组，m个学生，不同种类的东西用不同的字母表示，相同种类的用同一个字母表示。不同学生和标准答案之间可能表示同一类东西用的字母不同，但是字母只是一个标号（But the LABEL of group doesn’t make sense and the LABEL is just used to indicate different groups. ） 给出事物分类的标准答案和每个学生的答案现在问每个学生的正确率是多少。

hdu 3722题目链接 题意：n个串，a串放在b串前面的val值是“The score of sticking two cards is the longest common prefix of the second card and the reverse of the first card”.问如何放使得总的val最大。 思路：先暴力处理出每两个的权值。。2002001000的复杂度。。还是可以接受的。。

hdu 3435题目链接 题意：给你一张图，图上可能有多个哈密顿回路。叫你求出形成多个哈密顿回路的总距离最小值 思路：题意杀啊。。。什么鬼了。。。然后时间。。1000的数据。。n3复杂度。。。还多组数据。。。。不是很懂这个时间是怎么算的。。为毛才2600MS啊。。。。

hdu 1853 题目链接 题意：一个带权有向图，要求找出若干的环，满足每个点恰好在一个环里，并且环的权值和最小……问最小权值和。 思路：没有思路，不知道怎么处理环的问题。于是去群里问了下。正确做法是拆点。

hdu 2813 题目链接 题意：吕布有n个武将，曹操有m（m>=n）个武将。给出k个关系，为吕布的某个武将和曹操的某个武将pk后会受到的伤害。吕布要求他所有n的武将都要上场，每个武将只能战斗一次，问如何安排，使得所有武将受到的伤害总和最小。

hdu 2282 题目链接 题意：n个盒子围成一个圈，给出n个盒子中每个盒子中的巧克力个数，巧克力的总数不超过n，从一个盒子中移动一块巧克力到相邻的盒子里称为one “move”，（由于围成一个圈，所以第1个和第n个盒子也是相邻的） 问最小的移动“move”数，使得每个盒子里最多有一快巧克力。

hdu 3395题目链接 题意：鱼，一些鱼认为自己是汉子，然后他会去和他认为是妹子的鱼啪啪啪，然后被啪啪啪的妹子就会产卵？ 卵的val是它parent的val的异或。给出n，为鱼的数量，然后给出一个n*n的 mat,a[i][j]==1表示第i条鱼认为第j条鱼是妹子。问卵的最大val之和是多少。需要注意的是：每条鱼最多可以去和一个妹子啪，并且可以作为妹子被啪一次（这两个是独立的。。。） （Each fish can attack one other fish and can only be attacked once）

hdu 2426 题目链接 题意：n个学生，m个宿舍，每个学生住一个宿舍，然后n个学生给若干个宿舍打分，分数可正可0可负，学生不能住打的分为负的宿舍，或者没有打分的宿舍。问在满足上述条件的前提下，所有学生住的宿舍的分数之和最大是多少。如果无解输出-1.