我胡汉三又滚回来了....保质期过了的题也得记下来。
以下题解包括：
\[1002【HDU-6635】 \\ 1005【HDU-6638】 \\ 1006【HDU-6639】 \\ 1008【HDU-6641】 \\ 1012【HDU-6645】\]
【1002】 LIS+暴力 HDU-6635 Nonsense Time
参考：
给定长度为 \(n\) 的两个数组 \(a,b\)，\(b_i\) 表示 \(a\) 中下标为 \(b_i\) 的数字当前可用，求 \(b_i\) 对应的 \(a\) 中的 LIS，\(a\) 中是 \([1，n]\) 的全排列。
由于数据随机生成，LIS 的期望长度为 \(\sqrt{n}\)，删除元素在 LIS 中的概率为 \(\frac{1}{\sqrt{n}}\)，因此总复杂度：\(o(n\sqrt{n}log(n)))\)。先求解全部的 LIS，然后从后往前遍历数组 \(b\)，如果删除的元素在 LIS 中就重新求一次。需要记录 LIS 的路径。
#include
【1005】 线段树 HDU-6638 Snowy Smile
参考：
给定 \(n(\leq 2000)\) 个点坐标和对应的权值，求最大权值和矩阵。
每次枚举上下边界，每次向线段树中加点，维护上下边界内的最大子段和【区间最大子段和】，要注意移动上边界时可能会有多个点在当前直线上，同样的，移动下边界时要把边界上的所有点都更新后才能更新 \(ans\)。
#include
【1006】 思维 HDU-6639 Faraway
有 \(n\) 个二维坐标点（士兵），他们有一个共同的目的地 \((x_{e},y_{e})\)，知道 \(x_e\) 和 \(y_e\) 都在 \([0,m]\) 的范围内，但是他们都只知道自己位置 \((x_i,y_i)\) 和目标的大概情况为 \((|x_{i}-x_{e}|+|y_{i}-y_{e}|) \% k_{i} = t_{i}\) 现在问你有多少个可能的目标 \((x_e,y_e)\)。
将 \(|x_i - x_e| + |y_i - y_e|\) 的绝对值拆掉，则每个点 \((x_i, y_i)\) 会将平面分割成 4 个部分，一共 \(n^2\) 个区域。枚举每个区域，计算该区域中可能的终点数量。因为 \(lcm(2, 3, 4, 5) = 60\)，所以只需要枚举 \(x_e\) 和 \(y_e\) 模 60 的余数，\(o(n)\) 判断是否可行。
#include
【1008】 数学 HDU-6641 TDL
队友写的，就酱。
#include #include #include #include #include #include #define lson node<<1#define rson node<<1|1using namespace std;typedef long long ll;const ll inf = 2e18;const ll mod = 998244353;const int maxn = 1e5 + 20;ll gcd(ll a, ll b) { return b == 0 ? a : gcd(b, a % b);}int main() { int t; scanf("%d", &t); while (t--) { ll k, m; scanf("%lld%lld", &k, &m); ll ans = inf; int flag = 0; for (int i = 1; i <= 2000; i++) { ll n = k ^ i; int cnt = 0; int j = 1; for (; j <= 1000; j++) { if (gcd(j + n, n) == 1) { cnt++; if (cnt == m) break; } } if ((n + j) == (i + n)) { ans = min(ans, n); flag = 1; } } if (flag) printf("%lld\n", ans); else printf("-1\n"); }}
【1012】 水题 HDU-6645 permutation 2
我也不知道比赛时候为什么会去写拓扑...
就排个序一人一个分了就行。
#include