连号区间数
算法原理
暴力
三重循环，第一重枚举左端点 i ，第二重枚举右端点 j ，第三重枚举区间 [ i , j ] 三重循环，第一重枚举左端点i，第二重枚举右端点j，第三重枚举区间[i, j]三重循环，第一重枚举左端点i，第二重枚举右端点j，第三重枚举区间[i,j]
有不是连续的数， b r e a k ; 否则 r e s + + 有不是连续的数，break;否则res ++有不是连续的数，break;否则res++
时间复杂度： O ( n 3 l o g n ) 时间复杂度：O(n^3logn)时间复杂度：O(n3logn)
#include <iostream> #include <cstring> #include <algorithm> using namespace std; const int N = 1e4 + 10; int n; int p[N], b[N]; int res; int main() { cin >> n; for (int i = 1; i <= n; i ++) cin >> p[i]; for (int i = 1; i <= n; i ++) // 左端点 for (int j = i; j <= n; j ++) { // 右端点 memcpy(b, p, sizeof p); sort(b + i, b + j + 1); bool flag = true; for (int k = i; k < j; k ++) // 区间[i, j] if (b[k + 1] - b[k] != 1) { flag = false; break; } if (flag) res ++; } cout << res; return 0; }
100 分 ( 满分 ) 做法： 100分(满分)做法：100分(满分)做法：
枚举
1 、两重循环，第一重枚举左端点 i ，第二重枚举右端点 j ，同时不断确定 [ i , j ] 的最大 , 最小值 1、两重循环，第一重枚举左端点i，第二重枚举右端点j，同时不断确定[i, j]的最大,最小值1、两重循环，第一重枚举左端点i，第二重枚举右端点j，同时不断确定[i,j]的最大,最小值
2 、如果 m a x 1 − m i n 1 = = j − i ， r e s + + 2、如果max1 - min1 == j - i，res ++2、如果max1−min1==j−i，res++
( 由于所给的 n 个数是 1 到 n 的全排列，所以不会出现重复的数 ) (由于所给的n个数是1到n的全排列，所以不会出现重复的数)(由于所给的n个数是1到n的全排列，所以不会出现重复的数)
时间复杂度： O ( n 2 ) 时间复杂度：O(n^2)时间复杂度：O(n2)
#include <iostream> #include <cstring> #include <algorithm> using namespace std; const int N = 1e4 + 10, INF = 1e8; int n; int p[N]; int res; int main() { cin >> n; for (int i = 0; i < n; i ++) cin >> p[i]; for (int i = 0; i < n; i ++) { // 左端点 int max1 = -INF, min1 = INF; for (int j = i; j < n; j ++) { // 右端点 max1 = max(max1, p[j]); min1 = min(min1, p[j]); if (max1 - min1 == j - i) res ++; } } cout << res; return 0; }
递增三元组
算法原理
题目分析
首先考虑暴力做法，三个数组嵌套枚举，O ( n 3 ) O(n^3)O(n3)的时间复杂度，n ≤ 1 0 5 n≤10^5n≤105一定会超时。
尝试通过枚举的次序进行优化本题，先枚举B数组，在A中寻找小于B[i]的数的个数cnt1，在C中寻找大于B[i]的数的个数cnt2，带有B[i]的合法选择数就是cnt1*cnt2。
用暴力查找时间总的时间复杂度为O ( n 2 ) O(n^2)O(n2)，还是会超时。
二分
既然是查找，那么可以考虑进行二分查找，查找前先通过排序预处理三个数组，排序时间复杂度O ( n l o g 2 n ) O(nlog_2n)O(nlog2n),枚举B的所有元素+查找A,C中的元素时间复杂度也是O ( n l o g 2 n ) O(nlog_2n)O(nlog2n)，总的时间复杂度降为O ( n l o g 2 n ) O(nlog_2n)O(nlog2n)
#include <iostream> #include <cstdio> #include <algorithm> using namespace std; typedef long long LL; const int N = 1e5+10; int num[3][N]; int main() { int n; scanf("%d", &n); for(int i = 0; i < 3; ++i) for(int j = 1; j <= n; ++j) scanf("%d", &num[i][j]); for(int i = 0; i < 3; ++i) sort(num[i]+1, num[i]+n+1); LL ans = 0; //枚举B，寻找A满足的个数以及C满足的个数相乘 for(int i = 1; i <= n; ++i) { int key = num[1][i]; //A中二分查找第一个小于key的数的下标 int pos1 = lower_bound(num[0]+1, num[0]+n+1, key)-num[0]-1; //C中二分查找第一个大于key的数的下标 int pos2 = upper_bound(num[2]+1, num[2]+n+1, key)-num[2]; if(pos1 >= 1 && pos2 <= n) { ans += (LL)pos1*(n-pos2+1); } } cout<<ans<<endl; return 0; }
双指针
进一步对查找进行优化，对于排过序的数组A和B，寻找A中小于B[i]的元素的个数可以考虑双指针算法，因为每个指针最多移动n次，故查找的时间复杂度降到O(n)，查找C与查找A同理，只是找第一个大于B的位置。
只需要将上述二分程序中的
//二分 for(int i = 1; i <= n; ++i) { int key = num[1][i]; //A中二分查找第一个小于key的数的下标 int pos1 = lower_bound(num[0]+1, num[0]+n+1, key)-num[0]-1; //C中二分查找第一个大于key的数的下标 int pos2 = upper_bound(num[2]+1, num[2]+n+1, key)-num[2]; if(pos1 >= 1 && pos2 <= n) { ans += (LL)pos1*(n-pos2+1); } }
更改为
//双指针 int a = 1, c = 1; for(int i = 1; i <= n; ++i) { int key = num[1][i]; while(a<=n && num[0][a] < key) a++; while(c<=n && num[2][c] <= key) c++; ans += (LL)(a-1)*(n-c+1); }
完整的双指针程序为：
#include <iostream> #include <cstdio> #include <algorithm> using namespace std; typedef long long LL; const int N = 1e5+10; int num[3][N]; int main() { int n; scanf("%d", &n); for(int i = 0; i < 3; ++i) for(int j = 1; j <= n; ++j) scanf("%d", &num[i][j]); for(int i = 0; i < 3; ++i) sort(num[i]+1, num[i]+n+1); LL ans = 0; //枚举B，寻找A满足的个数以及C满足的个数相乘 int a = 1, c = 1; for(int i = 1; i <= n; ++i) { int key = num[1][i]; while(a<=n && num[0][a] < key) a++; while(c<=n && num[2][c] <= key) c++; ans += (LL)(a-1)*(n-c+1); } cout<<ans<<endl; return 0; }
前缀和
之前的双指针算法时间复杂度的瓶颈为：排序O ( n l o g 2 n ) O(nlog_2n)O(nlog2n)
考虑是否可以不排序在O(n)的时间内解决此问题呢？
既然要排序实现快速的查找A中小于B[i]的数的个数，可以将数组A中所有元素出现的次数存入一个哈希表中，因为数组中元素的范围只有n 5 n^5n5, 可以开一个大的数组cnta 作为哈希表。
在枚举B中元素时，我们需要快速查找找小于B[i]的所有元素的总数，只需要在枚举之前先将求出表中各数的前缀和即可。
查找C与查找A同理可得。
代码实现
//前缀和 #include <iostream> #include <cstdio> using namespace std; typedef long long LL; const int N = 1e5+10; int A[N], B[N], C[N]; int cnta[N], cntc[N], sa[N], sc[N]; int main() { int n; scanf("%d", &n); //获取数i在A中有cntc[i]个，并对cnt求前缀和sa for(int i = 1; i <= n; ++i) { scanf("%d", &A[i]); cnta[++A[i]]++; } sa[0] = cnta[0]; for(int i = 1; i < N; ++i) sa[i] = sa[i-1]+cnta[i]; //B只读取即可 for(int i = 1; i <= n; ++i) scanf("%d", &B[i]), B[i]++; //获取数i在C中有cntc[i]个，并对cnt求前缀和sc for(int i = 1; i <= n; ++i) { scanf("%d", &C[i]); cntc[++C[i]]++; } sc[0] = cntc[0]; for(int i = 1; i < N; ++i) sc[i] = sc[i-1]+cntc[i]; //遍历B求解 LL ans = 0; for(int i = 1; i <= n; ++i) { int b = B[i]; ans += (LL)sa[b-1] * (sc[N-1] - sc[b]); } cout<<ans<<endl; return 0; }
特别数的和
算法原理
常用小技巧：关于取出x的每位数字 和 将字符数字转为数字
1.取出x的每位数字
int t = x % 10; x /= 10;
2.将字符数字转为数字
int x = 0; for (int i = 0; i < str.size(); i ++ ) x = x * 10 + str[i] - '0';
代码实现：
#include<iostream> #include<algorithm> using namespace std; int main() { int n; cin >> n; int res = 0; for (int i = 1; i <= n; i ++ ) { int x = i; while(x) { int t = x % 10; // 取出x的个位数 x /= 10; // 取它的上一位 if (t == 0 || t == 2 || t == 1 || t == 9) { res += i; break; } } } cout << res << endl; return 0; }
错误票据
某涉密单位下发了某种票据，并要在年终全部收回。
每张票据有唯一的ID号。
全年所有票据的ID号是连续的，但ID的开始数码是随机选定的。
因为工作人员疏忽，在录入ID号的时候发生了一处错误，造成了某个ID断号，另外一个ID重号。
你的任务是通过编程，找出断号的ID和重号的ID。
假设断号不可能发生在最大和最小号。
输入格式
第一行包含整数 N，表示后面共有 N 行数据。
接下来 N 行，每行包含空格分开的若干个（不大于100个）正整数（不大于100000），每个整数代表一个ID号。
输出格式
要求程序输出1行，含两个整数 m,n，用空格分隔。
其中，m表示断号ID， n 表示重号ID。
数据范围
1≤N≤100
样例
blablabla
思路
找出最大和最小的数，同时再用一个数组记录每个数字的个数，最后遍历一遍即可
代码实现
#include <iostream> #include <cstdio> #include <cstring> #include <algorithm> using namespace std; const int M=100010; int cnt[M]; int main() { int line,Min=100001,Max=0,a; int n,m; //m表示断号ID，n表示重号ID cin>>line; while(line--) { while(cin>>a) { cnt[a]++; Max=max(Max,a); Min=min(Min,a); } } for(int j=Min;j<=Max;j++) { if(cnt[j]==0) m=j; else if(cnt[j]==2) n=j; } cout<<m<<" "<<n<<endl; return 0; }
回文日期
算法原理
(枚举,模拟) O ( 1 0 4 ) O(10^4)O(104)
由于只有八位数，而且回文串左右对称，因此可以只枚举左半边，这样只需枚举 0 ∼ 9999 0 \sim 99990∼9999 总共一万个数，然后判断：
- 整个八位数构成的日期是否合法；
- 是否在范围内
时间复杂度
一共枚举 1 0 4 10^4104 个数，判断每个数是否合法的计算量是常数级别的，因此总计算量是 O ( 1 0 4 ) O(10^4)O(104)。
代码实现
#include <cstdio> #include <cstring> #include <iostream> #include <algorithm> using namespace std; int months[13] = {0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31}; bool check(int date) { int year = date / 10000; int month = date % 10000 / 100; int day = date % 100; if (!month || month >= 13 || !day) return false; if (month != 2 && day > months[month]) return false; if (month == 2) { bool leap = year % 4 == 0 && year % 100 || year % 400 == 0; if (day > 28 + leap) return false; } return true; } int main() { int date1, date2; cin >> date1 >> date2; int res = 0; for (int i = 0; i < 10000; i ++ ) { int x = i, r = i; for (int j = 0; j < 4; j ++ ) r = r * 10 + x % 10, x /= 10; if (r >= date1 && r <= date2 && check(r)) res ++ ; } printf("%d\n", res); return 0; }
日期问题
算法原理
题目思路
首先我们要知道判断闰年的方法：
如果是 4 44 的倍数，该年份一般是闰年；如果不是 4 44 的倍数，该年份一般是平年。
公历年份是整百数的必须是 400 400400 的倍数才是闰年，反之则是平年。
用 C + + 实现就是： 用C++实现就是：用C++实现就是：
int year = 1234; //定义变量年 if (year % 4 == 0 && year % 100 != 0 || year % 400 == 0) return true; //闰年判断 else return false;
暴搜方法就可以解决。
首先输入a ， b ， c a，b，ca，b，c，然后与年月日，月日年，日月年相比较就可以。
代码实现
# include <bits/stdc++.h> using namespace std; int M[13] = {0,31,28,31,30,31,30,31,31,30,31,30,31}; bool check(int Year, int Month , int Day) { if (Month < 1 || Month >= 13) return false; if (Day == 0) return false; if (Month != 2) { if (Day > M[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 i = 19600101; i <= 20591231; i ++) { int year = i / 10000; int month = i%10000 / 100; int day = i % 100; if(check(year, month, day) == true) { if(( a== year%100) && (month == b) && (day == c) || (a==month) && (b==day)&& (c==year%100) || (a==day) && (b==month) && (c==year%100)){ printf("%d-%02d-%02d\n",year,month,day); } } } return 0; }
航班时间
算法原理
去乘起飞时间+航行时间+时差=去乘降落时间 (公式一)
回程起飞时间+航行时间-时差=回程降落时间 (公式二)
求:航行时间
已知:去乘起飞时间,回程起飞时间,去乘降落时间,回程降落时间
根据公式一+公式二:
去乘起飞时间+回程起飞时间+2*航行时间=去乘降落时间+回程降落时间
航行时间=(去乘降落时间-去乘起飞时间+回程降落时间-回程起飞时间)/2
这是求飞机飞行时间的推导，而本题，对于读入数据的处理也同样重要！！
这里的输入很恶心人，所以这里为了处理更加方便，将所有的时间都转化为当天零点到该时间的秒数，这样就很方便的可以进行计算了
在输出答案的时候，还需要将 秒数再转化为时间数：这个处理与 上一题类似。
//秒数：24*3600 int hours = time / 3600; int minutes = time % 3600 / 60; int seconds = time % 60;
在处理输入的时候，还是有很多地方需要注意的！
代码：
#include <iostream> #include <cstdio> #include <cstring> #include <algorithm> using namespace std; //得到该时间到该天零点的秒数 int get_second(int h,int m,int s) { return h*3600+m*60+s; } //读入数据 int get_time() { string line; //读入第一行数据 getline(cin,line); if(line.back()!=')') { //如果最后超过一天 line+="(+0)"; } //分别表示小时 分钟 秒数 和跨越的天数 int h1,m1,s1,h2,m2,s2,d; //sscanf：从字符串读取格式化输入 sscanf(line.c_str(),"%d:%d:%d %d:%d:%d (+%d)",&h1,&m1,&s1,&h2,&m2,&s2,&d); //得到秒数 return get_second(h2,m2,s2)-get_second(h1,m1,s1)+d*24*3600; } int main() { int n; scanf("%d",&n); string line; getline(cin,line); //先读掉输入n 后面的那个回车 while(n--) { int time=(get_time()+get_time())/2; int hour=time/3600; //获取前面小时数 int minte=time%3600/60; //先获得后面的分钟和秒数，再从中获得分钟数 int second=time%60; //获得后面的秒数 printf("%02d:%02d:%02d\n",hour,minte,second); } return 0; }
