题目链接 d:题意：一棵树，给出边权和点权，定义点v控制点u，当且仅当u是v的子树中的点，并且dis(u,v)<=a[u]，其中dis(u,v)为点u到点v路径上的边权和，a[u]为点u的点权，现在问对于每个节点v，其能控制的点有多少个。 思路：先写了个rmq+dfs的lca。。。那么任意两个点的距离都可以O(1)得到了。然后不会了233333. upd:和lca没有什么关系，因为一个点能控制另一个点这两个点一定在一条通向根的链上，因此距离直接减一下就好了。 机智的做法：dfs的时候维护一个栈，对于栈中序列，后面一半是对当前点有贡献的。问题时求对于每个v统计其能控制多少个u，现在我们固定u，考虑能控制他的v。这些v在树上的形态 …

题目链接 题意： m个区间，要求构造一个长度为n的数组，满足m个区间中，每个区间的mex值中的最小值最大。 s思路：很容易想到的是...这个最大的mex 不可能超过每一组区间长度，假设最小的区间长度为mn 那么是否一定可以构造出mex为mn的数组呢？ 是的。 只需要按照 0,1,2...mn-1,0,1....的方式构造即可。 /* *********************************************** Author :111qqz Created Time :2016年11月24日 星期四 09时00分04秒 File Name :code/cf/#381/C.cpp …

题目链接 题意： 地主小花有n座山，这些山在地主家门前排成一条直线。这些山一开始均有相同的高度。 每一天，小花都会要求ZJiaQ开挖机把几座山挖掉一定高度，或者给一些山堆上一些高度。并且要求报告ZJiaQ报告现在有多少座山属于“高山脉” 当一排山的高度相等，并且比这排山左边和右边的山要高时，这排山被称为高山脉。 当然，最左边和最右边的山不可能是“高山脉”的一部分 思路：线段树，要维护的域蛮多的。 下面高山脉简称"HM" sum:区间中HM的总长度。 lsum,rsum,区间中包含左端点，右端点的高度相同的山的长度。 lh,rh：区间中包含左端点，包含右端点的的高度相同的山的高度。 llh,rrh:从左端点向右， …

题目链接 题意：长度为n的序列，单点更新，或者询问某一个区间中最长连续严格递增序列的长度是多少。（此处的连续为位置连续，并非数值连续，也就是3,5,7,9，这样的就是满足题意的长度为4的序列） 思路：线段树区间合并。维护三个域。 mx:区间中最长连续严格递增序列的长度 lm:包含区间左端点的最长连续严格递增序列的长度。 rm:包含区间右端点的最长连续严格递增序列的长度。 PushUp的时候，一个区间的答案显然可以从左右两个子区间的最大值得到。 还有一种可能是左右区间各取一部分，此时必须满足左区间的右端点值严格小于右区间的左端点值。 需要注意的是，如果某区间的最长连续严格递增子序列的长度等于区间长度，那么该区间可以向相应方向延伸。 查 …

http://codeforces.com/contest/740 A:现在有n个某种物品，要买k个使得n+k是4的倍数，可以的购买方案为a元1个，b元2个，c元3个，每种方案都可以买无限多。 思路：需要注意买多个未必比买少个贵.. 所以分情况讨论：n%4==0，输出0 n%4==1，需要买3+4k个， 可以的方案为，买1个c，或者3个a，或者1个a 1个b（此处用价钱指代方案，下同） n%4==2时，需要买2+4k个 可以的方案为：2个a，或者1个b，或者2个c n%4==3时，需要买4K+1个 可以的方案为：1个a,或者1个b+1个c，或者3个c 注意要开long long. /* …

题目链接 题意：给出n（n<=1E3）个不同的点，问最多组成多少个平行四边形。 思路：这道题的关键是，对于平行四边形的判断条件，要利用平行四边形对角线的交点平分两条对角线的性质。 也就是说，如果两条线段的对角线重合，那么一定可以组成一个平行四边形。 因此统计中点的位置即可，复杂度nnlg(n*n) /* *********************************************** Author :111qqz Created Time :2016年11月22日 星期二 22时43分26秒 File Name :code/poj/1971.cpp …

题目链接 题意：一个字符串，其仅由nc种字符组成，问其所有长度为n的字串里，共用多少种不同的。 思路：一开始木有懂nc种字符有什么用... 然后写了hash，发现会TLE。。。因为用到了map，被卡了个log.. nc的作用是，可以把字符串看成一个nc进制的数，这样做的好处是，得到的hash值可以尽可能的小而且保证了不同的字符串对应了不同的hash值。 然后就可以不用map而是一个数组，就变成了O(1)赋值和判断了。。。 （然而没有数据范围其实还是有点耍流氓的嫌疑。。 #include <iostream> #include <cstring> #include <stdio.h> using …

题目链接 题意：n个人，每个人有一个level值，用一个最长30位的，可能带前缀0的数字串表示，如果i的level大于j的level，那么i可以教j飞行，每个人只能有一个老师，每个人也只能收一个徒弟。师生可以共用一把扫帚飞行。现在问最少需要多少扫帚。 思路：分析发现，影响扫帚多少的是相等的数有多少，因为只要不相等，就肯定可以构成师生关系.... 更确切得说，是所有数出现次数的最大值。 有一个trick点，就是带前缀0和不带前缀0的两个level被认为是相等的，hash的时候要处理前缀0. /* *********************************************** Author :111qqz Created …

题目链接 题意：网站的注册系统..处理用户要注册的用户名，如果数据库中没有重名输出OK，否则输出要注册的用户名的字符串+num,num的大小为之前一共有多少个用户试图用该用户名。 思路：hash一下。。。 /* *********************************************** Author :111qqz Created Time :2016年11月22日 星期二 19时00分58秒 File Name :code/cf/problem/4C.cpp ************************************************ */ #include <cstdio> …

题目链接 题意：给定一个两种语言的对照关系表...给出后一种语言中的单词，问对应的前一种语言的单词是什么。。。 思路：hash一下然后map存一下即可。。。。读入方式由于单词表和查询是根据空行分开的。。那么读入不能用scanf(因为会跳过空行），要用gets。。。然后再sscanf一下。。。 /* *********************************************** Author :111qqz Created Time :2016年11月20日 星期日 11时13分29秒 File Name :code/poj/2503.cpp …