ACM模版 Bash #define _MAX 10000 int a[_MAX]; int b[_MAX]; int bash(int N, int K) { if (N % (K + 1) == 0) { return 2; } return 1; } int main() { int T; scanf("%d", &T); for (int i = 0; i < T; i++) { scanf("%d%d", a + i, b +...

ACM模版 大数平方根（字符串数组表示） void Sqrt(char *str) { double i, r, n; int j, l, size, num, x[1000]; size = (int)strlen(str); if (size == 1 && str[0] == '0') { cout << "0\n"; return; } if (size % 2 == 1) { n = str[0] - 48; ...

ACM模版 追赶法解周期性方程 /* * 周期性方程定义(n = 5) * |a_1 b_1 c_1 d_1 e_1| = x_1 --- 1 * |e_2 a_2 b_2 c_2 d_2| = x_2 --- 2 * |d_2 e_2 a_2 b_2 c_2| = x_3 --- 3 * |c_4 d_2 e_2 a_4 b_4| = x_4 --- 4 * |b_5 c_5 d_5 e_5 a_5| = x_5 --- 5 * 输入： a[], b[], c[], x[] * 输出： 求解结果x在x[]中 */ const int ...

ACM模版 阶乘最后非零位 /* * 阶乘最后非零位 复杂度O(nlongn) * 返回改为，n以字符串方式传入 */ #define MAXN 10000 const int mod[20] = {1, 1, 2, 6, 4, 2, 2, 4, 2, 8, 4, 4, 8, 4, 6, 8, 8, 6, 8, 2}; int lastDigit(char *buf) { int len = (int)strlen(buf); int a[MAXN], i, c, ret = 1; if (len == 1) { return mod[b...

ACM模版 排列 类循环排列 用递归实现多重循环,本递归程序相当于n重循环,每重循环的长度为m的情况,所以输出共有m^n行。 /* * 输入样例: 3 2 * 输出样例: * 0 0 0 * 0 0 1 * 0 1 0 * 0 1 1 * 1 0 0 * 1 0 1 * 1 1 0 * 1 1 1 */ #define MAX_N 10 int n, m; // 相当于n重循环,每重循环长度为m int rcd[MAX_N]; // 记录每个位置填的数 void loop_permutation(int l) ...

ACM模版 BM算法改进的算法：Sunday Algorithm BM算法优于KMP SUNDAY 算法描述:字符串查找算法中,最著名的两个是KMP算法(Knuth-Morris-Pratt)和BM算法(Boyer-Moore)。两个算法在最坏情 况下均具有线性的查找时间。但是在实用上,KMP算法并不比最简单的c库函数strstr()快多少,而BM算法则往往比KMP算法快上3-5倍。但是BM算法还不是最快的算法,这里介绍一种比BM算法更快一些的查找算法。例如我们要在”substring searching algorithm”查找”search”,刚开始时,把子串与文本左边对齐: ...

ACM模版 两个长字符串 参考题目链接： HDU 1841 Find the Shortest Common Superstring 题解 将KMP进行略微的改动，依然是查找匹配段，要求要么一个串包含另一个串，要么一个串的前缀等于另一个串的后缀。 代码 /* * The shortest common superstring of 2 strings S1 and S2 is * a string S with|the minimum number of characters which * contains both S1 and S2 as a sequence of con...

ACM模版 AC自动机 参考题目链接 HDU 2222 Keywords Search 代码 /* * 求目标串中出现了几个模式串 */ struct Trie { int next[500010][26], fail[500010], end[500010]; int root, L; int newnode() { for (int i = 0; i < 26; i++) { next[L][i] = -1; } end[L++] = 0; ...

ACM模版 DA算法 /* * suffix array * 倍增算法 O(n*logn) * 待排序数组长度为n,放在0~n-1中,在最后面补一个0 * da(str, sa, rank, height, n, m); * 例如: * n = 8; * num[] = { 1, 1, 2, 1, 1, 1, 1, 2, $ }; 注意num最后一位为0,其他大于0 * rank[] = { 4, 6, 8, 1, 2, 3, 5, 7, 0 }; rank[0~n-1]为有效值,rank[n]必定为0无效值 * sa[] = { 8, 3, 4, 5, 0, 6, 1, 7, 2 }; ...

ACM模版 后缀自动机 const int CHAR = 26; const int MAXN = 250010; struct SAM_Node { SAM_Node *fa, *next[CHAR]; int len; int id, pos; SAM_Node(){} SAM_Node(int _len) { fa = 0; len = _len; memset(next, 0, sizeof(next)); } }; SAM_Node SAM_node[MAXN * 2], ...

ACM模版 DP + DFS /* * INIT: g[][]邻接矩阵 * CALL: res = clique(n); */ const int V = 10010; int g[V][V]; int dp[V]; int stk[V][V]; int mx; int dfs(int n, int ns, int dep) { if (0 == ns) { if (dep > mx) { mx = dep; } return 1; } int i, j, k,...

ACM模版 堆栈实现 参考题目链接 POJ 3159 Candies 代码 const int INF = 0x3F3F3F3F; const int V = 30001; const int E = 150001; int pnt[E], cost[E], nxt[E]; int e, head[V]; int dist[V]; bool vis[V]; int relax(int u, int v, int c) { if (dist[v] > dist[u] + c) { dist[v] = dist[u] + c; r...

ACM模版 这是一个新兴的OJ，希望可以越办越好，以后也多一个训练自己的平台~~~ 试题一 将字符串中的字符按规则重新排列 描述 请编写程序,将输入字符串中的字符按以下规则重新排列(字符串长度不超过 1000,同时满足所有规则)。 规则 1:英文字母从 A 到 Z 排列,不区分大小写。例如,输入“Much”则输出“chMu”。 规则 2:同一个英文字母的大小写同时存在时,按照输入顺序排列。例如,输入“BabA”则输出“aABb”。 规则 3:非英文字母的其它字符保持原来的位置。例如,输入“By?e”则输出“Be?y”。 输入描述 输入数据为一行字符串。 输出描述 输出数据为一...

ACM模版 最小树形图 /* * 最小树形图 * int型 * 复杂度O(NM) * 点从0开始 */ const int INF = 0x3f3f3f3f; const int MAXN = 1010; const int MAXM = 1000010; struct Edge { int u, v, cost; }; Edge edge[MAXM]; int pre[MAXN], id[MAXN], visit[MAXN], in[MAXN]; int zhuliu(int root, int n, int m) { int res = 0, v; wh...