1T
CMO 2023 Day1T1
\(n=2^{2024}\) 时最优方案为 \(2,2,\cdots ,4\) 此时 \(\lambda_0=\frac{1}{1012}\) 则 \(\lambda_{\min}\geq \lambda_0\)。对于 \(\lambda =\frac{1}{1012}\) 构造,令 \(n=\pr ......
NOIP模拟赛35T1T2
T1 KAMEN 只能说一言难尽。 60pt暴力模拟每一个石头往下掉的情况。 在这里,我并没有打暴力,而是用set存储了每一列的X和O的石子分布情况。当前节点的位置在(x, y),寻找x列中比y大的第一个位置在ny(这里可以用upper_bound),那么石子在这一列能往下掉到的位置就是(x, ny ......
JOISC 2014 D1T1 巴士走读
洛谷传送门 LOJ 传送门 考虑把边按到达时间排序,然后从前往后扫并做一个 dp。 设 \(f_u\) 表示 \(1\) 到达 \(u\) 的最晚出发时间。那么对于一条边 \((u, v, a, b)\): 若 \(u = 1\),则 \(f_v = \max(f_v, x)\); 否则 \(f_v ......
CWOI T1T2 训练
感觉难度还好? A - Intercity Travelling 点击查看代码 #include<bits/stdc++.h> #define int long long using namespace std; const int inf=1e18,mod=998244353,i2=(mod+1) ......
NOI2023 D1T2 桂花树
称编号 \(> n\) 的点为新点。 由条件 1 可以推出树 \(T\) 为结点 \(1 \sim n\) 在树 \(T'\) 上的 虚树。 由条件 2 可以推出 \(\forall 1 \le u < v \le n + m, \operatorname{lca}(u, v) \le v + k\ ......
JOISC 2022 D1T1 监狱
[洛谷传送门](https://www.luogu.com.cn/problem/P9520 "洛谷传送门") [LOJ 传送门](https://loj.ac/p/3685 "LOJ 传送门") 观察可得,若存在合法解,则一定存在一种解,使得每个人都不停顿地从起点走到终点。 因为如果一个人走到一半 ......
省选 2023 D1T2 城市建造
显然地,这 $t$ 座城市一定由每个连通块出一座得来,换言之,新修建道路的两城市原来一定不连通。 进一步可以想到,若选择了 $u, v$ 两座城市且它们连通,则 $u \rightsquigarrow v$ 上的所有城市都应被选择。 更进一步地可以推出,若选择的城市同属一个点双,则该点双内的所有城市 ......
[九省联考 2018 D1T3] 秘密袭击
考虑转化为求 $\ge i$ 的权值个数 $\ge k$ 的联通块数量。 设 $f(u,i,j)$ 表示 $u$ 子树内含 $u$ 联通块内权值 $\ge i$ 的有 $j$ 个的方案数,$g(u,i,j)$ 维护子树的和,也就是最终答案。发现转移非常简单所以可以写成生成函数: $$ F(u,i) ......
CEOI Team Selection D1T2 Prosjek
首先全奇全偶的情况是容易的,将 $\bmod4$ 意义下相同的合并即可保持原来的奇偶状态,当只有两个是直接合并即可,归纳即可说明全奇全偶一定合法。 但关键的问题在于奇偶状态可能互相影响,一个直观的想法是将奇合并为一个 $x$,偶合并为一个 $y$,如果 $x,y$ 的奇偶性相同,那么它们即可合并,即 ......
pkusc2023 d1t3
整自闭了,快一个月后才想出来怎么做。 设点 $i$ 是 1 的概率为 $p_i$,定义 $P_i(x)=1-p_i+p_ix$。那么 $p_i$ 是 $i$ 的儿子节点和自己的 $P(x)$ 卷起来后取后一半的系数和。 树上修改很魔怔,考虑 ddp。维护每个点轻儿子和自己的 $\prod P(x)$ ......