在一个由n x m个正方形格子组成的的矩形上画一条这矩形的对角线，这线段将穿过多少个格子？_词汇网
在一个由n x m个正方形格子组成的的矩形上画一条这矩形的对角线，这线段将穿过多少个格子？
责任编辑：词汇网 发表时间： 15:31:54
比如在n等于m时显然对角线上有n个格子，问题是在不相等时对角线上会有多少个格子？【以下解答】为什么像我这种从来不回答问题，也从来只看抖机灵答案，把词汇当段子集看的低逼格值账号，居然会被人在这么正经的问题里邀请？词汇的推荐邀请算法是不是出了什么问题？好吧姑且高中也是拿过奥数全国奖项的，依稀还有点记忆，我来试着解答一下，如果答错了请偷偷告诉我，我再来想个不那么丢脸的方式偷偷把回答删掉。首先从m、n互质的情况开始讨论，结论是m+n-1个格子。证明如下：因为m、n互质，除了起点和终点外，对角线不会穿过格点。而对角线在起点和终点间必然穿过m-1条竖线和n-1条横线，这将各产生m-1和n-1个交点，因为其中没有格点，也即交点没有重复，所以交点总数为m-1+n-1=m+n-2个，它们把整条对角线分成m+n-1段。显然每一段对应对角线穿过的一个格子，从而对角线穿过的格子数也为m+n-1。接着来看m、n不互质的情况，假定它们的最大公约数为k，显然k>1且m/k、n/k互质。根据上面的结果我们有m/k x n/k的矩形对角线将穿过m/k+n/k-1个格子。而m x n的矩形对角线将穿过k个m/k x n/k的矩形，也即(m/k+n/k-1)k=m+n-k个格子。考虑到互质的两数最大公约数为1，最后的结论是m+n-k个格子，其中k为m、n的最大公约数。题主的m=n情况是一个特例，此时m=n=k，从而m+n-k=m=n=k。【以下解答】占个坑 考虑m n 互质时候即可而互质的时候对应的格子数是m+n-1【以下解答】手机ppi:每英寸的像素点数。计算公式为两边像素数的平方和再开根号得到"像素数"。用手机尺寸(英寸)除"像素数"得到的就是ppi。明显的对角线上的像素并不等于"像素数"。其实是任一边的英寸除那边上的像素数量才是正确的ppi.解决了我心中疑问:到底ppi是量对角还是边的问题。
上一集:没有了 下一集:
相关文章：
最新添加资讯
24小时热门资讯
附近好友搜索04 2013 档案
摘要: 训练的题目模拟题，蛇形矩阵，保证是n*n的矩阵，并且n是奇数 ， 在矩阵中填数，从最中心开始填，逆时针转圈，1,2,3…………n*n。输入n，表示矩阵的大小，输入一个数字m，找出m在矩阵的哪行哪列其实这个蛇形矩阵可以分为一圈一圈来看，要找m，可以先确定它在哪一圈每一圈都值的范围是 [ k^2+1 , (k+2)*(k+2) ] ，其中k是奇数看一圈的四个角，右上角最大： max = (k+2)*(k+2)左上角次之： max - (k+2) + 1左下角再次： max - 2*(k+2) + 2右下角 ： max - 3*(k+2) + 3所以可以以这4个值作为一个范围，将这个圈分成4份，..
Titanium 阅读(88) |
摘要: 训练的题目最大流题意：题意直白，就是一个网格从（0,0）编号到（N-1，M-1），每个点可以走到和它相连的4个点，没条边都有容量，为你从（0,0）到（N-1，M-1）的最大流1.建图细心一点不要出错，注意检查2.无向图，本来建的是无向图，无端端注释掉一部分，WA了一次才想起来怎么注释掉了，改回来过了3.建图后，直接上最大流模板，这里用EK#include &cstdio&#include &cstring&#include &algorithm&#include &queue&#define N 10100
Titanium 阅读(63) |
摘要: 训练的题目最短路变形题意：这个题意，太长了，总结回来只有两三句话。输入n表示n个点，从0到n-1，输入m表示m条无向边，输入t，表示终点。要你求起点0到终点t的最短路，不过要先满足一个条件，就是路径的点数不超过10个（包括起点和终点在内 &= 10），如果在10个点内娶不到或者图根本不连通，那么输出no，否则输出最短路又是一个加了限制的最短路，是要先满足10个点以内再求最短路的，训练的时候就是看错了一直WA。这题和 poj 1724 ROADS 是一样的题目。可以看作每条边的花费是1点数，你从0出发，手上有9点数，在点数够用的情况下走到终点t的最短路因此仿照poj这题的代码，写了一个dp
Titanium 阅读(69) |
摘要: 差束约分有人将这题归为最短路的中等题，所以做一下，但是发现其实是裸的差束约分题意：n个人，m个信息，每行的信息是3个数字，A,B,C，表示B比A多出来的糖果不超过C个，问你，n号人最多比1号人多几个糖果m行信息，所以得到m个不等式 ： XB - XA &= C , 所有不等式加起来就是一个差束约分系统对应最短路模型，一开始是 d[v] &= d[u]+w (有向边u---&v) ， 在进行完最短路后则变为 d[v] &= d[u] + w ，转化为 d[v] - d[u] &= w这个和上面的 XB - XA &= C 是相同的模式 ， 因此建图的时候有向边
Titanium 阅读(559) |
摘要: 最短路变形题意：你有K个点数，有N个点，M条边，边为有向边，包含4个信息，两个端点+边长+走这条边需要付出的点数。你的任务是，从1号点出发走到n号点，在点数够用的情况下，走出一条最短路，单case显然是一个最短路的变形，而且是一种常见的模型。最短路本身是一个求解最优解的问题，在这里加多了一个限制条件，就是点数，所以变为“在一定的限制条件下求解一个最优化问题”的模型，这样的模型，可以由一个大致的套路，就是，在满足限制条件后，再进行更新下面将讲3个方法，前两个其实都是BFS，第3个事DFS，是一个记忆化搜索。我们先说BFS1.优先队列+dij（最快） 判断一个元素能否入队，不再是看它的最短路估计值
Titanium 阅读(1740) |
摘要: 地址：/contest/200/problem/C模拟题题意：模拟足球小组赛的排名变化。规定只有4个球队，我方球队为BERLAND，一定会有的，然后另外3个球队的名字不一定。4个球队，两两球队间打且仅打一场比赛（所以可以知道一共是打了6场）。输入中给出5行，即5场比赛的信息，还剩下一场的信息没有给出。保证最后一场一定是BERLAND打某个队的，对手是谁要找出来（这个不难），而且也规定这场比赛一定是BERLAND胜利。你的任务是，要令BERLAND在这场比赛后，排在第1名或第2名，满足这个条件下，这场比赛的净胜球数最少，如果净胜球数一样，要令对方的进球数
Titanium 阅读(128) |
摘要: 隐式图搜索训练的题目，题意：输入n表示串（串为基因，只会出现ACGT）的长度，下面两行长度为n的串，第一个为起始串，第二个为目标串。对串能做两种操作。1.将头元素移动到尾部。2.最前面两个元素交换位置。从起始串到目标串的最少操作次数是多少，输出这题一看，觉得是DP，后来发了两三分钟的样子想到了是搜索。对于当前的串，它是一个状态，通过两个操作，能产生两个新的状态，所以这个过程就可以建图，搜索，找出两点间的最短路。注意这里不是树，因为很容易想到，这个图是可以有环的。另外，可以大致计算到状态数是很多的（串长最大为12），所以不能显式建图，当然也没必要显式建图，因为很多点（状态）是不会去到的很快打出代
Titanium 阅读(128) |
摘要: 概率题题意：输入case数，每组case两个数字，表示A的点数和B的点数，他们玩游戏，每个人赢的概率都是0.5。输的人要将自己的一部分点数给对方，给的点数是min(na,nb)。例如na=3，nb=2如果A赢了，B要给2点给A，即全部给完。如果B赢了，A要给2点给B，A变为1，B变为4。一个人的点数为0，那么游戏结束了。题目要你输出两个数学期望，第一个是，这个游戏要结束，要玩多少局的数学期望，另一个是A赢的概率这题一开始看觉得是期望DP，后来想想也可以不写DP，能把状态表达出来即可。设一个状态（n，m，c）表示A现在的点数是n，B的点数是m，已经玩了c局。那么游戏结束的状态就是（n,0,c）或
Titanium 阅读(122) |
摘要: 继续复习暴力给出n个点的坐标，选出最多的点，在一条直线上直接暴力，不过时间比较糟糕。一个二重循环，枚举i，j两个点，这两点确定一条直线，然后枚举剩下的点看是否在这条直线上，所以一个三重循环，时间复杂度O(n^3)注意枚举不要做重复的工作，否则会超时另外这题是有O(n^2logn)的算法的#include &cstdio&#include &cstring&#include &cmath&#include &algorithm&#define N 710#define LEN 110struct
Titanium 阅读(203) |
摘要: 继续复习暴力题意：输入有点恶心，首先是case数，然后一个空行，然后再输入信息，然后又以一个空行结束该组数据，如果是最后一组数据了，不以空行结束，而是直接以EOF结束。输出，case之间有一个空行，最后一个case后面不要加空行每组case的信息，就是N行的串，串中只有01，串的个数一定是偶数。原本有很多个一样的长串，每个长串都分成了两个短串但是分割的位置不一定相同即两个短串不一定是平分的（就是输入中的那些串）。你要把这偶数个短串拼回那个长串（即2N个短串拼回N个相同的长串），如果有多种可能，任意一种即可，然后输出这个长串题目保证一定有有解的数据不大，144，直接暴力。首先按短串的长度升序排序
Titanium 阅读(530) |
摘要: 继续复习基础算法题意，给n个数字，将它们重新排序得到一个最大的数字，好像给出123 456 789 拼为
最大这题可以算是一个排序题，不过排序的规则有讲究如果想用字典序排序，显然错了，好像 ， 按字典序排序999123在前面，得到的数字为 ， 显然没有不够 大有两种不同的思想解这题1.处理前缀的问题，上面那个例子，999是999123的前缀，这种比较不能简单以字典序比较，而是应该用一种“环”的思想去比较，即999比完了，A串到了1，B串应该轮回来变为9，。也就是A串和B串都已这种环的方式去计较，知道第一个不相同的字符出
Titanium 阅读(1024) |
摘要: 哈希题意简短：单case，输入一列单词即一个字典，已经按字典序排好输入，上限为120000，然后要你找一些单词，这种单词可以分为两部分，两部分都是字典里面的单词，按字典序输出这种单词很裸的哈希，对于每个单词，将其分成两部分，一共有len中分法，然后去查找是否都在字典中，如果都在字典中就输出（因为输入已经按字典序排好，扫描时直接扫下来就可以了，找到合适的就输出）问题的关键就转变为，给你一个单词，怎么判断这个单词是不是在字典中，用哈希就可以快速判断到。输入时随便将每个单词都用哈希函数映射掉，每得到要查询的单词也直接映射过去查找处理冲突的方法是链表（静态链表数组模拟）用了BKDHash函数在处理字符
Titanium 阅读(538) |
摘要: 原文地址 ：/blog/string-hash-compare常用的字符串Hash函数还有ELFHash，APHash等等，都是十分简单有效的方法。这些函数使用位运算使得每一个字符都对最后的函数值产生影响。另外还有以MD5和SHA1为代表的杂凑函数，这些函数几乎不可能找到碰撞。常用字符串哈希函数有BKDRHash，APHash，DJBHash，JSHash，RSHash，SDBMHash，PJWHash，ELFHash等等。对于以上几种哈希函数，我对其进行了一个小小的评测。Hash函数数据1数据2数据3数据4数据1得分数据2得分数据3得分数据4得分平均
Titanium 阅读(68) |
摘要: 复习一下基础DP，记忆化搜索题意：给一个名字，和n*m矩阵，下面是矩阵信息，每次在一个格子，可以向上下左右移动，但是要求那个数字比当前所在格子数字小。可以从任意点出发，问最长的距离是多少dp[i][j]表示从（i，j）出发能走的最长路dp[i][j] = max{ dp[x][y] } + 1 , 其中（x，y）是（i，j）附近的四个格子之一并且a[x][y] & a[i][j]#include &cstdio&#include &cstring&#define N 110#define MAX 110#define max(a,b) ((a)&(b)?(a
Titanium 阅读(203) |
摘要: poj 2168 相同的题目区间DP题意：输入n，表示有n个海龟在一条直线上，乌龟可以站在相同的位置（即坐标可以相同），下面n行，每行两个数字，表示第i个乌龟给出的信息，第一个数字表示它前面有多少只乌龟，第二个数字表示它后面有多少个乌龟。并不是每个乌龟的信息都是正确，有些乌龟的信息是假的，或者和别的乌龟信息冲突，你的任务是选出尽量多的乌龟，使他们的信息不冲突，然后输出有多少个乌龟说谎，和那些乌龟的编号，可能有多种情况，只要保证说谎的乌龟数最少，输出哪种情况都可以分析：乌龟可以站在一样的位置，我们给乌龟排名，可以把它们放在不同的位置 例如 1 2 3 3 3 4 4 5 ， 虽然有些排名相同，但
Titanium 阅读(189) |
摘要: 数据结构--二叉查找树遍历题意：n，表示二叉查找树的节点个数，每个节点有个数值，并且数值各异不会出现重复的，查找树左子树的节点数值小于根，右子树的节点数值大于根。 一般的后序遍历二叉树时 左孩子，右孩子，根 ； 现在定义一种新的后序遍历 右孩子，左孩子，根 输入n，下面一个序列，是普通后序遍历二叉树的序列 ， 要你根据这个序列，输出新定义的那种后序遍历序列 讲到这里，看图，看sample可以理解题意了要是一般的二叉树只知道后序遍历序列是不能建树的，但是这里是二叉查找树却可以对于一个后序遍历序列，它可以分解为 （左子树部分）（右子树部分）（根），由于是查找树，可知（左子树）&（...
Titanium 阅读(148) |
摘要: 找规律约瑟夫环问题变形。在这个约瑟夫环问题中，固定每次间隔两人，10个人，杀人顺序为2,4,6,8,10,3,7，1,9，最后剩下5定义一种运算J^m(n) 表示 m次嵌套 J( J( J(n) )好像J^2(10) = J(J(10)) = J(5) = 3而m和n的最大值是 10^9这个问题 主要是能快速算出 J（n），不难想到如果能算出J（n），可以暴力地一步一步迭代下去做m次，容容易发现不用做m次，因为J(1) = 1，当n降到1的时候，m再大都没意义了可以发现这个问题是指数递减的，m&=10^9 是个纸老虎同样地可以打表看看J（n）的值，一看就能看到规律对于一个范围的n ， [
Titanium 阅读(64) |
摘要: 数论+打表A的所有因子和位B，B的所有的因子和为A，则称{A,B}是一对ooxx number输入数字n，求出[1,n]里面有多少对ooxx number，其中（A,B），(B,A)这样算作一对n最大为5百万（）hits 220= （1+2+4+71+142） &--- 284,284= (1+2+4+5+10+11+20+22+44+55+110) &--- 220。220 and 280 is a pair of ooxx numberssample input3001300sample output12定义sum[i]=i的因子和，用筛法来构建i枚举因子i..
Titanium 阅读(100) |
摘要: 线段树题意：有一个长H宽W的板，上面贴纸条，纸条都是长1宽w的，贴纸条的原则是，不能覆盖或重叠别人的纸条，尽量往上贴，进而尽量往左贴第一行3个数字，H,W,N，N表示有N个纸条，下面n行每行一个数字，表示每个纸条的宽，每个输入对应一个输出，就是这个纸条放在哪一行，如果没地方放它就输出-1数据很大，不过是纸老虎，因为H=min(H,N),这个很容易理解，行数多了也用不上。/*h=min(h,Q);线段树区间长度为h，每个叶子a[i]表示第i行剩下的长度，一开始都是w对于每个询问，我们其实是将长度为l的长条放入一行呢，即对应放到a数组的一位里，要满足a[i]&=l，并且最靠左所以问题转化为在
Titanium 阅读(73) |
摘要: 暴力训练的题目，给出一个数字（最长1000位即10^1000），给出m表示交换次数（每次可以交换任意两位的数字），问交换后得到的最小数字。注意，数字不能有前导0，另外有m次交换机会，但不必全部用完，只要交换到最小数字了就可以退出为了得到最小数字，就是从高位开始，不断找最小的数字放到高位（但第一位要特殊处理不能为0）。如果现在使第i位最小，从第i到最后一位扫描找到最小值然后交换然后交换次数减1，如果刚好第i位就是最小值，则不交换，直接跳过，所以交换次数不能减1。如果m&len，即大于数字的位数，那么显然后面的交换机会都是多余的，最多交换len次就可以退出了所以结束枚举的条件是，以为枚举了全
Titanium 阅读(187) |
摘要: 计算几何训练的题目，给出n个点的坐标（整数），选3个点组成三角形问能形成多少个锐角三角形直接暴力解决，用三个for循环枚举3个点（升序枚举避免重复），然后用余弦判断三角形中三个角是否为锐角判断一个角为锐角：已知j，i，k三个点形成一个角，以i为交点向j，k做两个向量a，b，用余弦定理cos = a*b/( |a| * |b| ) ，因为|a|*|b|必为正整数而且我们不是要算确切的角度只是判断锐，直，钝角所以直接用 a*ba*b=0 ， 直角a*b&0 , 锐角或0度a*b&0,钝角或180度所以不用单纯靠 a*b 的正负来判断是什么叫，对于a*b&0的情况还要判断是否为0度
Titanium 阅读(109) |
摘要: 线段树求面积并升级版题意中文，不解释这题的代码在一般的线段树求面积并的基础上进行了修改，但是所用的思想是一样的，所以不难理解回忆一下一般的求矩形覆盖面积，线段树节点里面有一个重要的变量，cnt。这个变量表示了该节点表示的区间被完全覆盖，如果cnt=0，说明没有被完全覆盖（但不代表没有被覆盖），要算出该节点所代表的区间被覆盖的长度，需要由它左右孩子节点被覆盖的长度相加所得。如果cnt=1，表示被完全覆盖，覆盖长度就是该区间长度。如果cnt&1说明也是被完全覆盖，不过不止覆盖了一次，在算覆盖长度的时候，和cnt=1的计算方法是一样的。注意一点，节点里还有另一个变量len，就是该区间被覆盖的长
Titanium 阅读(1375) |
摘要: 找规律题同样是训练的题目题目：给出n，得到一个n*n的方阵，n保证为奇数，从第1行最中间的位置开始填1，然后以某种规则一直填数，每次填2,3,4,5……直到n*n。填充规则是每次把下一个数填在现在位置的右上方（即上移一格再右移一格），如果另外把这个方阵看做一个环，如果现在位于第一行，上移一格其实移到了最底那行，如果现在位于最右边那列，右移一格就是移到了最左边那列，同样的，如果刚好位于右上角，移动后就在左下角了；另一部分，在移动到右上方的时候，如果右上方已经被填充了，那么就不能向右上移动，而是向下移动，然后再继续向右上移动，画个图便知最后要求，右下角那个位置填的数字时多少这题的规律还是不难找到答
Titanium 阅读(131) |
摘要: 图论今天训练的题目，题意：有一些工作要做必须等某些工作做完了才能开始，每个工作也要花费时间去做。输入先给出n，m，表示有n个工作，要求完成第m个工作的最短时间（工作从1到n标号），下面n行给出每个工作的信息，每行第一个数表示做这个工作要多少时间，后面可能有1个或多个或0个数字，表示这个工作要在这些工作做完后才能动工。另外注意一点，同一个时刻只能做一个人工作，不能同时进行多个工作这题一开始看错，以为又是关键路径，敲了模板发现wa，才看到那句话，同一个时间只能做一个工作不能同时进行多个工作，因为这个条件，这道题可以说和关键路径就毫无关系了。后来想不出方法，在队友的提醒下想到了正解。其实我们只要知道
Titanium 阅读(142) |
摘要: 两种方法详细分析：线段树辅助——扫描线法计算矩形周长并（轮廓线）第一种，对横线和竖线做相同的操作/*对横线和竖线做两次一样的操作这题不需要离散化*/#include &cstdio&#include &cstring&#include &algorithm&#define N 5010#define MAX 10010#define lch(i) ((i)&&1)#define rch(i) ((i)&&1|1)struct segment{ int l,r,h,v;}sx[2*
Titanium 阅读(776) |
摘要: 例题：hdu 1828 Picture有两种方法，不过常用的第二种，两种都说一下。第一种：把矩形分成横线和竖线去处理，可知是完全相同的操作，我们来讲下怎么算出横线部分，竖线部分就是照搬即可。将横线保存在一个表中，按横线所处的竖直位置排序（升序），另外每条横线带一个标记值，原矩形的下线为1，上线为-1（对应过去就是插入线段和删除线段）从低到高扫描横线,没扫到一条横线就能计算出一部分横线值。计算方法是算出现在总区间的被覆盖的长度，然后求出与上一次的总区间的覆盖长度的差（即相减求绝对值），因为每次添加了一条线段，如果没有没有使总区间覆盖长度发生变化，说明这条线段其实在多边形的内部，被覆盖掉了，不能计
Titanium 阅读(1488) |
摘要: 分析:1.矩形比较多，坐标也很大，所以横坐标需要离散化（纵坐标不需要），熟悉离散化后这个步骤不难，所以这里不详细讲解了，不明白的还请百度2.重点：扫描线法：假想有一条扫描线，从左往右（从右往左），或者从下往上（从上往下）扫描过整个多边形（或者说畸形。。多个矩形叠加后的那个图形）。如果是竖直方向上扫描，则是离散化横坐标，如果是水平方向上扫描，则是离散化纵坐标。下面的分析都是离散化横坐标的，并且从下往上扫描的。 扫描之前还需要做一个工作，就是保存好所有矩形的上下边，并且按照它们所处的高度进行排序，另外如果是上边我们给他一个值-1，下边给他一个值1，我们用一个结构体来保存所有的上下边struct s
Titanium 阅读(5978) |
摘要: 找规律题？YY题？题意：给出一条线的长度L（直线在[0,L])，和蚂蚁数，下面m个数字表示m个蚂蚁的起始位置(整数，坐标)，所有蚂蚁向哪边走不确定，但是两个蚂蚁相撞会掉头走。蚂蚁的速度1cm/s，蚂蚁没有长度是一个点，另外蚂蚁走到直线的两个尽头就会掉下去。问怎么走，所有蚂蚁最快掉下去，输出时间（所有蚂蚁都掉下去后再输出时间而不是第一个掉下去就输出），然后怎么走最晚掉下去，输出所有蚂蚁都掉下去的时间这题真想不到什么算法，不过可以确定一些基本的策略1.最快掉下去：以中点为轴，位于两端的蚂蚁都向两端走，这样他们不会发生任何的碰头，直接全部掉下去，那么最后掉下去的蚂蚁，是离中点最近的蚂蚁，它是最后掉下
Titanium 阅读(277) |
摘要: 数据结构：暴力（可用哈希优化）+建树+前序遍历题意：输入行数n，下面n行是一下文件的路径（和平常使用的电脑一样），一整行数据中没有空格（还好，别有搞些空格出来），要你整理好所有文件的路径，从根开始，输出所有的文件夹名首先一点，我们要名字，在同一个文件夹下，是不会有重名的文件夹的即a\ba\b这种是非法的（和电脑一样），但是输入中可以有，有的话只是一种重复输入，不是代表a下面真的有两个b然后不同文件夹下可以由相同的名字，就好比你D盘和E盘都有一个文件夹叫“电影”例如a\bd\b这种是合法的在输入中也是会出现的，看case就知道。另外，每个文件夹都只有一个双亲好像a\b\c\d , 你要找d，输入
Titanium 阅读(151) |
摘要: 简单树型DP题意：一个图，N个点，N-1条边，并且说明是树（一棵树，连森林都排除掉了）。在这颗树中删除一个点rt以及和他关联的边，那么剩下的部分将会是森林，统计森林中每棵树的节点数，最大值记录下来为dp[rt]，你的任务是找出最小的dp[rt]，如果有多个rt相等，那么按升序输出所有rt的编号一个最大值最小的问题，解法是求出所有的dp[rt]然后记录最小值因为本来是一棵树，用哪个做顶点都可以，默认为1，为整个树的祖先。定义sum[rt] = 以rt为根的子树含有的节点数 dp[rt] =dp[rt]：除去rt后，各个分块中节点数的最大值 ans = min{ dp[rt] }; 删掉rt...
Titanium 阅读(149) |
摘要: 树DP题意：输入n和m，表示n个城市，m条无向边，下面一行n个数字，表示每个城市的权值，下面m行是每条边的信息，u，v，w，顶点和边权。问你从一个城市出发，走出一条路线，使得权值和最大，权值和包括这条路线上城市的权值和边的权值和。题中有一句话出卖了它是个树DP：It turned out that if Petrovich can fly (using one or several flights) from townito townj, then there is exactly one way to do this.从一个顶点去另一个顶点如果连通的话只有一条路径，说明这个无向图其实是个无根
Titanium 阅读(95) |
摘要: http://www.cqoi.net:2012/JudgeOnline/problem.php?id=1380题意什么的都在里面，中文题目不用解释个人感觉是数据的问题，因为网上找遍了代码都不能通过，算了还是不纠结了代码写得也不好，无心机改了/*dp思想:dp[rt][p]，当前节点rt，有p点，能获得的最大价值1.可以用一部分来升级当前的这个技能，升的级数不确定，但升级需要花费点数，花费的点数 c&=p2.不升级当前,全部用于升级子树和兄弟。但注意，若不升级当前节点而且当前节点等级是0，那么 其子树不能升级，只能升级其兄弟*/#include &cstdio&#includ
Titanium 阅读(96) |
摘要: 树DP经典问题，公司聚会，下属和直属上司不能共存，给出每个人的快乐值，再给出每个人的编号和他的上司，选出一些人参加聚会使快乐值最大/*从叶子开始选择，每个节点只有选不和不选两种可能，dp[rt][0],dp[rt][1]分别表示选和不选该节点dp[rt][1]=sum{ dp[son][0] }+val[rt] , 因为跟选了它的儿子就全部不能选dp[rt][0]=sum{ max{dp[son][0] , dp[son][1]} }如果根不选，那么儿子的选择就多样化了，每个儿子又是互不干扰的所以令每个儿子最优，加起来根就是最优的，而每个孩子无非还是选和不选，一比较就能得到每个儿子的最优方案而
Titanium 阅读(124) |
摘要: 提交地址：http://www.cqoi.net:2012/JudgeOnline/problem.php?id=1709问题描述如果一个数x的约数和（不包括它本身，下同）比它本身小，那么x可以变成它的约数和；如果对于某个y&x且y的约数和为x，那么x也可以变成y。例如，4可以变为3，1可以变为7。限定所有的数字变换在不超过n的正整数范围内进行，求不断进行数字变换且没有重复数字出现的最多变换步数。输入数据 输入一个正整数n。输出数据 输出最少需要花费的时间。 （这里原题应该打错了，应该是输出最大转换步数）样例说明 一种方案为：4→3→1→7。时间限制 各测试点1秒内存限制 你的程序将..
Titanium 阅读(311) |
摘要: 树型DP这题刘汝佳居然归在数学题里面，他的用意应该是想归在递推的，但是这题更应该属于一个经典树DP题意：给一个图，两个点间不会有重边，边时双向连通的，另外注意这句话，there is only one route from a village to a village that does not pass through some other village twice.这句话说明了，这个图是很特殊的，其实是一个无根树。要求的是，找出两点，他们的距离最远有两种思路，但是本质还是一样的，写法不同，推荐后面那种第一种:/*思考方法：这个图的本质是个无根树，所以我们指点任意一个节点为树根即可，因而指
Titanium 阅读(193) |
摘要: 提交地址：http://www.cqoi.net:2012/JudgeOnline/problem.php?id=1286这题是OI的经典题，不难，注意一点，原题是用文件输入输出的，但是这里的提交直接标准输入输出即可这题的题意很清晰，明说了是二叉树（而且只能在两个孩子的节点和叶子节点）。注意输入给出的信息，对于一对数据，a，b，a指通过走廊的时间，那是不是树中边的信息呢？不是的，应该是点的信息。树中每一个点都应该包含两个信息，就是时间花费和它有多少张画，对于非叶子节点而言，它的画数都是0，而时间是有的，对于叶子节点，除了有画数外，它也是有时间花费的另外，本题读题要仔细，它是说在警察来之前就要离
Titanium 阅读(259) |
摘要: 数据结构：堆题目请你写一个内存管理系统。 内存中有30000个块，编号为1..30000。 当操作系统需要内存时内存管理系统会找出编号最小的空闲块，向里面写入数据。 操作系统还会会发出指令读取某个编号的内存块。如果目标块空闲，读取失败，否则读取成功。 一开始所有块都是空闲块。被写入数据之后就不是空闲块了。 如果一个块在600秒内没有被写入或读取，这块内存自动清空，变为空闲块。 本题中不会出现内存块不够用的情况。输入格式每行一个要求，可能是申请内存或读取。申请内存的格式如下： T + T表示这条请求收到时的时间，是不大于65000的整数，以秒为单位。读取内存的格式如下： T . N T表示这条请
Titanium 阅读(123) |
摘要: 树状数组题意：一个树，以树枝连接两个点的形式给出，固定以1为整棵树的根。苹果长在树的节点上，节点上只可能0或1个苹果，一开始每个节点都有1个苹果有两种操作，C表示更改某个节点的苹果数，0变1,1变0。Q表示查询，某个节点（包括）的子树上一共有多少个苹果这题是选拔赛时候的题，一看，单点修改，区间查询？线段树？后来一直没想出来，今天看解题报告才明白真的是，不过是树状数组（不过按照理论来将，凡是树状数组能解决的问题，线段树都可以解决，反之不然）。整个问题最难的时候怎么映射成树状数组，映射后，只是树状数组的模板操作1.首先数据太大，不用显式建树，只是用vector来保存边的信息，仅仅是利用vector
Titanium 阅读(90) |
摘要: 树型DP：二叉苹果树另外一个提交地址：http://www.cqoi.net:2012/JudgeOnline/problem.php?id=1375里面有中文题目，不解释题目了。树型DP：主要是两点，怎么建树，怎么DP。这两者应该说是相互制约相互影响的，怎么DP就要怎么建树，而建树方法对不对也决定了你能不能DP。所以先分析怎么DP的，再分析怎么建树题意说要保留m个树枝，而且注意权值不是点的而是树枝的，这样子并不利于我们解决问题，我们可以转化一下，把权值转移给节点。首先给出所有边的信息后，我们的建树是唯一的（这个问题值得思考一下为什么，唯一是指不考虑左右孩子的位置，而只考虑从属关系，好像1（3
Titanium 阅读(210) |
摘要: 线段树题意：很明显的线段树。做了这题更加让我注意了用点和用段来建树的区别。这题是用点来表示线段的。一开始从0到10^9这个点之间的线段都是白色的，然后m个更新，每个更新 a，b，col，表示从点a到点b这条线段染成黑色或白色，问最后，白色线段中最长的是哪一段，输出它的位置（即线段两端的端点）注意更新的时候a，b的数值范围是 0&a&b&10^9 ， 其实这样给数据方便了处理，否则的话最后要搞一下挺烦的先看看用段和用点表示线段树的区别。用点的话，0,1，表示的长度是1。1,3表示的长度是2。而用段的话1,3表示的长度是3，就是这个意思线段树的建树，无论在何种情况下，应该说建树的
Titanium 阅读(262) |
摘要: 并查集题意：题意比较好懂简单说一下。一个序列，只有0，1；输入n，表示序列长度（从1到n标号），输入m，下面m个更新，每行都是a，b，string，表示说序列中下标a到下标b的元素中有偶数个或奇数个1.没得到一个更新就更新序列的信息，知道读入第k个信息，和已建立的信息矛盾，那么结束，输出k-1，表示前面k-1个更新不矛盾，如果m个更新都成立，那么输出m这题要转化一下，一转化就比较明显了。我们定义前缀和为sum[i]表示1到i的和，那么sum[b]-sum[a-1]=c[a]+c[a+1]+c[a+2]……c[b] ， 即序列的[a,b]区间和因为序列中只有0,1所以区间和的奇偶性就是该区间拥有
Titanium 阅读(305) |
摘要: 网络流UVA 1161 是相同的题目这题网上找不到任何题解的，看上去是个最大流，但是最难搞的就是有时间限制，现在基本上能确定的就是要拆点，但是怎么拆不确定，我用了这种拆法就一直超时超时的原因我总结一下有几个可能。1.构图的代码太烂，可能出了什么差错但是找不出来。2.数组开小了？开大了？3.和第1个原因，然后运行EK的时候掉进了死循环或者效率太慢。4.EK太慢，要用ISAP超时的代码/*原本的点从0到n-1标号，但是每个点需要占用2880个空间，所以对于原来第u个顶点，怎么确定那个范围是它可以用的就是[u*2880 , (u+1)*2880-1]如果读入了点u，时间为t而且它是作为到达时间，那么
Titanium 阅读(171) |}