腾讯极客技术挑战赛-植树节
周末在家,突然王同学发给我一个链接腾讯极客技术挑战赛-码上种树。于是一拍即合,开启了这场逆向破解竞赛。
竞赛的操作上很简单,点击网页上的按钮一次就可以种一棵树。实质上每次先从服务器拉取一道题目,浏览器用本地脚本计算出答案,然后再将答案发送到服务器。整个竞赛的核心在于逆向破解计算答案的脚本,并优化其中的算法,越快越好。每种树到一定数量,题目就会发生变化,也就是进入了下一题,需要继续破解新的脚本文件。
整体上来说,后面的题目很有难度,需要有汇编、计算机操作系统和编译原理的功力。
0x01
题目 1 A274075A.js
123window.A274075A = async function ({ a }) { return new Promise((_) => setTimeout((__) => _(a[0]), 2000));};
不必多说,将 setTimeout 时间改成 0,然后循环点击按钮就可以了。还要重写页面代码中的 sleep 函数,设置为 0 秒。
1234567891011function sleep(ms) & ...
最近的叶子节点
fcf6d42fef418147bcf48ca76b661251aaf539bc191b153e26b64f77044d07a590a838231e23b2ff71cd38f0f17ec28960c2ad8e4d92bf3e926e3a0bfdd0dbf56f19077dc8e8a3def2fcc48310ebc211efa7e95f6e72cf6af1883f54cfefd1423fcf199558b085ccfffd7adb1f8e359d449f4e57acb8f3a4268499375329e5e074b15278581be99a91613dc36590b6f73276ec4ab6ebc89d21ef7a49d426c942a6e6765555d741efb29fc6ffad6e6b6dbe73654aab89bbbd71161cfecfa23c082c1d29bfdc5f5546a63a619e1d934cdf9103fca13a56b65c7c9344d286e68cf644de3390552874915aa0bc92a1a1077495505117cf5efb2c1 ...
外星文字典
1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556const int N = 26, M = N * N;class Solution { public: int cnt = 0; bool st[N]; int h[N], e[M], ne[M], in[N], out[N], idx; void add(int a, int b) { e[idx] = b; ne[idx] = h[a]; h[a] = idx++; out[a]++; in[b]++; } string alienOrder(vector<string>& words) { memset(h, -1, sizeof h); memset(st, 0, sizeof st); int n = words.size(); for (int ...
数位 DP
数位 DP 是这样一类问题:求某个区间内,满足某种性质的数的个数。
有两个技巧:
前缀和思想。区间有两个界限,把它转化成一个界限,例如通过 f(N) 表示 0 - N 中满足这种性质的数的个数,求 [X, Y] 时,可用 f(Y) - f(X - 1)。
从树的角度进行考虑,按位进行分类讨论。
度的数量
度的数量
组合数的计算公式为:Cab=Ca−1b+Ca−1b−1C_a^b = C_{a-1}^b + C_{a-1}^{b-1}Cab=Ca−1b+Ca−1b−1
简化题意:给一个区间 [X, Y],问这个区间内有多少个数符合这样的条件:这个数的 B 进制表示中,有 K 位上是 1,其余位都是 0.
思路:
先将 n 转换成 B 进制数保存起来
n 每一位上的数我们成为限定值,对 n 的每一位进行分类讨论
可以取限定值
取 0 ~ 限定值-1 的一个数
对于本题,用不到 2、3、9 这种限定值,本题要求 K 位上全填 1,其余位全填 0,当某位上的限定值 > 1 时,后面的位可以随便填(0 或 1),方案数可以直接算出来,然后 break 掉就可以了。
对 ...
C++ 字符串
Strings, Vectors, and Arrays
Namespace using Declarations
A using declaration lets us use a name from a namespace without qualifying the name with a namespace_name:: prefix. A using declaration has the form using namespace::name;
12using std::cin;using std::cout;
Library string Type
12#include <string>using std::string
初始化 string:
1234string s1; // default initialization; s1 is the empty stringstring s2 = s1; // s2 is a copy of s1string s3 = "hiya"; // s3 is a copy of the stri ...
C++ 初始化
初始化
1234567891011121314151617181920#include <iostream>using namespace std;int x; // 在任何函数之外定义的基本类型变量,默认值是 0int main() { int u; // 内容是 undefined int a = {1}; int b{2}; // 等号可以省略 int c(3); // 等价于 int c = 3; double i = {3.14}; // int j = {3.14}; // 错误,不允许对初始化列表中的值进行截断,或者说隐式转换 int k = 3.14; // 可以,k = 3 int m(3.14); // 可以,k = 3 cout << x << ' ' << a << ' ' << b << ' ' ...
Cxx字符类型
123456789101112131415161718192021222324252627282930#include <iostream>using namespace std;int main() { char c1 = 'a'; char16_t c2 = u'好'; char32_t c3 = U'💩'; wchar_t c4 = L'你'; cout << sizeof c1 << endl; cout << sizeof c2 << endl; cout << sizeof c3 << endl; cout << sizeof c4 << endl; cout << c1 << endl; cout << c2 << endl; cout << c3 << endl; cout &l ...
树形DP
树的最长路径
1072. 树的最长路径
1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950#include <cstring>#include <iostream>using namespace std;const int N = 10010, M = N * 2;int n;// 邻接表存树,h[u] 存每个节点对应的链表,是相邻节点int h[N], e[M], ne[M], w[M], idx;int ans;void add(int a, int b, int c) { e[idx] = b; w[idx] = c; ne[idx] = h[a]; h[a] = idx++;}int dfs(int u, int father) { int dist = 0; // 表示从当前点往下走路径的的最大长度 int d1 = 0, d2 = 0; // 树的直径对应从当前点往下走的所有路 ...
每日打卡-LeetCode-1994-好子集的数目
1994. 好子集的数目
12345678910111213141516171819202122232425262728293031323334353637383940typedef long long LL;class Solution { public: int numberOfGoodSubsets(vector<int>& nums) { const int mod = 1e9 + 7; int p[15] = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29}; int cnt[35] = {0}; int n = nums.size(); for (auto& x : nums) cnt[x]++; int s = 1 << 10; LL f[1030] = {0}; f[0] = 1; for (int i = 2; i <= 30; i++) { i ...
区间DP
环形石子合并
1068. 环形石子合并
对于环形 DP 问题,一种通用的处理环形的方式是,将原数组复制一份再接到后面,然后再按照区间 DP 的做法来解。
1234for 区间长度 len: 1 ~ n for 左端点 l: 1 ~ l + len - 1 r = l + len - 1 for 分界点 k
f[l][r] 状态表示的集合:将 l ~ r 堆的石子合并成一堆的所有方案,属性:花费力气的最小值
集合划分依据:将区间 l 到 r 的所有石子合并成一堆,最后一次合并发生的位置 k
状态转移方程:f[l][r] = min{f[l][k] + f[k + 1][r] + s[r] - s[l - 1]},其中 k = 1, 2, …, r - 1.
1234567891011121314151617181920212223242526272829303132333435363738394041424344#include <cstring>#include <iostream>using namespace std;const int N ...