2008/10/11 / 电脑网络 » ProgramArt
NOIP初赛自己de笔记
Mod,div运算
总结起来就是mod和div都是先不看符号进行运算，然后mod的符号跟被mod的数一样，div的符号是“同正异负”。
And,or,xor运算
And:(奇偶乘法法则) 对于二进制的每一位and是(1,1)取1,(1,0)取0,(0,1)取0,(0,0)取0;
or: 对于二进制的每一位or是(1,1)取1,(1,0)取1,(0,1)取1,(0,0)取0;
Xor: (奇偶加法法则)
还有 A xor B=B xor A [交换率] A xor B=C <==> A xor C=B <==>C xor B=A
优先级: not>and(∧)>or(∨)
Shr,shl 运算
Shr: 右移N位 m shr n= m div 2^n (shr 1=div 2)
Shl: 左移N位 m shl n= m*2^n
第一类Stirling数
S[p,k]代表将n个物体排成k个非空的循环排列（就是圆圈）的方法数
S[p,k] =(p-1)*s[p-1,k] + s[p-1,k-1]
初始条件与S(p,k)一样是s(p,0)=0（p>=1）,s(p,p)=1。
证明：把p分两种情况分析：一是自己排成一个圈，有S(p-1,k-1)种；一种是和别人排在一个圈内，共有(p-1)*S(p-1,k)，系数(p-1)是因为p可以排在任何一个人的左边。
第二类Stirling数
S[n,m]代表将一个含有n个不同元素的集合划分成m个不相交的非空子集(盒子不做区分)的不同方案数
S[n,m]=m*S[n-1,m]+S[n-1,m-1]，其中1
For j:=1 to i do
If j=1 then s[i,j]:=1
Else s[i,j]:=j*s[i-1,j]+s[i-1,j-1];
(第一类和第二类Stirling数事实上的意义比上面讲到的要丰富，它们是P(n,p)与n^p这两组多项式向量空间的基互相表示的系数)
变形:
现有r个互不相同的盒子和n个互不相同的球，要将这n个球放入r个盒子中，且不允许有空盒子(vijos1210)
Ans:=s[n,r]*r! Or S’[i,j]:=j*(s’[i-1,j]+s’[i-1,j-1]);
Bell数:B_p表示将p个元素的集合划分成一些不可辨别的非空集合的方法数，由第二类Stirling数的定义，显然有：B_p = S(p,0) + S(p,1) + …… + S(p,p)。
还有一个递推式：B_p = ∑C(p-1,i)B_i (0<=i< p)
阅读全文
总结起来就是mod和div都是先不看符号进行运算，然后mod的符号跟被mod的数一样，div的符号是“同正异负”。
And,or,xor运算
And:(奇偶乘法法则) 对于二进制的每一位and是(1,1)取1,(1,0)取0,(0,1)取0,(0,0)取0;
or: 对于二进制的每一位or是(1,1)取1,(1,0)取1,(0,1)取1,(0,0)取0;
Xor: (奇偶加法法则)
| AxorB，就是要么A而不B，要么B而不A T xor F=F xor T=T T xor T=F xor F=F | 变成位运算就是不同取1，相同取0 1 xor 0=0 xor 1=1 1 xor 1=0 xor 0=0 |
优先级: not>and(∧)>or(∨)
Shr,shl 运算
Shr: 右移N位 m shr n= m div 2^n (shr 1=div 2)
Shl: 左移N位 m shl n= m*2^n
第一类Stirling数
S[p,k]代表将n个物体排成k个非空的循环排列（就是圆圈）的方法数
S[p,k] =(p-1)*s[p-1,k] + s[p-1,k-1]
初始条件与S(p,k)一样是s(p,0)=0（p>=1）,s(p,p)=1。
证明：把p分两种情况分析：一是自己排成一个圈，有S(p-1,k-1)种；一种是和别人排在一个圈内，共有(p-1)*S(p-1,k)，系数(p-1)是因为p可以排在任何一个人的左边。
第二类Stirling数
S[n,m]代表将一个含有n个不同元素的集合划分成m个不相交的非空子集(盒子不做区分)的不同方案数
S[n,m]=m*S[n-1,m]+S[n-1,m-1]，其中1
For j:=1 to i do
If j=1 then s[i,j]:=1
Else s[i,j]:=j*s[i-1,j]+s[i-1,j-1];
(第一类和第二类Stirling数事实上的意义比上面讲到的要丰富，它们是P(n,p)与n^p这两组多项式向量空间的基互相表示的系数)
变形:
现有r个互不相同的盒子和n个互不相同的球，要将这n个球放入r个盒子中，且不允许有空盒子(vijos1210)
Ans:=s[n,r]*r! Or S’[i,j]:=j*(s’[i-1,j]+s’[i-1,j-1]);
Bell数:B_p表示将p个元素的集合划分成一些不可辨别的非空集合的方法数，由第二类Stirling数的定义，显然有：B_p = S(p,0) + S(p,1) + …… + S(p,p)。
还有一个递推式：B_p = ∑C(p-1,i)B_i (0<=i< p)
阅读全文
2008/06/02 / 电脑网络 » ProgramArt
百度之星Astar2008初赛试题
1. 广告排名区间 (10分)
问题背景
shifen广告消费预估系统可以估计出一段时间内一个特定的广告在检索结果中排在各个位置的几率。比如系统对某广告的输出如下：
p1 = 0.03, p2 = 0.08, p3 = 0.04 ……
这说明该广告展现在第1位的概率是 3%，展现在第2位的概率是 8%，展现在第3位的概率是 4%……
问题是：如何给出一个排名估计区间[i, j]，使得广告出现在该区间中的概率大于或等于一个预设值p，同时这个区间所包含的元素尽可能的少。也可用数学语言来描述：给定数p和数列 p1, p2, … , pn，求 i和 j (1 <= i <= j <= n)，在满足pi + pi+1 + … + pj >= p的前提下让j-i 最小。
一般来说，pi只需保留6位小数就足够了。这样，若令ai=106pi，a=106p，则a和所有的ai均为[0,106]之间的整数。这样就避免了对实数的处理。
输入格式
第一行包含一个整数n (1 <= n <= 100,000)。
以下n行每行包含一个[0,106]内的整数，依次为a1，a2，…，an。这n个整数之和保证不超过106。
最后一行包含一个[0,106]内的整数a。保证所有ai之和不小于a。
输出格式
输出仅一行，包含一个整数，即j – i的最小值。
样例输入
7
5
8
4
7
10
5
2
18
样例输出
2
样例解释
a2=8, a3=4, a4=7之和为19，满足条件。而任何两个相邻数之和均小于18。
阅读全文
问题背景
shifen广告消费预估系统可以估计出一段时间内一个特定的广告在检索结果中排在各个位置的几率。比如系统对某广告的输出如下：
p1 = 0.03, p2 = 0.08, p3 = 0.04 ……
这说明该广告展现在第1位的概率是 3%，展现在第2位的概率是 8%，展现在第3位的概率是 4%……
问题是：如何给出一个排名估计区间[i, j]，使得广告出现在该区间中的概率大于或等于一个预设值p，同时这个区间所包含的元素尽可能的少。也可用数学语言来描述：给定数p和数列 p1, p2, … , pn，求 i和 j (1 <= i <= j <= n)，在满足pi + pi+1 + … + pj >= p的前提下让j-i 最小。
一般来说，pi只需保留6位小数就足够了。这样，若令ai=106pi，a=106p，则a和所有的ai均为[0,106]之间的整数。这样就避免了对实数的处理。
输入格式
第一行包含一个整数n (1 <= n <= 100,000)。
以下n行每行包含一个[0,106]内的整数，依次为a1，a2，…，an。这n个整数之和保证不超过106。
最后一行包含一个[0,106]内的整数a。保证所有ai之和不小于a。
输出格式
输出仅一行，包含一个整数，即j – i的最小值。
样例输入
7
5
8
4
7
10
5
2
18
样例输出
2
样例解释
a2=8, a3=4, a4=7之和为19，满足条件。而任何两个相邻数之和均小于18。
阅读全文
2008/05/22 / 电脑网络 » ProgramArt
CTSC2008 Day1,2题目下载
下载文件
2008/03/15 / 电脑网络 » ProgramArt
SHTSC2007 Day1,2题目+数据下载
2008/02/11 / 电脑网络 » ProgramArt
SPFA算法
这个算法，简单的说就是队列优化的bellman-ford,利用了每个点不会更新次数太多的特点发明的此算法
SPFA——Shortest Path Faster Algorithm，它可以在O(kE)的时间复杂度内求出源点到其他所有点的最短路径，可以处理负边。SPFA的实现甚至比Dijkstra或者Bellman_Ford还要简单：
设Dist代表S到I点的当前最短距离，Fa代表S到I的当前最短路径中I点之前的一个点的编号。开始时Dist全部为+∞，只有Dist[S]=0，Fa全部为0。
维护一个队列，里面存放所有需要进行迭代的点。初始时队列中只有一个点S。用一个布尔数组记录每个点是否处在队列中。
每次迭代，取出队头的点v，依次枚举从v出发的边v->u，设边的长度为len，判断Dist[v]+len是否小于Dist，若小于则改进Dist，将Fa记为v，并且由于S到u的最短距离变小了，有可能u可以改进其它的点，所以若u不在队列中，就将它放入队尾。这样一直迭代下去直到队列变空，也就是S到所有的最短距离都确定下来，结束算法。若一个点入队次数超过n，则有负权环。
SPFA 在形式上和宽度优先搜索非常类似，不同的是宽度优先搜索中一个点出了队列就不可能重新进入队列，但是SPFA中一个点可能在出队列之后再次被放入队列，也就是一个点改进过其它的点之后，过了一段时间可能本身被改进，于是再次用来改进其它的点，这样反复迭代下去。设一个点用来作为迭代点对其它点进行改进的平均次数为k，有办法证明对于通常的情况，k在2左右
代码如下：
下面还有篇论文可以看看
SPFA——Shortest Path Faster Algorithm，它可以在O(kE)的时间复杂度内求出源点到其他所有点的最短路径，可以处理负边。SPFA的实现甚至比Dijkstra或者Bellman_Ford还要简单：
设Dist代表S到I点的当前最短距离，Fa代表S到I的当前最短路径中I点之前的一个点的编号。开始时Dist全部为+∞，只有Dist[S]=0，Fa全部为0。
维护一个队列，里面存放所有需要进行迭代的点。初始时队列中只有一个点S。用一个布尔数组记录每个点是否处在队列中。
每次迭代，取出队头的点v，依次枚举从v出发的边v->u，设边的长度为len，判断Dist[v]+len是否小于Dist，若小于则改进Dist，将Fa记为v，并且由于S到u的最短距离变小了，有可能u可以改进其它的点，所以若u不在队列中，就将它放入队尾。这样一直迭代下去直到队列变空，也就是S到所有的最短距离都确定下来，结束算法。若一个点入队次数超过n，则有负权环。
SPFA 在形式上和宽度优先搜索非常类似，不同的是宽度优先搜索中一个点出了队列就不可能重新进入队列，但是SPFA中一个点可能在出队列之后再次被放入队列，也就是一个点改进过其它的点之后，过了一段时间可能本身被改进，于是再次用来改进其它的点，这样反复迭代下去。设一个点用来作为迭代点对其它点进行改进的平均次数为k，有办法证明对于通常的情况，k在2左右
代码如下：
procedure spfa(v:integer);
var
stack:array[1..10000] of integer;
use :array[1..800] of boolean;
len,i:integer;
now,q:integer;
begin
for i:=1 to n do begin d[i]:=maxnum;use[i]:=false;end;
len:=1;
stack[len]:=v;
d[v]:=0;
q:=1;
use[v]:=true;
while len>0 do
begin
now:=stack[q];
for i:=1 to l[now] do
if (d[p[now,i].t]>d[now]+p[now,i].d) then
begin
d[p[now,i].t]:=d[now]+p[now,i].d;
if not use[p[now,i].t] then
begin
inc(len);
stack[q+len-1]:=p[now,i].t;
use[p[now,i].t]:=true;
end;
end;
use[now]:=false;
inc(q);
dec(len);
end;
end;
var
stack:array[1..10000] of integer;
use :array[1..800] of boolean;
len,i:integer;
now,q:integer;
begin
for i:=1 to n do begin d[i]:=maxnum;use[i]:=false;end;
len:=1;
stack[len]:=v;
d[v]:=0;
q:=1;
use[v]:=true;
while len>0 do
begin
now:=stack[q];
for i:=1 to l[now] do
if (d[p[now,i].t]>d[now]+p[now,i].d) then
begin
d[p[now,i].t]:=d[now]+p[now,i].d;
if not use[p[now,i].t] then
begin
inc(len);
stack[q+len-1]:=p[now,i].t;
use[p[now,i].t]:=true;
end;
end;
use[now]:=false;
inc(q);
dec(len);
end;
end;
下面还有篇论文可以看看
