250725 模拟赛
在左上角是 \((0,0)\)，右上角是 \((n,m)\) 的网格中，有 \((n+1)\times (m+1)\) 个格点。你需要找 \(k\) 个不同的点，使得它们在一条直线上，并且直线上相邻点之间的距离不小于 \(d\)，求方案数，对 \(10^9+7\) 取模。
\(n,m,d\le 500,\ k\le 50\)
有 \(n\) 个物品排成一列，要求选 \(k\) 个物品，并且任意两物品之间都至少间隔 \(d-1\) 个物品，求方案数。这个经典问题显然可以使用插板法组合数解决。
考虑如何解决原问题。对于直线平行于网格线的平凡情况，最后处理即可。其余情况，我们可以钦定直线斜率为正，并在最后将答案乘以 \(2\)。
一种朴素的想法是枚举所有可能的直线，但是需要去重，而且时间复杂度非常爆炸。
考虑将所有点框住的最小矩形，那么它的左下角和右上角一定被选择了，其余点分布在它的一条对角线上。注意到在矩形确定之后（即钦定选择两端点），方案数仍然是容易求出的。同时，矩形是可以在网格内任意平移的，并且总是唯一对应一种合法方案。
因此，枚举矩形的长和宽即可。
代码
| #include<iostream>
#include<set>
#include<algorithm>
#include<cassert>
#include<cmath>
#define ll long long
using namespace std;
const int MOD = 1e9 + 7;
const int N = 510;
const int N2 = N * N;
inline void add(int &a, int b) { a = (a + b) % MOD; }
int T;
int n, m, k, d;
int ans;
int fact[N], ifact[N], inv[N];
int c(int a, int b) {
if(a < b) return 0;
return (ll)fact[a] * ifact[a - b] % MOD * ifact[b] % MOD;
}
int calc(int n, int d) {
return c(n - d - 1 - (k - 2) * d + k - 2, k - 2);
}
void work() {
ans = 0;
for(int i = 0; i <= n; i++) {
for(int j = 0; j <= m; j++) {
int g = __gcd(i, j);
if(g + 1 < k) continue;
int x = i / g, y = j / g;
int d2 = ceil(d / sqrt(x * x + y * y));
if(i == 0 || j == 0) ans = (ans + (ll)calc(g + 1, d2) * (n - i + 1) * (m - j + 1) % MOD) % MOD;
else ans = (ans + (ll)calc(g + 1, d2) * (n - i + 1) * (m - j + 1) * 2 % MOD) % MOD;
}
}
cout << ans << '\n';
}
int main() {
inv[1] = fact[0] = ifact[0] = 1;
for(int i = 2; i < N; i++) inv[i] = MOD - (ll)inv[MOD % i] * (MOD / i) % MOD;
for(int i = 1; i < N; i++) fact[i] = (ll)fact[i - 1] * i % MOD;
for(int i = 1; i < N; i++) ifact[i] = (ll)ifact[i - 1] * inv[i] % MOD;
cin >> T;
while(T--) {
cin >> k >> n >> m >> d;
if(k == 1) {
cout << (n + 1) * (m + 1) % MOD << '\n';
continue;
}
work();
}
return 0;
}
|
嘻嘻 俩 \(\log\) 跑的比某人的一 \(\log\) 还快 嘻嘻嘻嘻嘻
给定一棵 \(n\) 个节点，以 \(1\) 为根的有根树。称一个长度为 \(m\) 的序列 \(a\) 是合法的，当且仅当 \(\forall i\in [1,n-1]\)，\(a_i\) 与 \(a_{i+1}\) 存在祖先后代关系，并且 \(a\) 中元素互不相同。问最长合法序列长度。
\(T\le 5,\ n\le 10^5\)
注意到问题等价于在树上移动，可以任选一个点开始，每次可以移动到任意祖先或者任意孩子，一个节点最多被经过 \(1\) 次，问最多移动多少步。
给每个节点维护一个堆表示，每次跳入当前子树，可以收获多少步数。
对于一棵子树 \(u\)，一定是先跳入 \(u\) 的一个儿子子树，然后跳到 \(u\)，然后再跳入一棵儿子子树。两棵子树一定是收获步数最大次大的两个（一个）。之后每次都是直接跳进某棵子树，再直接跳出来。
因此一个节点的堆就是所有儿子的堆并起来，然后拿出前两项 \(a,b\)（不存在则为 \(0\)），并将 \(a+b+1\) 放入堆。这里可以用启发式合并实现，容易做到 \(O(n\log^2n)\)。
代码
| #include<iostream>
#include<queue>
using namespace std;
const int N = 1e5 + 10;
struct Edge {
int v, next;
} pool[2 * N];
int ne, head[N];
void addEdge(int u, int v) {
pool[++ne] = {v, head[u]};
head[u] = ne;
}
int T, n;
int sz[N], son[N];
int swp[N];
priority_queue<int> que[N];
void dfs(int u, int fa) {
sz[u] = 1; son[u] = 0;
for(int e = head[u]; e; e = pool[e].next) {
int v = pool[e].v;
if(v == fa) continue;
dfs(v, u);
sz[u] += sz[v];
if(sz[v] > sz[son[u]]) son[u] = v;
}
if(!son[u]) { que[swp[u]].push(1); return; }
swp[u] = swp[son[u]];
for(int e = head[u]; e; e = pool[e].next) {
int v = pool[e].v;
if(v == fa || v == son[u]) continue;
while(!que[swp[v]].empty()) { que[swp[u]].push(que[swp[v]].top()); que[swp[v]].pop(); }
}
int first = 1;
if(!que[swp[u]].empty()) first += que[swp[u]].top(), que[swp[u]].pop();
if(!que[swp[u]].empty()) first += que[swp[u]].top(), que[swp[u]].pop();
que[swp[u]].push(first);
}
void clear() {
for(int i = 1; i <= n; i++) head[i] = 0;
ne = 0;
for(int i = 1; i <= n; i++) { while(!que[i].empty()) que[i].pop(); }
for(int i = 1; i <= n; i++) swp[i] = i;
}
int main() {
cin >> T;
while(T--) {
cin >> n;
clear();
for(int i = 1; i <= n - 1; i++) {
int u, v;
cin >> u >> v;
addEdge(u, v);
addEdge(v, u);
}
dfs(1, 0);
cout << que[swp[1]].top() << '\n';
}
return 0;
}
|