这个人赛时看错了几次题目导致样例调了 1h。
\(Sol1: n \leqslant 10, T \leqslant 10\)
乱搞分。
枚举跳跃的顺序，判断可不可行，最后取最大值，复杂度 \(O((n - 1 )!)\)。
\(Sol2: B\)
感觉跟正解没什么关系，先说这个。
- 特殊性质 \(\mathbf B\)：保证对于任意跳跃球 \(u, v\)，如果 kid 理论上能从 \(u\) 跳到 \(v\)，那么他理论上一定可以从 \(v\) 跳到 \(u\)。
两点一定互相可达，题目求的是能到的最大的点的数量。
并查集维护最大连通块大小即可。
\(Sol3: A\)
提示正解的部分。
- 特殊性质 \(\mathbf A\)：保证对于任意不同跳跃球 \(u,v\)，如果 kid 理论上能从 \(u\) 跳到 \(v\)（理论上：不考虑 kid 能否从起点到达 \(u\) 的问题，下同），那么他理论上一定不可以从 \(v\) 跳到 \(u\)。
一定没有环，所以建完图后一定是一个 DAG，直接在 DAG 上跑 dp。
$Sol4: $ 如何建图
如果点 \(u\) 能跳到点 \(v\) 的话，就连接一条 \(u\) 向 \(v\) 的边。
每下坠一格时，可以移动一格，所以 \(y\) 坐标的差应该小于等于 \(x\) 坐标的差。
bool check(int a, int b)
{
int x1 = x[a], x2 = x[b], y1 = y[a] + d, y2 = y[b];
if(y1 < y2) return false;
if(abs(x1 - x2) > y1 - y2) return false;
return true;
}
\(Sol5:\)
建完图之后显然不是 DAG，于是想到缩点，缩点完用 \(Sol3\) 的方法去 dp。
bool check(int a, int b)
{
int x1 = x[a], x2 = x[b], y1 = y[a] + d, y2 = y[b];
if(y1 < y2) return false;
if(abs(x1 - x2) > y1 - y2) return false;
return true;
}
int h[N], nxt[M], to[M], cnt;
void add(int u, int v)
{
to[++ cnt] = v, nxt[cnt] = h[u], h[u] = cnt;
}
int dfn[N], low[N], bel[N], tim, scc_cnt;
bool ins[N];
int siz[N], f[N], in_deg[N];
stack<int> s;
void tarjan(int u)
{
dfn[u] = low[u] = ++ tim;
ins[u] = true;
s.push(u);
for(int i = h[u]; i; i = nxt[i])
{
int v = to[i];
if(!dfn[v])
{
tarjan(v);
low[u] = min(low[u], low[v]);
}
else if(ins[v]) low[u] = min(low[u], dfn[v]);
}
if(low[u] == dfn[u])
{
int v;
scc_cnt ++;
do
{
siz[scc_cnt] ++;
v = s.top();
s.pop();
ins[v] = false;
bel[v] = scc_cnt;
} while(v != u);
}
}
vector<int> adj[N];
int top()
{
queue<int> q;
for(int i = 1; i <= scc_cnt; i ++) if(in_deg[i] == 0) q.push(i), f[i] = siz[i];
while(q.size())
{
int u = q.front();
q.pop();
for(auto v : adj[u])
{
f[v] = max(f[v], f[u] + siz[v]);
if(-- in_deg[v] == 0) q.push(v);
}
}
}
void init()
{
for(int i = 1; i <= n; i ++)
{
h[i] = 0;
adj[i].clear();
in_deg[i] = 0;
f[i] = 0;
siz[i] = 0;
ins[i] = false;
bel[i] = 0;
nxt[i] = 0;
to[i] = 0;
dfn[i] = 0;
low[i] = 0;
}
cnt = scc_cnt = tim = 0;
}
void solve()
{
cin >> n >> d >> c;
for(int i = 1; i <= n; i ++) cin >> x[i] >> y[i];
for(int i = 1; i <= n; i ++)
for(int j = 1; j <= n; j ++) if(check(i, j) && i != j) add(i, j);
for(int i = 1; i <= n; i ++) if(!dfn[i]) tarjan(i);
for(int i = 1; i <= n; i ++)
for(int j = h[i]; j; j = nxt[j])
if(bel[i] != bel[to[j]]) adj[bel[to[j]]].push_back(bel[i]), in_deg[bel[i]] ++;
queue<int> q;
for(int i = 1; i <= scc_cnt; i ++) if(in_deg[i] == 0) q.push(i), f[i] = siz[i];
while(q.size())
{
int u = q.front();
q.pop();
for(auto v : adj[u])
{
f[v] = max(f[v], f[u] + siz[v]);
if(-- in_deg[v] == 0) q.push(v);
}
}
cout << f[bel[c]] << '\n';
}