Panda2134's Blog

Not only coding

湖南省队雅礼集训Day5题解

Marshland 神网络流……思维固化导致没想出来…… 题意在一个 $n \times m$ 的网格内，每个格子有权值 $w_{i, j}$。保证 $i+j$ 为偶数的点权值为 $0$ . 要用最多 $m$ 个 $\text{L}$ 形的石头对网格进行部分的覆盖。石头不能重叠。每块石头会产生拐角处权值的收益。有 $k$ 个格子不能被石头覆盖。求最大收益。 $n \le 50...

Posted by panda_2134 on June 30, 2018

湖南省队雅礼集训Day3题解

circular 题意有一个长度为 $M$ 的环，环上有 $M$ 个等距离的点，按顺时针顺序依次标号为 $0, 1, 2, \dots, n$. 环上有 $N$ 个线段 $(a_i, b_i) (1 \le i \le n)$. 需要注意的是 $(a_i, b_i)$ 所指的线段是从点 $a_i$ 顺时针延伸到 $b_i$ 的线段。小 c 希望知道最多能选多少个不重叠的线段（线段的...

Posted by panda_2134 on June 22, 2018

湖南省队雅礼集训Day1题解

风格有点像 NOI2017，有送分题，但是并不很好写（不过似乎比去年 day2 游戏好写？）今天发挥还不错，争取把分数稳定下来。 Tree 对于操作 1 ，用一个变量记录。对于操作 2 ，对两点在原树上 $\text{lca}$ 的位置进行讨论。不妨设之为 $\text{lca_0}$ 。分为以下情况： $\text{lca}$ 在新根 $\text{rt}$ 与 $...

Posted by panda_2134 on June 20, 2018

PyFormula-用在线API实现的公式编辑器

发现 UOJ 群里面每次讨论学术的时候就有大量的公式出现，但是 QQ 并不能渲染 $\LaTeX$ ，所以很蛋疼。于是抽这几天晚上的时间，写了个调用CodeCogs和知乎API的公式编辑器，支持拖拽和监听剪切板。只需要把要渲染的公式给 Ctrl + C 一下，再 Ctrl + V 就可以把渲染过的粘贴出来了= = 介绍和下载链接求各位轻喷qwq

Posted by panda_2134 on June 15, 2018

吉老师的屯题计划1 - 题解

感觉自己综合解题能力还不够，于是刷刷吉老师做过的题。完成程度： 44 / 49 只有一部分有题解…… P4404 发现移除下一次出现更靠后的答案不会更坏。贪心即可。用 pb_ds的优先队列更方便 P4280 贪心好题。可以证明-1单调不减，然后直接DP，时空复杂度均为 $O(nk)$ P3565 直接DP，分别按照DFS序和BFS序转移。复...

Posted by panda_2134 on June 15, 2018

最长双回文串

Luogu-P4555 题意标题即题意。注意两个子串不能重复。思路并不会 $\text{Manacher}$ ，所以脑补了一种 $O(n \lg n)$ 的做法。首先考虑转化所有偶数长度回文串。每个字符之间以及开头结尾插入 # 即可全部转为奇数长度。然后可以维护正反串 Hash，每次枚举回文中心并且枚举回文串一半的长度。但是这样是 $O(n^2)$ 的。这个长度显然满足...

Posted by panda_2134 on June 6, 2018

OI日记

还有五十几天就要退役了。这几天非常低落，状态非常差。写点什么吧。写给自己看的，懒得加密了。如果有人想看就看吧。 2018.5.20 省队训练 day3. 又一次垫底。我不知道是哪一点没有做好。考场上一次次检查确认无误的 DP，交上去却爆零。别人第三题乱搞MST有65分，我加上了多次迭代取最优却适得其反，只有19. 似乎乱搞题从来就没有青睐过我，好像乱搞的人变成了我就总是会fs...

Posted by panda_2134 on May 20, 2018

[雅礼集训]Tree

真神。题意给出一个 $n (n \le 10^5)$ 个点的带权树（边权 $w_i \le 10^6$），以及 $q(q \le 100)$ 个修改边的操作，输出每次修改边后以及所有修改之前，树上满足最短路径边权值 $\gcd$ 是 $1$ 的无序点对数。思路首先考察莫比乌斯函数的容斥含义。这可以由 $\gcd = 1$ 想到。如下式： \(\sum_{d \backsla...

Posted by panda_2134 on May 3, 2018

2-SAT学习笔记

参考了这个Blog $O(nm)$ 算法假设一个点取 0，并且顺着往下标记；如果有矛盾，假设它取 1，再标记。如果取 0 或者 1 都不行，可以证明问题无解。代码：用感叹号标记的行对应于输出方案。注意从 $0$ 开始标号较为方便，此时输入编号后要减 $1$ . 点数是从句数目的两倍！ bool dfs(int u) { if(vis[u]) retu...

Posted by panda_2134 on April 22, 2018

[HNOI2007]梦幻岛宝珠

题意 01背包，但是 $c_i$ 范围很大（$c_i \le 2^{30}$），且可以分解为 $c_i = p_i \cdot 2^{q_i} (p_i \le 10, q_i \le 30)$ 的形式。思路膜拜了 PoPoQQQ 的题解。考虑泛化物品合并。按照 $q_i$ 不同，分为多个背包，即 $f(i, j)$ 表示背包容量为 $j \cdot 2^i$. 用对应背包装对...

Posted by panda_2134 on April 20, 2018