[关闭]
@Dmaxiya 2022-02-12T20:42:31.000000Z 字数 2273 阅读 1106

2022 春节寒假最后一次培训

Hello_World


时间复杂度的计算*

简介

运行时间计算方式:
如:对 ~ 进行求和,若使用如下代码:

  1. long long sum = 0, i;
  2. for(i = 1; i <= 1000000000LL; ++i) {
  3. sum += i;
  4. }

则程序执行的次数为 ,需要 10s,若使用如下代码:

  1. long long sum = (1 + 1000000000LL) * 1000000000LL / 2;

则程序执行的次数为 ,所需要时间为
实际代码的运行时间可能少于估计值,但大多数题目的数据都能保证:若程序运行次数超过 必然返回超时。

练习

计算以下题目的时间复杂度:

  1. P6685 可持久化动态仙人掌的直径问题
  2. P1601 A+B Problem(高精)
  3. P1109 学生分组
  4. P2676 [USACO07DEC]Bookshelf B

习题讲解

高精度计算

加法

参考题目:P1601 A+B Problem(高精)
参考代码:https://www.luogu.com.cn/paste/e237i3pn

  1. int add(int *a, int lena, int *b, int lenb, int *c) {
  2. int s = 0;
  3. int len = max(lena, lenb);
  4. for (int i = 0; i < len; ++i) {
  5. c[i] = s + a[i] + b[i];
  6. s = c[i] / 10;
  7. c[i] %= 10;
  8. }
  9. if (s != 0) {
  10. c[len++] = s;
  11. }
  12. return len;
  13. }

减法

  1. int sub(int *a, int lena, int *b, int lenb, int *c) {
  2. int s = 0;
  3. int aa, bb;
  4. int len = max(lena, lenb);
  5. for(int i = 0; i < len; ++i) {
  6. aa = a[i];
  7. if(i >= lenb) {
  8. bb = 0;
  9. } else {
  10. bb = b[i];
  11. }
  12. c[i] = (aa - bb - s + 10) % 10;
  13. if(aa < bb + s) {
  14. s = 1;
  15. } else {
  16. s = 0;
  17. }
  18. }
  19. for (int i = maxn - 1; i >= 0; --i) {
  20. if (c[i] != 0) {
  21. return i + 1;
  22. }
  23. }
  24. return 1;
  25. }

乘法

参考题目:P1045 [NOIP2003 普及组] 麦森数
参考代码:https://www.luogu.com.cn/paste/dyv59ovw

  1. int mult(int *a, int lena, int *b, int lenb, int *c) {
  2. for (int i = 0; i < lena; ++i) {
  3. for (int j = 0; j < lenb; ++j) {
  4. c[i + j] += a[i] * b[j];
  5. }
  6. }
  7. int cc = 0;
  8. for (int i = 0; i < lena + lenb; ++i) {
  9. c[i] += cc;
  10. cc = c[i] / 10;
  11. c[i] %= 10;
  12. }
  13. int idx = lena + lenb;
  14. while (cc != 0) {
  15. c[idx++] = cc % 10;
  16. cc /= 10;
  17. }
  18. for (int i = maxn - 1; i >= 0; --i) {
  19. if (c[i] != 0) {
  20. return i + 1;
  21. }
  22. }
  23. return 1;
  24. }

二分专题

P1045 麦森数

  1. 求位数
  2. 计算时间复杂度,发现硬算不过
  3. 快速幂优化

参考代码:https://www.luogu.com.cn/paste/dyv59ovw

贪心专题

P1016 旅行家的预算

思路1:

  1. 优先保证能跑到下一个城市
  2. 在能跑到下一个城市的前提下,如果当前城市的油价更便宜,就用当前城市的油去跑,否则就只把油买到刚好能跑到油价更便宜的那个城市

思路2(代码更好写):

  1. 每到一个城市就把油装满
  2. 到一个城市后,要走的下一段路,找出已经装满的油中,最便宜的那种油,用最便宜的油去跑

参考代码:https://www.luogu.com.cn/paste/p12panu1

P1080 国王游戏

  1. 可以参考题解(看起来比较好理解,但不够严谨的证明)
  2. 拓展题目:leetcode 179. 最大数,详见题解

参考代码:https://www.luogu.com.cn/paste/oaufv02y

P2512 糖果传递

这题不太好讲,我也看不懂别人的题解,直播的时候再说,希望能把大家讲明白
参考代码:https://www.luogu.com.cn/paste/takzq46c

递归 & 递推

P2437 蜜蜂路线

  1. 递推
  2. 大数加法

参考代码:https://www.luogu.com.cn/paste/8vbtwifq

DFS(深度优先搜索)

P2392 kkksc03考前临时抱佛脚

  1. 暴力搜索思路,参考代码:https://www.luogu.com.cn/paste/e9751rb2
  2. 01 背包思路,参考代码:https://www.luogu.com.cn/paste/rwx1skai

P1784 数独

  1. 0 在行、列表示中的作用
  2. 思路简介

参考代码:https://www.luogu.com.cn/paste/6u96nsc0

P1556 幸福的路

  1. 简单几何计算,点积、叉积
    1.1 点积的运用:计算向量夹角,判断前后方向
    1.2 叉积的应用:计算面积,判断顺时、逆时针,排极角序
  2. 重载运算符,向量的简单计算,参考代码:https://www.zybuluo.com/Dmaxiya/note/1241504
  3. next_permutation 的使用,参考代码:https://www.luogu.com.cn/paste/b08iism5

参考代码:https://www.luogu.com.cn/paste/3po7fba8

其他

P1999 高维正方体

直接讲自己的思路

添加新批注
在作者公开此批注前,只有你和作者可见。
回复批注