由于只有八位数,而且回文串左右对称,因此可以只枚举左半边。然后判断:
一共枚举1e4个数。判断过程是常数级别的,所以总计算量是
代码中的check属于基操。
#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;
}
真就是在枚举。
#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-%02d-%02d\n", year, month, day);
}
}
}
return 0;
}
不知道时差是多少,要求真实的飞行时间。 去的时候,从东向西,减时差:
回的时候,从西向东,加时差:
两式作和,然后除以二,就可以求出飞行时间。
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("%02d:%02d:%02d\n", hour, minute, second);
}
return 0;
}
数据量为1e5,如果按时间顺序枚举每一份订单,很有可能超时。 在整个过程中,有一部分时间是没有订单的,这一部分就可以暂时跳过。 等到有订单的时候再来处理。 这样,只有在有订单的时间点才去处理数据,而非遍历从头到尾的每个时刻。减少数据量。 这就需要:在枚举之前,先对订单数组按时间排序。 然后,按时间顺序遍历订单。 遍历每个订单时,查看上一次该店铺收到订单的时间。存储该时间需要创建一个数组,店铺号作为下标,值为上一次的订单时间。
如果当前店铺的最后一个订单不在最后一个时刻。那么遍历订单的时候,不会再遍历到该店铺,不会进入上面两步,处理该店铺的无订单事件,但是这期间,该店铺的优先级在持续降低。 解决方案就是,在最后一个时刻,遍历所有店铺上一次订单的时间。统一处理无订单事件。
#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;
}
上面的代码中,比较费解的是:
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;
所以,上面这段代码的作用是:
归并排序:
以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;
}