建设网站需要哪些东西,做网站时无法上传图片,怎么对网站标注做记号,外国人做那个的视频网站回文日期 原文链接#xff1a;https://www.acwing.com/problem/content/468/ 由于只有八位数#xff0c;而且回文串左右对称#xff0c;因此可以只枚举左半边。然后判断#xff1a;
整个八位数日期是否合法是否在范围内
一共枚举1e4个数。判断过程是常数级别的#xff0…回文日期 原文链接https://www.acwing.com/problem/content/468/ 由于只有八位数而且回文串左右对称因此可以只枚举左半边。然后判断
整个八位数日期是否合法是否在范围内
一共枚举1e4个数。判断过程是常数级别的所以总计算量是 O ( 1 0 4 ) O(10^4) O(104) 代码中的check属于基操。
#includebits/stdc.husing 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/ 真就是在枚举。
#includebits/stdc.husing 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;
}
航班时间 原题链接https://www.acwing.com/problem/content/1233/ 不知道时差是多少要求真实的飞行时间。 去的时候从东向西减时差
飞行时间起降时间之差-时差
回的时候从西向东加时差
飞行时间起降时间之差时差
两式作和然后除以二就可以求出飞行时间。
将所有时间转换成距离当天00:00:00的秒数。按行读入对于行末可能有也可能没有的()格式化统一处理。
cin和scanf都不会干掉第一行的回车。 在这些函数执行完成之后执行getline之前多执行一次getline去掉回车。
#includebits/stdc.husing 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;
}
外卖店优先级 原题链接https://www.acwing.com/problem/content/1243/ 数据量为1e5如果按时间顺序枚举每一份订单很有可能超时。 在整个过程中有一部分时间是没有订单的这一部分就可以暂时跳过。 等到有订单的时候再来处理。 这样只有在有订单的时间点才去处理数据而非遍历从头到尾的每个时刻。减少数据量。 这就需要在枚举之前先对订单数组按时间排序。 然后按时间顺序遍历订单。 遍历每个订单时查看上一次该店铺收到订单的时间。存储该时间需要创建一个数组店铺号作为下标值为上一次的订单时间。
先减去时间差统一处理之前的无订单事件。再提高优先级处理订单事件。
如果当前店铺的最后一个订单不在最后一个时刻。那么遍历订单的时候不会再遍历到该店铺不会进入上面两步处理该店铺的无订单事件但是这期间该店铺的优先级在持续降低。 解决方案就是在最后一个时刻遍历所有店铺上一次订单的时间。统一处理无订单事件。
#includebits/stdc.husing namespace std;#define x first
#define y second
typedef pairint, 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; 所以上面这段代码的作用是
枚举每一个订单。枚举之前已经排序对于当前订单相同的订单的数量并将指针移动到下一个不同的订单。处理当前订单指向的店铺之前的“无订单”事件。处理当前订单指向的店铺当前的“有订单”事件。更新last数组存储的是当前订单指向的店铺的上一次订单时刻。
逆序对的数量 原题链接https://www.acwing.com/problem/content/790/ 归并排序
[L,R][L,mid],[mid1,R]递归排序[L,mid]和[mid1,R]归并将左右两个有序序列合并成一个有序序列
以mid为分界点逆序对的两个数可能同时出现在左半边也可能同时出现在右半边也可能一个在左一个在右。 各区间内的逆序对数量
左半边内部的逆序对数量merge_sort(L,mid)右半边内部的逆序对数量merge_sort(mid1,R)
一个在左一个在右的情况 在左半部分和右半部分时假设已经排好序了并且返回了所在区间的逆序对数量。 对左半部分和右半部分继续归并排序左区间指针大于右区间指针时由于左右区间已经分别排好序了那么左区间指针右侧的值都大于右区间指针当前指向的值左区间的较大值都可以与右区间当前值构成逆序对。符合要求的取值的数量就等于mid-i1。 也就是用两个指针每次发现右侧有较小值时答案加上mid-i1。 当一侧指针指到结束位置的时候扫尾。扫尾的时候不需要修改答案。
#includebits/stdc.husing 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;
}
