poj3252 题意：给出两个数n，m，求出其区间中round number的个数，round number即满足在二进制写法中，0的个数大于等于1的个数的正整数。 利用前缀和思想，求出（1，n），（1，m）中round number的个数，相减即可。 求法： 对于数字21，它的二进制写法为 10101，共五位，我们首先求得位数低于五位的round number有多少，例如在求四位round number时，首位一定为1，后面三位可以有三个0或两个0，该计算可通过组合数的性质进行化简。 接下来，对于五位的round number，我们从最高位依次下推，遇到1就计算出从该位以下000…...

知识背景：首先明确强连通分量(strongly connected component)的概念，从任一顶点能够到达任一其他顶点的有向图 的顶点子集，而任意有向图均可以分解成若干不相交的scc。把每个scc视作一个顶点，可得到一个DAG。 实现算法：两次dfs，第一次 dfs 遍历将顶点后序(post order)记录下来vs（vector），这里需要注意的是，不管从哪个点dfs，由于是后序记录，故最终得到的记录是一样的，vs中的顶点（按下标）从前至后对应在DAG中为从尾到头。第二次dfs对于vs中的元素从尾到头进行，使用反向边，故每次dfs只能访问到同一个强连通分量。因而每次dfs时给所到顶...

并查集：用以将元素高效分组以及区分。 题目来源：codeforces 1012B 原问题如下，在一个（n*m）的table上，element会做出一种增值行为，如果有三个物质处于某个矩形的三个顶点上，那么在第四个顶点上会自动增值出一个element。现在table上已经存在了一些物质，求出最少仍需多少额外的物质，使得其可以将table覆盖。 对于解这道题来说，灵活的转化思想非常重要。首先我们可以证明，如果一个矩形有两条相邻的边被覆盖满，这个矩形就可以通过增值自行覆盖。进一步我们可以发现，如果将这两条边按垂直方向“打散”之后分散在矩形中，依然可以完成增值。 这个性质的本质是什么呢，可以将...

题目来源：poj3250 题目链接 题目大意：有一群列队，面朝右站立的牛，输入每头牛的身高，如果视线前方有一头高于自己的牛，则看不到它之后的牛；求出所有牛能看到头顶的个数。 n方算法超时，故考虑优化，首先能想到的是，在计算左边的牛能看到多少牛时，可以利用右边的结果。栈优化的思路即是，从右向左遍历牛的身高，同时对栈进行操作（栈中存放牛的编号），栈首牛低于当前牛，则去掉该元素；反之则说明该牛最远能看到的，是栈首牛的前一头牛。如果栈空，则说明能一直看到头。至于为何该算法是正确的，核心原因在于，靠前的牛的身高对看的距离远近影响至关重要，所以用靠前的牛的身高来更新栈是正确的。即每当出现较高的牛，栈中...

递归法 按字典序生成 整体思路：首先原序列已经按照字典序排好，继而通过逐个添加新字符生成新序列，字符添加所遵守的规则即是，按照字典序贪心地添加，（遇到未与已确定序列重复的字符，就添加在后面；遇到重复的就跳过这个字符），第一个由于不存在会重复的情况，所以生成序列即为原table，之后逐个回溯，由于是从后往前，故字典序逐个上升，符合要求。附代码 #include<iostream> #include<cstring> using namespace std; //permutation char table[]="abcdefgh"; char ...

知识基础： 我们平时所见到的，类似于（2+9）*6的计算式，都可称之为中缀表达式，其双目运算符位于两个操作数之间；而逆波兰表达式又可称为后缀表达式，其操作符位于两个操作数之后，例如 1+1 -> 11+，（2+9）*6 -> 29+6*。在进行计算时，从左到右遍历算式遇到操作数即压入数栈，遇到操作符即从数栈中弹出两个数字进行计算，再将结果压入栈中，由于其可通过有序遍历得到结果这一特征，故算式计算中，一般需将中缀表达式转为后缀表达式，再按相应规则计算出结果。 至于转化方法，首先明确的是，由于计算时从左到右遍历，故优先级高的运算符位置要靠前，前面两个数字（包括之前运算符生效时产生的...

问题原型：n个人围坐一圈依次报数（1~n），第m个人离席；之后从第（m+1）个人开始继续报数，报至第m个人时同样离席，求最后剩下的人的最初编号。 1.递归法 考虑将问题拆分，对于刚去掉m的环： 1，2，，m-1，m+1，，，n， 可以视作环（通过平移得到，前面原本有m个元素）： m+1，，，n，1，2，，m-1 即从m+1开始依次从1重新编号，如果我们能找到这个长度为n-1的环的解，将其（x+m-1)%n+1即为原环的解，（这个计算式是因为最小编号为1，，故普通取余不能满足要求——结果为0~n-1，而我们要保证调整后编号在1~n之间） 附代码： int ysf(int n,i...

C 括号 题目大意：对于输入的一串括号“()))(()()((”，可以删去若干位（删除位置不完全相同时均算作两种操作），若想最终得到合法括号串，求共有多少种操作方法可选。 先说算法后解释：  dp[i][j]表示，加入第i个元素后，能将前i个字符转化为有j个未配对左括号‘（’的方法数。                                                                      以此为基础 dp[i][j] 的构成分为两部分，可根据操作中是否删去新字符来分类：                                       ...

思维题 链接 暂时没明白为啥好多poj的总结把它放在dp里 题目大意：现有汉诺塔残局，也就是说盘子零散地插在三个钉子上，当然各自也都遵守“上小下大”的摆放规律。求将其全部整理至一个钉子上所需最少步数，输出最后所在钉子位置（1，2，3）以及最小步数。 首先对于基础的汉诺塔问题，由数列递推式可得，将高度为n的塔从一个钉子上转移到另外一个钉子上所需步数为（2^n-1） 对于本题目，可逆向考虑，即求将一个整理好的塔分散至开局情况，所需最小步数。两者是一致的。 算法大致为，从下至上询问目的位置，在当前位则不需要移动，不在当前位则将其上（i-1）个移动至另一个位置，再将该盘子（i）移至目的地，花...

题目大意：给出一个大小为n的树，意欲破坏其中一个节点使得剩余残骸大小均不超过n/2，给出所有可行的节点编号（1~n） 思路很直接，拆除一个节点后，剩余部分为其若干儿子的子树以及该节点上层所连其余部分（n-size[i]），只要这些连接块大小都不超过n/2，该节点就满足条件。因而我们可以先求出每个节点所管辖的那棵树的大小，这里用到了dfs，也可以勉强算作dp：自下而上地为每个节点求出其子树规模（该点规模=其儿子的规模和+1）。 在建树的时候可以直接用连接表（vector）储存无向边，这时由于无法区分与每个点相连的是其父节点还是子节点，会引发问题：在dfs的时候把父节点误认作儿子节点，解决方法...

记录一些零碎知识 文本框需将Mutiline设置为true之后方可进行换行，滑块出现true选项；可通过在准备传入SetWindowTextw()的CString中加入\r\n实现换行 更改对话框ID后，要去头文件中更改 关联ID，这里IDE不会自动修改，需要手动完成，否则可能导致对话框无法添加变量。                   借书对话框中需要获取来自文档类的成员变量中的数据，由于采用（if(win.DoModal()==IDOK)）写法，故很难给对话框控件预设数据（触发确认按钮时才进入后面的程序），大概思路分两种，其一在对话框中利用文档类指针（可...

题目大意：每个节点有一个权值，可从任一边将树一分为二，求两边权和之差的最小值 附：题目链接 建树过程和上一道题一样，同时求出每个节点管辖子树的规模size，然后在dfs函数中判断：把当前点及其以下从树上割开时，两者之差是否更小，ans初始值设为所有点权和即可。 出现问题： 1.runtime error，vector<int>设为全局变量然后忘记了每次都要加上clear()处理。。 2.wrong answer，受了上一道题影响，，还认为每个点大小为1，sz数组忘记用a数组初始化。 #include<iostream> #include<vec...

SPFA为Shortest Path Faster Algorithm的缩写，用来解决单源最短路问题，在效率上相比传统算法有一定优势。 算法首先需要获取点点距离，不相通的点间距设为inf，准备一个vis数组用来判断点是否在队列中，一个dis数组记录每个点到起点的最短距离。 算法核心：不断试图用队列中的点（队首）更新其余点的距离(dis[])，更新成功则，将该点也加入队列（因为被优化成功的点也有可能优化其余点），当然前提是该点之前不在队列中，这个状态通过vis数组实时修改和查询。对1-n都更新尝试一遍之后，将该点从队列中pop出并把vis设为0。此处要注意的是，这个点在之后仍可能加入...

样题：poj2253 题目链接 题目大意：一只青蛙需从1号石头经由一系列石头跳跃至2号石头，每块石头相隔一定距离（任意两石头均可跳），求出在所有可能的跳跃路径中，单步跳跃距离最大值最小的一条路径中，该值的大小。 向最小生成树算法方向分析，无论是prim还是kruskal算法，均是优先挑选短边或离现有生成树最近的点加入生成树，这种处理顺序就可以保证最后连上二号石头时所加上的边比之前的都要长，且不可能存在一条路径，它的最大跳跃距离比该值小（否则在路径选择时也不会选择该路径） prim： #include<iostream> #include<cstdio&gt...