文章

题外话 说起来我作死做这题是觉得这个程序可以十块钱卖给化学组骗餐饭吃，结果发现氧化还原反应配不了，因为有什么归中不交叉率云云可以确定唯一配平系数，但是可怜的程序做不到，所以这个赚钱计划宣告破产 QAQ 解析 首先我们把每一个物质的系数看做未知数，把每一种元素看做方程，那么根据等号两边的元素系数相等可 阅读更多…

1. 题目 传送门=￣ω￣= 2. 题解 先遍历一遍图，建立二叉树。 再树型 dp 即可，对于当前节点，枚举给它左儿子多少，右儿子多少。 代码： #include <bits/stdc++.h> using namespace std; int n,q,f[105][105],l[105 阅读更多…

1. 题目 传送门=￣ω￣= 2. 题解 裸树型 dp 设 f1[i] 为选该节点的最小花费，f2[i] 为不选该节点的最小花费 $f1[i]=\sum{min(f1[son[i]],f2[son[i]])} + 1$ $f2[i]=\sum{f1[son[i]]}$ #include <bi 阅读更多…

1. 题目 传送门=￣ω￣= 2. 题解 裸树型 dp 设 $f1[i]$表示选 i 时的最大收益，$f2[i]$表示不选 i 时的最大收益。 $f1[i]=\sum{f2[son[i]]} + v[i]$ $f2[i]=\sum{max(f1[son[i]],f2[son[i]])} + v[i] 阅读更多…

不看题解我不会 题意: 有 k(k<=100) 个人粉刷 n 面连续的篱笆 (n<=16000)。第 i 人做在 Si 位置上，手有 Li 长，也只能刷 Li 面连续篱笆，并且必须刷第 Si 面。或者他可以一面也不刷。第 i 人每刷 1 面得 Pi 元。求最多得的钱。 思路: 如果我们用 阅读更多…

什么是单调队列 单调队列就是元素单调的队列，譬如一个队列中的元素为 1，2，3，4，5，6，单调递增，这就是一个单调队列。咱们先看一道单调队列的模板题：poj2823/洛谷 P1886 怎么维护单调队列呢？譬如维护一个单调递增的队列，就是要进入一个元素的时候，把队尾小于它的元素统统出队即可。而在例题 阅读更多…

1. 题目 传送门=￣ω￣= 2. 题解 强联通分量，缩点模板题。 第一个问题的答案是缩点以后入度为 0 的点的个数 第二个问题的答案是缩点以后入度为 0 的点的个数和出度为 0 的点的个数中较大的那个 如果只有 1 个强联通分量，那么第二问答案为 0，需要特判 至于证明的话，可以看这个，我懒得写了 阅读更多…

1. 题目 传送门=￣ω￣= 2. 题解 abs 大佬太强啦！这题打了 170 行。。。蒟蒻的 3 倍啊 Orz 此题最小费用最大流模板题，也许能用二分图的最大权匹配做。 abs 的题解：https://www.mina.moe/?p=1440 代码： #include <bits/stdc+ 阅读更多…

题意: 给定很多个数 (100000 以内个 100000 以内的数), 求选出三个数使其要么两两互质，要么两两不互质，的方案数。 分析: 如果用一条红边连接互质的数，黑边连接不互质的数。那么我们就要求单色三角形的数目。这样的问题往往可以通过补集转化转化为求双色三角形的数目，再用三角形总数减去双色三 阅读更多…

不想多说什么，再次错过一次 AK 机会 T1 青蛙的烦恼 蛤の烦恼 ⃢ — ⃢ 设 $f(i,j,k)$为在区间 $[l,r]$内，位置为 k 时遍历所有坐标的最短路径。 $dis(i,j)$表示从点 i 到点 j 的距离 这样空间复杂度为 $n^3$，1e9 无法接受 不难发现 k 只可能为 i 阅读更多…