leiyuanze

该文被密码保护。 阅读全文

该文被密码保护。 阅读全文

摘要： $\text{Day1}$ 三个 $998244353$ 直接惊出一身汗 然后冷静下来写暴力 $T1$ 写完暴力扔了个判行与列和相不相等的假东西，随机都不想随机了，随意构造一下就能卡，只能过 $40pts$ 结果出来过了？！感谢数据 正解是随机一个行向量 $\vec v$，判断 $\vec v \t 阅读全文

摘要： $\text{Code}$ #include <bits/stdc++.h> using namespace std; template<typename Tp> void read(Tp &x) { x = 0; char ch = getchar(); int f = 0; for(; !isd 阅读全文

摘要： $\text{Solution}$ 有关斜率优化的强势套娃题，感觉套出了巅峰 ~~我整整写了 5 个小时、、、~~ 简单 $dp$ $$ f_{i,j} = f_{i-1,k-1} + (j-k+1)\max_{l=k}^j a_l $$ 固定这个最大值，于是原序列可用笛卡尔树结构表示 考虑左侧对 阅读全文

摘要： $\text{Solution}$ 很好的想法是用平面图欧拉定理 $E=V+F-2$ 那么就要解决的问题是环内的边数与面数 科技的使用：平面图转对偶图 建图过程大概就是将每条无向边拆成两条双向边，考虑找出所有按逆时针方向围成的最小面 那么这个只需要考虑每条的下一条边是谁，极角排序即可 把面当点，点的 阅读全文

摘要： $\text{Solution}$ 原题：$\text{Honorable Mention}$ 一个费用流做法，$S$ 向 $2i-1$ 连流量为 $1$，费用为 $0$ 的边，$2i$ 向 $T$ 连流量为 $1$，费用为 $0$ 的边 $2i-1$ 向 $2i$ 连流量为 $1$，费用为 $a_ 阅读全文

摘要： $\text{Solution}$ 肯定扫描线在考虑维护什么东西，假设 $r$ 右移时可以暴力得到所有新值，发现需要维护区间历史版本和以及区间当前值之和 这三个操作对于一个数来说变化次数都是 $O(logV)$ 的，所以可以暴力修改发生变化的值的位置 这显然是一段后缀，可以直接暴力更新，原因是考虑到 阅读全文

摘要： $\text{Conclusion}$ ~~显然只需要这个~~ $\text{LGV}$ 引理 只适用于有向无环图 定义 $\omega(P)$ 表示 $P$ 这条路径上所有边权的乘积 $e(u,v)$ 表示 $u$ 到 $v$ 每一条路径 $P$ 的 $\omega(P)$ 之和 起点集合 $A$ 阅读全文

摘要： $\text{Conclusion}$ ~~显然只需要这个~~ 矩阵行列式 定义矩阵的行列式 $\det(A)=\sum_p \mathbb{sgn} \prod a_{i,p_i}$，$p$ 为一个排列 交换矩阵两行行列式变为相反数，一行加减另一行若干倍行列式不变 求行列式的方法：高斯消元消成上三 阅读全文

摘要： $\text{Problem}$ 术树数 $\text{Summary}$ 这题有许多优美的结论，并加深了对线性基的理解 图论中非常有用的结论（路径可重）： 1.包含一个点的简单环张成了包含一个点的所有环 2.考虑图的任意一棵生成树，取两点树上路径权值和异或上任意环的异或值构成了这两点间的所有路径 阅读全文

摘要： $\text{Solution}$ 感觉是很套路的题 按 $LIS$ 分层后 $dp$ 很容易想到 注意到同层 $x$ 递增，$y$ 递减 所以很容易猜到决策单调性，但是每个点的决策集合是不同的区间，这与一般的决策单调性可不一样 怎么办呢？扔到线段树把决策区间相同的放在一块一起做，最终答案取 $\m 阅读全文

摘要： $\text{Solution}$ 这个问题是不好判断的 考虑简单点的，$(1,1)$ 到 $(h,w)$ 是否连通 那么只要在最外围一圈 #（显然一些位置不能加），判断 $(h+1,n)$ 和 $(0,w+1)$ 是否能通过 # 八连通即可 如果是双连通呢？只要这两点所在连通块不能通过只加一个 # 阅读全文

摘要： $\text{Solution}$ 学习到了一些 $dp$ 的 $trick$ 设 $f_{i,j}$ 表示用了 $i$ 的元素，当前和为 $j$ 的方案数 $dp$ 有两样不好处理的东西 第一是当前和不一定为整数 第二是可重集合的重复计数问题 关于问题二的解决只需钦定加数大小顺序即可 这个显然不能 阅读全文

摘要： $\text{summary}$ 又是写暴力的一天 $\text{T1【USACO 2020 US Open Platinum】 Exercise}$ 发现自己连 $dp$ 都不会了 考场暴力都写不出来的原因：不知如何计算各个环长确定的情况下对应排列的数目 因为没有逆元，没法直接排列组合计数。。。 阅读全文