回文日期
原文链接：https://www.acwing.com/problem/content/468/
由于只有八位数，而且回文串左右对称，因此可以只枚举左半边。然后判断：
- 整个八位数日期是否合法
- 是否在范围内
一共枚举1e4个数。判断过程是常数级别的，所以总计算量是
代码中的check属于基操。
代码语言：javascript复制#include"bits/stdc .h"
using namespace std;
int date1, date2;
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 res = 0;
cin >> date1 >> date2;
for (int i = date1 / 1e4; i < date2 / 1e4; i ) {
int date = i, tmp = i;
for (int j = 0; j < 4; j )date = date * 10 tmp % 10, tmp /= 10;
if (date >= date1 && date <= date2 && check(date))res ;
}
cout << res << endl;
return 0;
}参考
- https://www.acwing.com/solution/content/3897/
日期问题
原题链接：https://www.acwing.com/problem/content/1231/
真就是在枚举。
代码语言：javascript复制#include"bits/stdc .h"
using namespace std;
int days[13] = {0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
int check(int year, int month, int day) {
if (month > 12 || month < 1)return false;
if (day == 0)return false;
if (month != 2) {
if (day > days[month])return false;
} else {
int leap = year % 4 == 0 && year % 100 || year % 400 == 0;
if (day > 28 leap)return false;
}
return true;
}
int a, b, c;
int main() {
scanf("%d/%d/%d", &a, &b, &c);
for (int date = 19600101; date <= 20591231; date ) {
int year = date / 10000, month = date / 100 % 100, day = date % 100;
if (check(year, month, day)) {
if (year % 100 == a && month == b && day == c ||
month == a && day == b && year % 100 == c ||
day == a && month == b && year % 100 == c) {
printf("%d-d-dn", year, month, day);
}
}
}
return 0;
}航班时间
原题链接：https://www.acwing.com/problem/content/1233/
不知道时差是多少，要求真实的飞行时间。 去的时候，从东向西，减时差：
- 飞行时间=起降时间之差-时差
回的时候，从西向东，加时差：
- 飞行时间=起降时间之差 时差
两式作和，然后除以二，就可以求出飞行时间。
- 将所有时间转换成距离当天
00:00:00的秒数。 - 按行读入，对于行末可能有也可能没有的
()，格式化统一处理。
cin和scanf都不会干掉第一行的回车。
在这些函数执行完成之后，执行getline之前，多执行一次getline：去掉回车。
#include"bits/stdc .h"
using namespace std;
int t;
int getSecond(int h, int m, int s) {
return h * 3600 m * 60 s;
}
int getTime() {
string line;
getline(cin, line);
if (line.back() != ')')
line = " ( 0)";
for (int i = 0; i < 2; i ) {
int h1, m1, s1, h2, m2, s2, d;
sscanf(line.c_str(), "%d:%d:%d %d:%d:%d ( %d)", &h1, &m1, &s1, &h2, &m2, &s2, &d);
return getSecond(h2, m2, s2) - getSecond(h1, m1, s1) d * 24 * 3600;
}
}
int main() {
cin >> t;
//忽略第一行的回车
string line;
getline(cin, line);
while (t--) {
int time = (getTime() getTime()) >> 1;
int hour = time / 3600, minute = time % 3600 / 60, second = time % 60;
printf("d:d:dn", hour, minute, second);
}
return 0;
}外卖店优先级
原题链接：https://www.acwing.com/problem/content/1243/
数据量为1e5，如果按时间顺序枚举每一份订单，很有可能超时。 在整个过程中，有一部分时间是没有订单的，这一部分就可以暂时跳过。 等到有订单的时候再来处理。 这样，只有在有订单的时间点才去处理数据，而非遍历从头到尾的每个时刻。减少数据量。 这就需要：在枚举之前，先对订单数组按时间排序。 然后，按时间顺序遍历订单。 遍历每个订单时，查看上一次该店铺收到订单的时间。存储该时间需要创建一个数组，店铺号作为下标，值为上一次的订单时间。
- 先减去时间差，统一处理之前的无订单事件。
- 再提高优先级，处理订单事件。
如果当前店铺的最后一个订单不在最后一个时刻。那么遍历订单的时候，不会再遍历到该店铺，不会进入上面两步，处理该店铺的无订单事件，但是这期间，该店铺的优先级在持续降低。 解决方案就是，在最后一个时刻，遍历所有店铺上一次订单的时间。统一处理无订单事件。
代码语言：javascript复制#include"bits/stdc .h"
using namespace std;
#define x first
#define y second
typedef pair<int, int> PII;
int n, m, T;
PII order[100010];
int score[100010], last[100010], st[100010];
int main() {
cin >> n >> m >> T;
for (int i = 0; i < m; i )scanf("%d%d", &order[i].x, &order[i].y);
sort(order, order m);
for (int i = 0; i < m;) {
int j = i;
while (j < m && order[j] == order[i])j ;
int t = order[i].x, id = order[i].y, cnt = j - i;
i = j;
score[id] -= t - last[id] - 1;
if (score[id] < 0)score[id] = 0;
if (score[id] <= 3)st[id] = false;
score[id] = cnt * 2;
if (score[id] > 5)st[id] = true;
last[id] = t;
}
for (int i = 1; i <= n; i ) {
if (last[i] < T) {
score[i] -= T - last[i];
if (score[i] <= 3)st[i] = false;
}
}
int res = 0;
for (int i = 0; i <= n; i )res = st[i];
cout << res << endl;
return 0;
}上面的代码中，比较费解的是：
代码语言：javascript复制for (int i = 0; i < m;) {
int j = i;
while (j < m && order[j] == order[i])j ;
int t = order[i].x, id = order[i].y, cnt = j - i;
i = j;
score[id] -= t - last[id] - 1;
if (score[id] < 0)score[id] = 0;
if (score[id] <= 3)st[id] = false;
score[id] = cnt * 2;
if (score[id] > 5)st[id] = true;
last[id] = t;
}order是一个pair二元组，.first和.second的值分别是时间和店铺。
while()的结束条件是：
j已经移动到了数组边界之外。- 或
order订单二元组不完全相等。
这是因为同一时刻，可能有多个指向同一店铺的订单，同无订单事件一样。也可以集中处理。
这个循环的作用，就是统计相同的订单的数量。相同订单的条件是，时间和店铺相同。
每个订单都会提供2点优先级，因此后面的代码中有score[id] = cnt * 2;
所以，上面这段代码的作用是：
- 枚举每一个订单。（枚举之前已经排序）
- 对于当前订单，相同的订单的数量，并将指针移动到下一个不同的订单。
- 处理当前订单指向的店铺，之前的“无订单”事件。
- 处理当前订单指向的店铺，当前的“有订单”事件。
- 更新last数组，存储的是，当前订单指向的店铺，的上一次订单时刻。
逆序对的数量
原题链接：https://www.acwing.com/problem/content/790/
归并排序：
- [L,R]=>[L,mid],[mid 1,R]
- 递归排序[L,mid]和[mid 1,R]
- 归并，将左右两个有序序列合并成一个有序序列
以mid为分界点，逆序对的两个数可能同时出现在左半边，也可能同时出现在右半边，也可能一个在左一个在右。 各区间内的逆序对数量：
- 左半边内部的逆序对数量：
merge_sort(L,mid) - 右半边内部的逆序对数量：
merge_sort(mid 1,R)
一个在左一个在右的情况：
在左半部分和右半部分时，假设已经排好序了，并且返回了所在区间的逆序对数量。
对左半部分和右半部分继续归并排序，左区间指针大于右区间指针时，由于左右区间已经分别排好序了，那么左区间指针右侧的值都大于右区间指针当前指向的值，左区间的较大值都可以与右区间当前值构成逆序对。符合要求的取值的数量就等于mid-i 1。
也就是用两个指针，每次发现右侧有较小值时，答案加上mid-i 1。
当一侧指针指到结束位置的时候，扫尾。扫尾的时候不需要修改答案。
#include"bits/stdc .h"
using namespace std;
typedef long long LL;
int q[100010], tmp[100010];
int n;
LL merge_sort(int l, int r) {
if (l >= r)return 0;
int mid = l r >> 1;
LL res = merge_sort(l, mid) merge_sort(mid 1, r);
int k = 0, i = l, j = mid 1;
while (i <= mid && j <= r)
if (q[i] <= q[j])tmp[k ] = q[i ];
else {
tmp[k ] = q[j ];
res = mid - i 1;
}
while (i <= mid)tmp[k ] = q[i ];
while (j <= r)tmp[k ] = q[j ];
for (int i = l, j = 0; i <= r; i , j )q[i] = tmp[j];
return res;
}
int main() {
cin >> n;
for (int i = 0; i < n; i )cin >> q[i];
cout << merge_sort(0, n - 1) << endl;
return 0;
}
