Loading... # ABCD略 # E - Ranges on Tree ## 题意 题面写的很长。大意是给定一个有根树，需要给每个节点赋一个区间，要求： * 父节点完全包含子节点区间 * 没有父子关系节点的区间不相交 然后要求所有节点中的区间出现的数字，其最大值最小。 ## 分析 其实就是给叶节点依次编号，然后父节点求子节点的并就好了。 用dfs可以快速实现。 叶节点依次编号可以保证用的数字尽量小，所以能够保证最优解。 ## 代码 ```cpp #define N 200005 int n; vector<int> nxt[N]; int root = 1; int l[N], r[N], fa[N]; bool vis[N]; int use = 0; void dfs(int now = root) { vis[now] = true; for (auto v : nxt[now]) { if (vis[v]) continue; fa[v] = now; dfs(v); } if (!l[now]) l[now] = r[now] = ++use; if (now != root) { if (!l[fa[now]] || l[now] < l[fa[now]]) l[fa[now]] = l[now]; if (!r[fa[now]] || r[now] > r[fa[now]]) r[fa[now]] = r[now]; } } int main() { int n; cin>>n; FOR(i,1,n-1) { int x, y; cin>>x>>y; nxt[x].pb(y); nxt[y].pb(x); } dfs(); FOR(i,1,n) cout<<l[i]<<' '<<r[i]<<endl; return 0; } ``` # F - Sum Sum Max ## 题意 给定数列$C$由一些连续相同段构成，也就是$C=\mathop{con}\limits_i(\{x_i\}*y_i)$。 $B$是$C$的前缀和，$A$是$B$的前缀和。 求$A$中的最大值。 有条件$|x_i|\le4$ ## 分析 对于$C$中任意一个连续段来说，它在$C$中是零次的，因而在$B$中就是线性的，在$A$中就是二次的。因此我们推一下公式，对于每个$\{x\}*y$直接推出它在$A$中的端点和极值就可以了。 假设$B$、$A$在上一段右端点分别为$u$、$v$，那么有： $$ B_i=u+ix $$ $$ A_i = v+\sum_{j=1}^i(u+jx)=v+iu+\frac{i(i+1)}{2}x=\frac{1}{2}xi^2+(u+\frac{1}{2}x)i+v $$ 这样就可以直接求出$B$、$A$新的端点也就是$u$、$v$来了。 接下来考虑$A$中最大值，如果$x>0$那么$A$是凹的，最大值只考虑端点就行。 如果$x<0$，那么$A$在 $$ -\frac{\beta}{2\alpha}=-\frac{2u+x}{2x} $$ 处取得一个极大值。首先判断这个极大值在$[1,y]$内，然后把这个它的上下取整值得到的数列实际能取到的离散值更新答案即可。 ### 学到的东西 注意表达式的阶数，每个部分既然都不超过二阶，那么用二次函数公式很好求端点值、极值。 ## 代码 ```cpp int t, n, m; #define N 200005 #define M 1000000009 // terms ll ca(ll i, ll x, ll u, ll v) // calcA { return v + u * i + i * (i + 1) / 2 * x; } int main() { cin >> t; while (t--) { cin >> n >> m; ll u = 0, v = 0; // b,a ll ans = LLONG_MIN; while (n--) { ll val, len; cin >> val >> len; if (val < 0) { double tt = -(double)u/val-0.5; if (tt >= 1 && tt <= len) { ll a = max(ca(ceil(tt), val, u, v), ca(floor(tt), val, u, v)); ans = max(ans, a); } } ans = max(ans, ca(1, val, u, v)); v = ca(len, val, u, v); u = u + val * len; ans = max(ans, v); } cout << ans << endl; } return 0; } ``` # G - Teleporting Takahashi ## 题意 四连通的三维空间，经过$N$步恰从$(0,0,0)$点走到$(X,Y,Z)$点，问共有多少种方案。 ## 分析 首先考虑一个简单的二维情况，走$M$步从$(0,0)$走到$(X,Y)$，这里要用一个非常牛逼的技巧。 首先由于是四连通的，所以位移 $$ (\Delta x, \Delta y)\in\{(1,0),(0,1),(-1,0),(0,-1)\} $$ 注意到$X$和$Y$轴上都有$1$、$0$、$-1$三种情况，这个组合很难写。 那么我们把$X$和$Y$**转换到一组非正交基上就可以了，比如旋转**$45^\circ$，那么我们就得到了 $$ (\Delta (x+y), \Delta (x-y))\in\{(1,1),(1,-1),(-1,1),(-1,-1)\} $$ 此时我们分开考虑每一维，比如$X+Y$维，事情变得非常简单（用$p、n$分别表示$+1、-1$）： $$ \left\{ \begin{aligned} p-n & = & X+Y \\ p+n & = & M \end{aligned} \right. $$ 解得 $$ \left\{ \begin{aligned} p & = & \frac{M+X+Y}2 \\ n & = & \frac{M-X-Y}2 \end{aligned} \right. $$ 从而得到一个非常简单的两类排列问题，答案就是$\binom{M}{p}$。另一个维度也这样做一下，然后相乘，得到最后结果为 $$ \binom{M}{\frac{M+X+Y}2}\binom{M}{\frac{M-X+Y}2} $$ 然后再把第三维考虑进来，只需要枚举第三维上走的步数然后插入（插空）即可。 ## 代码 ```cpp #define N 10000007 #define Mod 998244353 int n, x, y, z; ll fac[N], inv[N], finv[N]; ll C(ll n, ll k) { if (n < k) return 0; if (n < 0 || k < 0) return 0; return fac[n] * finv[k] % Mod * finv[n - k] % Mod; } int main() { cin >> n >> x >> y >> z; x = abs(x), y = abs(y), z = abs(z); fac[0] = fac[1] = finv[0] = finv[1] = inv[1] = 1; FOR(i, 2, 10000000) { fac[i] = fac[i - 1] * i % Mod; inv[i] = Mod - inv[Mod % i] * (Mod / i) % Mod; finv[i] = finv[i - 1] * inv[i] % Mod; } ll ans = 0; for (int i = z; i <= n; i++) { ll m = n - i; if ((m + x + y) & 1 || (m - x + y) & 1 || (i - z) & 1 || m < (x + y) || (m - x - y) & 1) continue; ans = (ans + C(m + 1, i) * C(m, (m + x + y) / 2) % Mod * C(m, (m - x + y) / 2) % Mod) % Mod; } cout << ans; return 0; } ``` # Ex - © 允许规范转载 打赏 赞赏作者 赞 如果觉得我的文章对你有用，请随意赞赏