A 解锁专家  一开始看到这个A题的时候我的想法是直接DFS进行暴力搜索（因为没有注意到是多组输入），于是代码成功的TLE了。但是这个代码是一个很好的对拍代码！   然后手动写了几个数据发现好像前后之间存在一定的关联，于是我就用我TLE的代码进行打表去观察数据了   打表代码：   void dfs(int k) {     if (k > n) {         cnt++;  &nbs...

  希望明年多中几次奖

第一种方法就是先不断到加元素，然后再考虑删去一个元素，再加一个新到元素进来    1 void print_subset(int n,int A[],int cur) { 2 for (int i=0;i<cur;i++) 3 printf("%d ",A[i]); 4 printf("\n"); 5 int s = cur ? A[cur-1]+1 : 0; 6 for (int i=s;i<n;i++) { 7 A[cur] = i; 8 print_subset(n,A,cur+1); 9 }    第二种方法就更好理解了，就是对于每个...

题目链接：https://vjudge.net/problem/UVA-725   思路：其实就是暴力枚举，但是枚举的时候可以采取些策略减少枚举次数。 因为我们以及知道了 n 和 a，那么我们就可以推出 b ，所以其实我们需要枚举的就是 a ，a 的范围就是[1234,98765] 这题比较烦的就是对前导0的处理，这里采用 sprintf() 处理前导0 。输出的话就控制一下格式。 当然调用next_pertation函数好像也可以水过去     1 #include <cstdio>  2 #include <cstring>  3  4 bool vis[10]; ...

next_permutation就是按照字典序排列得到所有的排列组合！   例如 我们需要输出{ 1 , 2 , 3 , 4 } 的全排列（调用STL）   1 #include<iostream>  2 #include<algorithm>  3 using namespace std;  4 int main()  5 {  6 int ans[4]={1,2,3,4};  7 sort(ans,ans+4); /* 这个sort可以不用，因为{1，2，3，4}已经排好序*/  8 do /*注意这步，如果是while循环，则需要提前输出*/  9  { 10 f...

优先级队列默认less 大数优先。 priority_queue<Type, Container, Functional>其中Type 为数据类型， Container 为保存数据的容器，Functional 为元素比较方式。Container 必须是用数组实现的容器，比如 vector, deque 但不能用 list.STL里面默认用的是 vector. 比较方式默认用 operator< , 所以如果你把后面俩个参数缺省的话，优先队列就是大顶堆，队头元素最大。   最常见的两种优先队列的比较方式：    std::priority_queue<int,std::v...

题目链接：http://hihocoder.com/problemset/problem/1343   题目大意：给一个有向无环图,定义一个点为unstable当且仅当删掉一个点（不能为它自己或点0）时，它不能与点0连通；其他点则为stable，求图中有几个stable点。   思路： 如果一个点是Stable点的话，那么它的到达该点的路径肯定是不止一条（并且路径没有交叉）的。如果我们采取染色的方法，那么也就是说遍历它的父亲结点及以上的结点不可以都是一样的（因为如果都是一样的话那么就说明发生路径交叉了）。 对于每个顶点v，采用染色的方法：即对于某个顶点v，采用拓扑排序的方法遍历其后续顶点，并依...

拓扑排序就是每次选择一个入度为0的点，然后删去该点及该点所连的边。   拓扑排序单独出题挺少的，主要是用来优化其他算法。     拓扑排序模版：   1 #include <math.h>  2 #include <stdio.h>  3 #include <stdlib.h>  4 #include <iostream>  5 #include <algorithm>  6 #include <string>  7 #include <string.h>  8 #include <vector> ...

题目链接：https://vjudge.net/contest/344930#problem/I   题目大意：给你一个串s,和m,l.问你有多少长度为m*l的s的子串满足该子串由m个长度为l且个不相同的子串组成的个数.问的是长度为m * l的子串的个数。   思路：首先预处理出所有长度为l的字串的Hash值，之后有点像滑动窗口，前面减少了一个那么后面就增加一个。这样就可以避免算法的复杂度成为O(n^2)     1 #include <stdio.h>  2 #include <algorithm>  3 #include <iostream>  4 #i...

做这题之前首先需要先了解一下二维的Hash 二维的Hash其实就是先对一行的每列元素进行一次hash，处理完之后。再对每一行的元素进行hash 查询的时候有点类似二维的前缀和：       题目链接：https://vjudge.net/contest/344930#problem/H   题目大意：让你在一个大小为𝑛∗𝑚的矩阵中找大小是𝑥∗𝑦的矩阵的出现次数   思路：就是一个裸的二维Hash     1 #include <stdio.h>  2 #include <algorithm>  3 #include <iostream>  4 #in...

题目链接：https://vjudge.net/contest/344930#problem/G   题目大意：给你字符串，如果他包含至少两个长度大于等于3的回文，并且这些回文不能嵌套（例如aaa嵌套在aaaa，waw嵌套在awawa），如果这个字符串这么牛逼的话，就输出他。   题目思路：其实这道题有一个贪心的思想在里面，其实每次我们只需要去找长度为3和长度为4的回文串就好了。这里的处理策略就是先处理长度为3的回文串，再处理长度为4的回文串。处理长度为4的回文串的时候，要避免它的子串也是一个回文串。     1 #include <stdio.h>  2 #include &lt...

题目链接：https://vjudge.net/contest/344930#problem/F   题目大意：给你n个字符串，让你求给定的两个串的最长公共前缀   题目思路：处理所给的n个字符串的Hash值，然后对于每次给定的两个串，二分长度就可以了。 值得注意的是这道题需要利用vector进行存储     1 #include <stdio.h>  2 #include <algorithm>  3 #include <iostream>  4 #include <stdlib.h>  5 #include <string>  6...

题目链接：https://vjudge.net/contest/344930#problem/E   题目大意：给出一个字符串，在末尾补充最少的字母，使其整个成为一个回文串   题目思路：对字符串进行顺序Hash和逆序Hash，然后去枚举位置，如果此时顺序的Hash和逆序的Hash值想等就说明此时是一个回文串。然后就直接输出该回文串前面的部分，再输出该回文串。如果没有回文串，那么就使整个字符串成为回文串     1 #include <stdio.h>  2 #include <algorithm>  3 #include <iostream>  4 #in...

Farmer John has noticed that the quality of milk given by his cows varies from day to day. On further investigation, he discovered that although he can't predict the quality of milk from one day to the next, there are some regular patterns in the daily milk quality. To perform a rigorous study, he h...