文章

题目大意 有一个长度为 $n$ 的非负整数序列 $a_i$，每次可以选择一段区间减去 $1$，要求选择的区间长度 $\in[l,r]$，问最少多少次把每个位置减成 $0$。 不保证有解，$1 \leq l \leq r \leq n \leq 10^6,\ r – l + 1 \geq 阅读更多…

wrp 划水记录 (cnblogs.com) 题意 给定一张连通无向简单图 $G$，每条边有一个边权。 给定正整数 $k$，你需要找到 $G$ 的一条从 $1$ 到 $n$ 的路径，设该路径的长度为 $l$，你需要使得这条路径中边权前 $\min\left{ k, l \right&#12 阅读更多…

记录一下出题的过程。 关于 t1： 这是最早就定好的，在萱有次模拟赛看错题的时候就觉得可以作为一个简单题放上去。 开始觉得还行，在某一个周末突然意识到是个笛卡尔树板子，但是似乎更好地对标 noip t1 了，所以没关系。 造数据的时候重造了好几次，不小心全造成大数据了，不小心 srand() 有问题 阅读更多…

不难看出这是一道差分约束的题目。 但是如果想按照通常的题目那样去建边的话，就会发现这句话——相邻两站的距离至少是 1 公里——建边后就直接让整个题出现了负环 (默认是按求最短路建边)，没法做了。 这时我们就需要使用断环为链的技巧。 可以设 $len$为地铁环线总长 那么就需要把 $a→b(a>b)$ 阅读更多…

之所以现在放是因为之前忘了（流水账 Day-4 写了 ICPC 的一道 DP，有点细节，虽然写得有点难受，但挺好玩 Day-3 写了 PKUSC2018 最水的一题 是随机开的题 Day-2 可以去 pkusc 了，从今天中午开始停课 刚吃完饭就开始模拟考试，晕晕乎乎的，好在 dalao 们上午考 阅读更多…

题目大意 Problem Link IOI 农场是一个种植苹果的农场，以位于一个巨大的环形湖周边而闻名。 在 IOI 农场，共有 $N$ 个员工，从 $1$ 到 $N$ 标号。共有 $M$ 棵苹果树，从 $1$ 到 $M$ 标号。湖的周长为 $L$ 米。 在初始时刻，第 $i$ ($1 \leq i 阅读更多…

用途 求积性函数前缀和。 要求该积性函数在质数点的取值为关于 $p$的多项式或者可以用完全积性函数模拟出来。 简介？ $\text{Min25}$筛还有一个本质上等价的筛法叫洲阁筛， 其本质来源于扩展的线性筛法。 不妨考虑一下线性筛法的复杂度瓶颈， 其统计答案利用的是枚举每个质因子去贡献其倍数的答案 阅读更多…

支持下 Qiuly ~ QWQ。 转置原理是一种基于矩阵转置的方法， 用以解决二元生成函数的相关问题。 初等矩阵（有基础的同学可以跳过）要学会转置原理，首先要知道初等矩阵。 通过高斯消元，我们已经知道了矩阵的初等变换： 把两行（列）互换。 把某行（列）乘一非零常数 $k$（其实是零也行，只是不 阅读更多…

很妙的一道计数题 思路 首先可以明确如果枚举每种连边情况 暴力计算连通块时间复杂度是不可接受的（题目中%1e9+7 不就表明了这一点）因此考虑计算每一种连通块的总出现次数 即对答案的贡献（“因此” 好难想）性质： 如果设 $(l1,r1)$,$(l2,r2)$分别为两条连边且 $l1< 阅读更多…

我水平很菜，你忍一下。 题面 树形 DP。 首先可以发现， $m>2$ 时，难受度只出现在最大的头吃的果子上（因为我把果子分成最大的头吃的和其他的，其他的里面，相邻的果子让不同的头吃即可）。 然后我定义 $f_{i,j,k}$ 为当前为 $i$ 节点，当前节点分 $j$ 个果子给最大的头，当前节点选 阅读更多…