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 …

题目链接 题意：n个人的上下级关系形成一棵树..每一个人有一个val（可正可负），要选若干个人参加一个party,要求是一个人和他的直接上级不能同时在场。问参加party的人最大的val之和。 思路：树形dp入门题。 dp[i][0]和dp[i][1]分别表示第i个人不参加和参加party对应的val和。 注意dp转移方程是放在每次dfs之后的回溯位置的。。。 这样做的话访问是从根节点到叶子节点，更新就成了从叶子节点到根节点。。。 联想到数字三角形...其实是一样的。。 sad...dp苦手如我也开始刷dp了吗。。。。 /* *********************************************** Author …

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

cf660C solution:ruler.1A /* *********************************************** Author :111qqz Created Time :2016年06月08日 星期三 23时43分18秒 File Name :code/cf/problem/660C.cpp ************************************************ */ #include <cstdio> #include <cstring> #include <iostream> #include <algorithm> …

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

学完了km..感觉匈牙利真是非常的。。easy... 匈牙利算法学习链接 有一种题目会用1*2的小格子填充大的，问能不能填满之类的，可以用匈牙利搞。hdu 4185解题报告 poj2446解题报告 其实主要是关于建图的启示，上面两个题，还有这道题： poj1325解题报告 还有就是一些有用的结论： **(1)二分图的最小顶点覆盖 ** 最小顶点覆盖要求用最少的点（X或Y中都行），让每条边都至少和其中一个点关联。 Knoig定理：二分图的最小顶点覆盖数等于二分图的最大匹配数。 (2)DAG图的最小路径覆盖 用尽量少的不相交简单路径覆盖有向无环图(DAG)G的所有顶点，这就是DAG图的最小路径覆盖问题。 结论：DAG …

km算法我的理解 刷了不到20道题。。。回来总结一发。。 如果题目求的是最小权值匹配，比较好的做法是将权值取取值，最后res再取负就好。需要注意的是初始化的时候w和lx要比所有值都小，所以要ms(lx,0xc0) 最正确解最小权匹配的办法是用一个很大的数-当前边权值，而不是直接对边权取反(这样只能处理左右点相等的完全二分图，即K(n, n)(bin神博客看到的) 有时候需要考虑无解的情况，一般如果有无解的情况，对应了存在lx[i]=初始化的值。 不少题目有一个点都是先用一种暴力或者不暴力的方法处理出w,然后裸的km hdu3722解题报告 有向图的覆盖可以对应二分图最佳匹配的模型，用km算法搞 hdu1853解题报告 遇到了一种题是 …

hdu 3523 题目链接 题意：有m个排列，每个排列有n个，然后要找一个长度为n的排列（1..n每个数字恰好出现一次），使得这个排列到其他m个排列的距离之和最小。 两个排列之间的距离是对应位置上数字差的绝对值的和。 思路：妈蛋，什么鬼题面。。。看不懂。。。然后看了题解。。。知道了题意。。 的的确确做过相当类似的一道呢。 先nnn的复杂度(1E6)处理权值，然后KM. 1A. /* *********************************************** Author :111qqz Created Time :2016年06月03日 星期五 19时34分36秒 File Name …

hdu3315 题目链接 题意：两个人分别各有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 …

hdu 2853题目链接 题意：n个公司，m个任务（m>=n),一个公司只能对应一个任务，一个任务也只能对应一个公司。给出一个n*m的mat,表示每个公司对应每个任务产生的val。 然后给出n个数，表示初始钦定（雾）这n个公司分别做哪些任务。 但是可能初始的安排得到的val表示最大的。我们现在想得到最大的val,并且保证改变的安排数最少。求安排后得到的 val比初始安排大多少，以及需要改变的安排数量。 思路：最大val很好求，KM就好。。。但是，怎么才能保证改变的安排数最少呢？ 尤其是当两个安排val一样的时候，如何才能保证优先选已经安排好的，而不取选另一个呢？ 并没有想出来，看了题解T T 太神辣。 由于KM算法会根据权值来 …