别样的，不好评价，烂完了Rank
A. 送信卒
签，我是唐氏。
为什么呢
题目没给最短路的定义，我赛时觉得最短路就是最短路径，于是直接 bfs 一遍随便加个 check 就做完了。当然过得那遍按我的思路来说是错的，然后我也发现了这一点，然后就改了，然后就 WA 了。总结：错误思路的错解是正确思路的正解，错误思路的正解是正确思路的错解。
bfs 太好理解了，没什么说的。但总感觉正确性有问题，不断加特判 corner cases 大概也不过不了题意的最短路不是最短路径的情况，所以还是记录一下题解做法。
二分 k 的大小，跑最短路 check，复杂度 \(\mathcal{O(n^2\log n)}\)。
话说我都多久没场上打出过 T1 题解做法了
点击查看代码（bfs）
#include<bits/stdc++.h>
#define fo(x, y, z) for(int (x) = (y); (x) <= (z); (x)++)
#define fu(x, y, z) for(int (x) = (y); (x) >= (z); (x)--)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
#define lx ll
inline lx qr()
{
char ch = getchar(); lx x = 0, f = 1;
for(; ch < '0' || ch > '9'; ch = getchar()) if(ch == '-') f = -1;
for(; ch >= '0' && ch <= '9'; ch = getchar()) x = (x << 3) + (x << 1) + (ch ^ 48);
return x * f;
}
#undef lx
#define qr qr()
#define pii pair<int, int>
#define ppp pair<pii, pii>
#define fi first
#define se second
#define M_P(x, y) make_pair(x, y)
#define P_B(x) push_back(x)
const int Ratio = 0;
const int N = 100 + 5;
const int mod = 1e9 + 7;
int n, m;
int sx, sy, ex, ey;
int d[N][N];
pii f[N][N];
bool yz[N][N];
int xxx[5] = {0, -1, 0, 0, 1};
int yyy[5] = {0, 0, 1, -1, 0};
double s, k;
namespace Wisadel
{
inline bool Wck(int x, int y, int id)
{
int tx = x + xxx[id], ty = y + yyy[id];
if(tx && tx <= n && ty && ty <= m && d[tx][ty] != 1)
{
if(!yz[tx][ty]) return 1;
else if((f[tx][ty].fi + f[tx][ty].se == f[x][y].fi + f[x][y].se + 1) && f[tx][ty].fi > f[x][y].fi + (id == 1 || id == 4)) return 1;
}
return 0;
}
inline void Wbfs(int x, int y)
{
queue<pii> q;
yz[x][y] = 1;
f[x][y] = M_P(0, 0);
q.push(M_P(x, y));
while(q.size())
{
int ux = q.front().fi, uy = q.front().se;
q.pop();
if(f[ux][uy].se + (max(uy, sy) - min(uy, sy)) > s) continue;
fo(i, 1, 4)
{
if(Wck(ux, uy, i))
{
if(i == 1 || i == 4)
f[ux + xxx[i]][uy + yyy[i]] = M_P(f[ux][uy].fi + 1, f[ux][uy].se);
else f[ux + xxx[i]][uy + yyy[i]] = M_P(f[ux][uy].fi, f[ux][uy].se + 1);
yz[ux + xxx[i]][uy + yyy[i]] = 1;
q.push(M_P(ux + xxx[i], uy + yyy[i]));
}
}
}
}
short main()
{
freopen("msg.in", "r", stdin), freopen("msg.out", "w", stdout);
n = qr, m = qr;
sx = qr, sy = qr, ex = qr, ey = qr;
fo(i, 1, n) fo(j, 1, m) d[i][j] = qr;
cin >> s;
Wbfs(ex, ey);
k = (s - f[sx][sy].se) / (1.0 * f[sx][sy].fi);
printf("%.3lf\n", k);
return Ratio;
}
}
signed main(){return Wisadel::main();}
// Now there's only one thing I can do
// Fight until the end like I promised to
B. 共轭树图
树形 dp + 计数。
前几天天天有卡特兰数直接被洗脑，上来看链的性质直接发现就是卡特兰数，然后多求了一个，然后挂 32pts。
设 \(f_{i,j}\) 表示点 \(i\) 向上能连深度不超过 \(j\) 祖先的方案数。考虑转移，发现子节点能连的祖先当前节点一定能连（除去当前节点），父节点连不了的子节点也一定不能连，那么子节点能连的数量实质上是父节点的数量加上它本身。而我们所设 \(f\) 完全可以等效将深度向上若干个，又根据乘法原理，每个子节点的子树方案数互不干扰，那么转移方程有：
\[f_{u,i}=\prod_{v\in subtree_u}\sum_{j=1}^i\ f_{v,j+1} \]那么做完了，复杂度 \(\mathcal{O(n^2)}\)。
点击查看代码
// ubsan: undefined
// accoders
#include<bits/stdc++.h>
#define fo(x, y, z) for(int (x) = (y); (x) <= (z); (x)++)
#define fu(x, y, z) for(int (x) = (y); (x) >= (z); (x)--)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
#define lx ll
inline lx qr()
{
char ch = getchar(); lx x = 0, f = 1;
for(; ch < '0' || ch > '9'; ch = getchar()) if(ch == '-') f = -1;
for(; ch >= '0' && ch <= '9'; ch = getchar()) x = (x << 3) + (x << 1) + (ch ^ 48);
return x * f;
}
#undef lx
#define qr qr()
#define pii pair<int, int>
#define ppp pair<pii, pii>
#define fi first
#define se second
#define M_P(x, y) make_pair(x, y)
#define P_B(x) push_back(x)
const int Ratio = 0;
const int N = 3000 + 5;
const int mod = 998244353;
int n;
int hh[N], to[N << 1], ne[N << 1], cnt;
ll f[N][N], ans;
namespace Wisadel
{
inline void Wadd(int u, int v)
{
to[++cnt] = v;
ne[cnt] = hh[u];
hh[u] = cnt;
}
void Wdfs(int u, int fa)
{
fo(i, 1, n) f[u][i] = 1;
for(int i = hh[u]; i != -1; i = ne[i])
{
int v = to[i];
if(v == fa) continue;
Wdfs(v, u);
ll zc = 0;
fo(i, 1, n)
{
zc = (zc + f[v][i + 1]) % mod;
f[u][i] = f[u][i] * zc % mod;
}
}
}
short main()
{
freopen("reflection.in", "r", stdin), freopen("reflection.out", "w", stdout);
n = qr;
memset(hh, -1, sizeof hh);
bool task1 = 1, task2 = 1;
fo(i, 1, n - 1)
{
int a = qr, b = qr;
Wadd(a, b), Wadd(b, a);
}
Wdfs(n, 0);
printf("%lld\n", f[n][1]);
return Ratio;
}
}
signed main(){return Wisadel::main();}
// Now there's only one thing I can do
// Fight until the end like I promised to
C. 摸鱼军训
不是很难想的思维题。场上只会暴力。
考虑一次询问 \(x,k\)。如果 \(k\gt n-x\)，那么此时 \(x\) 一定已经被排到最后它原本应该的位置，\(ans=x\)。然后是一个比较 trick 的分类，设 \(x\) 原本位置前面有 \(s\) 个大于 \(x\) 的数。当 \(k\le s\) 时，可以容易想到这 \(k\) 个数会依次经过 \(x\)，而 \(x\) 也就顺次向前移动了 \(k\) 个，故 \(ans=pre_x-k\)。而剩下的最后一种情况，即此时 \(x\) 后比 \(x\) 大的数依次归位时，我们会发现每次会被“卡”在 \(x\) 后第一个比 \(x\) 大的位置上，一共会这样卡 \(k-s\) 次。手模再次发现，这相当于是比 \(x\) 大的数按顺序第 \(k\) 个的位置向前移动 \(k\) 次，即 \(ans=search(k)-k\)。
发现线段树所需要的操作只有单点修改和查询第 \(k\) 个 1 的位置。我们直接将询问挂在 \(x\) 上倒序处理，处理完将当前 \(x\) 在原序列上标为 1，意思是比之后的 \(x\) 大。然后就做完了，查询直接线段树上二分，复杂度 \(\mathcal{O(n\log n)}\)，代码很好写。
点击查看代码
#include<bits/stdc++.h>
#define fo(x, y, z) for(int (x) = (y); (x) <= (z); (x)++)
#define fu(x, y, z) for(int (x) = (y); (x) >= (z); (x)--)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
#define lx ll
inline lx qr()
{
char ch = getchar(); lx x = 0, f = 1;
for(; ch < '0' || ch > '9'; ch = getchar()) if(ch == '-') f = -1;
for(; ch >= '0' && ch <= '9'; ch = getchar()) x = (x << 3) + (x << 1) + (ch ^ 48);
return x * f;
}
#undef lx
#define qr qr()
#define pii pair<int, int>
#define ppp pair<pii, pii>
#define fi first
#define se second
#define M_P(x, y) make_pair(x, y)
#define P_B(x) push_back(x)
const int Ratio = 0;
const int N = 5e5 + 5, M = 3000 + 5;
const int mod = 998244353;
int n, m;
int a[N], pre[N];
vector<pii> q[N];
int v[N << 2];
int ans[N];
namespace Wisadel
{
#define ls (rt << 1)
#define rs (rt << 1 | 1)
#define mid ((l + r) >> 1)
inline void Wpushup(int rt){v[rt] = v[ls] + v[rs];}
inline void Wupd(int rt, int l, int r, int x)
{
if(l == r){v[rt] = 1; return ;}
if(x <= mid) Wupd(ls, l, mid, x);
else Wupd(rs, mid + 1, r, x);
Wpushup(rt);
}
inline int Wq(int rt, int l, int r, int k)
{
if(l == r) return l;
if(v[ls] >= k) return Wq(ls, l, mid, k);
return Wq(rs, mid + 1, r, k - v[ls]);
}
short main()
{
freopen("bubble.in", "r", stdin), freopen("bubble.out", "w", stdout);
n = qr;
fo(i, 1, n) a[i] = qr, pre[a[i]] = i;
m = qr;
fo(i, 1, m)
{
int k = qr, x = qr;
q[x].P_B(M_P(k, i));
}
fu(i, n, 1)
{
for(pii kk : q[i])
if(kk.fi > n - i) ans[kk.se] = i;
else ans[kk.se] = max(Wq(1, 1, n, kk.fi), pre[i]) - kk.fi;
Wupd(1, 1, n, pre[i]);
}
fo(i, 1, m) printf("%d\n", ans[i]);
return Ratio;
}
}
signed main(){return Wisadel::main();}
// Now there's only one thing I can do
// Fight until the end like I promised to
D. 神奇园艺师
向 Qyun 学会了，不知道今天晚上来不来得及改出来。
首先质因数拆分，发现每个质数是独立的，因此分开算，每个数只与指数有关。
一个重要结论：求出一个 \(x\) 使得 \(\sum_{i=1}^n\ |a_i-x|\) 最小的结果是中位数。这个手模一下很好出，但很重要，后面都围绕这个展开。
枚举每一个指数 \(num_i\) 作中间的数，然后枚举其左边有 \(a\) 个，右边有 \(b\) 个。如果 \(a\lt b\)，说明当前中间的数在中位数左边，贡献是负的，然后组合数可以得出答案：
\[ans=-num_i\binom{i-1}{a}\binom{n-i}{b} \]\(a\gt b\) 的情况同理，答案为：
\[ans=num_i\binom{i-1}{a}\binom{n-i}{b} \]那么就得到了一个 \(\mathcal{O(n^3\log n)}\) 的做法，枚举质数，然后枚举每一项，然后分别枚举 \(a,b\)。
发现这样枚举两项是很不优的，考虑优化。先考虑 \(a\lt b\) 的情况，设 \(d=b-a\)，那么对于每个 \(num_i\)，答案有：
\[\begin{aligned}ans_i&=\sum_{d=0}^{\max(i,n-i)}\sum_{a=0}^i\ -num_i\binom{i-1}{a}\binom{n-i}{a+d}\\ &=\sum_{d=0}^{\max(i,n-i)}\sum_{a=0}^i\ -num_i\binom{i-1}{a}\binom{n-i}{n-i-a-d} \end{aligned}\ \]然后什么范德蒙德卷积，原式为：
\[\sum_{i=0}\ \binom{n}{i}\binom{m}{s-a}=\binom{n+m}{s} \]Qyun 讲了个生动的例子：\(n\) 个男人，\(m\) 个女人中选出 \(s\) 个人。这就很显然了。
然后答案就变成了：
\[ans=\sum_{d=0}^{\max(i,n-i)}\binom{n-1}{n-i-d} \]这个式子就已经很优了，我们直接前缀和优化求组合数就可以在 \(\mathcal{O(n\log n)}\) 的复杂度内解决了！
末
其他的明天再说。
标签：ch,uy,21,int,qr,模拟,binom,NOIP2024,define From： https://www.cnblogs.com/Ratio-Yinyue1007/p/18542558