腾讯极客技术挑战赛-植树节
周末在家,突然王同学发给我一个链接腾讯极客技术挑战赛-码上种树。于是一拍即合,开启了这场逆向破解竞赛。
竞赛的操作上很简单,点击网页上的按钮一次就可以种一棵树。实质上每次先从服务器拉取一道题目,浏览器用本地脚本计算出答案,然后再将答案发送到服务器。整个竞赛的核心在于逆向破解计算答案的脚本,并优化其中的算法,越快越好。每种树到一定数量,题目就会发生变化,也就是进入了下一题,需要继续破解新的脚本文件。
整体上来说,后面的题目很有难度,需要有汇编、计算机操作系统和编译原理的功力。
0x01
题目 1 A274075A.js
123window.A274075A = async function ({ a }) { return new Promise((_) => setTimeout((__) => _(a[0]), 2000));};
不必多说,将 setTimeout 时间改成 0,然后循环点击按钮就可以了。还要重写页面代码中的 sleep 函数,设置为 0 秒。
1234567891011function sleep(ms) & ...
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 ...
状态压缩 DP
小国王
1064. 小国王
1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677#include <cstring>#include <iostream>#include <vector>using namespace std;typedef long long LL;const int N = 12, M = 1 << 10, K = 110;int n, m;// state 记录所有合法状态vector<int> state;// cnt[i] 记录状态 i 中包含多少个 1int cnt[M];// head[i] 记录所有可以转移到状态 i 的状态vector<int> head[M];// DP 数组LL f[N][K][M];// 检查一个状态是不是合法状态boo ...
状态机模型
1049. 大盗阿福
这道题其实就是 LeetCode 打家劫舍。可以用状态机的方式来思考。
1234567891011121314151617181920212223#include <iostream>using namespace std;const int N = 1e5 + 10, INF = 0x3f3f3f3f;int f[N][2];int w[N];int main() { int T; cin >> T; while (T--) { int n; cin >> n; for (int i = 1; i <= n; i++) cin >> w[i]; f[0][0] = 0, f[0][1] = -INF; for (int i = 1; i <= n; i++) { f[i][0] = max(f[i - 1][0], f[i - 1][1]); f[i][1] = f[i - 1][0] + w[i]; ...
每日打卡-LeetCode-2006-差的绝对值为 K 的数对数目
2006. 差的绝对值为 K 的数对数目
12345678910111213141516const int N = 110;int h[N];class Solution { public: int countKDifference(vector<int>& nums, int k) { memset(h, 0, sizeof h); int cnt = 0; for (int i = 0; i < nums.size(); i++) { int t = nums[i]; if (t - k >= 0) cnt += h[t - k]; if (t + k <= 100) cnt += h[t + k]; h[t]++; } return cnt; }};