前提算法 二分图染色得到L，R数组 （以下是利用染色得到二分图的代码） #include<bits/stdc++.h> using namespace std; const int MAXN = 100; //假如最大100个结点的图 int graph[MAXN][MAXN]; int color[MAXN]; //用于确定分组,颜色为1和2 int dfs(int index,int n,int c) //仅仅用来染色出发点所在的连通分量 { //直接用对边不同色考虑 color[index]=c; for(int i=0;i<n;i++) if(graph[index][i] && (color[i]==c || (color[i]==0 && !dfs(i,n,3-c))) ) return 0; return 1; } int main() { int n,m; cin >> n >> m; for(int i=0;i<m;i++) { int s,t; cin >> s >> t; graph[s][t]=1,graph[t][s]=1; } for(int i=0;i<n;i++) { if(!color[i]) if(!dfs(i,n,1)) { cout << "错误，不是二分图" << endl; return 0; } } vector<int> color1,color2; for(int i=0;i<n;i++) { if(color[i]==1) color1.push_back(i); if(color[i]==2) color2.push_back(i); } cout << "染色结果:" << endl; for(int i=0;i<color1.size();i++) cout << color1[i] << ' '; cout << endl; for(int i=0;i<color2.size();i++) cout << color2[i] << ' '; return 0; } 染色后，可以用来得到最大匹配，最大匹配又可以用来得到最小点覆盖，最小点覆盖又可以用来实现匈牙利算法，匈牙利算法用可以用来解决指派问题。顺了，都理顺了:)。 最大匹配 面向问题 求解一个二分图中的最大匹配问题。 总体思路 从任意一个顶点出发， 写代码 1. 起步：初始化所用变量与内存。 const int MAXN : 根据题目调整 int n : 两边的顶点总数 int graph[MAXN][MAXN] : 基于二维数组的邻接矩阵 int match[MAXN] : match[i]表示与i匹配的点(因为最大匹配饱和点中每一个点都只可能与唯一点匹配)，如果为-1表示未匹配 int used[MAXN] : dfs访问标记（这个级别低于匹配标记match） 2. 深入： 了解所用函数。 ...

01背包 问题 有N个物品要装到一个只能承重W的背包里，每个物品重量为w[i]（weight），价值为v[i]（value），问背包能装的最大价值 前提 每类物品只能装一个（此谓01）。 二维解法 /*01背包二维数组解决*/ #include<bits/stdc++.h> using namespace std; int main() { int N,W; //物品种类数,背包总能承受重量 cin >> N >> W; int w[N+1]; //每个物品的重量,从1开始 int v[N+1]; //每个物品的价值,从1开始 int dp[N+1][W+1]; //dp[i][j]表示考虑第i个物品,总重量为j时,能达到的最大价值 for(int i=1;i<=N;i++) cin >> w[i] >> v[i]; //重量 价值 for(int i=0;i<=N;i++) for(int j=0;j<=W;j++) dp[i][j]=0; for(int i=1;i<=N;i++) for(int j=W;j>=w[i];j--) dp[i][j] = max(dp[i-1][j],dp[i-1][j-w[i]]+v[i]); //(不用第i个物品,用第i个物品) cout << dp[N][W]; return 0; } 一维解法 int main() { int N,W; //物品种类数,背包总能承受重量 cin >> N >> W; int w[N+1]; //每个物品的重量,从1开始 int v[N+1]; //每个物品的价值,从1开始 int dp[W+1]; //dp[i][j]表示考虑第i个物品,总重量为j时,能达到的最大价值 for(int i=1;i<=N;i++) cin >> w[i] >> v[i]; //重量 价值 for(int i=0;i<=W;i++) dp[i]=0; for(int i=1;i<=N;i++) for(int j=W;j>=w[i];j--) dp[j] = max(dp[j],dp[j-w[i]]+v[i]); //(不用第i个物品,用第i个物品) cout << dp[W]; return 0; } 示例 输入 10 15 2 3 3 4 4 8 5 8 9 10 3 5 4 6 2 4 6 7 7 9 输出 26 完全背包 关于我 关于我

楼房 思路 属于扫描线算法思想，通过动态维护当前高度集合，利用最大高度(天际线)来不断动态变化，同时记录轮廓拐点，最后顺序输出。 题解 #include <bits/stdc++.h> using namespace std; int n,cnt,num ; struct build { int h,l,r; }a[100010]; //楼房 struct line { int up,x,k; //up代表线高度(楼房左右边线),k代表出入属性,1代表入，2代表出 }l[200020]; struct ANS { int ax,ay; }ans[400040]; //储存答案的交叉点 int cmp(line a,line b) { if(a.x != b.x) return a.x<b.x; if(a.k != b.k) return a.k<b.k;//入度优先 // 区分入度出度考虑高度优先级 if(a.k == 1) return a.up > b.up; //入度，高的优先 if(a.k == 2) return a.up < b.up; //出度，矮的优先 } multiset<int> s; int main() { cin >> n; for(int i=1;i<=n;i++) { cin >> a[i].h >> a[i].l >> a[i].r; l[++cnt] = {a[i].h,a[i].l,1}; //楼左，入度 l[++cnt] = {a[i].h,a[i].r,2}; //楼右，出度 } s.insert(0); //初始化最高为0 sort(l+1,l+cnt+1,cmp); for(int i=1;i<=cnt;i++) { int m = *s.rbegin(); //存最大高度 if(l[i].k==1) { if(l[i].up <= m) s.insert(l[i].up); else { ++num;ans[num].ax=l[i].x;ans[num].ay=m; ++num;ans[num].ax=l[i].x;ans[num].ay=l[i].up; s.insert(l[i].up); } } else if(l[i].k == 2) { if(l[i].up==m && s.count(m)==1) { s.erase(m); //移除该高度(存交叉点)，继续下 ++num;ans[num].ax=l[i].x;ans[num].ay=l[i].up; ++num;ans[num].ax=l[i].x;ans[num].ay=*s.rbegin(); } else s.erase(s.find(l[i].up)); } } cout << num << '\n'; for(int i=1;i<=num;i++) cout << ans[i].ax << ' ' << ans[i].ay << '\n'; return 0; } 这里代码借鉴（其实是抄的）了题解中shuri001佬的代码，写得太好了，叹为观止。 ...

hugo项目结构 my-blog/ ├── archetypes/ # 内容模板 ├── assets/ # 需要 Hugo Pipes 处理的资源 (SCSS, JS) ├── content/ # Markdown 内容 ├── layouts/ # 模板布局 (覆盖主题) ├── static/ # 静态文件 (图片, 字体) ├── themes/ # 主题目录 └── hugo.yaml # 核心配置文件 快速生成并推送到github网页 1.Windows系统 编辑一个deploy.ps1文件(.bat 是 cmd 的脚本，而 .ps1 是 PowerShell 的脚本)实现自动化推送比如： 1param ( 2 [string]$msg = $(Read-Host "请输入本次提交信息") 3) 4 5# 进入 Hugo 项目根目录 6cd F:\myblog 7 8# 生成 Hugo 网页（包含草稿） 9hugo -D 10 11# 进入 public/ 目录 12cd public 13 14# 添加所有修改 15git add . 16 17# 提交 18git commit -m "$msg" 19 20# 强制推送到 gh-pages 分支 21git push -f origin gh-pages 22 23# 返回项目根目录 24cd .. 25 26# 输出提示信息 27Write-Host "" 28Write-Host "======================================" -ForegroundColor Yellow 29Write-Host "✅ 网站已成功部署！" -ForegroundColor Green 30Write-Host "🌐 访问地址: https://caoxuan5211.github.io/" -ForegroundColor Cyan 31Write-Host "======================================" -ForegroundColor Yellow 生成文档间链接 1.普通文档链接 目前只用到了相对路径 ...

线段树1 用到线段树基础知识 #include<bits/stdc++.h> using namespace std; // 线段树我默认每个数组下标都是从1开始的 void build(const vector<long long>& nums,vector<long long>& d,int s,int t,int p); long long getSum(vector<long long>& d,vector<long long>& b,int l,int r,int s,int t,int p); void update_plus(vector<long long>& d,vector<long long>& b,int l,int r,int s,int t,int p,long long c); int main() { int n,m,type,l,r; long long k; cin >> n >> m; vector<long long> nums(n+1), d(4*n+1), b(4*n+1, 0); // 修改这里 for(int i=1;i<=n;i++) cin>>nums[i]; build(nums,d,1,n,1); while(m--) { cin >> type; if(type==2) { cin >> l >> r; cout << getSum(d,b,l,r,1,n,1) << '\n'; } else if(type==1) { cin >> l >> r >> k; update_plus(d,b,l,r,1,n,1,k); } } return 0; } void build(const vector<long long>& nums,vector<long long>& d,int s,int t,int p) { if(s==t) { d[p] = nums[s]; return; } int m = s + ((t-s)>>1); build(nums,d,s,m,2*p); build(nums,d,m+1,t,2*p+1); d[p] = d[2*p] + d[2*p+1]; } long long getSum(vector<long long>& d,vector<long long>& b,int l,int r,int s,int t,int p) { if(l<=s && t<=r) { return d[p]; } int m = s + ((t-s)>>1); long long sum=0; if (b[p] && s != t) //下传懒标记 { d[p*2] += b[p]*(m-s+1); d[p*2+1] += b[p]*(t-m); b[p*2] += b[p]; b[p*2+1] += b[p]; b[p] = 0; } if(l<=m) sum += getSum(d,b,l,r,s,m,2*p); if(r>m) sum += getSum(d,b,l,r,m+1,t,2*p+1); //等价于r>=m+1 return sum; } void update_plus(vector<long long>& d,vector<long long>& b,int l,int r,int s,int t,int p,long long c) { // 当前区间为修改区间的子集时直接修改当前节点的值,修改后标记 if (l <= s && t <= r) { d[p] += (t - s + 1) * c, b[p] += c; return; } int m = s + ((t - s) >> 1); if (b[p] && s != t) //下放标记(不会有s==t的情况因为s==t的时候肯定是lr的子区间已经直接return了) { d[p * 2] += b[p] * (m - s + 1), d[p * 2 + 1] += b[p] * (t - m); b[p * 2] += b[p], b[p * 2 + 1] += b[p]; b[p] = 0; } if (l <= m) update_plus(d, b, l, r, s, m, p * 2, c); if (r > m) update_plus(d, b, l, r, m + 1, t, p * 2 + 1, c); d[p] = d[p * 2] + d[p * 2 + 1]; } 这里用了懒惰区间标记。对有些当次不需要访问但是确实有变化的区间进行了标记，如果下次访问到了标记区间，则执行修改并下放标记。 ...

失踪的7 直接找pascal的n以内的最大值 由于需要删除7（单位大于7就减，小于7直接用）,所以可以把十进制转换为去除7的模拟九进制。 #include <bits/stdc++.h> using namespace std; #define ll long long int main() { int t; cin >> t; while(t--) { string s; cin >> s; ll result = 0; for(char c : s) { int dig = c-'0'; if(dig > 7) dig--; result = result*9 + dig; } cout << result << "\n"; } return 0; }

Mivik 不会做 观摩题解后的感触 求概率取余时候除以的分母可以用模逆元转换为乘。 还有就是KMP中的next数组可以转换为n个等差数列（顺序排列，不交叉）。也就是字符串边界理论（Border Theory） 题解里面FjswYuzu写的还可以,有时间学学。 题解(ctrl+c/v) #include<bits/stdc++.h> using namespace std; typedef long long LL; char buf[1<<18],*p1=buf,*p2=buf; #define getchar() (p1==p2 && (p2=(p1=buf)+fread(buf,1,1<<18,stdin),p1==p2)?EOF:*p1++) int read() { int x=0; char c=getchar(); while(c<'0' || c>'9') c=getchar(); while(c>='0' && c<='9') x=(x<<1)+(x<<3)+(c^'0'),c=getchar(); return x; } void write(int x) { if(x>9) write(x/10); putchar(x%10+'0'); } const int MOD=998244353; inline int Add(int x,int y){return x+y>=MOD?x+y-MOD:x+y;} inline int Sub(int x,int y){return x<y?x-y+MOD:x-y;} inline int Mul(int x,int y){return 1ll*x*y%MOD;} int QuickPow(int x,int p) { int ans=1,base=x; while(p) { if(p&1) ans=Mul(ans,base); base=Mul(base,base); p>>=1; } return ans; } int n,m,k; int s[100005],nxt[100005]; struct BorderSeq{ int l,r,d; BorderSeq(){} BorderSeq(int L,int R,int D){l=L,r=R,d=D;} }brd[200005]; int cnt,dp[200005],sum[200005]; int pw[200005],ipw[200005]; void Kmp() { int j=0; for(int i=2;i<=k;++i) { while(j && s[j+1]!=s[i]) j=nxt[j]; if(s[j+1]==s[i]) ++j; nxt[i]=j; } int now=nxt[k],d=k-nxt[k],fir=nxt[k]; while(now) { if(d!=now-nxt[now] || !nxt[now]) brd[++cnt]=BorderSeq(now,fir,d),fir=nxt[now]; if(!nxt[now]) break; d=now-nxt[now],now=nxt[now]; } } vector<int> Sum[20][200005]; int pos[20][200005]; int main(){ n=read(),m=read(),k=read(); for(int i=1;i<=k;++i) s[i]=read(); Kmp(); int invm=QuickPow(m,MOD-2); pw[0]=ipw[0]=1; for(int i=1;i<=n;++i) pw[i]=Mul(pw[i-1],m); for(int i=1;i<=n;++i) ipw[i]=Mul(ipw[i-1],invm); memset(pos,-1,sizeof pos); for(int i=k;i<=n;++i) { dp[i]=Sub(pw[i-k],sum[i-k]); for(int j=1;j<=cnt;++j) { int d=brd[j].d,l=brd[j].l,r=brd[j].r; int idx=(l+i-k)%d; if(!Sum[j][idx].empty()) { int L=l+i-k,R=r+i-k; if(~pos[j][R]) dp[i]=Sub(dp[i],Sum[j][idx][pos[j][R]]); if(pos[j][L]>0) dp[i]=Add(dp[i],Sum[j][idx][pos[j][L]-1]); } } for(int j=1;j<=cnt;++j) { int d=brd[j].d; int idx=i%d; pos[j][i]=int(Sum[j][idx].size()); Sum[j][idx].push_back(Add(Sum[j][idx].empty()?0:Sum[j][idx].back(),dp[i])); } sum[i]=Add(Mul(sum[i-1],m),dp[i]); } int ans=0; for(int i=k;i<=n;++i) ans=Add(ans,Mul(dp[i],pw[n-i])); write(Mul(ans,ipw[n])); return 0; }

打开网页后出现异常 当时github_pages生成的网页的css加载异常，F12用浏览器控制台看了之后发现是SRI不匹配问题。 后来找到了这篇博客:hugo发布css无法加载问题 | Le blog de Lz0o0 得以解决。

感觉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; }

笔记 广播