洛谷题目练习——枚举+模拟

一、基础模拟排序数组1.洛谷|P1059方法一#includebits/stdc.husing namespace std;const int N1e5;int a[N];intmain(){ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);int n;cinn;for(int i0;in;i){cina[i];}sort(a,an);int num0;for(int i0;in;i){if(i0||a[i]!a[i -1])num;}coutnum\n;for(int i0;in;i ){if(i0||a[i]!a[i -1])couta[i] ;}return0;}方法二#includebits/stdc.husing namespace std;const int N1e5;int a[N];intmain(){ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);int n;cinn;for(int i0;in;i){cina[i];}sort(a,an);int munique(a, an)- a;coutm\n;for(int i0;im;i){couta[i] ;}return0;}2.洛谷|P1068#includebits/stdc.husing namespace std;struct node{intid;int score;};bool cmp(node a,nodeb){if(a.score!b.score)returna.scoreb.score;elsereturna.idb.id;}intmain(){ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);int n, m;cinnm;vectornodea(n);for(int i0;in;i){cina[i].ida[i].score;}sort(a.begin(),a.end(),cmp);int flagm *3/2;int linea[flag -1].score;int cnt0;for(int i0;in;i){if(a[i].scoreline)cnt;}coutline cnt \n;for(int i0;in;i){if(a[i].scoreline)couta[i].id a[i].score\n;}return0;}字符串1.洛谷|P1308#includebits/stdc.husing namespace std;intmain(){ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);string target,s;getline(cin,target);getline(cin,s);for(autoc:target)ctolower(c);for(autoc:s)ctolower(c);int cnt0;int pos-1;int ns.size();int i0;while(in){if(s[i] ){i;continue;}string word;int starti;while(ins[i]! ){words[i];i;}if(wordtarget){cnt;if(pos-1)posstart;}}if(cnt0)cout-1;elsecoutcnt pos;return0;}2.洛谷|P1200#includebits/stdc.husing namespace std;int num1[7];int num2[7];intmain(){string s1, s2;cins1;cins2;int ns1.size();int ms2.size();int x1, y1;int p0, q0;for(int i0;in;i){num1[i]s1[i]-64;x *num1[i];}px %47;for(int i0;im;i){num2[i]s2[i]-64;y *num2[i];}qy %47;if(pq){coutGO;}else{coutSTAY;}return0;}3.洛谷|P1553#includebits/stdc.husing namespace std;string prev(string s){reverse(s.begin(),s.end());int i0;while(is.size()-1s[i]0)i;returns.substr(i);}string end(string s){reverse(s.begin(),s.end());int is.size()-1;while(i0s[i]0)i--;returns.substr(0, i 1);}intmain(){string s;cins;if(s.back()%){string ts.substr(0,s.size()-1);coutprev(t)%;}elseif(s.find(/)!string::npos){int poss.find(/);string as.substr(0,pos);string bs.substr(pos 1);coutprev(a)/prev(b);}elseif(s.find(.)!string::npos){int poss.find(.);string as.substr(0,pos);string bs.substr(pos 1);coutprev(a).end(b);}else{coutprev(s);}return0;}三、模拟1.洛谷|P1421#includebits/stdc.husing namespace std;intmain(){int a, b;cinab;intsuma *10 b;int ressum/19;coutres\n;return0;}2.洛谷|P1425#includebits/stdc.husing namespace std;intmain(){int a,b, c, d;cinabcd;int p, q;if(db){pc - a -1;qd 60- b;}else{pc- a;qd - b;}coutp q\n;return0;}3.洛谷|P5707#includebits/stdc.husing namespace std;intmain(){int s,v;cinsv;int m(s v-1)/v10;int res480- m;const int d24*60;if(res0)res1440;intshres /60;int fres %60;printf(%02d:%02d,sh,f);return0;}二、枚举模板 蓝桥杯枚举模板思路枚举题大多数特点范围小→ 可以直接暴力枚举条件多→ 枚举 剪枝重复/排列/组合问题→ 用数组或位运算处理1️⃣ 基本模板最常见多层循环枚举for(intiL1;iR1;i){// 枚举第1个数for(intjL2;jR2;j){// 枚举第2个数if(ij)continue;// 去重/剪枝for(intkL3;kR3;k){// 枚举第3个数if(ki||kj)continue;// 去重if(check(i,j,k)){// 检查题目条件couti j k\n;}}}}✅ 核心continue用来去掉重复check()用来判断复杂条件比例、和、数字不重复等范围一定要尽量小 → 提前剪枝2️⃣ 数字拆分/排列模板inta,b,c;// 枚举 afor(a100;a333;a){b2*a;c3*a;if(c999)break;// 剪枝if(check(a,b,c))couta b c\n;}✅ 核心能用公式算出的直接算不用多层循环check()判断数字不重复或符合比例3️⃣ 判重/数字使用模板boolcheck(inta,intb,intc){boolvis[10]{0};// 数字1~9intnums[9]{a/100,a/10%10,a%10,b/100,b/10%10,b%10,c/100,c/10%10,c%10};for(inti0;i9;i){if(nums[i]0||vis[nums[i]])returnfalse;// 去0判重vis[nums[i]]true;}returntrue;}✅ 核心用数组标记数字是否使用过方便判断题目要求的“不重复数字”4️⃣ 位运算枚举模板高级如果题目涉及组合/子集for(intmask0;mask(1n);mask){// 枚举子集// mask 二进制表示哪些元素被选中if(check(mask))cout...;}✅ 核心每个位表示一个元素是否被选常用在“从n个数字中选k个”的问题5️⃣ 竞赛思路总结套路确定枚举对象→ 数字、位置、组合确定范围→ 最小最大尽量小剪枝/去重→ 不符合直接 continue检查条件→ 用函数或 if输出结果→ 按题目要求顺序⚡ 总结一句话枚举题就是 “暴力 剪枝 判重 check()”看公式能算就算数字拆分/位运算都可以用1.洛谷|P1008#include bits/stdc.husing namespace std;bool check(int a, int b, int c){int vis[10]{0};// 拆三组数 int nums[9]{a/100, a/10%10, a%10, b/100, b/10%10, b%10, c/100, c/10%10, c%10};for(int i0;i9;i){if(nums[i]0||vis[nums[i]])returnfalse;vis[nums[i]]1;}returntrue;}intmain(){for(int x100;x333;x){int ax;int b2* x;int c3* x;if(c999)break;if(check(a, b, c)){couta b c\n;}}return0;}2.洛谷|P1085#includebits/stdc.husing namespace std;intmain(){int n, m;int res0;int t0;for(int i0;i7;i){cinnm;intsumn m;if(sum8sumt){tsum;resi 1;}}coutres;return0;}3.洛谷|P1036#includebits/stdc.husing namespace std;int a[21];int n,k;int res0;bool prime(int x){if(x2)returnfalse;for(int i2;i * ix;i){if(x % i0)returnfalse;}returntrue;}void dfs(int start, int cnt, intsum){if(kcnt){if(prime(sum))res;return;}for(int istart;in;i){dfs(i1,cnt1,suma[i]);}}intmain(){cinnk;for(int i0;in;i){cina[i];}dfs(0,0,0);coutres;return0;}4.洛谷|P1115DP#includebits/stdc.husing namespace std;intmain(){int n;cinn;vectorinta(n);for(int i0;in;i)cina[i];int cura[0];int ansINT_MIN;for(int i1;in;i){curmax(a[i],a[i] cur);ansmax(ans,cur);}coutans;return0;}