周测复盘【前缀和and差分】

其实存了三个草稿没发因为题解半路解不出来了。花了四十分钟搞三个平台关联最后一道题还是没来得及交上哈哈OK直接进入正题题目AAtcoder Trifecta题目翻译编号为1到N的N匹马进行了一场比赛所有马匹同时起跑。第i匹马从起点到终点用时Ti​秒找出获得第一名、第二名。和第三名的马匹的编号保证所有的T。i​都互不相同第一反应就是排序c语言中是用struct来储存id和timec中第一想法是二维vector哼哼就是喜欢用vector直接用sort以下是我的代码(AC)#include bits/stdc.h using namespace std; bool cmp(pairint, int a, pairint, int b) { return a.second b.second; } int main() { int n; cin n; vectorpairint, int time(n); for (int i 0; i n; i) { time[i].first i 1; int x; cin x; time[i].second x; } sort(time.begin(), time.end(), cmp); if (n 3) { cout time[0].first time[1].first time[2].first; //用printf更方便哈 } return 0; }这个是老师的题解解法一三层循环int pos1,pos2,pos3; int minn1,minn2,minn3; minn1minn2minn3INF; for(int i1;in;i) { if(minn1t[i]) { minn1t[i]; pos1i; } } for(int i1;in;i) { if(ipos1) continue; if(minn2t[i]) { minn2t[i]; pos2i; } } for(int i1;in;i) { if(ipos1||ipos2) continue; if(minn3t[i]) { minn3t[i]; pos3i; } } printf(%d %d %d\n,pos1,pos2,pos3);解法二一样sort但用的是结构体struct node { int id,val; }t[N]; bool mycmp(node x,node y) { return x.valy.val; } //老师的均为不完整代码 scanf(%d,n); for(int i1;in;i) { int x; scanf(%d,x); t[i]{i,x};//欸其实我是第一次见这个写法哈哈我一直是分开写学之学之 } sort(t1,t1n,mycmp); printf(%d %d %d\n,t[1].id,t[2].id,t[3].id);题目BluoguU69096 前缀和的逆经典前缀和第一反应是按照公式倒推然后根据输入输出调整一些参数哈哈老师的题解里还包含了差分这是道前缀和数组求差分以下是我的代码(AC)#includebits/stdc.h using namespace std; int a[100],b[100];//经常看到大佬喜欢把这种写到全局学之学之 int main() { int n; cinn; for(int i0;in;i) { cina[i]; } for(int i0;in;i) { if(i0) { b[i]a[i]; continue; } b[i]a[i]-a[i-1]; } for(int i0;in;i) { coutb[i] ; } coutendl; return 0; }这个是老师的题解scanf(%d,n); for(int i1;in;i) scanf(%d,a[i]); for(int i1;in;i) printf(%d ,a[i]-a[i-1]);题目CluoguP3397 地毯诶不知为什么第一个想法是哈希表之前刷到过好像我是用暴力枚举来做的原来题型是前缀和和差分哈哈以下是我的代码(第一次TLE了第二次提交AC了emmm)#include bits/stdc.h using namespace std; int pos[1000][1000] {0}; int main() { int n, m; cin n m; for (int i 0; i m; i) { int x1, y1, x2, y2; cin x1 y1 x2 y2; for (int x x1; x x2; x) { for (int y y1; y y2; y) { pos[x - 1][y - 1]; } } } for (int i 0; i n; i) { for (int j 0; j n; j) { printf(%d , pos[i][j]); } printf(\n); } return 0; }第一次TLE的原因是题目看错了设置成int pos[50][50] {0};在写的时候尝试用了while(cinxy)之前在一个题解中看到的但是发现在本地编译器无法停止输入豆老师帮忙分析的弊端while(cin x y) 是 C 里非常常用的写法但它确实有几个明显弊端尤其在处理不规范输入、异常数据时很容易出问题。1. 无法区分“正常结束”和“输入错误”- 循环退出只有两种情况1. 读到文件末尾EOF2. 输入类型不匹配比如输入字母- 程序不知道到底是正常结束还是输错了。2. 类型不匹配会直接导致流失效例如你定义 int x,y 却输入abc 123- cin 进入失败状态failbit- 循环直接退出- 后面所有 cin 都会失效除非手动 cin.clear()3. 无法处理多余/非法字符比如输入10 20 extra words- 读完 10 20 后后面的字符串留在输入缓冲区- 下次读会继续读到这些垃圾数据4. 不能自定义分隔符- 只能按**空白空格/换行/Tab**分割- 想按逗号、冒号等分割时完全不适用5. 无法精确控制输入行数- 换行和空格对它是一样的- 想一行一行严格处理时不适用6. 用户体验差输错一个字符就直接退出没有重试机会。更健壮的写法思路string line; while (getline(cin, line)) { // 按行解析 // 出错可以 clear、重试、提示 }这是老师的题解scanf(%d%d,n,m); for(int i1;im;i) { int x1,y1,x2,y2; scanf(%d%d%d%d,x1,y1,x2,y2); a[x1][y1]; a[x21][y21]; a[x1][y21]--; a[x21][y1]--; } for(int i1;in;i) { for(int j1;jn;j) { a[i][j]a[i-1][j]a[i][j-1]-a[i-1][j-1]; printf(%d ,a[i][j]); } puts(); }题目DluoguP1387 最大正方形第一想法暴力枚举但感觉很容易TLE但是我看网上有人说靠暴力可以拿到两百分๑ᵒᯅᵒ๑然后暴力枚举写一段之后发现走不通(就是自己想不出怎么让电脑判断这是块正方形啦)然后从数学方面思考行列的规律通过公式来更新边长本来用了新数组来储存正方形数组中间依旧出问题呵呵直接在矩形数组中修改反正只遍历一次这算一种矩阵吗矩阵我要新写几个帖子链接后面再放以下是我的代码#includebits/stdc.h using namespace std; int main() { int n,m; cinnm; int a0; vectorvectorintv(n, vectorint(m, 0)); for (int i 0; i n; i) { for (int j 0; j m; j) { cinv[i][j]; } } for (int i 0; i n; i) { for (int j 0; j m; j) { if (v[i][j] 1) { if (i 0 j 0) { v[i][j] min(min(v[i-1][j], v[i][j-1]), v[i-1][j-1]) 1; //超级关键一步 } if (v[i][j] a) { a v[i][j]; } } } } coutaendl; return 0; }这是老师的题解注二维前缀和三重循环前两重枚举正方形左上角的坐标第三重枚举正方形的边长然后判断正方形内数值之和是否等于面积即可scanf(%d%d,n,m); for(int i1;in;i) { for(int j1;jm;j) { scanf(%d,a[i][j]); a[i][j]a[i-1][j]a[i][j-1]-a[i-1][j-1]; } } for(int i1;in;i) { for(int j1;jm;j) { for(int k1;kmin(n-i1,m-j1);k) { int x1i, y1j, x2ik-1, y2jk-1; int sum(a[x2][y2]-a[x1-1][y2]-a[x2][y1-1]a[x1-1][y1-1]); if(sumk*k) ansmax(ans,k); } } } printf(%d\n,ans);题目EAtcoder Swap and Range Sumatcoder好烦òᆺó能不能保存一下我的代码当时做完我的代码挺短的我记得挺惊讶的跟第二题差不多的长度好像感觉我的逻辑过于简单了(所以这就是没AC的原因吗…)一开始没用前缀和TLE了重写一遍gogogo以下是我的代码#include bits/stdc.h using namespace std; int main() { int n, q; cin n q; vectorint a(n 1); vectorint pre(n 1, 0); for (int i 1; i n; i) { cin a[i]; pre[i] pre[i - 1] a[i];//构造前缀和数组 } for (int i 0; i q; i) { int choice; cin choice; if (choice 1) { int x; cin x; swap(a[x], a[x 1]); for (int j x; j n; j) { pre[j] pre[j - 1] a[j]; } } else if (choice 2) { int l, r; cin l r; cout pre[r] - pre[l - 1] endl; } } return 0; }这是老师的题解while(q--) { int k,x,l,r; scanf(%d,k); if(k1) { scanf(%d,x); s[x]-a[x]; s[x]a[x1]; swap(a[x],a[x1]); } else { scanf(%d%d,l,r); printf(%d\n,s[r]-s[l-1]); } }题目FAtcoder Many Repunit Sum上次看到有个题解用了#define Int long long;本来想用用我本地编译器依旧不允许全部写完之后发现那个特别长的例子无法通过超出了long long的存储范围然后诶那就用字符串呗从头开始但是时间没多少了跟着教程把前几道题交了还是没赶上写完这题小妹妹你字符串很差劲哦字符串也要单独写几篇以下是当时自己写的long long的代码过于简单了是吧哈哈#includebits/stdc.h using namespace std; int main() { int n; cinn; vectorinta(n); for(int i0;in;i) { cina[i]; } long long sum0; vectorlong longb(n); for(int i0;in;i) { long long p1; for(int j0;ja[i];j) { b[i]p; p*10; } sumb[i]; } coutsumendl; return 0; }(自己尝试写的字符串代码没AC俺对字符串目前还不是很熟代码缺胳膊少腿的让D老师帮忙它也没AC ⦁֊⦁꧞)这是老师的题解scanf(%d,n); for(int i1;in;i) { int x; scanf(%d,x); mmax(m,x); d[x1]--; d[1]; }for(int i1;im1;i) d[i]d[i-1];然后从低到高依次进位即可。最后按位输出最终数字。for(int i1;im;i) { if(d[i]10) d[i1]d[i]/10,d[i]%10; if(imd[i1]0) m; }for(int im;i1;i--) printf(%d,d[i]); puts();这道题是真的学到东西了老师用的差分对B数组区间加法就该想到差分的啊......下次详细分析再编辑今天END!