Home
Problem
Status
Contest
Workbook
User
Group
Forum
Register
Login
{"managingGroups":{},"author":"hhc0716","updateTime":1697015758000,"title":"OI Trick:根对枚举 总结","dislikeCnt":0,"content":"\n# Intro\n根对枚举,就是一种使用数学方法优化过后的枚举。因为其时间复杂度中经常带一个根号或是 $\\log$,因此被我这样命名。\n# 引入\n先看一道例题(也是我第一次发现这个 Trick 的题目):\n\n## 例 1 CF1846E2(一定是 E2!不是 E1!)Rudolph and Snowflakes\n\n[vjudge 链接](https://vjudge.net/problem/CodeForces-1846E2)\n[原题链接](https://codeforces.com/problemset/problem/1846/E2)\n\n它的弱化版,CF1846E1,暴力枚举即可解决。\n\n但是,它,暴力会 T 飞 :(\n\n观察数据范围,只有二次方和三次方需要特殊处理。\n\n但由于这个多项式函数在 $\\mathbb{N^{*}}$ 的定义域下单调递增,所以二分即可。\n\n更高次的话由于次数过高就不会 T 飞了 :)\n\n时间复杂度:\n\n$$\nO(T + \\log_2 \\sqrt V + \\log_2 \\sqrt[3]V + \\sum \\limits_{i \u003d 4}^{\\log_2 V} \\sqrt[i]V)\n$$\n\n$$\n\\approx O(T + \\log_2 \\sqrt V + \\log_2 \\sqrt[3]V + \\log V \\sqrt[\\log V] V)\n$$\n\n$$\n\\approx O(T + \\log \\sqrt V + \\log \\sqrt[3]V + \\log V)\n$$\n\n$$\n\\approx O(T + \\log V)\n$$\n\n空间复杂度:\n\n$O(1)$。\n\n可以发现,这套算法的复杂度带有一个 $\\log$。\n\n事实上这里面真实情况是~~已删除~~,真正的时间复杂度远没有这么简洁......所以我在所有简化了式子的行的最前面都加了一个约等号,因为每一轮都忽略掉了什么东西。\n\n---\n\n讲下一道:\n\n## 例 2:AT-abc227C ABC Conjecture\n\n[vjudge 链接](https://vjudge.csgrandeur.cn/problem/AtCoder-abc227_c)\n[原题链接](https://atcoder.jp/contests/abc227/tasks/abc227_c?lang\u003den)\n\n还是一样的,暴力会 T 飞,又看题目,想出根对枚举。\n\n发现 $C$ 可以不用枚举,在枚举 $A, B$ 之后直接统计 $C$ 的个数即可。\n\n时间复杂度:\n\n$$\nO(\\sqrt{\\frac{N}{\\sqrt[3]{N}}})\n$$\n\n$$\n\u003d O(\\sqrt{N^{\\frac{2}{3}}})\n$$\n\n$$\n\u003d O(\\sqrt[3]N)\n$$\n\n空间复杂度:\n\n$O(1)$。\n\n---\n\n## 习题 1\n\n### AT-abc254D Together Square\n\n[vjudge 链接](https://vjudge.csgrandeur.cn/problem/AtCoder-abc254_d)\n[原题链接](https://atcoder.jp/contests/abc254/tasks/abc254_d?lang\u003den)\n\n### AT-abc296D M\u003c\u003dab\n\n[vjudge 链接](https://vjudge.csgrandeur.cn/problem/AtCoder-abc296_d)\n[原题链接](https://atcoder.jp/contests/abc296/tasks/abc296_d?lang\u003den)\n\n### AT-abc292C Four Variables\n\n[vjudge 链接](https://vjudge.csgrandeur.cn/problem/AtCoder-abc292_c)\n[原题链接](https://atcoder.jp/contests/abc292/tasks/abc292_c?lang\u003den)\n\n### AT-abc300D AABCC\n[vjudge 链接](https://vjudge.csgrandeur.cn/problem/AtCoder-abc300_d)\n[原题链接](https://atcoder.jp/contests/abc300/tasks/abc300_d?lang\u003den)\n\n## 需要记住的东西:\n\n### 判别\n\n1. long long 般的数据范围\n2. 超高的变量总次数(总次数是所有变量的次数加起来的和)\n\n### 口诀\n\n一定得死几个!\n\n来源:\n\n这些根对枚举题中要么是次数死几个,要么是死几个变量,要么上界本身是死的。","threadId":172103,"likeCnt":0,"createTime":1696822988000,"isWorkbook":false,"viewCnt":235,"openness":2,"fav":false,"id":4149,"trustable":false}