题目链接 题意： 一棵树，给出点权，问一条树链上第k大的点权，点权可以动态修改。 思路： 暴力即可orz(数据是真的水啊。 求路径上的点的时候需要用到LCA /* *********************************************** Author :111qqz Created Time :2017年07月31日 星期一 01时12分54秒 File Name :3078.cpp ************************************************ */ #include <cstdio> #include <cstring> #include …

题目链接 题意： 给出一棵树，以及三个点（可能重合），问两两组成的3条路径中，哪2条路径重合部分最长。 思路： LCA还是一下就能想到的，rmq+dfs在线求。 然后我开始分情况讨论，讨论了一年也没讨论完，哭哭 结论是：求出三个lca，并取深度最大的那个，就是我们要的三岔路口K，然后分别求出K到a，b，c三点的路径长度，取最大值+1就是答案。 所以我的问题在于，没有试图往一般性的方向考虑，以为讨论一下就可以了... 这大概就是所谓的猜结论？ 感性的理解的话，LCA越深，意味着另一个点到LCA的距离越远，也就是相交的路径越长 但是我的话，估计还是很难在短短不到一个小时内得出这样一般性的结论orz... 这大概就是数学方面的天赋差距 …

Given a set of candidate numbers (C) (without duplicates) and a target number (T), find all unique combinations in C where the candidate numbers sums to T. The same repeated number may be chosen from C unlimited number of times. Note: * All numbers (including target) will be positive integers. * The solution set must …

Given a 2D board and a word, find if the word exists in the grid. The word can be constructed from letters of sequentially adjacent cell, where "adjacent" cells are those horizontally or vertically neighboring. The same letter cell may not be used more than once. 思路：dfs即可。记得要回溯一下... /* …

题目链接 题意：nm个格子，有和.两种类型。定义一个湖为边相邻的只有.组成的最大点集合，且任何一个.不在边界上。现在给出一个nm的图保证至少有k个湖。问填多少个.成，才能使得恰好有k个湖。 思路：贪心，先处理出所有的湖的大小，然后从小往大填。 注意dfs的时候如果某个“可能”的湖遇到了边界，要把之前打的标记撤销掉。 /* *********************************************** Author :111qqz Created Time :2016年10月03日 星期一 21时18分03秒 File Name :code/cf/#375/D.cpp …

题目链接 题意：求约数个数恰好为n个的最小的x 思路：这道题是作为反素数的例题出现在acdreamer的博客里的。 但是实际上，这道题应该和反素数没有关系。 如果题目问的是最小的约数个数大于等于n的x，那么答案一定是反素数...打表就行了。。。 但是问的是**恰好，**比如如果n为5，那么最小的x是16，但是x不是反素数。 所以其实就是个dfs啦。 理论依据是： 一个数 A 可以分解成 p1k1 * p2k2 * …… * pnkn 其中p为素数。这样分解之后，A的因子个数 S = （k1+1） *（ k2+1） * …… *（ kn+1） 以及要找的是一个最小的x，满足约数个数等于n。 那么关于反素数的两个性质依然是满足的： …

hdu 3336 题目链接 题意：给一个字符串，问这个字符串的所有前缀的出现次数的和。 思路：这道题需要完全理解nxt函数是干嘛的。。nxt[i]表示的是字符串的0..i-1位中，前缀和后缀相等的串的最长长度为nxt[i] 这东西对于这道题有什么用呢？ 举个例子，对于字符串ababa： s a b a b a i 0 1 2 3 4 5 next[i] -1 0 0 1 2 3 ans初始为len(因为长度为len的字符串有len个前缀，每个前缀至少出现一次) next[3] = 1，ans + 1 = 6，next[1] = 0 next[4] = 2，ans + 1 = 7，next[2] = 0 next[5] = 3，ans …

poj3310 题目链接 题意：给出一个无向图。。。问是否满足。。联通，并且无环，并且能找到一条路径，图中所有的顶点要么在这条路径上，要么与这条路径上的顶点相邻。 思路：一个一个来。。。联通的话任意起点开始跑一遍dfs? 开一个bool数组标记走过的点。。最后扫一遍。。看是否有点没走过 环的话并查集就好。。 关键是第三个条件。。。根据题中题中的例子。。感觉如果存在这样的路径。。。那么这样的路径应该尽可能长？ 于是想到求直径。。。然后在bfs的时候顺便记录路径。。。这样我就知道直径是哪些点。。。然后对于所有点。。判断是否在这条直径上或者与之相邻就好。。。 具体做法是。。。开了一个bool数组ok标记直径上的点。。。在存边的时候用一 …

hdu 3225题目链接 题意：给出一个n*m的矩阵。每个格子有一个数。每行1..n必须每个出现一次。每列1..n每个数最多出现一次。现在要添加一行，并且补违反上述规则。问添加的方案中字典序第k小的方案。如果一共不足k种方案，那么输出-1. 思路：有点像八皇后。。。就是纯搜。。。不过n好大。。。这么搜会TLE... 想了半天也没思路。。。看了题解。。发现是用二分图匹配来剪枝。。 比较重要的一点是。。。 n个数的某种排列，可以看做是一个位置集合{1..n}和数字集合{1..n}的二分图最大匹配。 我们可以根据这个来剪枝。 具体做法： **我们先求出一个完备匹配，然后搜索每个位置能够种的花，假设当前位k置种了花i,那么判断k+1--n位 …

poj1470题目链接 题意：求两点的lca. 思路：dfs+rmq. 读入技巧。 读入比较坑爹。。。 学会了一种新的读入技巧。 scanf("%2s",st); 表示读一个长度为2的字符串。。。读的时候会忽略各种空白字符。 /* *********************************************** Author :111qqz Created Time :2016年05月19日 星期四 15时44分12秒 File Name :code/poj/1470.cpp ************************************************ */ #include …