Jason Fan.

「USACO18JAN」 Stamp Painting G 动态规划，dp优化 题面 题目描述 Bessie has found herself in possession of an NNN-unit long strip of canvas (1≤N≤1061 \leq N \leq 10^61≤N≤106) and she intends to paint it. However, she has been unable to acquire paint brushes. In their place she has MMM rubber stamps of different colors (1≤M≤1061 \leq M \leq 10^61≤M≤106), each stamp KKK units wide (1≤K≤1061 \leq K \leq 10^61≤K≤106). Astounded by the possibilities that lie before her, she wishes to know exactly how many different ...

「USACO18FEB」 Taming the Herd G 动态规划 题面 题目描述 Early in the morning, Farmer John woke up to the sound of splintering wood. It was the cows, and they were breaking out of the barn again! Farmer John was sick and tired of the cows’ morning breakouts, and he decided enough was enough: it was time to get tough. He nailed to the barn wall a counter tracking the number of days since the last breakout. So if a breakout occurred in the morning, the counter would be 0 that day; if the most recent breakout ...

NOIP 初赛复习....前言的前言：转载自 Here，当然有一部分是我写的。

XJ contest1587「树」 牛客「路径计数机」 树上差分，LCA 题意 给你一棵 nnn 个点的树和两个整数 p,qp, qp,q，求满足以下条件的四元组 (a,b,c,d)(a, b, c, d)(a,b,c,d) 的个数： 1≤a,b,c,d≤n1\le a,b,c,d \le n1≤a,b,c,d≤n 点 aaa 到点 bbb 的距离为 ppp 点 ccc 到点 ddd 的距离为 qqq 不存在一个点，它既在 aaa 到 bbb 的路径上，又在 ccc 在 ddd 的路径上 注：数据范围 测试点编号 nnn p,qp,qp,q 特殊性质 1 ≤30\le 30≤30 ≤30\le 30≤30 无 2 ≤50\le 50≤50 ≤50\le 50≤50 无 3，4 ≤200\le 200≤200 ≤200\le 200≤200 无 5 ≤3000\le 3000≤3000 =2=2=2 无 6 ≤3000\le 3000≤3000 ≤3000\le 3000≤3000 树是一条链 7 ≤3000\le 3000≤3000 ≤3000\ ...

https://vjudge.net/contest/387981 概率、期望基础训练解题报告，部分简单题题解较简略 A 「SGU495」 Kids and Prizes 题意 有n个奖品放在n个盒子里，有m个小朋友轮流去选择一个盒子，若有奖品则拿走。无论有没有奖品都要将空盒子放回去。问最后总共获得奖品的期望。n,m≤1×105n,m\le 1\times10^5n,m≤1×105 题解 一开始写了个假算法： f[i][j]f[i][j]f[i][j] 表前i个人选了j个礼物的概率， f[i][j]+=f[i−1][j]×(jn)f[i][j]+=f[i-1][j]\times (\cfrac{j}{n})f[i][j]+=f[i−1][j]×(nj​) 没选中 f[i][j]+=f[i−1][j−1]×(n−j+1n)f[i][j]+=f[i-1][j-1]\times (\cfrac{n-j+1}{n})f[i][j]+=f[i−1][j−1]×(nn−j+1​) 选中 f[1][1]=1f[1][1]=1f[1][1]=1 ans=∑ini×f[m][i]ans=\sum\l ...

线段树&多种毒瘤操作 柯朵莉树板题 重构了3次（我菜），旁边那位柯朵莉10minAC HDU - 4578 题意简述 给一个长度为nnn的序列（初始都为0），要求支持区间加，区间乘，区间赋值。询问区间一次和、二次和、三次和。 1≤n≤1000001\le n\le 1000001≤n≤100000 题解 别慌，就是操作多了点，多打几个懒标记而已 define 设 tagadd,tagmultagadd,tagmultagadd,tagmul 三种懒标记表区间加、乘。设 sum1,sum2,sum3sum1,sum2,sum3sum1,sum2,sum3 表示区间一次和、二次和、三次和。 Q：区间赋值到哪去了？ A：这其实可以转化为区间乘0再加vvv，还能减小码量 modify 考虑如何更新节点，区间[l,r][l,r][l,r]，操作值为vvv，len=r−l+1len=r-l+1len=r−l+1 (刚开始一脸蒙，还来发现其实只要展开就行了) 加法 sum1′=sum1+len×vsum2′=(al+v)2+(al+1+v)2+⋯+(ar+v)2=(al2+al+12+⋯+ ...

线段树+矩阵乘法（毒瘤题 ） LOJ - 2980 题意简述 给你nnn个三元组，表示为(Ai,Bi,Ci)(A_i,B_i,C_i)(Ai​,Bi​,Ci​) ；mmm次操作，每次选择一段区间，对于区间内的元素∀i∈[l,r]\quad \forall i \in [l,r]∀i∈[l,r]，有一下7种操作 令Ai=Ai+BiA_i=A_i+B_iAi​=Ai​+Bi​ 令Bi=Bi+CiB_i=B_i+C_iBi​=Bi​+Ci​ 令Ci=Ci+AiC_i=C_i+A_iCi​=Ci​+Ai​ 令Ai=Ai+vA_i=A_i+vAi​=Ai​+v (vvv为每次给的值，下同) 令Bi=Bi∗vB_i=B_i*vBi​=Bi​∗v 令Ci=vC_i=vCi​=v 分别求出∑i=lrAi\sum_{i=l}^r A_i∑i=lr​Ai​ , ∑i=lrBi\sum_{i=l}^r B_i∑i=lr​Bi​ 和 ∑i=lrCi\sum_{i=l}^r C_i∑i=lr​Ci​ 1≤n,m≤2.5×1051\le n,m \le 2.5\times 10^51≤n,m≤2. ...

字符串哈希+质因数分解 Luogu P3538 题意 给出一个由小写英文字母组成的字符串S，再给出q个询问，要求回答S的某个子串的最短循环节。 如果字符串B是字符串A的循环节，那么A可以由B重复若干次得到。 ∣S∣≤500000,q≤2000000|S| \le 500000 , q \le 2000000∣S∣≤500000,q≤2000000 题解 初看此题，感觉与 UVA10298 Power Strings 十分相似（但那题数据水啊，字符串hash+暴力即可），此题询问过百万肯定TLE。 考虑优化，首先一个很显然的命题： 判断区间[l,r][l,r][l,r]构成循环节长度为lenlenlen的循环只要判断hash[l,r−len]=hash[l+len,r]hash[l,r-len]=hash[l+len,r]hash[l,r−len]=hash[l+len,r]即可。这个证明很简单，不再赘述。 继续优化，可以发现循环节的个数是串长与串内每个字符个数的因数。也就是说要求出串长与串内每个字符个数的最大公约数ggg，再枚举ggg的因子，每次O(∣s∣),∣s∣O(\sqrt{| ...

引用自：link 浏览器调试console里输入 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061function TrexRunnerBot() { const makeKeyArgs = (keyCode) => { const preventDefault = () => void 0; return {keyCode, preventDefault}; }; const upKeyArgs = makeKeyArgs(38); const downKeyArgs = makeKeyArgs(40); const startArgs = makeKeyArgs(32); if (!Runner().playing) { Runner().onKeyDown(startArgs); setTimeou ...

匈牙利算法（二分图最大匹配），二分图最小点覆盖，二分图最小边覆盖，有向图最小路径覆盖，二分图最大独立集。 一些数量关系&定理 二分图最小点覆盖数 === 二分图最大匹配数 二分图最小边覆盖数 === 点的总数 −-− 二分图最大匹配数 有向图最小路径覆盖数 === 二分图最小边覆盖数 二分图的最大独立集数 === 点的总数 −-− 二分图最小点覆盖数 完美匹配的条件： XXX的点数 <<< YYY的点数 对于XXX的任意一个子集aaa,及其所连到的YYY中的点集bbb,满足所有∣a∣>∣b∣|a| > |b|∣a∣>∣b∣ 二分图最大独立集 定义：选一些点使其两两不相邻，这些点构成的集合为独立集。找到一个包含点数最多的独立集称为最大独立集。 定理：二分图的最大独立集数 === 点的总数 −-− 二分图最小点覆盖数 首先，我们假设最大匹配数为nnn，那至少nnn对点是相邻的，那么要删去大于等于nnn的点。其次，我们也知道最小点覆盖有nnn个，那么只删去这些点就能满足条件了（剩下的点肯定不相连），因为假如这些点间还有边，那这些边没有被最小点 ...