NOIP2013 提高组 解题报告 Day1 转圈游戏 题意分析 容易看出每次进行一轮，x=(x+m)% n（出题人很好心地让位置从0开始）。 一共进行了10k轮，则x=(x+$10^k$m)% n。 根据数据范围和上面的式子分析，这道题的关键是求$10^k$。 再进一步，求$10^k$% n。 几个有用的结论 (ab)% c=[ (a % c)(b % c)] % c 简单的证明一下：

NOIP2015提高组 解题报告 Day1 神奇的幻方 【题目描述】略。 思路分析 ​ 幻方问题是一个经典的数学问题，这道题叙述的是奇数幻方的构造方法。 题目中已经很明确地说明了构造的方法，只要一条条转换为代码即可。 具体代码 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49

后缀数组转述 概念 要了解后缀数组，首先要知道字符串的后缀。 后缀 ​ 对于字符串str，从str的某个位置pos到str的末尾的所有字符依次排列组成的新字符串。 即： str.suffix(pos) = str.substr(pos,str.length-pos) /其中substr是C++的库函数（头文件），用来求字符串的子串。用法为：string::substr(起始位置,子串长度)/ 我们可以看出

AC自动机 概念 AC自动机，不是自动AC机，而是Aho-Corasick automation。 采用与kmp类似的方法在trie上构造失败指针来实现快速的字符串匹配。 例题：hdu2222 代码太丑试了几次才勉强卡过。 代码 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43

字符串查找树（Trie） 例题:luogu2580 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 /* luogu2580 */ #include<iostream> #include<cstdio> #include<cstring> #include<cstdlib> #include<vector> #include<algorithm> #include<string> using namespace std; int n,m; char name[55]; struct node { char c;

Manacher算法 用于寻找给定字符串中的最长回文子串。 模板（待修改） 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 /* Manacher */ #include<stdio.h> #include<string.h> #include<stdlib.h> //using namespace std; #define maxn 2*11000003 char s[maxn]; int lens=0,spread[maxn]; int maxl,maxid; void Manacher() { int id=0,rbound=0; maxid=0;maxl=0; int i=0; for(;i<=lens;++i) { if(i<rbound) { int j=2*id-i; if(spread[j]<rbound-i) { spread[i]=spread[j]; } else spread[i]=rbound-i; }//else spread[i]=0 while ( i-spread[i]-1>=0 &&i+spread[i]+1<=lens &&s[i+spread[i]+1]==s[i-spread[i]-1]) { ++spread[i]; } if(i+spread[i]>rbound) rbound=i+spread[i],id=i; if(spread[i]>maxl) maxl=spread[i],maxid=i; } } int main()

kmp算法 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 /* kmp */ #include<iostream> #include<cstdio> #include<cstring> #include<cstdlib> #include<string> using namespace std; int nxt[1003],len1,len2; char s1[1000003],s2[1003]; void initNxt() { nxt[0]=-1; int j=-1; for(int i=1;i<=len2-1;++i) { while(j!=-1&&s2[i]!=s2[j+1]) j=nxt[j]; if(s2[i]==s2[j+1])++j; nxt[i]=j; } } void findApr() { int i,j; for(i=0,j=-1;i<=len1-1;++i) { while(j!=-1&&s1[i]!=s2[j+1]) j=nxt[j]; if(s1[i]==s2[j+1])++j;//find the same if(j==len2-1) { printf("%d\n",i-j+1); } } } int main() { freopen("kmp.in","r",stdin); //freopen("kmp.out","w",stdout); scanf("%s %s",s1,s2); len1=strlen(s1),len2=strlen(s2); initNxt(); findApr(); for(int i=0;i<=len2-1;++i) { printf("%d ",nxt[i]+1); } printf("\n"); return 0; }

计算几何 ! 这部分笔记还不完整。 部分例题 hdu1348 Wall 有一个光源和N 个镜子，问是否存在射出角度使得可以使其接触的前N 面镜子恰好是这N 面镜子的排列 N <=10 hdu1392 Surround the Trees(凸包) poj1654 Area

字符串哈希 例题：luogu3370 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 #include<iostream> #include<cstring> #include<cstdios> #include<string> #include<algorithm> using namespace std; const int maxn=10005; typedef unsigned long long ULL; char s[maxn]; ULL Base=62; struct Hash { inline Hash(ULL M,ULL d):Mod(M),low(d){} ULL Mod; ULL low; ULL pre[maxn],//pre[i] store hash of s.substr(1,i) Pow[maxn];//Pow[i] store