Luogu

P1177 【模板】排序 - 洛谷 我用归并排序写的。(时间复杂度O(nlogn),空间复杂度O(n))。 #include<bits/stdc++.h> using namespace std; vector<int> A; //归并排序 void gbsort(int l,int r) { vector<int> temp; if(l==r) return; int m=((l+r)>>1); printf("划分的区间:[%d,%d],[%d,%d]\n",l,m,m+1,r); gbsort(l,m); gbsort(m+1,r); int curL=l,curR=m+1; //左右分为[l,m] [m+1,r] for(int i=0;i<r-l+1;i++) { if( curL>m ) { temp.push_back(A[curR]); curR++; } else if( curR>r ) { temp.push_back(A[curL]); curL++; } else if(A[curL]>A[curR]) { temp.push_back(A[curR]); curR++; } else if(A[curL]<=A[curR]) { temp.push_back(A[curL]); curL++; } } for(int i=l;i<=r;i++) { A[i]=temp[i-l]; } } int main() { int N; cin >> N; for(int i=0;i<N;i++) { int x; cin >> x; A.push_back(x); } // sort(A.begin(),A.end()); gbsort(0,N-1); for(int i=0;i<N;i++) { cout << A[i] << ' '; } return 0; } C++标准库sort用的是快速排序

楼房 思路 属于扫描线算法思想，通过动态维护当前高度集合，利用最大高度(天际线)来不断动态变化，同时记录轮廓拐点，最后顺序输出。 题解 #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佬的代码，写得太好了，叹为观止。 ...

线段树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; }

[HNOI2008] GT考试 思路 状态转移矩阵T[i][j]其实就是添加一个字符之后从状态i转移到状态j的方案数量，也就是先用kmp得到对应的T然后对于长度为N的串只需要让这个转移矩阵N次方就行了，然后Tn[0][j]就是子串最大匹配到j位的方案数，所求结果就是Tn[0][0]一直加到Tn[0][M-1](M是子串的长度)。 算法 KMP 自动机建模 + 矩阵快速幂 主要函数以及主要流程 矩阵相乘函数 矩阵快速幂函数(利用到矩阵相乘函数和快速幂算法) 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

生活大爆炸版石头剪刀布 思路 数字化选择方式 纯手抄一个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]的数组存储对局输赢，后面处理简单一些。