Posts

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… 匈牙利算法学习链接

km算法我的理解 刷了不到20道题。。。回来总结一发。。

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最大。

hdu 3435题目链接 题意：给你一张图，图上可能有多个哈密顿回路。叫你求出形成多个哈密顿回路的总距离最小值

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.

hdu 1533 题目链接 题意：给出一个 n*m 的 maze，其中包含一些人（用 m 表示），以及和人数相等的房子（用 H 表示），其他都是‘.’，表示可以经过的路径。人向一个方向移动花费代价 1。问每个人都回到一个房子里的最小代价是多少。ps：每个格子是无限大的，也就是所有人可以同时踩在一个格子里。以及：路过一个房子可以不住，而只是“经过”。

hdu 2255 题目链接 题意：传说在遥远的地方有一个非常富裕的村落，有一天，村长决定进行制度改革：重新分配房子。 这可是一件大事，关系到人民的住房问题啊。村里共有 n 间房间，刚好有 n 家老百姓，考虑到每家都要有房住（如果有老百姓没房子住的话，容易引起不安定因素），每家必须分配到一间房子且只能得到一间房子。 另一方面，村长和另外的村领导希望得到最大的效益，这样村里的机构才会有钱。由于老百姓都比较富裕，他们都能对每一间房子在他们的经济范围内出一定的价格，比如有 3 间房子，一家老百姓可以对第一间出 10 万，对第 2 间出 2 万，对第 3 间出 20 万。（当然是在他们的经济范围内）现在这个问题就是村领导怎样分配房子才能使收入最大。（村民即使有钱购买一间房子但不一定能买到，要看村领导分配的）。

poj 3041题目链接 题意：一个nn的网格中，有k个大小为11的小行星，现在可以用激光枪每次消灭一行的小行星或者消灭一列的小行星。问最少需要使用多少次激光枪消灭所有的小行星。