G.枚举
基础知识
1.一般思路
枚举和模拟是没有什么算法可言的，按照题目说的意思去模拟一下即可，要求对语法代码的熟练度比较高。
解题思路：一般是先想一个暴力解法，如果时间复杂度过高，再考虑一下如何去优化，一般是思考能不能减少几重几次循环。实在想不出来，直接提交暴力做法，OI赛制中也能过部分分。
2.注意
所有枚举题目都需要注意两点：
①顺序：想办法去把答案枚举到，即想一个能不重不漏枚举所有答案的顺序。
②优化：对代码做一些等价变形，即想有没有什么性质能优化某些步骤，从而降低时间复杂度。
例题
一、连号区间数
1.解题思路：
（１）做题前一定要注意给的数据范围，通过数据范围递推出我们要写的代码时间复杂度。本题的范围是10000，所以复杂度最好控制在O(logn)之内，O(n*n)可能也行。
（２）暴力思路：
从头开始枚举每一段序列，对每一段序列进行排序，看看他是否是单调递增序列，如果是cnt++
#include <iostream>
#include <cstring>//memcpy()头文件
#include <algorithm>//sort()头文件
using namespace std;
const int N=10010;
int n;
int a[N];
int t[N];//辅助数组
int main()
{
cin>>n;
for(int i=1;i<=n;i++) cin>>a[i];
int cnt=0;
for(int i=1;i<=n;i++)
{
for(int j=i;j<=n;j++)
{
memcpy(t,a,sizeof a); // 这里要把数组的初始状态存在t数组中，因为每次sort排序后，数组的顺序会发生改变。
sort(a+i,a+j+1);//注意sort()的边界
bool flag=true;
for(int k=i;k<j;k++)
{
if(a[k+1]-a[k]!=1)
{
flag=false;
break;
}
}
if(flag)
{
cnt++;
}
memcpy(a,t,sizeof a); // 还原数组a的初始状态
}
}
cout<<cnt;
return 0;
}
注意几点：
①sort()函数的使用：
sort()有三个参数sort(begin, end, cmp)，其中begin为指向待sort()的数组的第一个元素的指针，end为指向待sort()的数组的最后一个元素的下一个位置的指针，cmp参数为排序准则，cmp参数可以不写，如果不写的话，默认从小到大进行排序。
②memcpy函数的使用：
这里要把数组的初始状态存在t数组中，因为每次sort排序后，数组的顺序会发生改变。
拷贝函数，memcpy函数的功能是从源src所指的内存地址的起始位置开始拷贝n个字节到目标所指的内存地址的起始位置中。三个参数：目的地址，源地址，所需要复制的字节数。
（３）暴力做法时间复杂度O(n^3logn)大于O(n^2)，所以只能过一部分的数据，但能得一部分得分数
（４）优化：将暴力中的sort和第三重循环优化，即如何快速的判读一个区间是不是连号区间？
排列性质：只要说是排列 ，那么序列中就不会出现重复的数
因为没有重复的数，并且区间内排序后为递增序列差值为1，因此可以转化为区间最大最小值作差等于区间长度，即max-min = j - i
区间[a,b]，若区间中max-min=b-a，且区间中有b-a+1个数，则说明该区间为连号区间（递增且连续）。
枚举的同时算一下最大值和最小值，时间复杂度优化为O(n^2)，虽然数据范围是10000，但是由于指令代码行数比较少，常数很小。当代码量很大时，一般常数就很大。
2.代码：
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 10010, INF = 100000000;
int n;
int a[N];
int main()
{
cin >> n;
for (int i = 0; i < n; i ++ ) cin >> a[i];
int res = 0;
for (int i = 0; i < n; i ++ ) // 枚举区间左端点
{
int minv = INF, maxv = -INF; //先定义最大值和最小值
for (int j = i; j < n; j ++ ) // 枚举区间右端点
{
minv = min(minv, a[j]);
maxv = max(maxv, a[j]); //枚举的同时算一下最大值和最小值，此时maxv和minv就是最大值和最小值
if (maxv - minv == j - i) res ++ ;
}
}
cout << res << endl;
return 0;
}
二、递增三元组
1.解题思路：
暴力做法：时间复杂度为O(n^3)
#include <iostream>
using namespace std;
const int N=100010;
int n;
int a[N],b[N],c[N];
int main()
{
cin>>n;
for(int i=0;i<n;i++) cin>>a[i];
for(int i=0;i<n;i++) cin>>b[i];
for(int i=0;i<n;i++) cin>>c[i];
int cnt=0;
for(int i=0;i<n;i++)
{
for(int j=0;j<n;j++)
{
for(int k=0;k<n;k++)
{
if(a[i]<b[j]&&b[j]<c[k])
cnt++;
}
}
}
cout<<cnt;
return 0;
}
优化：
通过数据范围逆推出该题的时间复杂度应该为O(n*logn)，所以最多只能枚举一个数组。
尝试通过枚举的次序进行优化本题，先枚举B数组，在A中寻找小于B[i]的数的个数cnt1，在C中寻找大于B[i]的数的个数cnt2，带有B[i]的合法选择数就是cnt1*cnt2。
如何查找呢？用暴力查找时间总的时间复杂度为O(n^2)，还是会超时。
方法一：前缀和
1、acnt[i]表示在A中i这个值出现多少次,ccnt[i]表示在C中i这个值出现多少次
2、关键的一步，通过s[]记录当前数组从1到i中,所有数出现的次数的前缀和
3、as[]记录在A中由多少个数小于B[i]，as[i] = s[b[i] - 1]
4、cs[]记录在C中由多少个数大于B[i], cs[i] = s[N - 1] - s[b[i]]
5、由于a[]和c[]互斥，通过乘法原理可得res += as[i] * cs[i]
方法二：sort+二分
方法三：双指针算法
2.代码：
//前缀和
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long LL;
const int N = 100010;
int n;
int a[N], b[N], c[N];
int as[N]; // as[i]表示在A[]中有多少个数小于b[i]
int cs[N]; // cs[i]表示在C[]中有多少个数大于b[i]
int cnt[N], s[N];
int main()
{
scanf("%d", &n);
for (int i = 0; i < n; i ++ ) scanf("%d", &a[i]), a[i] ++ ;
for (int i = 0; i < n; i ++ ) scanf("%d", &b[i]), b[i] ++ ;
for (int i = 0; i < n; i ++ ) scanf("%d", &c[i]), c[i] ++ ;
// 求as[]
for (int i = 0; i < n; i ++ ) cnt[a[i]] ++ ;
for (int i = 1; i < N; i ++ ) s[i] = s[i - 1] + cnt[i]; // 求cnt[]的前缀和
for (int i = 0; i < n; i ++ ) as[i] = s[b[i] - 1];
// 求cs[]
memset(cnt, 0, sizeof cnt);
memset(s, 0, sizeof s);
for (int i = 0; i < n; i ++ ) cnt[c[i]] ++ ;
for (int i = 1; i < N; i ++ ) s[i] = s[i - 1] + cnt[i];
for (int i = 0; i < n; i ++ ) cs[i] = s[N - 1] - s[b[i]];
// 枚举每个b[i]
LL res = 0;
for (int i = 0; i < n; i ++ ) res += (LL)as[i] * cs[i];
cout << res << endl;
return 0;
}
//sort+二分
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long lld;
const int N = 100005;
int a[N], b[N], c[N];
int n;
lld sum;
int main()
{
scanf("%d", &n);
for (int i = 1; i <= n; i++)
scanf("%d", &a[i]);
for (int i = 1; i <= n; i++)
scanf("%d", &b[i]);
for (int i = 1; i <= n; i++)
scanf("%d", &c[i]);
//由于二分的前提是单调序列 所以预先对a b c排序 直接sort
sort(a + 1, a + 1 + n);
sort(b + 1, b + 1 + n);
sort(c + 1, c + 1 + n);
for (int i = 1; i <= n; i++)
{
//直接用STL中的两个二分函数解决
lld x = (lower_bound(a + 1, a + 1 + n, b[i]) - a) - 1; //在数组a中找比b[i]小的数
lld y = n - (upper_bound(c + 1, c + 1 + n, b[i]) - c) + 1; //在数组c中找比b[i]大的数
sum += x * y;
}
printf("%lld", sum);
return 0;
}
参考题解：
AcWing 1236. 递增三元组 (二分+双指针+前缀和) - AcWing
三、回文日期
1.解题思路：
（1）数据范围八位数不是很大，所以方法有很多
考虑：①时间复杂度②空间复杂度③代码复杂度，只要在第一个和第二个能满足题意得清空下，要找一个最好写，代码量最少的做法。
我们可能会去试着暴力枚举这两个日期间的所有日期，然后再判断有多少个日期是回文的，但是这样的日期处理非常的复杂，且不确定性很高，要做很多的细节处理
（2）接着我们可以想到一个新的思路：构造枚举
①先枚举所有回文串日期：枚举所有8位数字组成的回文数（因为是回文的，所以只要枚举四位（因为不能含有前导零，所以就是枚举1000到9999）即可代替枚举8位）
②判断该回文数是否在我们考虑的范围内：直接拿数值判断即可。
③判断回文日期是否合法：如果在范围内，再判断该8位数是否是一个合法的有意义的日期
把年月日分别拆分出来，分别判断：因为枚举的是1000~9999，所以年份必然合法；月份要判断是不是在1~12之间；日子必须要>=1,并且要小于等于当月天数。最后要特判断一下是不是平年和闰年，平年和闰年的二月日子不同。
（3）注意：
如何判断日子是不是小于等于当前天数？
可以用一个数组将12个月份的天数提前存先下来，下标从1开始，利用桶的思想，直接判断这个数组对应的天数即可。（先不用管平年闰年，最后特判一下即可）
如何判断闰年？
①年份是可以被 400整除
②年份可以被4整除，并且不能被100整除
2.代码：
方法一：
时间复杂度：常数级别的，总计算量是 O(10^4)
#include<iostream>
using namespace std;
int days[13]={0,31,28,31,30,31,30,31,31,30,31,30,31}; //把1-12月的天数存下来
bool check_valid(int date)
{
int year=date/10000; //从date中拆分出年月日
int month=date%10000/100;
int day=date%100;
if(month==0||month>12) return false; //如果月份不合法，直接返回false
if(day==0||(month!=2&&day>days[month])) return false; //2月份特判，如果当前月份天数比实际的多，也不合法
if(month==2) //二月特判
{
int leap=(year%100&&year%4==0)||year%400==0; //若果是闰年的话，leap是1，否则是0
if(day>28+leap) return false; //这里一开始我写错了写成了！=,其实不合法的情况是出现的天数，大于是实际该有的，小于的话其实是合法的，不等于的条件判断太大了
}
return true;
}
int main()
{
int date1,date2;
cin>>date1>>date2;
int res=0;
for(int i=1000;i<10000;i++) //枚举1000-9999的所有四位数，构成所有可能的8位回文序列
{
int date=i,x=i;
for(int j=0;j<4;j++) date=date*10+x%10,x/=10; //造回文数,把i反过来再接到后面去
if(date>=date1&&date<=date2&&check_valid(date)) res++; //符合条件的才能算
}
printf("%d",res);
return 0;
}
方法二：枚举月和日，用月和日算出年和日期
时间复杂度：O(366)
#include<bits/stdc++.h>
using namespace std;
int a, b;
long long cnt = 0;
int days[] = {-1, 31, 29, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
int main(){
scanf("%d %d", &a, &b);
for(int month = 1; month <= 12; month ++){
for(int day = 1; day <= days[month]; day ++){
int year = 1000 * (day % 10) + 100 * (day / 10) + 10 * (month % 10) + month / 10;
int date = 10000 * year + 100 * month + day;
if(date >= a && date <= b) cnt ++;
}
}
printf("%d\n", cnt);
return 0;
}
方法三：打表
可以在自己本地写一个程序 比如枚举每一个日期来判断是不是回文日期，然后把这些回文日期存下来就行了。把想要的数据输出到文件里面，然后再从文件里面粘到另一个程序中，文件输出的时候可以for循环直接输出date[%d]=%d\n 这样的格式，之后直接复制过去就行了。
#include <iostream>
using namespace std;
int date[400];
int main(){
date[1]=10011001;
date[2]=10100101;
date[3]=10111101;
date[4]=10200201;
date[5]=10211201;
date[6]=10300301;
date[7]=10400401;
date[8]=10500501;
date[9]=10600601;
date[10]=10700701;
date[11]=10800801;
date[12]=10900901;
date[13]=11011011;
date[14]=11100111;
date[15]=11111111;
date[16]=11200211;
date[17]=11211211;
date[18]=11300311;
date[19]=11400411;
date[20]=11500511;
date[21]=11600611;
date[22]=11700711;
date[23]=11800811;
date[24]=11900911;
date[25]=12011021;
date[26]=12100121;
date[27]=12111121;
date[28]=12200221;
date[29]=12211221;
date[30]=12300321;
date[31]=12400421;
date[32]=12500521;
date[33]=12600621;
date[34]=12700721;
date[35]=12800821;
date[36]=12900921;
date[37]=13011031;
date[38]=13100131;
date[39]=13211231;
date[40]=13300331;
date[41]=13500531;
date[42]=13700731;
date[43]=13800831;
date[44]=20011002;
date[45]=20100102;
date[46]=20111102;
date[47]=20200202;
date[48]=20211202;
date[49]=20300302;
date[50]=20400402;
date[51]=20500502;
date[52]=20600602;
date[53]=20700702;
date[54]=20800802;
date[55]=20900902;
date[56]=21011012;
date[57]=21100112;
date[58]=21111112;
date[59]=21200212;
date[60]=21211212;
date[61]=21300312;
date[62]=21400412;
date[63]=21500512;
date[64]=21600612;
date[65]=21700712;
date[66]=21800812;
date[67]=21900912;
date[68]=22011022;
date[69]=22100122;
date[70]=22111122;
date[71]=22200222;
date[72]=22211222;
date[73]=22300322;
date[74]=22400422;
date[75]=22500522;
date[76]=22600622;
date[77]=22700722;
date[78]=22800822;
date[79]=22900922;
date[80]=30011003;
date[81]=30100103;
date[82]=30111103;
date[83]=30200203;
date[84]=30211203;
date[85]=30300303;
date[86]=30400403;
date[87]=30500503;
date[88]=30600603;
date[89]=30700703;
date[90]=30800803;
date[91]=30900903;
date[92]=31011013;
date[93]=31100113;
date[94]=31111113;
date[95]=31200213;
date[96]=31211213;
date[97]=31300313;
date[98]=31400413;
date[99]=31500513;
date[100]=31600613;
date[101]=31700713;
date[102]=31800813;
date[103]=31900913;
date[104]=32011023;
date[105]=32100123;
date[106]=32111123;
date[107]=32200223;
date[108]=32211223;
date[109]=32300323;
date[110]=32400423;
date[111]=32500523;
date[112]=32600623;
date[113]=32700723;
date[114]=32800823;
date[115]=32900923;
date[116]=40011004;
date[117]=40100104;
date[118]=40111104;
date[119]=40200204;
date[120]=40211204;
date[121]=40300304;
date[122]=40400404;
date[123]=40500504;
date[124]=40600604;
date[125]=40700704;
date[126]=40800804;
date[127]=40900904;
date[128]=41011014;
date[129]=41100114;
date[130]=41111114;
date[131]=41200214;
date[132]=41211214;
date[133]=41300314;
date[134]=41400414;
date[135]=41500514;
date[136]=41600614;
date[137]=41700714;
date[138]=41800814;
date[139]=41900914;
date[140]=42011024;
date[141]=42100124;
date[142]=42111124;
date[143]=42200224;
date[144]=42211224;
date[145]=42300324;
date[146]=42400424;
date[147]=42500524;
date[148]=42600624;
date[149]=42700724;
date[150]=42800824;
date[151]=42900924;
date[152]=50011005;
date[153]=50100105;
date[154]=50111105;
date[155]=50200205;
date[156]=50211205;
date[157]=50300305;
date[158]=50400405;
date[159]=50500505;
date[160]=50600605;
date[161]=50700705;
date[162]=50800805;
date[163]=50900905;
date[164]=51011015;
date[165]=51100115;
date[166]=51111115;
date[167]=51200215;
date[168]=51211215;
date[169]=51300315;
date[170]=51400415;
date[171]=51500515;
date[172]=51600615;
date[173]=51700715;
date[174]=51800815;
date[175]=51900915;
date[176]=52011025;
date[177]=52100125;
date[178]=52111125;
date[179]=52200225;
date[180]=52211225;
date[181]=52300325;
date[182]=52400425;
date[183]=52500525;
date[184]=52600625;
date[185]=52700725;
date[186]=52800825;
date[187]=52900925;
date[188]=60011006;
date[189]=60100106;
date[190]=60111106;
date[191]=60200206;
date[192]=60211206;
date[193]=60300306;
date[194]=60400406;
date[195]=60500506;
date[196]=60600606;
date[197]=60700706;
date[198]=60800806;
date[199]=60900906;
date[200]=61011016;
date[201]=61100116;
date[202]=61111116;
date[203]=61200216;
date[204]=61211216;
date[205]=61300316;
date[206]=61400416;
date[207]=61500516;
date[208]=61600616;
date[209]=61700716;
date[210]=61800816;
date[211]=61900916;
date[212]=62011026;
date[213]=62100126;
date[214]=62111126;
date[215]=62200226;
date[216]=62211226;
date[217]=62300326;
date[218]=62400426;
date[219]=62500526;
date[220]=62600626;
date[221]=62700726;
date[222]=62800826;
date[223]=62900926;
date[224]=70011007;
date[225]=70100107;
date[226]=70111107;
date[227]=70200207;
date[228]=70211207;
date[229]=70300307;
date[230]=70400407;
date[231]=70500507;
date[232]=70600607;
date[233]=70700707;
date[234]=70800807;
date[235]=70900907;
date[236]=71011017;
date[237]=71100117;
date[238]=71111117;
date[239]=71200217;
date[240]=71211217;
date[241]=71300317;
date[242]=71400417;
date[243]=71500517;
date[244]=71600617;
date[245]=71700717;
date[246]=71800817;
date[247]=71900917;
date[248]=72011027;
date[249]=72100127;
date[250]=72111127;
date[251]=72200227;
date[252]=72211227;
date[253]=72300327;
date[254]=72400427;
date[255]=72500527;
date[256]=72600627;
date[257]=72700727;
date[258]=72800827;
date[259]=72900927;
date[260]=80011008;
date[261]=80100108;
date[262]=80111108;
date[263]=80200208;
date[264]=80211208;
date[265]=80300308;
date[266]=80400408;
date[267]=80500508;
date[268]=80600608;
date[269]=80700708;
date[270]=80800808;
date[271]=80900908;
date[272]=81011018;
date[273]=81100118;
date[274]=81111118;
date[275]=81200218;
date[276]=81211218;
date[277]=81300318;
date[278]=81400418;
date[279]=81500518;
date[280]=81600618;
date[281]=81700718;
date[282]=81800818;
date[283]=81900918;
date[284]=82011028;
date[285]=82100128;
date[286]=82111128;
date[287]=82200228;
date[288]=82211228;
date[289]=82300328;
date[290]=82400428;
date[291]=82500528;
date[292]=82600628;
date[293]=82700728;
date[294]=82800828;
date[295]=82900928;
date[296]=90011009;
date[297]=90100109;
date[298]=90111109;
date[299]=90200209;
date[300]=90211209;
date[301]=90300309;
date[302]=90400409;
date[303]=90500509;
date[304]=90600609;
date[305]=90700709;
date[306]=90800809;
date[307]=90900909;
date[308]=91011019;
date[309]=91100119;
date[310]=91111119;
date[311]=91200219;
date[312]=91211219;
date[313]=91300319;
date[314]=91400419;
date[315]=91500519;
date[316]=91600619;
date[317]=91700719;
date[318]=91800819;
date[319]=91900919;
date[320]=92011029;
date[321]=92100129;
date[322]=92111129;
date[323]=92200229;
date[324]=92211229;
date[325]=92300329;
date[326]=92400429;
date[327]=92500529;
date[328]=92600629;
date[329]=92700729;
date[330]=92800829;
date[331]=92900929;
int day1,day2,ans=0;
cin>>day1>>day2;
for(int i=1;i<=331;i++){
if(day2>=date[i]&&day1<=date[i]) ans++;
}
cout<<ans<<endl;
return 0;
}
参考题解：
四、日期问题
1.解题思路：
构造枚举顺序：19600101~20591231，看成是八位数，对于每个日期拆分成年月日，判断是否合法，判断这个八位数是否和给定的表示相同，如果是输出。
枚举19600101~20591231八位数
①对于每个日期判断是否合法
②对于每个日期判断它的三种表示是否和给定表示相同
2.代码：
//构造枚举
#include <cstdio>//scanf头文件
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
int days[13] = {0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
bool check_valid(int year, int month, int day)
{
if (month == 0 || month > 12) return false;
if (day == 0) return false;
if (month != 2)
{
if (day > days[month]) return false;
}
else
{
int leap = year % 100 && year % 4 == 0 || year % 400 == 0;//判断闰年表达式
if (day > 28 + leap) return false;
}
return true;
}
int main()
{
int a, b, c;
scanf("%d/%d/%d", &a, &b, &c);//注意输入格式
for (int date = 19600101; date <= 20591231; date ++ )
{
int year = date / 10000, month = date % 10000 / 100, day = date % 100;
if (check_valid(year, month, day))//判断年、月、日是否合法
{
//判断三种表示方式是否和给定格式a,b,c相等
if (year % 100 == a && month == b && day == c || // 年/月/日
month == a && day == b && year % 100 == c || // 月/日/年
day == a && month == b &&year % 100 == c) // 日/月/年
printf("%d-%02d-%02d\n", year, month, day);
}
}
return 0;
}
3.注意：
字符串处理时习惯用scanf，printf输入输出。scanf，printf为格式化输入输出，cin，cout为流式输出
scanf("%d/%d/%d", &a, &b, &c);
sscanf是从字符串当中格式化输入，scanf是指从标准读入格式化读入，场景用的不一样，但本质上是一个东西。
printf输出时，不足补零
printf("%d-%02d-%02d\n", year, month, day);
CSDN链接： https://blog.csdn.net/qq_46009744/article/details/123877381?spm=1001.2014.3001.5502
