<![CDATA[C' est La vie]]> http://www.redswallowz.com/blog/index.php zh-cn http://www.redswallowz.com/blog/read.php?241 <![CDATA[NOIP初赛自己de笔记]]> redswallow <redswallowjysc@126.com> Sat, 11 Oct 2008 11:46:05 +0000 http://www.redswallowz.com/blog/read.php?241 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: (奇偶加法法则)
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
还有    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]，其中1For i:=1 to n do
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)

Catalan数
H (0) = 1
H (n) = H (0) H (n-1) + H (1) H (n-2) + H (2) H (n-3) … + H (n-2) H (1) + H (n-1) H (0)
=> H (n) = (1/ (n+1)) * C (n, 2n)

数字划分模型
*NOIP2001数的划分
将整数n分成k份，且每份不能为空，任意两种分法不能相同(不考虑顺序)。
d[0,0]:=1;
for p:=1 to n do
for i:=p to n do
for j:=k downto 1 do inc(d[i,j],d[i-p,j-1]);
writeln(d[n,k]);
*变形1：考虑顺序
d[ i, j] : = d [ i-k, j-1] (k=1..i)
*变形2：若分解出来的每个数均有一个上限m
d[ i, j] : = d [ i-k, j-1] (k=1..m)

错位排列
递推
d[1] = 0; d[2] = 1;
d[n] = (n-1) * (d[n-1] + d[n-2])
排列组合
d[n] = C(n,0)*n!-C(n,1)*(n-1)!+...-...C(n,n)*0!
       = ∑(-1)^k*c(n,k)*(n-k)!  (k=0 to n)
错位排列前5项: D[2]=1 d[3]=2 d[4]=9 d[5]=44

Pascal集合运算
+:并 –差(A-B表示属于A但不属于B) *:交 <=:包含于 >=:包含
硬件
图灵, “计算机科学之父”,提出一种计算机抽象模型,该计算模型现在被大家称为“图灵机”
1944年，美籍匈牙利数学家 冯•诺依曼 提出计算机基本结构和工作方式的设想，为计算机的诞生和发展提供了理论基础。
1946, 美国宾夕法尼亚大学, 世界上第一台电子计算机ENIAC
冯诺依曼与莫尔小组研制了离散变量自动电子计算机EDVAC 第一台现代意义的通用计算机, 1949, 世界上第一台存储程序式计算机 EDSAC（电子延迟存储自动计算机）
世界上第一个高级程序语言：Fortran, 一美国人发明于20世纪50年代
Pascal创始人: 1970瑞士N.Wirth 尼克劳斯.沃斯
地址总线AB  地址总线的位数决定了CPU可直接寻址的内存空间大小
数据总线DB  传送数据信息, 其位数通常与微处理的字长相一致
控制总线CB  传送控制信号和时序信号
微机内存储器的地址是按字节编址，寄存器的位数是计算机字长

进制与编码
带符号二进制数最高位：0正1负
原码、反码和补码表示(计算机用补码表示数)
真值+0和-0的补码表示是一致的
8位二进制补码能表示数的范围是-128..+127, 不存在-128的8位原码和反码形式
浮点数:  
E——阶码（Expoent），是有符号的整数
S——尾数（Mantissa），是数值的有效数字部分，一般规定取二进制定点纯小数形式。

汉字信息编码
汉字输入码: 区位码（数字码）、音码、形码、音形码
汉字交换码: GB2312－80标准包括了6763个汉字，按其使用频度分为一级汉字3755个和二级汉字3008个。一级汉字按拼音排序，二级汉字按部首排序
字形存储码: 也称字模

网络
网络的主要功能：资源共享 信息传输 分布处理 综合信息服务
Internet的服务有：电子邮件、远程登陆、文件传输、信息服务等
我国Internet的发展情况: 1989年我国第一个公用分组交换网CNPAC建成运行
已陆续建成与Internet互联的四个全国范围的公用网络：
中国公用计算机互联网（CHINANET）、中国金桥信息网（CHINAGBN）
中国教育和科研计算机网（CERNET）、中国科学技术网（CSTNET）

OSI 的七层体系结构：
应用层 应用层协议的代表包括：Telnet、FTP、HTTP、SNMP等
表示层
会话层
运输层 传输层协议的代表包括：TCP、UDP、SPX等
网络层 数据包packet 网络层协议的代表包括：IP、IPX、RIP、OSPF等
数据链路层 帧frame 数据链路层协议的代表包括：SDLC、HDLC、PPP、STP、帧中继等
物理层 比特bit

TCP/IP：用于网络的一组通讯协议。
包括IP(Internet Protocol)和TCP(Transmission Control Protocol)
TCP/IP 协议把Internet网络系统描述成具有四个层次功能的网络模型
1. 链路层：这是TCP/IP 结构的第一层，也叫网络接口层，其功能是提供网络相邻节点间的信息传输以及网络硬件和设备驱动。
2. 网络层：（IP协议层）其功能是提供源节点和目的节点之间的信息传输服务，包括寻址和路由器选择等功能。
3. 传输屋：（TCP 协议）其功能是提供网络上的各应用程序之间的通信服务。
4. 应用层：这是TCP/IP最高层，其功能是为用户提供访问网络环境的手段，主要提供FTP、TELNET、GOPHER等功能软件。

IP地址: IP地址分A、B、C、D；E五类
最高位1..126为A类，128..191是B类，192..223是C类

域名：计算机名.组织结构名.网络名.最高层域名

路由器：所谓“路由”，是指把数据从一个地方传送到另一个地方的行为和动作，而路由器，正是执行这种行为动作的机器，它的英文名称为Router, 是一种用于连接多个网络或网段的网络设备。工作在网络层。（交换机，归于网桥，在数据链路层）
集线器：Hub，集线器的主要功能是对接收到的信号进行再生整形放大，以扩大网络的传输距离，同时把所有节点集中在以它为中心的节点上。它工作于OSI第一层。其不具备交换机所具有的MAC地址表，所以它发送数据时都是没有针对性的，而是采用广播方式发送。
网桥：网桥工作在数据链路层，将两个LAN连起来，根据MAC地址来转发帧，可以看作一个“低层的路由器”。 网桥通常比路由器难控制，网桥则只用MAC地址和物理拓扑进行工作。因此网桥一般适于小型较简单的网络。
MAC地址（Media Access Control, 介质访问控制）地址是识别LAN（局域网）节点的标识。

NAT:全称Network Address Translation(网络地址转换)
ICMP:全称Internet Control Message Protocol(Internet控制消息协议)，该协议是TCP/IP协议集中的一个子协议，主要用于在主机与路由器之间传递控制信息
PPPoE:全称PPP over Ethernet(以太网上的点对点协议)，通过PPPoE技术，可以让宽带调制解调器(比如ADSL Modem)用户获得宽带网的个人身份验证访问，能为每个用户创建虚拟拨号连接，这样就可以高速连接到Internet
DDNS:全称Dynamic Domain Name Server(动态域名解析系统)
POP3：POP 即为 Post Office Protocol 的简称，是一种电子邮局传输协议，支持“离线”邮件处理
SMTP：简单邮件传输协议，SMTP 是建模在 FTP 文件传输服务上的一种邮件服务，主要用于传输系统之间的邮件信息并提供来信有关的通知。SMTP 重要特性之一是其能跨越网络传输邮件，即“ SMTP 邮件中继”。 可实现相同网络上处理机之间的邮件传输，也可通过中继器或网关实现某处理机与其它网络之间的邮件传输。
Tags - , ]]> http://www.redswallowz.com/blog/read.php?155 <![CDATA[百度之星Astar2008初赛试题]]> redswallow <redswallowjysc@126.com> Mon, 02 Jun 2008 08:16:07 +0000 http://www.redswallowz.com/blog/read.php?155 问题背景
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。

2. LZW网页判重 (20分)
问题背景
有一种简单的网页判重的方法，通过求两个网页内容的最长公共子序列(LCS)长度来判定两个网页的相似程度。如：
（网页A）老师：请用“果然”造句。
（网页B）学生：先吃水果，然后喝汽水……
它们的最长公共子序列为“果然”，长度为2。注意这里的“子序列”并不要求连续。
类似的，下面两个网页：
（网页A）老师：请用“果然”造句。
（网页B）学生：先吃水果，然后喝汽水，果然拉肚子……
最长公共子序列还是“果然”，长度为2。但不难看出，由于“果然”两个字在网页B中也曾连续出现，第二组网页比第一组更加“相似”。为了区分开这两种情况的区分度，我们改用一种称为LZW的理论。为了严格的叙述相似度的计算方法，我们首先定义“文本单元”。
假定网页用一个不包含空白字符（空格、回车换行、水平制表符）的字符串来表示。它只包含纯文本，没有标签。在计算相似度之前，你应该首先对该字符串进行处理，划分成一个个“文本单元”。每个文本单位可以是一个中文字、英文单词（由一个或多个连续的半角英文字母和数字组成，正规表达式为[a-zA-Z0-9]+）、或者一个标点符号。
根据上述定义，同一个标点符号的全角和半角应该被作为不同的文本单元，尽管他们看起来可能很相近；每个单独全角英文和全角数字都应该被看成一个单独的文本单元，而连续的半角英文字母和数字应被看成一个整体。总之，全角的字符可以与中文字同等对待。
这样，网页被看成文本单元序列。例如，网页“内容？１２345６??web2.00#”切分出的文本单元序列为（为了显示方便，用下划线分隔各文本单元）：
内_容_？_１_２_345_６_?_?_web2_._00_#

而网页“why内容相似??1234567890,web#00”的切分结果为：
why_内_容_相_似_?_?_1234567890_,_web_#_00

黑体部分给出了两个网页的一个公共子序列。注意“内容”、“??”分别在两个网页中都是连续出现的文本单元。为了奖励这种情况，LZW规定一段由连续k个文本单元组成的字符串权值为k2。在刚才的例子中，“内容”、“??”的权值均为4。但“00”是一个数字串，应当被看成一个单独的文本单元。所以权值仅为1。

根据上述规则，公共子序列“内容 ?? 00”的权值为22+22+1=9。在所有可能的子序列中，这个权值是最大的。
给定两个网页，求他们的LZW相似度，即所有可能的公共子序列中的最大权值。
注意
1) 输入的网页内容以GBK编码(参见FAQ)
2) 除了大小写英文字母和数字之外的其他半角字符均视为标点符号。

输入格式
包含两行，分别是网页A和B对应的字符串（不包含空白字符）。每行至少包含5个字节，最多包含200个字节。
输出格式
输出仅一行，包含一个整数，为两个网页的LZW相似度。

样例输入
内容？123456??web2.00#
why内容相似??1234567890,web#00
样例输出
9
样例解释
尽管两个网页里看上去都有“123456”但一方面第一个网页中混杂的全角和半角字符，而另一方面，即使全部改成半角字符，由于数字串“123456”和“1234567890”将分别看成一个单独的文本单元，因此无法部分匹配。  

3. 钉子与木板 (30分)
问题背景
墙上有n个钉子，编号为1, 2, ..., n。其中钉子i的横坐标为i，纵坐标初始为xi。可以进行两种操作：
0 k v：移动操作。竖直移动钉子k，坐标变为(k, v)。
1 s t v：测试操作。若在高度为v处放一块横坐标范围是[s,t]的水平木板，它将下落到什么高度？换句话说，求出钉子s, s+1, s+2, …, t的纵坐标中，不超过v的最大值。如果这些钉子的高度全部大于v，则木板将落到地上，高度为0。
注意，在测试操作时，水平木板只是用来测试的“临时木板”，将在测试后立即被拿走，不会影响到后续测试工作。

输入格式
第一行包含两个整数n, m，即钉子的个数和操作的个数（1<=n,m<=105）。以下n行每行一个不超过109的非负整数，即xi。以下 m 行为各操作 （1 <= k <= n, 1 <= s < t <= n, 1 <= v <= 109 ）
输出格式
按照输入的顺序，对于每个测试操作输出一个整数，即该测试水平木板的最后高度。

样例输入
5 4
1
3
5
7
9
1 2 4 6
0 3 10
1 3 5 7
1 3 5 5
样例输出
5
7
0

4. 圆面覆盖 (40分)
问题背景
在平面上有一个长为L，宽为W的长方形，左下角坐标为(0,0)，右上角坐标为(L,W)。给定一些圆，第i个圆的圆心坐标为(xi,yi)，半径为Ri。
你的任务是求最小的正实数k，使得把每个圆的半径变为原来的k倍后（即：第i个圆半径变为kRi，圆心位置不变），长方形将被这些圆完全覆盖。换句话说，长方形内部或边界上的任意点均至少在一个圆的内部或边界上。

输入格式
输入第一行包含三个整数n, L, W（1<=n<=50，1<=L,W<=1000），即圆的个数、长方形的长和宽。
以下n行，每行三个不超过1000的正整数xi, yi和Ri。
输出格式
仅一行，包含一个实数k，保留小数点后三位。

样例输入
1 2 2
1 1 1
样例输出
1.414
Tags - , , ]]> http://www.redswallowz.com/blog/read.php?153 <![CDATA[CTSC2008 Day1,2题目下载]]> redswallow <redswallowjysc@126.com> Thu, 22 May 2008 07:19:41 +0000 http://www.redswallowz.com/blog/read.php?153 点击这里下载文件
or 请到http://www.immortalleyuan.com/download/
OI目录下 CTSC2008.rar
Tags - , ]]> http://www.redswallowz.com/blog/read.php?103 <![CDATA[SHTSC2007 Day1,2题目+数据下载]]> redswallow <redswallowjysc@126.com> Sat, 15 Mar 2008 10:23:03 +0000 http://www.redswallowz.com/blog/read.php?103 点击这里下载文件
or 请到http://www.immortalleyuan.com/download/
OI目录下 SHTSC2007.rar
Tags - , , , , ]]> http://www.redswallowz.com/blog/read.php?72 <![CDATA[SPFA算法]]> redswallow <redswallowjysc@126.com> Mon, 11 Feb 2008 14:05:38 +0000 http://www.redswallowz.com/blog/read.php?72
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;


下面还有篇论文可以看看
引用
最短路算法及其应用.rar

Tags - , ]]> http://www.redswallowz.com/blog/read.php?37 <![CDATA[一个数学编程题站 - Project Euler]]> redswallow <redswallowjysc@126.com> Sun, 13 Jan 2008 05:41:39 +0000 http://www.redswallowz.com/blog/read.php?37 Project Euler和Euler其实没什么关系。它是一个趣味数学题的Online Judge，(国内应该做得人还不多)，题目都是提交答案式的。说是一个Programming Exercises倒八九不离十，对那些想学习并快速熟悉一些比较高级的语言的人来说，是一个不错的选择。它提供了一系列的问题，按照官方的说法，require more than just mathematical insights to solve，但是同时你还必须会Program，否则就是mission impossible。每个题目刚给出时分值是20分，被解决的次数越多分数就越低，所以个别仅供热身或练打字的题目(例如Problem 1：Add all the natural numbers below 1000 that are multiples of 3 or 5)只有2分。
还有就是推荐给想玩玩数论应用题的人，这上面也涉及了一些基本数论的知识。比如，Pell方程与连分数的关系，二次型方程的整数解等等。

另外一个特点是，所有题目都遵守“One-minute rule”,意思是，如果你有有效的算法，那么所有这些题目都能在一台过得去的电脑上在一分钟之内找出答案。

刚刚已经去刷了几道，hehe...寒假准备用c++ Mathematica去练练。

转自[ADN.cn]Library
http://adn.cn/blog/article.asp?id=85
Tags - , , , , ]]> http://www.redswallowz.com/blog/read.php?29 <![CDATA[酷毕了的javascript,让你随意编辑网页!]]> redswallow <redswallowjysc@126.com> Tue, 01 Jan 2008 05:36:27 +0000 http://www.redswallowz.com/blog/read.php?29 code:
javascript:document.body.contentEditable='true'; document.designMode='on'; void 0
回车,OK,你就可以随意编辑这个这个页面了.
想想google的页面被自己改得面目全非,是不是过足了黑客瘾啊...
还没过足的话,那就暂时别关浏览器吧!也不要刷新当前页,刷新了你所做的一切都不见滴
Tags - , , ]]> http://www.redswallowz.com/blog/read.php?5 <![CDATA[Noip2007普及+提高解题报告 --RS版]]> redswallow <redswallowjysc@126.com> Sun, 16 Dec 2007 04:21:42 +0000 http://www.redswallowz.com/blog/read.php?5 NOIP2007tg解题报告.doc
点击这里下载文件
NOIP2007pj解题报告.doc
点击这里下载文件


NOIP 2007 普及组 解题报告
By Redswallow

奖学金
解题思路:
排序,模拟…ms怎么做都行
水题是肯定要拿满分的，所以题目一定要看清楚了

奖品分组
解题思路:
贪心
2种贪心方法
排序，2个指针扫描最小和最大配 ，可以的i+1,j-1，不行j-1，直到i>j
排序，i从小到大，找能和当前奖品a[i]可以配到的最大奖品a[j]
推荐第一种方法复杂度O(N)
注意这里排序可选用桶排or快排



守望者的逃离
解题思路:
这是本次比赛最难的一道
Dp
f[i][j]表示在时间为I，且魔法值为j (0<=j<=13)的时候所能走的最远路程
f[i,j]=max{f[i-1,j-4],f[i-1,j]+17,f[i-1,j+10]+60}   (1<=i<=t)
优化：f[i][j]均只需要f[i-1][j],可采用滚动数组进行降维
复杂度O(T*14)
这里再讲一个枚举的方法，比dp更优
枚举停多少次(t),因为你开始停和后来魔法没有了再停的效果是一样的
这样你知道整个过程中可以用多少魔法。
魔法总是要尽量用掉的，所以可以在O(1)复杂度内算出可以用多少次魔法，和要走多少次
就可以算出停t次走到S需多少秒，这个结果是唯一确定的，
若小于，记录最小值
若大于，调整计算最远走到的s
总的复杂度O(T)
var m,s,t,i,mm,ss,s1,s2,tt,t1,t2:longint;{mm:能用多少魔法;s1:用魔法走的距离;s2:走的距离;t1:用魔法花的时间;t2:走的时间;i:停的(恢复魔法)时间;tt:总时间;总路程}
  anst,anss:longint;
function min(a,b:longint):longint;
begin
if a>b then exit(b) else exit(a);
end;
begin
assign(input,'escape.in'); reset(input);
assign(output,'escape.out'); rewrite(output);
readln(m,s,t);
anst:=t+1;anss:=0;
for i:=0 to t do begin
  mm:=m+i*4;
  t1:=mm div 10;s1:=t1*60;
  if s-s1>0 then begin
    t2:=(s-s1)div 17;if (s-s1)mod 17<>0 then inc(t2);
  end
  else t2:=0;
  tt:=t1+t2+i;
  ss:=s1+t2*17;
  if tt<=t then begin
    if tt  end
  else begin{调整ss}
    ss:=min(t1,t-i)*60;
    if t-i-t1>0 then ss:=ss+min(t-i-t1,t-i)*17;
    if ss>anss then anss:=ss;
  end;
end;
if anst>t then begin
  writeln('No');writeln(anss)
end
else begin
  writeln('Yes');writeln(anst);
end;
close(input);close(output);
end.


Hanoi双塔
解题思路:
数学归纳+高精度
Hanoi单塔的最少移动步数是2n-1，现在有2层，可以将2层看作1层(单塔)，便回到了单塔的问题上，每移动想象中的“单个”盘子需要两步，故，Hanoi双塔=Hanoi单塔*2
f(n)=2n+1-2
证明可以通过数学归纳法证得
高精度只要编个乘法就可以了，不要忘记最后-2
那个提示可以无视掉
用递推做高精度更烦些，因为还要编加法



NOIP 2007 提高组 解题报告
By Redswallow
统计数字
解题思路:
这是个水题
注意不要被不相同的数不超过10000个这个条件迷惑去做hash
不要想太复杂，直接快排+O(n)的扫描
复杂度0(nlogn)

字符串的展开
解题思路:
也是个水题，考察对语言的运用能力，字符串处理的技巧和仔细读题的能力
测试数据已经包括所有情况了，但是有些细节要想清楚，而且一些特殊的情况也要单独测试一下，如9-a-a，--a-1
需要注意的是：首尾‘-’的情况，要用ansistring

矩阵取数游戏
解题思路:
很多人可能会被第一个样例误导认为贪心，第二个样例就提示我们贪心是错误的
其实有经验的选手一看就是dp，可以看作类似于石子归并，每次在2边进行合并
我们可以把问题转化为每次要取完一整行，一共取m次。注意到每一行都是独立的一个结构，所以可以每行的结果计算出来后求和。
对于每一行，f(i,j)表示从i到j这一子段单独操作可以达到的最大权值。有状态转移方程：
f(i,j) = 2*max(a(i)+f(i+1,j),a(j)+f(i,j-1))
边界f(i,i)=2*a(i)
最后答案就把每一行的f(0,m-1)加起来即可。这里可以算得答案不超过30位10进制数，所以高精度的digit数组开到30足够了。乘法也不用写，用两次加法即可。

树网的核
解题思路:
可以证明的是，如果图中存在多条路径，则在任何一条直径上都存在一条core（反证法，用到直径的距离最大性）。因此只需讨论一条直径上的core的情况即可。接着，如果一条路径包括了一条子路径的所有边，那么子路径的解不会比父路径更优。这一点后面将用到。
下面是算法：先寻找一条直径：任取一点u'，遍历得到到它的最远点u，再对u寻找一个到它的最远点v，则路径u-v一定是一条直径（想想为什么），在刚才遍历u-v的时候记录遍历到每一个点的时候的前继，那么从v出发一直寻找前继到u，就能记录下这一条直径。这里复杂度是O(n)。
然后枚举core：注意刚才说到了路径是越长越好，因此枚举的时候，每枚举一个初始点，向后都尽量延伸到不超过s的距离。这样每个初始点只确定一个枚举对象。对于终止点的选定可以采用一个游标的方式，当初始点从u到v扫过一遍时，游标也从u扫到了v（回想怎么求解凸多边形最远点对的），因此这里复杂度是O(n)。
最后求ECC：暂时删除枚举对象（那条路径）上的所有边，然后以那条路径上的那些顶点作为源点开始遍历图，找到的最大距离就是该路径的ECC。这里复杂度也将是O(n)。
因此总复杂度为O(n)+O(n)*O(n) = O(n^2)，ac。

线性算法：
同样只要考虑一条直径。先对于直径上的顶点赋值：与该顶点连通的最远点的距离。这样可以构成一个线性模型，点（记为v[i]）有一个值（记为f[i]），边有一个值（即原来图中v[i]和v[i+1]之间的距离，记为e[i]）。这一步可以O(n)完成。
接着考虑这个线性模型。枚举过程还是和刚才一样。假设枚举的是v[a]到v[b]这一段路径，那么，这一段路径的ECC应当是以下几个值的最大值：1)max(v[a],v[a+1]...,v[b]); 2)max(v[i]+e[i]+e[i+1]+...+e[a-1],ib);
如果以上3个值能够在O(1)内回答，那么总复杂度就将是O(n)
对于1，显然这是个RMQ模型，有一个O(n)算法（当然st的O(nlogn)也可以接受）。或者考虑到这个问题的特殊性，所有(a,b)类的询问区间都不是严格包含的（即任取询问(a,b)(c,d)都不存在a>b&&c对于2，设一个数组a[1..n]，a[k]表示max(v[i]+e[i]+...+e[k-1],i3和2同理，不再详述


Tags - , , , , , ]]>