AI Models Blog

Flows Explained Simply: A Visual Guide

diffusion

flow-matching

generative-models

Imagine a river with currents flowing in different directions at different locations.

Understanding Diffusion and Flow Matching Models

diffusion

flow-matching

generative-models

A deep dive into the mathematics behind diffusion models and flow matching, two powerful approaches to generative modeling.

Constructing the Training Target

diffusion

flow-matching

generative-models

A conditional probability path is a set of distribution \(\mathbf{p}_t(x | z)\) over \(\mathbb{R}^d\) such that

Welcome to My AI Blog

news

introduction

Welcome to my blog! This is where I’ll be sharing my thoughts and explorations on AI models.

SRM 654 DIV 1

algorithms

imported

SquareScores http://community.topcoder.com/stat?c=problem_statement&pm=13694&rd=16318&rm=325638&cr=23296695 Let a random variable \[X\] denote the total combined score for…

A nice trick for computing modular multiplicative inverses for first n consecutive numbers in linear time

algorithms

imported

Suppose we want to find \[i^{-1}\bmod{m}\] for \[ 1\leq i \leq n\] assuming \[ m > n\], and m is a prime. An intuitive way is to compute modular inverse for each i by using…

Weird mod behaviour when using #define

imported

notes

It turns out that

Binary Raise Algorithm

algorithms

imported

Given \[f(x)\], we want to compute \[f^k(x)\] where \[f^k(x)=\overbrace{{f(...f}}^k(x))\] and \[f^1(x)=f(x)\]. In other words, \[f^k(x)\] is the result after applying \[f(x)\]…

SRM 653 DIV 1

algorithms

imported

CountryGroupHard http://community.topcoder.com/stat?c=problem_statement&pm=13688&rd=16317&rm=325529&cr=23296695 Solution Dynamic Programming Definitions A** group** is a…

Zoutendijk’s condition

imported

notes

Consider any iteration of the form \(x_{k+1}=x_k+\alpha_k p_k\) where \(p_k\) is a descent direction and \(\alpha_k\) satisfies the Wolfe conditions:

Some notes about fundamentals of Unconstrained Optimization

imported

notes

Given \[\mathbf{f(x_k+\alpha t)\approx f(x_k)+\alpha p^T \nabla f(x_k)}\], the steepest decent direction is \[\mathbf{-\bigtriangledown f_x}\] Proof: Let p be a unit vector…

Backpropagation Derivation

algorithms

imported

Although I learnt it a long time ago, I haven’t had a chance to derive it formally, now it’s time to do it. Definitions There are n layers, the last layer is the output…

Solution for the Critical Isotherm from Van Der Waals Equation

imported

notes

At critical temperature \[T_c\], and critical Pressure \[P_c\], the Van Der Waals Equation has exactly one solution for the critical molar volume \[\bar{V}_c\] \[…

Codeforces Round #286 (Div. 2) D. Mr. Kitayuta’s Technology

algorithms

imported

1. Building a graph G(V,E) from input 2. Reduction Let G’(V,E’) be a graph such that (u,v) \[\in\] E’ iff (u,v) or (v,u) \[ \in \] E. Finding connected components of G’…

Conversion between Factorial Numbers and Permutations

algorithms

imported

Conversion methods can be found in http://en.wikipedia.org/wiki/Factorial_number_system A naive algorithm takes \[O(n^2)\], which can be reduced to \[O(nlogn)\] if segment…

Round #282 (Div. 2) C. Treasure

algorithms

imported

Consider a string S consisting of ‘(’ and ‘)’ characters. Let left[i] be the number of ‘(’ in S[0..i], right[i] be the number of ‘)’ in S[0..i] for \[ 0 \leq i<n \] Let…

Round #283 (Div. 2) E. Distributing Parts

algorithms

imported

http://codeforces.com/contest/496/problem/E Greedy Algorithm Sorting songs and actors first by their lower bounds then by their upper bounds in non-decreasing order. For…

Round #283 (Div. 2) D. Tennis Game

algorithms

imported

http://codeforces.com/contest/496/problem/D Crucial insight: Given t, there are at most \[\frac{n}{t}\] total sets. (We want to minimize the size of each set and the size of…

Beta Round #1 C. Ancient Berland Circus

algorithms

imported

Finding a regular polygon with smallest area given three corner points A,B and C. (The Following angles are represented in radians.) First we need to find the radius of the…

Some Segment Tree problems

algorithms

imported

UVA 11235 just do a normal range search on frequency table. Here is the code:

Proof of ” perfect squares <=> a number which has an odd number of factors”

imported

notes

Proof of ” perfect squares \[\Rightarrow\] a number which has an odd number of factors” Let a perfect square n=\[k^2\], k is a natural number. Let \[k=p_0^{r_0}p_1^{r_1}\]…\[…

Proof of Evenshtein Distance

imported

notes

There is a little mistake here, I have fixed it with blue pen. Source:http://www.cs.uiuc.edu/~jeffe/teaching/algorithms/notes/05-dynprog.pdf

Got in top 11 in UVA problem 143 “Orchard Trees”

imported

notes

Explanation of the binary shift method for Josephus Problem

imported

uncategorized

“The most elegant form of the answer involves the binary representation of size n: f(n) can be obtained by a one-bit left cyclic shift of n itself.” Link: http://en.wikipedia…

Udacity CS255 finally made it through….

imported

notes

[embed]/images/uploads/2013/08/certificate.pdf[/embed] This course is horrible,literally.If I took this course as the first course at Udacity, I will never come back to it.…

USACO 4.2 Job Processing analysis

algorithms

imported

First we look at the first “A” machine problem: Suppose we got N jobs. Denote machine_delay[j] be the earliest time we can start a job on jth machine Denote C[i] be the…

An important proof of Hungarian algorithm

algorithms

imported

Proposition:we only need to check every node in one set of vectors of bipartite graph exactly once. Proof:Let G be a bipartite graph with bipartition X,Y,Let vector v∈X. We…

USACO 4.2 Ditch

algorithms

imported

I thought I must have flunked my final exams cause I did a really bad job in this term(always got up little,missed huge amount of classes,spent plenty of time playing…

网络流的一些个人证明

imported

notes

1.对于一个网络流G=(V,E),u∈V-{s},前置流f:V×V\(right\)R. f(V,u)=f(A,u)-f(u,B) (A={v∈V|f(v,u)>0};B={v∈V|f(u,v)>0}) 证明：f(V,u)=f(A,u)+(-f(u,B))=f(A,u)-f(u,B)

最大流最小割定理个人理解

imported

notes

1.首先很重要的一个引理：任意割的净流量都是相同的，且与流的值相等。直观上很容易理解，个人证明：设流网络G=(V,E) 假如一割净流量与流的值不等，那肯定有剩余的流从源点经由网络流之外的路线到达汇点，那么表示对于u,v∉E,存在f(u,v)≠0且-f(v,u)≠0。…

压入与重标记算法中不存在顶点v∈V-{s,t},且h(v)=h(s)证明

imported

notes

假设存在顶点v∈V-{s,t},且h(v)=h(s)，意味着e(v)=0（因为无法有流量进入此点）,且这个顶点一定被重标记过，根据算导引理26.15（溢出的顶点可以被压入或重标记），可知此顶点重标记前（设为v’)为溢出顶点，那么e(v’)>0。…

算法导论 Edmonds-Karp算法时间复杂度证明

imported

notes

这里有几点解释下： 1.什么原理？根据BFS基本原理以及所有边的权值都为1的特性，因为是一层一层搜索，所以最早搜索到的增广路经一定是所有增广路经中最短的。 2.为何每个顶点最多搜索一次？…

算法导论第26章网络流引理26.1证明

imported

notes

引理26.1 设G=(V,E)是一个网络流，f是G中的一个流。那么下列等式成立：证明：设点a,b\(\in\)X,根据反对称性f(a,b)=-f(b,a),且f(X,X)中有X中元素数目个组{f(a,b),f(b,a)|a,b\(\in\)X},所以总和为0，引理成立。证明： f(X,Y)=\(\sum{x \in…

USACO 4.1 Fence Rails题解

algorithms

imported

本人习惯不写题解，但此题给我的印象过于深刻，写的时候有想死的感觉。。。。。。囧此题乃本人第一次见到如此恶心的搜索题，花4个小时修改一直超时，最后去看了下大牛的剪枝的思路才完成。题解在代码注释里： [php] /* PROG:fence8 LANG:C++ / //#include “stdafx.h” #include #include …

DFSID迭代加深搜索

algorithms

imported

具体原理很简单，先搜索1..K层搜索树，若无解，则继续搜索1..K+1层搜索树。时间复杂度分析：设：节点度数为c，完整搜索一个深度为d的树（这里d的定义:根的深度为1)。总搜索次数： \(c^0\)+(\(c^0+c^1\))+(\(c^0+c^1+c^2\))+…+(\(c^0+c^1+c^2+...+c^{d-1}\)) =\({1-c…

两个互质的数a,b，ax+by(x,y,a,b≥0)最大不能表示为ab-a-b证明

imported

notes

条件：gcd(a,b)=1，(a,b∈\(\mathbb{N}\)) 若可以表示为ab-a-b则： ab-a-b=ax+by 因为有解，所以可以凑出一个特殊解，取解（-1，a-1)正好等式成立根据一元二次不定方程通解公式得出通解（-1-bt,a(t+1)-1） ∵-1-bt≥0…..① a(t+1)-1≥0…..② 两式联立解得：$…

USACO 4.1 Beef McNuggets DP上界证明

algorithms

imported

假设两个数是a，b，如果c可以用a，b表示，则意味着不定方程

素数无穷性的证明

imported

notes

素数有无穷多个。现在已知最早的证明方法是欧几里得在他的《几何原本》中提出的，该证明方法如下：

二元一次不定方程通解公式推导

imported

notes

方程：px+qy=m(p,q,m∈\(\mathbb{Z}\)) 根据裴蜀定理当且仅当d|m时方程有解且有无数个整数解。假设有解，两边约掉公约数d,设新方程为 ax+by=c(a,b,c∈\(\mathbb{Z}\)) 且gcd(a,b)=1 存在一组整数解（\(x_0,y_0\)),假设另一组整数解为（\(x_1,y_1\)) \(ax_0+…

裴蜀定理

imported

notes

对任意两个整数、，设是它们的最大公约数。那么关于未知数和的线性丢番图方程（称为裴蜀等式 ）：

扩展欧几里德算法

imported

notes

计算满足d=gcd(a,b)=ax+by (a,b∈\(\mathbb{N}\)) 当b=0时： d=a=gcd(a,0)=ax+by,取x=1,y=0时满足。当b≠0时： d=d’=gcd(b,a mod b)=bx’+(a mod b)y’=bx’+(a-[\(a/b\)]b)y’ =ay’+b(x’-[\(a/b\)]y’)…

gcd(n,n+1)=1 证明

imported

notes

gcd(n,n+1)=1 (n >0或n<-1,n\(\in \mathbb{N}\)) 若gcd(n,n+1)=d>1 (d\(\in \mathbb{N}\)) 设：n=ad,n+1=bd,\(a,b \in \mathbb{N}\) bd-ad=1\(\Rightarrow d=1/{b-a}\) ∵b>a ∴d<0,与假设d>1矛盾…

纪念在深圳打得第一场也应该是最后一场比赛

miscellaneous

imported

最近参加了个2012深圳石岩广羽杯业余羽毛球赛小组赛结果：小组第一并且完胜淘汰赛（最终）结果：B组单打亚军战利品：奇怪的尤尼克斯球包。。。。感觉淘汰赛只发挥了50%，主要是过度紧张打不开，很多球撞框。。。另外还有气氛和体能原因。需要加强体能训练。

如果a和b是不都为0的任意整数，则gcd(a,b)是a与b的线性组合集合{ax+by:x,y∈Z}中的最小正元素证明

imported

notes

[Image unavailable: 定理31.2.png] 31.4在下面：算导证明的相当简洁漂亮！参考资料：《算法导论》-第七部分算法研究问题选编-第31章有关数论的算法-定理31.2 及式31.4

对于在vector中当前迭代器在末尾时使用pop_back()出错解决方法

imported

notes

[cpp] #include “stdafx.h” #include #include using namespace std; vector test; bool Delete(vector::iterator it) //确认是否删除，若是返回真，否则返回假。 { if(*it==3) { test.pop_back(); return…

计算几何-线段相交

imported

notes

1.相互进行跨立试验若都成功，相交否则 2.若出现边界情况看点是否在线段上，若是，则相交否则不相交。具体代码：

任意二维多边形面积

imported

notes

推导过程：设多边形有N个顶点。去原点与个顶点连线，将多边形分为N个三角形，按顺序用叉积将有向三角形面积相加即可。（这里提一下：有向面积比无向面积更本质！) [Image unavailable: 推导.png]

向量的向量积

imported

notes

笔记：向量的大小：\(delim{|}{vec{a}}{|}delim{|}{vec{b}}{|}s\in theta\) 向量的方向：右手螺旋法则 1.行列式的记法：计算i向量，遮住i向量，向右走，计算j向量，遮住j向量，继续向右走，走到头回到第一个，以此类推，这样子j向量表示不用加负号。 2.\(vec{a}\)·(\(vec{b}*ve…

欧拉路径错误原因研究

algorithms

imported

这几天写USACO3.3 Fence那一题时，出现了一个怪错误，在第7个点出现了连续经过同一个点的解，非常郁闷。。。。后来发现将顶点加入解得过程写到遍历其边的循环中，这样的写法在欧拉回路中没问题，但到了非欧拉回路的欧拉路径是会出现问题。如图：这种情况下，以起点1寻找路径时，首先1-2-3到终点一条路径，然后以1自身的回路为一条路径，就产生…

Dijkstra的堆优化时间复杂度【转载】

algorithms

imported

使用二叉堆(Binary Heap)来保存没有扩展过的点的距离并维护其最小值，并在访问每条边的时候更新，可以把时间复杂度变成O((V+E)logV)。…

诗【无题】

miscellaneous

imported

用生成器生成的，反正我挺无语的。【无题】作者：一台pc

BFS如何记录路径【转帖】

algorithms

imported

在写某道USACO的时候第一次遇到这个问题.(表示本人遇到的某题和这位的某题一样。。。）首先，我想到了一种方法：从遍历的方案队列中寻找需要的方案. 在那道usaco中，遍历的实际上是一个三叉树，我们可以像二叉树一样根据节点编号来推断父节点或者子节点.如下图：推算起来比较麻烦……

a*b=gcd(a,b)lcm(a,b)个人证明

imported

notes

设: a=\({p_1}^e1{p_2}^e2...{p_r}^er\) b=\({p_1}^f1{p_2}^f2...{p_r}^fr\) 所以 ab=\({p_1}^e1{p_2}^e2...{p_r}^er{p_1}^f1{p_2}^f2...{p_r}^fr\) 因为gcd(a,b)=\({p_1}^{m\in(e1,f1)}{p_2}^…

一个圆盘，旋转速度为V度，360个时间单位后必回到初始状态。

imported

notes

证明:360V%360=0 即使有若干个圆盘以不同的速度旋转，在360个时间单位后都回到初始状态，在一些问题中这点很关键。

组合数快速算法【转载】

imported

notes

计算组合数最大的困难在于数据的溢出，对于大于150的整数n求阶乘很容易超出double类型的范围，那么当C(n,m)中的n=200时，直接用组合公式计算基本就无望了。另外一个难点就是效率。对于第一个数据溢出的问题，可以这样解决。因为组合数公式为： C(n,m) = n!/(m!(n-m)!)…

今天看了下11年ACM的队名，我彻底无语了。。。。。。

miscellaneous

imported

尤其是北大的《弱爆了》。。。。。

在这吐槽下，USACO输出格式真是欠扁。。。！

imported

notes

再次对这种无聊的固定长度表示强烈鄙视！害我一次过的变成十几次才过。。。囧。。。

在一个有限的范围内，若干个物体以各自的规则移动，范围内可能会有若干障碍物，构成死循环的条件证明。

imported

notes

为方便证明，假设空间维度为2。设：死循环不具有周期性设有n个物体，每个物体坐标为\(x_i,y_i (1<=i<=n)\) 设由若干种不同的状态设为Q={\(x_i,y_i\)|\((1<=i<=n)\)}构成的状态集合为P 假设在时间无限的情况下，因为不具有周期性，所以一定会得到具有所有可能状态的状态集合P,下一步状态{{\(x_i,y_…

史上最无语的冷笑话。。。【转载】

miscellaneous

imported

3x12=36 2x12=24 1x12=12 0x12=18 这个实在是太冷了。。。。

如果你是ACMer,你会选择哪个职业?【转自某牛博客】（巨搞！）

miscellaneous

imported

下午受ACM-DIY群里的大神们的启发YY了一套ACMer的技能. 以下十个职业参照WoW.如果你是ACMer,你会选择哪个职业? 战士: 拦截:阻止对方一个AC. 战斗怒吼:友方程序效率提高100%,持续10分钟断筋:使对方无法提交,持续20分钟雷霆一击:周围目标程序效率降低99%,持续10分钟致死打击:过了80%数据就算AC…

USACO第一章通关！

miscellaneous

imported

怎么说呢，也没有太多感想，第一章水题还是比较多的，不过纠正了一些不良的习惯（如写完就手贱按F5…),记录了一下常犯的错误，还是感觉花的时间太长了，看来得集中精力刷第二章。。

USACO上看到一个极妙的分数[0,1]排序。

algorithms

imported

0/1                                                              1/1
                               1/2
                  1/3                      2/3
        1/4           …

【转】sstream数字与字符串相互转换

algorithms

imported

[php] #include #Include string num2str(double i) { stringstream ss; ss<<i; return ss.str(); } //字符串转数字： int str2num(string s) { int num; stringstream ss(s); ss>>num;…

写了个生命游戏，无聊做下数据统计。

miscellaneous

imported

和原版的有些差别，每个周期每个方块有一定概率P出现生命，以便持续打破平衡，观察发展。区域大小400 [Image unavailable: 六十分之一.jpg] 生命体数量平均

回文词细节问题

imported

notes

注意可以一个在中间也可以二个相同的在中间。

C++文件读入所有字符（空格，换行符。。。）方法

imported

notes

fin.get(ch)函数并且没达到末尾返回1，否则返回0 [php] while(fin.get(ch)) //这样更简便 { ….. } [/php]

USACO S1.3 Barn Repair 贪心证明

algorithms

imported

证明1：用M个板子所得的最小长度不会比用K（$ 1<=K<M\()个板子所得的最小长度大（在非空畜栏数量大于可购买的最多的板子数量时）若在用K个板子所得最优解中，存在至少覆盖一个空的畜栏的某一个板子，将板子分开，空过空的畜栏，显然最优解会更小。…

USACO S1.3 Mixing Milk 贪心证明

algorithms

imported

将牛奶单价以不递减顺序排列：P={A1，A2，A3，…,An} 贪心规则：按牛奶单位价格重小到大选择卖家且其储存量>0，每次若所需量>=该卖家可供给量则全部买完，否则仅买所需量，所需量=0到此结束。证明归纳基础：至少有一个最优解包含选择1.…

思路启示

imported

notes

1.出现有序序列查找，想到二分。 2.出现一对多的生成情况，转换为多对一生成，可以有效减少计算。 3.出现排列问题（选择的先后效果一样），像这种 1,2,3,4,5 和 5,4,3,2,1 相等采用非递减/非递增排列，有效减少计算。 4.遇到某问题思路清楚，但数据需要排序，但是数据量过大或者必须用高精度，那么一定有可以简化到手工排序的方法。…

USACO/milk2 个人题解

algorithms

imported

==分段动态规划==
时间复杂度（nlogn),全部0毫秒。
以开始时间从小到大快排每个农民

快排后：

f[i]表示第i个农民所在的最长连续线段
last_start表示这个线段的起点。
a[i].begin 第i个农民的起点时间，a[i].end 终点时间

可以得出方程：
f[i]={max{f[i-1],a[i].end} …

环问题处理方法

imported

notes

如果不方便处理，可以把这个环转成链再复制两边。

二分答案需注意的细节问题

imported

notes

[php] l:=0;r:=max; while l<=r do begin mid:=(l+r)shr 1; if check(mid)then r:=mid-1 else l:=mid+1 end; ans:=l; [/php] 因为循环结束后有两种可能：上一次循环设r=l+1 mid=[(2l+1)/2]=l…

验证二分图

imported

notes

染色法：开始对任意一未染色的顶点染色，之后判断其相邻的顶点中，若未染色则将其染上和相邻顶点不同的颜色，若已经染色且颜色和相邻顶点的颜色相同则说明不是二分图，若颜色不同则继续判断. 判断是否有奇数环：

位运算相关【转载】

imported

notes

功能 | 示例 | 位运算 -———————+—————————+——————– 去掉最后一位 | (101101->10110) | x shr 1 在最后加一个0 | (101101->1011010) | x shl 1 在最后加一个1 | (101101->1011011) | x shl 1+1 把最后一位变成1 |…

Tarjan的理解

imported

notes

Tarjan算法基于定理：在任何深度优先搜索中，同一强连通分量内的所有顶点均在同一棵深度优先搜索树中。也就是说，强连通分量一定是有向图的某个深搜树子树。根据Tarjan: low(u)=min(dfn(u),(low(v),u与v相连且v在栈中)) 其实low(u)是表示u所在的强连通分量的根的dfn值。…

链式前向星【转帖】

imported

notes

普通前向星好是好，可是如果数据规模大，排序他也不是O(1)时间，也许你排个序就把时间耽误了，不合适，这时候用邻接矩阵存不下，你还不会写邻接链表，怎么办呢？链式前向星！先介绍一下链式前向星的组成： HEAD数组：记录每个顶点的起点位置 E数组：记录每条边的终点 NEXT数组：记录下一条边的位置…

弗洛伊德求最小环算法

imported

notes

spfa及其优化【转载】

imported

notes

procedure spfa; begin fillchar(q,sizeof(q),0); h:=0; t:=0;//队列 fillchar(v,sizeof(v),false);//v[i]判断i是否在队列中 for i:=1 to n do dist[i]:=maxint;//初始化最小值 inc(t); q[t]:=1;…

贪心证明法

imported

notes

[Image unavailable: QQ截图20111105192205.jpg] [Image unavailable: QQ截图20111105192224.jpg] [Image unavailable: QQ截图20111105192240.jpg] [Image unavailable: QQ截图20111105192301.jpg]…

2007问题求解1

imported

notes

给定n个有标号的球，标号依次为1，2，…，n。将这n个球放入r个相同的盒子里，不允许有空盒，其不同放置方法的总数记为S(n,r)。例如，S(4,2)=7，这7种不同的放置方法依次为{(1) , (234)} , {(2) , (134)} , {(3) , (124)} , {(4) , (123)} , {(12) , (34)} …

2007问题求解2

imported

notes

N个人在操场里围成一圈，将这N个人按顺时针方向从1到N编号，然后从第一个人起，每隔一个人让下一个人离开操场，显然，第一轮过后，具有偶数编号的人都离开了操场。依次做下去，直到操场只剩下一个人，记这个人的编号为J(N)，例如，J(5)=3，J(10)=5，等等。则J(400)= 。（提示：对N=2m+r进行分析，其中0≤r<2m）。列出来：…

比较法排序为何能以最少的对换次数完成证明

imported

notes

首先，设有n个元素且最值不再第一位（仅为方便证明，如在第一位，则问题变成第2位~第n位，不影响）限制条件：元素归位后不再调换（后面将会证明此条件可达成最小次数）比较法：将最小（大）的放在第一位后…

最大和连续子序列问题

imported

notes

我们令F(n)表示[0,n]区间内以d[n]为结尾的最大和，d为原序列，那么有： F(n + 1) = Max{d[n + 1],F(n) + d[n + 1]} = d[n + 1] + Max{0, F(n)} 为什么不用考虑F(n-1) + d[n ]+d[n+1 ] 的情况呢？ F(n-1) + d[n ]+d[n+1 ] F(n) +…

15届noip初赛问题求解2

imported

notes

2、某个国家的钱币面值有1，7，7^2，73共计四种，如果要用现金付清10015元的货物，假设买卖双方各种钱币的数量无限且允许找零，那么交易过程中至少需要流通______张钱币。首先先看10015分别包含多少个上述面值的钱币，那么我们要把10015化成10015=a7^{3+b7^{2+c7^{0+d7^0 这种形式看起来是不是很熟悉？…}}}

15届noip提高组初赛问题求解1

imported

notes

因为拓扑排序只需满足题目叙述的条件，所以可以先选取一条最长的（为方便计算），选择1,2,3,7,6. 将4插入到合适的位置，只需满足3->4,4->6 所以有两种 1,2,3,4,7,6 1,2,3,7,4,6 第二步，看5 同理，5只需满足1->5即可那么有6种。第三步，看8和9 若合起来看，不用满足任何条件，那么有8种，…

完全二叉树 Fp=[Cp/2]证明

imported

notes

完全二叉树 Fp=[Cp/2]

终于想明白为什么单调队列因入队而删掉的元素不影响最值。

imported

notes

入队的元素出对原因只有2种–过期或者被更大（小）的元素删除此元素过期那么被删掉的元素均过期，所以不影响。被删除那么新进入的更大（小）的元素比删掉的元素（更早删除的）仍然更优，所以不影响。否则此元素仍为最大(小)，所以不影响。

Henry拣钱(money.pas/c/cpp)

imported

notes

背景描述：最近,Henry由于失恋(被某大牛甩掉！)心情很是郁闷.所以,他去了大牛家,寻求Michael大牛的帮助,让他尽快从失恋的痛苦中解脱出来.Michael大牛知道Henry是很爱钱的,所以他是费尽脑水,绞尽脑汁想出了一个有趣的游戏,帮助Henry….. 题目描述：…

挖地雷问题

imported

notes

挖地雷问题来源：NOIP1996（提高组）第三题（有改动）【问题描述】在一个地图上有N个地窖（N<=20），每个地窖中埋有一定数量的地雷。同时，给出地窖之间的连接路径。如图3 图3 当地窖及其连接的数据给出之后，某人可以从任一处开始挖地雷，然后可以沿着指出的连接往下挖（仅能选择一条路…

新年趣事之打牌

imported

notes

新年趣事之打牌来源： vijos P1071 【问题描述】过年的时候，大人们最喜欢的活动，就是打牌了。xiaomengxian不会打牌，只好坐在一边看着。这天，正当一群人打牌打得起劲的时候，突然有人喊道：“这副牌少了几张！”众人一数，果然是少了。于是这副…

石子合并注意地方。

imported

notes

在f[i,1]的时候没有石子合并，所以为0，而不是第i个石头的重量。读取重量时只用读取sum[i,1]即可。

最长不下降子序列注意问题

imported

notes

在所有f[i]求完后，注意不能直接输出f[n]，而应逐个寻找最大值，因为f[i]表示在前i个数字中最长不下降子序列，但是以第a[i]数结尾.所以不是每个f[i]都能取到。

Untitled

imported

notes

采药 TYVJ P1005

imported

notes

0/1背包注意事项（重要）

imported

notes

for i:=1 to n do for j:=0 to m do to m 因为 f[i,j]中w[i]可以等于j，表示在前i件物品中选取若干放入剩余空间为j的背包中，w[i]的重量可以为剩余空间总重量，这样将会调用f[i-1,0]。 ……

滑雪 tyvj P1004

imported

notes

if (map[i-1,j]>map[i,j])and(f[i-1,j]>=m) then begin m:=f[i-1,j];judge:=true end; if (map[i+1,j]>map[i,j])and(f[i+1,j]>=m) then begin m:=f[i+1,j];judge:=true end; if…

数的计数

imported

notes

var sum:integer; function num(x:integer):integer; var i,s:integer; begin if x=1 then num:=1 else begin s:=0; for i:=1 to (x div 2) do s:=s+num(i); num:=s+1 end end;{num}…

tyvj 表达式计算 P1040

imported

notes

最大公约数和最小公倍数问题

imported

notes

题目:最大公约数和最小公倍数问题问题编号:304 题目描述输入二个正整数x0,y0(2<=x0<100000,2<=y0<=1000000),求出满足下列条件的P,Q的个数条件: 1.P,Q是正整数 2.要求P,Q以x0为最大公约数,以y0为最小公倍数. 试求:满足条件的所有可能的两个正整数的个数. 输入格式第一行，两个整数，x0，y0…

取石子问题

imported

notes

有一种很有意思的游戏，就是有物体若干堆，可以是火柴棍或是围棋子等等均可。两个人轮流从堆中取物体若干，规定最后取光物体者取胜。这是我国民间很古老的一个游戏，别看这游戏极其简单，却蕴含着深刻的数学原理。下面我们来分析一下要如何才能够取胜。（一）巴什博奕（Bash…