连号区间
思路：
1.暴力思路：枚举起始、终止位置；对子区间排序；依次判断相邻位置是否差1.
- 时间复杂度(O(n^3log^n)),显然需要优化
2.优化 - 性质：子序列中max - min == r - l
代码：
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 10010;
int a[N];
int n;
int main(void)
{
cin >> n;
for(int i = 0; i < n;i++)
cin >> a[i];
//性质:最大值 - 最小值 == 数的个数 - 1
int ans = 0;
for(int i = 0; i < n; i++)
{
int maxv = -N, minv = N;
for(int j = i; j < n; j++)
{
maxv = max(maxv, a[j]);
minv = min(minv, a[j]);
if(maxv - minv == j - i) ans++;
}
}
cout << ans << endl;
return 0;
}
递增三元组
思路：
1.暴力：三重循环找出对于每一个A，满足条件的B的个数，对于每一个B，满足条件的C个个数，然后相乘。
- 时间复杂度(O(n^3)),需要优化
2.本题最关键的是因为枚举A或C，则其余两个都会有联系，而枚举B，则A、C之间没有联系，可以使用乘法原理 - 枚举每一个B，找出满足条件的A、C，然后相乘
- 时间复杂度(O(n^2)),还是会超时，需要优化到(O(n))或(O(nlog^n))
3.排序+二分 (O(nlog^n)) - 对A、C进行排序，然后使用二分法，找出满足条件的A、C
4.前缀和-mark-(O(n))
-使用数组cnt分别统计A、C中每一个数字出现的次数
-计算数组cnt的前缀和数组s,则s[i]表示小于i的所有数的个数
代码1-二分：
#include <cstring>
#include <cstdio>
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long LL;
const int N = 100010;
int a[N],b[N],c[N];
LL ans,res;
int main(void)
{
int n;
cin >> n;
for(int i = 1; i <= n; i++) scanf("%d", &a[i]), a[i]++;
for(int i = 1; i <= n; i++) scanf("%d", &b[i]), b[i]++;
for(int i = 1; i <= n; i++) scanf("%d", &c[i]), c[i]++;
// 排序 + 二分
sort(a + 1,a + n + 1);
sort(c + 1,c + n + 1);
for(int i = 1; i <= n; i++)
{
int l = 1, r = n;
//寻找a[l] < b[i]
while(l < r)
{
int mid = l + r + 1 >> 1;
if(a[mid] < b[i])
l = mid;
else
r = mid - 1;
}
int anum = l;
//边界判断
if(b[i] <= a[1])
anum = 0;
//寻找c[l] > b[i]
l = 1; r = n;
while(l < r)
{
int mid = l + r >> 1;
if(c[mid] > b[i])
r = mid;
else
l = mid + 1;
}
int cnum = n - l + 1;
//边界判断
if(b[i] >= c[n])
cnum = 0;
res += (LL)anum * cnum;
}
cout << res << endl;
return 0;
}
代码2 -前缀和
#include <cstring>
#include <cstdio>
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long LL;
const int N = 100010;
int a[N],b[N],c[N];
int cnt[N],as[N],cs[N];
LL ans,res;
int main(void)
{
int n;
cin >> n;
for(int i = 1; i <= n; i++) scanf("%d", &a[i]), a[i]++;
for(int i = 1; i <= n; i++) scanf("%d", &b[i]), b[i]++;
for(int i = 1; i <= n; i++) scanf("%d", &c[i]), c[i]++;
//前缀和
for(int i = 1; i <= n; i++) cnt[a[i]]++;
for(int i = 1; i < N; i++) as[i] = as[i-1] + cnt[i];
memset(cnt,0, sizeof(cnt));
for(int i = 1; i <= n; i++) cnt[c[i]]++;
for(int i = 1; i < N; i++) cs[i] = cs[i-1] + cnt[i];
for(int i = 1; i <= n; i++)
ans += (LL)as[b[i]-1] * (cs[N-1] - cs[b[i]]); //如果不加强制类型转换(LL),答案会错误
cout << ans << endl;
return 0;
}
强调：
res += (LL)anum * cnum;
如果不进行强制类型转化，那么在乘积爆int的情况下就会计算出错
回文日期
在日常生活中，通过年、月、日这三个要素可以表示出一个唯一确定的日期。
牛牛习惯用 8 位数字表示一个日期，其中，前 4 位代表年份，接下来 2 位代表月份，最后 2 位代表日期。
显然：一个日期只有一种表示方法，而两个不同的日期的表示方法不会相同。
牛牛认为，一个日期是回文的，当且仅当表示这个日期的8位数字是回文的。
现在，牛牛想知道：在他指定的两个日期之间（包含这两个日期本身），有多少个真实存在的日期是回文的。
一个 8 位数字是回文的，当且仅当对于所有的 i(1≤i≤8) 从左向右数的第i个数字和第 9−i 个数字（即从右向左数的第 i 个数字）是相同的。
例如：
•对于2016年11月19日，用 8 位数字 20161119 表示，它不是回文的。
•对于2010年1月2日，用 8 位数字 20100102 表示，它是回文的。
•对于2010年10月2日，用 8 位数字 20101002 表示，它不是回文的。
输入格式
输入包括两行，每行包括一个8位数字。
第一行表示牛牛指定的起始日期date1，第二行表示牛牛指定的终止日期date2。保证date1和date2都是真实存在的日期，且年份部分一定为4位数字，且首位数字不为0。
保证date1一定不晚于date2。
输出格式
输出共一行，包含一个整数，表示在date1和date2之间，有多少个日期是回文的。
思路：
1.对于日期问题，一般的做法是：
- 枚举范围内的所有符合条件的数字
- 判断是不是一个日期，判断是否满足每个月份的天数要求
代码：
#include <cstring>
#include <cstdio>
#include <iostream>
using namespace std;
int days[13] = {0, 31 , 28, 31, 30 , 31, 30, 31, 31 , 30, 31, 30, 31};
int date1,date2;
bool check(int date)
{
int year = date / 10000;
int mouth = date / 100 % 100;
int day = date % 100;
if(mouth == 0 || mouth > 12) return false;
if(day == 0 || mouth != 2 && day > days[mouth]) return false;
//判断闰年 + 特判二月
int is = year % 100 && year % 4 == 0 || year % 400 == 0;
if(day > days[mouth] + is) return false;
return true;
}
int main(void)
{
cin >> date1 >> date2;
int ans = 0;
//枚举回文数
for(int i = 1000; i < 9999; i++)
{
int date = i, x = i;
for(int j = 0; j < 4;j++) date = date * 10 + x % 10, x /= 10;
//判断是否符合日期范围,是否是合法日期
if(date >= date1 && date <= date2 && check(date)) ans++;
}
cout << ans << endl;
return 0;
}
日期问题
小明正在整理一批历史文献。这些历史文献中出现了很多日期。
小明知道这些日期都在1960年1月1日至2059年12月31日。
令小明头疼的是，这些日期采用的格式非常不统一，有采用年/月/日的，有采用月/日/年的，还有采用日/月/年的。
更加麻烦的是，年份也都省略了前两位，使得文献上的一个日期，存在很多可能的日期与其对应。
比如02/03/04，可能是2002年03月04日、2004年02月03日或2004年03月02日。
给出一个文献上的日期，你能帮助小明判断有哪些可能的日期对其对应吗？
输入格式
一个日期，格式是”AA/BB/CC”。
即每个’/’隔开的部分由两个 0-9 之间的数字（不一定相同）组成。
输出格式
输出若干个不相同的日期，每个日期一行，格式是”yyyy-MM-dd”。
多个日期按从早到晚排列。
数据范围
(0≤A,B,C≤9)
代码：
#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
int days[13] = {0, 31 , 28, 31, 30 , 31, 30, 31, 31 , 30, 31, 30, 31};
bool check(int year ,int mouth, int day)
{
if(mouth > 12 ||mouth == 0 || day > 31 || day == 0) return false;
if(mouth != 2 && day > days[mouth]) return false;
int is = year % 100 && year % 4 == 0 || year % 400 == 0;
if(mouth == 2 && day > days[mouth] + is) return false;
return true;
}
int main(void)
{
int a,b,c;
scanf("%d/%d/%d",&a,&b,&c); //使用scanf可以规定读入格式
for(int date = 19600101 ; date <= 20591231; date ++)
{
int year = date / 10000, mouth = (date / 100) % 100, day = date % 100;
if(check(year, mouth, day))
if(year % 100 == a && mouth == b && day == c ||
year % 100 == c && mouth == a && day == b ||
year % 100 == c && mouth == b && day == a)
printf("%d-%02d-%02d
", year, mouth, day); //以两位输出整数,如果不足两位,则使用前导0补充
}
return 0;
}
注意：
使用scanf和printf模拟输入和输出格式
外卖店的优先级
思路：
1.暴力：对时间遍历，枚举对应时间的订单，每一次都需要对所有店铺操作，显然超时
2.优化：最费时的部分是对没有订单的店铺-1；
- 所以可以通过排序，将同一家店铺的订单按照时间排序，这样在两次订单时间间隔-1，可以通过一次操作完成。
代码：
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
typedef pair<int, int> PII;
const int N = 100010;
int cnt[N],last[N];
bool st[N];
PII dat[N];
int main(void)
{
int n,m,t;
cin >> n >> m >> t;
for(int i = 0; i < m;i++)
scanf("%d%d", &dat[i].first, &dat[i].second); //id + t
//sort对pair，默认按照第一个元素升序，相同按照第二个元素升序
sort(dat, dat + m);
for(int i = 0; i < m;)
{
int j = i;
while(j < m && dat[i] == dat[j]) j++; //统计id t都相同的个数
int tim = dat[i].first, id = dat[i].second, num = j - i;
i = j;
cnt[id] -= tim - last[id] - 1;
if (cnt[id] < 0) cnt[id] = 0;
if (cnt[id] <= 3) st[id] = false;
cnt[id] += num * 2;
if (cnt[id] > 5) st[id] = true;
last[id] = tim;
}
//从最后一次订单到t时刻的降级
for(int i = 1; i <= n; i++)
{
cnt[i] -= t - last[i];
if (cnt[i] <= 3) st[i] = false;
}
int ans = 0;
for(int i = 1; i <= n;i++)
if(st[i])
ans++;
cout << ans << endl;
return 0;
}