怪话怪的博客

KMP

感觉KMP很简单就没练过，用的时候太不熟练，写个博客熟悉熟悉。其实主要就是两部分，一个是确定next数组，一个是利用next找子串，这两部分大致思路很简单，有点异曲同工。具体细节代码中注释已经说的很清楚了，不再赘述。 #include<bits/stdc++.h> using namespace std; vector<int> getNext(const string &pattern) { int m = pattern.size(); // 既可以用来初始化也可以作为循环出口 vector<int> next(m); next.push_back(0); // 一个字符无法匹配默认为0 int i=1; // 后缀匹配到的字符位置（只增不减） int p=0; // 记录当前最大前缀(末)位置(其实也就是p=next[0]) while(i<m) { if(next[p] == next[i]) { p++; // 缀数增加，要推进主串，同时构建next next.push_back(p); i++; // 向后推进 } else // 后缀断连 { if(p == 0) // 没有回退空间（找不到更小前后缀）,保持缀数不变,继续推进 { i++; } else { p = next[p-1]; // 前后缀长度回退，循环继续 } } } return next; } int main() { string text;// 原串 string pattern;// 要找的目标字符串 cin >> text; cin >> pattern; int n=text.size(); int m=pattern.size(); if(n < m) return 0; //长度不符合标准 vector<int> next = getNext(text); // 这里只处理查找到第一个匹配串的位置，如果多个匹配点,重置变量(p),继续匹配不间断输出就行 int j=0; // pattern(副)串匹配到的位置 int i=0; // text(主)串匹配到的位置 while(j<m) { if(pattern[j] == text[i]) { j++; i++; } else { if(j==0) // 无法回退 { i++; // 向前推进 } else { j = next[j-1]; } } } // 这时i位于找到的子串所在位置后面一个 printf("第一个匹配的子串位置是[%d,%d]\n",i-m,i-1); // 输出所在区间 return 0; }

深度学习

笔记广播

洛谷 P1393

题目思路状态转移矩阵T[i][j]其实就是添加一个字符之后从状态i转移到状态j的方案数量，也就是先用kmp得到对应的T然后对于长度为N的串只需要让这个转移矩阵N次方就行了，然后Tn[0][j]就是子串最大匹配到j位的方案数，所求结果就是Tn[0][0]一直加到Tn[0][M-1](M是子串的长度)。主要函数以及主要流程矩阵相乘函数矩阵快速幂函数(利用到矩阵相乘函数和快速幂算法) kmp算法(过于基础就不介绍了) 利用next函数得到基础转移矩阵T[m][n] 对T运用幂n函数得到Tn Tn按照思路直接操作就行了题解（借鉴了AI，自己敲的，我太强了） #include<bits/stdc++.h> using namespace std; typedef long long ll; // 得到next函数 vector<int> getNext(string pattern) { int m = pattern.size(); vector<int> next(m,0); for(int i=1,j=0;i<m;i++) { while(j!=0 && pattern[i] != pattern[j]) j = next[j-1]; if(pattern[j] == pattern[i]) j++; next[i] = j; } return next; } // 矩阵相乘函数 vector<vector<int>> matMul(vector<vector<int>> a,vector<vector<int>> b,int K) { int m = a.size(); vector<vector<int>> res(m,vector<int>(m,0)); //结果 for(int i=0;i<m;i++) // i-k,k-j { for(int k=0;k<m;k++) { if(a[i][k]!=0) //剪枝减小工作量 { for(int j=0;j<m;j++) { res[i][j] = (res[i][j] + (ll)a[i][k] * b[k][j]) % K; } } } } return res; } // 矩阵幂函数(利用快速幂算法) vector<vector<int>> matPow(vector<vector<int>> a,int p,int K) { int m = a.size(); vector<vector<int>> res(m,vector<int>(m,0)); //结果 for(int i=0;i<m;i++) res[i][i] = 1; //单位矩阵用于起步 while(p!=0) { if(p & 1) res = matMul(res,a,K); a = matMul(a,a,K); p >>= 1; // p /= 2 } return res; } int main() { int N,M,K; // M<=20 N<=1e9 K<=10000,所以不能暴力解 cin >> N >> M >> K; string pattern; // 子串（此题中指的是不该出现的子串） cin >> pattern; // 求 pattern 的状态转移方程T[i][j] // 因为要用到pattern的next数组，所以先求next vector<int> next = getNext(pattern); vector<vector<int>> T(M,vector<int>(M,0)); // T[M][M],表示基础转移矩阵 for(int m=0;m<M;m++) // m为当前匹配数量,由于不准出现匹配到完整M的，所以最大长度为M-1 { for(int digit=0;digit<=9;digit++) // 尝试每一个数字,从而进行状态转移 { int cur = m; // 从当前位置开始回退 while(cur!=0 && (pattern[cur]-'0') != digit) cur = next[cur-1]; if((pattern[cur]-'0') == digit) cur++; if(cur < M) T[m][cur] = (T[m][cur] + 1) % K; } } // 得到完整的状态转移矩阵 vector<vector<int>> Tn = matPow(T,N,K); ll result = 0; for(int i=0;i<M;i++) { result = (result + Tn[0][i]) % K; } cout << result << endl; return 0; } 遇到问题 p>>1不会改变p的值应该是p>>=1 int类型乘法要注意防止溢出，一般用ll

w

（加图改md路径）

洛谷 P1328

题目思路数字化选择方式纯手抄一个map<pair<int, int>, int> mp用来记录出拳结果。如mp[{2,0}] = 2;表示b赢了直接取余数组处理得到结果 #include <bits/stdc++.h> using namespace std; int main() { // 0 表示剪刀， // 1 表示石头， // 2 表示布， // 3 表示蜥蜴人， // 4 表示斯波克 // 结果0表示平局，1表示a赢，2表示b赢 map<pair<int, int>, int> mp; int n,na,nb; int result[3]={0}; //0无意义，1为a分数，2为b分数 cin >> n >> na >> nb; vector<int> a(na),b(nb); for (int i=0;i<na;i++) { cin >> a[i]; } for (int i=0;i<nb;i++) { cin >> b[i]; } for(int i=0;i<5;i++) { mp[{i,i}] = 0; } mp[{2,0}] = 2; mp[{3,0}] = 2; mp[{3,1}] = 2; mp[{4,2}] = 2; mp[{4,3}] = 2; mp[{1,0}] = 1; mp[{2,1}] = 1; mp[{3,2}] = 1; mp[{4,0}] = 1; mp[{4,1}] = 1; mp[{0,2}] = 1; mp[{0,3}] = 1; mp[{1,3}] = 1; mp[{2,4}] = 1; mp[{3,4}] = 1; mp[{0,1}] = 2; mp[{1,2}] = 2; mp[{2,3}] = 2; mp[{0,4}] = 2; mp[{1,4}] = 2; for(int i=0;i<n;i++) { int xi = i%na; int x = a[i%na]; int y = b[i%nb]; result[mp[{x,y}]]++; } cout << result[1] << " " << result[2] << endl; return 0; } 优化看了别人的题解，大多是用一个二维[5][5]的数组存储对局输赢，后面处理简单一些。