beloved_ACM

SB,NB,都是一个B.
posts - 29, comments - 2, trackbacks - 0, articles - 0
  C++博客 :: 首页 :: 新随笔 :: 联系 :: 聚合  :: 管理

2011年9月11日

#include <iostream>
using namespace std;

int c[1000];
char s[10000000];
int ss[1000];
int key[1000];
bool hash[10000000];
int n,d;
int main() {
    
    
while(scanf("%d%d",&n,&d)!= EOF) {
       
       memset(hash,
0,sizeof(hash));
       scanf(
"%s",s);
       
int len = strlen(s);
       c[
0= 1
       
for(int i = 1; i < 100; i++)
          c[i] 
= c[i-1]*d;
       
int k = 0;
       
       
for(int i = 0; i < len; i++{
          
if(key[s[i]] == 0
             key[s[i]] 
= k++;
          
if(k == d) break;
       }

       
       
int h = 0;
       
for(int i = 0; i < n; i++{
          h 
= h*+ key[s[i]];
       }

       hash[h] 
= true;
       
int ans = 1;
       
for(int i = 0; i < len-n; i++{
          h 
= d*- key[s[i]]*c[n] + key[s[i+n]];
          
if(!hash[h]) {
             hash[h] 
= true;
             ans
++;
          }
 
       }

       printf(
"%d\n",ans);
    }

   
// system("pause");
    return 0;
}


posted @ 2011-09-11 12:38 成幸毅 阅读(186) | 评论 (0)编辑 收藏

排列组合专题之错排问题

1993年的全国高考试题一改以前数学高考“以知识立意”命题思路,开始明确提出“以能力立意”,这是数学高考改革的一项重要举措,高考数学命题更加注重了对能力和素质的考查,试题设计增加了应用性和能力型题目,其中的“贺卡问题”就属于这方面的一道好题。

贺卡问题:同室四人各写一张贺年卡,先集中起来,然后每人从中拿一张别人送的贺年卡,则四张不同的贺年卡不同的分配方式有:

A6 B9 C11 D23

这个问题的情境新颖,无法直接套用公式、法则,主要考查分类或分步计数原理或从反面考虑(排除法)的思想方法,考查分析问题与解决问题的能力,本题以组合数学中著名的“错排问题”为背景,用贴近学生身边生活的“贺卡”来设计问题,显得较恰当。其实,实际生活中的“错排问题”有多种多样,如信封中装错信件或坐错座位等等。

错排问题:有n个正整数123,……n,将这n个正整数重新排列,使其中的每一个数都不在原来的位置上,这种排列称为正整数123,……n的错排,问这n个正整数的排个数是多少?

设这n个正整数的错排个数为an,为了探求an的表达式,我们先从最特殊的情形入手。

n=1时,由于只有一个数1,不可能有错排,所以a1=0.

n=2时,两个数的错排是唯一的,所以a2=1.

n=3时,三个数123只有231312两种错排,所以a3=2.

n=4时,四个数1234的错排有:21432341241331423421412343124321,共有9种错排,所以a4=9.

刚才提到的93年高考试题——贺卡问题,实际上求的就是a4等于多少?

上面使用的是枚举法,当n较大时,这种方法是很麻烦的、难以解决问题的,必须另辟蹊径,现在考虑用排除法求出1234这四个正整数的错排的种数,从中摸索出规律。

对于四个正整数1234,这四个数的全排列数为4!。

有一个数不错排的情况应排除,由于1排在第1位的有3!种,2排在第2位的有3!种,……4排在第4位的有3!种,所以共应排除4×3!种。

然而在排除有一个数不错排的情况时,把同时有两个数不错排的情况也排除了,应予以补上,由于12分别排在第1、第2位上的情况共有2!种,同理13分别排在第1、第3位上的情况也有2!种,……,这四个数中同时有两个数不错排的情况共有种,所以应补上 种。

 

在补上同时有两个数不错排的情况时,把同时有三个数不错排的情况也补上了,应予以排除,四个数中有123不错排,124不错排,134不错排和234不错排共 种情况,所以应排除 种。

在排除同时有三个数不错排的情况时,把同时有四个数不错排的情况也排除了,所以应补上同时有四个数不错排的情况仅1234这一种。

综上所述,  

以及 ,我们猜想n个正整数1234、……、n的错排的种数an的表达式为an= ,下面我们来证明这个表达式。

一般来说,正整数123、……、n的全排列有n!种,其中第k位是k的排列有(n-1)!,当k123、……、n时,共有n×(n-1)!种排列,由于是错排,这些排列应排除,但是此时把同时有两个数不错排的排列多排除了一次,应补上;在补上时,把同时有三个数不错排的排列多补上了一次,应排除;……;继续这一过程,得到错排的排列种数为

,即 .

计数是一种常见的数学问题,涉及计数问题的另一种思路是运用递推方法,应该说,利用递推方法是解决计数问题的重要方法,下面我们再用递推关系求an的值。

由题意a1=0a2=1,当n3时,在错排中n必不在第n位,设n放在第k位上(1kn-1),则第n位上有两种可能:

1)如果第n位上不是k,那么把第n位看作第k位,将n以外的n1个数进行错排,错排个数是an-1

2)如果第n位上是k,那么除nk以外的n2个数的错排是an-2

所以n在第k位上的错排数共有an-1an-2,由于k可取1234、……、n1n1种取法,所以n个数的错排个数 ,其中n3.

下面我们来求数列{an}的通项。

为了方便起见,设 ,

即:

于是有

从而可求 ,所以

posted @ 2011-09-11 12:10 成幸毅 阅读(284) | 评论 (0)编辑 收藏

2011年9月10日

每堆石子的SG函数就是它自己k.因为他的后继结点可以是0,1,2..k-1,所以此题直接异或即可,为什么异或,参考<<游戏策略>>朱全民的论文

#include <iostream>
#include 
<cstdio>
#include 
<cstdlib>
#include 
<vector>
#include 
<algorithm>
using namespace std;


int main() {
    
    
int a,b,n;
    
while(scanf("%d",&n) != EOF) {
     
int k = 0;
     
for(int i = 0; i < n; i++{
        scanf(
"%d",&a);
        k 
^= a;
     }

    
if(k) cout<<"Yes"<<endl;
    
else cout<<"No"<<endl;
    }

    
  
//  system("pause");
    return 0;
}


 

posted @ 2011-09-10 01:45 成幸毅 阅读(319) | 评论 (0)编辑 收藏

转自http://blog.csdn.net/linulysses/article/details/6341984

无偏博弈(Impartial Game) 及几道相关的 POJ 解题报告

在本人的 POJ 1740 解题报告中,已经提到这是一题有关博弈论的题目。现在,就让我们来一窥博弈论中的无偏博弈及其理论,并应用这些知识来解决几道 POJ 题目。本文定位于无偏博弈的入门介绍和其简单应用,因此,博弈定理的证明和详细讨论将被忽略。

 

一、什么是无偏博弈?

 

通俗地说,博弈就是“游戏”,而无偏博弈就是一种任意局势对参与游戏的两个选手来说都是平等的回合制游戏。因此,选手的区别只在于谁先进行第一个回合(即谁是先手)。按此定义,象棋、五子棋等都不是无偏博弈。这是因为,在这些棋类中,对于任意一个局势,有些棋子只能由某一选手移动;例如,在中国象棋中执红的选手在每一回合中只能操作红棋,而不能操作黑棋。

 

除了局势对选手平等之外,还有额外的三个要求:

 

(1)信息完全公开。这就是说,有关游戏的所有信息对所有选手都是可知的。因此,像扑克之类的游戏,通常都不是无偏博弈,因为,你看不到对手的牌,对手的也看不到你的。

 

(2)无随机性。一旦游戏完全设立好,每一人操作都是非随机的。这就排除了大富翁之类的游戏。

 

(3)有限步终止。游戏在有限步之内必然终止。这是一条很强的要求。例如,象棋之类的游戏就不满足这条要求。比如,当对手下感情棋时,游戏就可能无限进行下去。

 

说了这么多不是无偏博弈的游戏,现在举一个是的例子,而最经典的例子莫过于最简单的取石子游戏,也叫尼姆(Nim)博弈:有两堆石子,石子数目为 m > 0 和 n > 0。两个选手轮流从这些石堆中取走石子。在每一回合中,选手选定一个至少有一个石子的石堆,从该堆中取走至少一个石子。若某选手最后取走所有的石子,则该选手获胜,游戏宣告结束。

 

现在我们来验证这是一个无偏博弈。首先,任意局势对选手都是平等的。在任意回合中,如果一个操作或策略(取走x个石子)是被规则允许的(在这里,是 1<= x <= k),则无论该回合是由选手a或选手b进行,该回合的选手都可以采取该操作或策略。其次,信息完全公正。显然,选手采取的任何策略对于对手来说都是可见的。再次,无随机性。这个很显然。最后,有限步终止。因为每一回合中,至少有一个石子被取走,因此,石子的数目一直在减少。这样,最多 m+n 个回合之后,将没有石子留下,游戏结束。

 

二、有向无环图游戏

 

现在,设想一个有向无环图上(如无特别说明,本系列中的图都是指有向无环图)的棋子移动游戏:在一个有向无环图上,在某个顶点处有一颗棋子。在每一回合中,选手把该棋子沿某一出边移动到相邻的顶点上。当某选手最后移动棋子,从而使棋子处于一个没有出边的顶点上时,该选手获胜,游戏结束。

 

之所以介绍这个图上的游戏,是因为,任意一个无偏游戏,等价于一个有向无环图上的棋子游戏:在无偏游戏中,把每一个局势,也即每一个状态,看成是一个有向图上的一个顶点,而把状态间的转移看成一条有向边。由于有限步原则,该图必然是无环图。在图上的对应于游戏最初状态的顶点处放置一颗棋子,采取某个策略把一个状态 x 变成状态 y则相当于把棋子从对应于状态 x 的顶点 u 沿着有向边移动到对应于状态 y 的顶点 v 上。当棋子无法移动时,游戏就结束。由于图没有环,图上的任意路径都是有限长的,因此,棋子在有限步之后必定无法移动,即到达一个没有出边的顶点上。由于这个对应关系,当我们讨论一个无偏游戏时,总同时假定了一个等价的有向无环图上的游戏。因此,我们不再区分状态和顶点这两个概念。

 

没有出边的顶点称为 P-态。如果一个状态可以转移到某一个 P-态,则称其为 N-态。如果一个状态只能转移到 N-态的顶点上,则也称为 P-态。在某回合中,如果选手面对的是 P-态,则当对手以最优策略进行游戏时,该选手必败。这是因为,如果该状态没有出边,则游戏结束,选手输掉了游戏;否则,无论他的策略是什么,都只能转移到某个N-态上,从而对手可以接着把该棋子转移到某个 P-态上。因此,P-态也叫必败态(相对于先手而言),N-态为必胜态(同样的,相对于先手而言)。

 

一个很自然的问题是,对于任意一个顶点,是否要么为 P-态,要么为 N-态?对于顶点数有限的图,回答是肯定的。证明留给读者,或者回复本文:)

 

另外注意,可以存在顶点数无限,甚至不可数的有向无环图游戏,但每一条路径长度却是有限的。例如,考虑如下游戏:两个选手轮流向一个半径为 R 的桌面上摆放半径为 r 的硬币,使得所有的硬币不得有任何部分位于桌面外,且硬币间互不重叠。摆下最后一个硬币的选手获胜。这个游戏中,状态数目是不可数,但路径长度是有限的,最长不过 R2/r2

 

图游戏可以扩展到在多个图上同时进行的游戏,即图游戏的和:设想 n 个图 G1,G2,...,Gn,每个图上在某个顶点处放置一颗棋子。在每一回合中,选手选择一个可以移动棋子的图,并且移动该图上的棋子。当某选手进行最后一次移动,从而使得所有的图上,棋子都无法移动,则游戏结束,该选手获胜。这个图游戏用 G=Gx Gx ... Gn 表示,并称其为 G1,G2,...,Gn 的和。例如,上述的取石子游戏可以看成是两个图游戏的和,每个子图游戏对应一个石子堆。

 

三、Nim 和

 

学计算机的读者对异或运算应当时非常熟悉的:1⊕1=0⊕0=0,1⊕0 = 0⊕1=1。⊕运算满足交换律和结合律。并且有如下性质:

 

(1)x⊕y=0 当且仅当 x=y

(2)x⊕0=x

 

有一道有关异或运算的很有名的题目:给定一个数组,除了某个数只出奇数次之后,其它的数都出现了偶数次,请找出这个数。答案就是对所有数进行异或运算,结果就是所求的数。这正是因为 x⊕x=0,x⊕0=x。

 

异或运算也被称为Nim 和,这是因为它跟尼姆游戏的密切关系。回到前面提到的取石子游戏。两堆石子数目相等的状态为 P-态。这时因为,无论先手从某堆石子中取走多少石子,对手总是可以在另一堆石子上取走相同数目的石子,从而使得两堆石子的数目再次相等。最终,先手将被逼取走某堆中的所有石子,而对手成为最后一个取走石子的选手,从而获胜。巧的是,在 P-态中,两堆石子数目的异或为 0。不过,这绝对不是巧合而已。事实上,我们可以断言,在有任意数目石堆的取石子游戏中,P-态为那些所有堆的石子数目的异或为 0 的那些状态。即,若一共有 m 堆,每堆有 ck 个石子,则当 c1⊕c2...⊕cm=0 时,状态 (c1,c2,...,cm) 为 P-态。这个结论很美妙,证明也不是很难。实际上,它只是某个更一般的定理的简单推论而已。我们接下来就介绍这个强大的定理。

 

四、Sprague-Grundy 定理

 

首先,定义Sprague-Grundy 函数(简称 SG 函数):在一个图游戏中,定义一个顶点到非负整数的函数 SG 如下

 

       SG(u)= 最小不属于整数集合 {SG(v) | v 是 u 的后继(即有一条边从 u 指向 v)}的非负整数。

 

若用 F(u) 表示顶点 u 的所有后继的集合,即 F(u) = { v | 有一条边从 u 指向 v },用 mex(S) (minimal exclusive) 表示最小的不属于集合 S 的非负整数,则 SG(u) = mex( F(u) )。

 

例如,在取石子游戏中,假定只有一堆石子,石子数目为 n。则 F(k)=k,0<=k<=n。特别的 F(n)=n。简单的思考可以证明,状态为 P-态当且仅当其 SG 值为0,为 N-态当且仅当 SG 值大于0。

 

著名的Sprague-Grundy 定理断言,对于有限图游戏 G=Gx Gx ... x Gn 上的顶点 (u1,u2,...,un), 其 SG 值为其子图游戏各顶点的 SG 值之 Nim 和,即 SG(u1,u2,...,un)=SG(u1)⊕SG(u2)⊕...⊕SG(un)。证明不难,从略。

 

有了这个定理,通过把游戏分解成多个图游戏的和,就可以把复杂的 P-态 判定问题转换成南计算简单子图游戏的 SG 值和子图间顶点 SG 值的 Nim 和,从而使很多游戏的分析变得简单起来。例如,考虑有 n 个堆的取石子游戏。每个堆可以看成一个图游戏,n 个堆上的取石子游戏就成了这些子图游戏的和。则状态 (c1,c2,...,cn) 的 SG 值为 SG(c1)⊕SG(c2)⊕...⊕SG(cn)=c1⊕c2⊕...⊕cn。这也验证了第三节中的断言。

 

SG 函数的计算并不难,应用深度优先搜索即可。

 

在实际的代码实现中,计算好的 SG 通常被记录起来,从而避免重复运算。

 

基础的无偏博弈就先介绍到这里。对此问题感兴趣的读者,包括定理的证明,本人推荐 UCLA 的 Ferguson 教授写的一篇讲稿(点击这里)。这篇讲稿通俗易懂,还带有练习,是不错的无偏博弈入门读物。

 

五、应用

 

现在就让我们用这个强大的武器来解决一些原先看起来很难现在很水的 POJ 题目。

 

(1)POJ 2234 (Matches Game)。这个就是有多个堆的取石子游戏。直接应用定理即可。

 

(2)POJ 2425 (A Chess Game)。这个也是定理的直接应用,只不过这次是直接应用于有向图上而已。计算出每个图的初态的 SG 值,然后取 Nim 和即可判断是否为 P-态。

 

(3)POJ 2960 (S-Nim)。这个是更一般的取石子游戏。每次取的石子的可能数目被限定于几个整数,而不是任意整数。解题思路和 (2) 相同,都是要求每个堆上的初态的 SG 值。

 

(4)POJ 1704 (Goergia and Bob)。这题也是一个无偏博弈,可以直接通过建立相应的图来求 SG 值。不过,这样一来,这个图会很大,计算量也不少。更好的做法是把游戏分解成多个游戏,使得每个子游戏的 SG 值能够容易计算出,最后应用定理求出原来图的初态的 SG 值,从而判断是否为 P-态。那么,最关键的就是如何分解游戏了。观察到一个棋子是否可以移动取决于它左边相邻的棋子,我们可以从最右边开始,把两个相邻的棋子分成一组,若棋子的有奇数个,则在棋盘的最左边设置一个虚拟的棋子。这样,每组棋子看成一个单独的游戏,其终态就是两个棋子紧挨在一起。从这个角度看,每个子游戏就是一个石堆,于是,每个子游戏就是一个取石子游戏,石子的数目等于两颗棋子之间的空格数目;而总的游戏就是有多个堆的取石子游戏。

 

(5)POJ 2348 (Euclid's Game)。这个是著名的经典 Euclid 游戏的一个变体。把每个状态看成图上的顶点,可以发现,如果顶点的出度至少为2,更从该状态出发,可以存在一条长度为奇数的路径到达终态或另一个出度至少也为2的顶点,并且这条路径上的顶点,除了端点外,出度都为1。因此,出度至少为2的顶点都是 N-态。出度为0的显然是终态。出度为1的顶点,如果它到最近的N-态的路径长度为偶数,则为 N-态;否则为 P-态。这样,问题就解决了。不过,这个问题存在更简单的解决办法。它 P-态和经典的 Euclid 游戏的 P-态存在极其简单的关系:经典的 Euclid 游戏中的 P-态,除了两数相等这一情况外,都是本题游戏中的 P-态。而经典的 Euclid 游戏中的 SG 函数,存在简单的解析解,这个解和黄金分割有关。详细见 《The Sprague-Grundy function of the game Euclid》(Nivasch - 2004)一文。

 

(6)POJ 2975 (Nim)。这道题也是一道经典的多堆取石子游戏。和题 2234 所不同的是,它不是要判定某个状态是 P-态还是 N-态,而要求获胜策略的数量。设初始状态的 SG 值为 s,则 s 的 MSB (most significant bit) 是指 s 的二进制表示中最左边的非0位。设 s 的 MSB是 x。可以证明,获胜策略的数量是所有堆的 SG 值中,第 x 位非 0 的 SG 值的个数。

 

(7)POJ 1082 (Calendar Game)。这题也可以用 SG 函数来分析,不过存在更简单的解决办法。注意到一般情况下,移动一天,或移动一个月,都将改变月或日的奇偶性,例外的情况发生在每个月的最后一天。现在先假定这些例外的日期不能被移动到。由于目标日期 11 月 4 日 是奇数月,偶数日,即奇偶不同,如果一个状态是奇奇或偶偶的情况,选手总可以移动一天或一个月转移到奇偶或偶奇(统称为奇偶)的状态上。而处于奇偶状态时,只能移动到奇奇或偶偶的日期上,从而永远也不可能到达终态。因此,奇偶为 P-态,奇奇或偶偶为 N-态。现在考虑例外的边界情况。逐个仔细研究可以发现,只有 9.30 和 11.30是两个例外。这两个奇偶的状态竟然也可以转到奇偶的状态上!因此,他们也是 N-态。至此,问题解决。

 

(8)POJ 1067 (取石子)。经典 Wythoff 博弈,通解和黄金分割有关。

 

(9)... ...

posted @ 2011-09-10 01:42 成幸毅 阅读(256) | 评论 (0)编辑 收藏

2011年9月9日

总结:可以从这里知道,0-1背包问题,价值和重量可以交换,对于其中只要一个为整型就可以解决
#include <iostream>
#include 
<cstdio>
#include 
<cstdlib>
using namespace std;

const int MAXN = 110;

double f[100000];
int w[MAXN];
double v[MAXN];
int main() {
    
    
int cas;
    scanf(
"%d",&cas);
    
while(cas--{
       
double p;
       
int n;
       scanf(
"%lf%d",&p,&n);
       
int sum = 0;
       
for(int i = 0; i < n; i++{
          scanf(
"%d%lf",&w[i],&v[i]);
          sum 
+= w[i];
       }

       
       memset(f,
0,sizeof(f));
       
       f[
0= 1;
       
for(int i = 0; i < n; i++)
         
for(int j = sum; j >= w[i]; j--{
            f[j] 
= max(f[j],f[j-w[i]]*(1-v[i]));
         }
 
       
       
for(int j = sum; j >= 0; j--{
          
if(f[j] > 1 - p) {
             cout
<<j<<endl;
             
break;
          }

       }

    }

    
  
//  system("pause");
    return 0;
}


posted @ 2011-09-09 13:47 成幸毅 阅读(142) | 评论 (0)编辑 收藏

#include <iostream>
#include 
<cstdio>
#include 
<cstdlib>
#include 
<cstring>
#include 
<string>
#include 
<queue>
#include 
<vector>
#include 
<algorithm>
using namespace std;

const int MAXN = 10010;
int n,m;
int father[MAXN], rank[MAXN], a,b;
int depth[MAXN],t;
void make() {
     
   
for(int i = 1; i <= n; i++{
      father[i] 
= i;
      rank[i] 
= 1;
      depth[i] 
= 0;
   }

}


int _find(int x) {
    
    
int h = x;
    t 
= 0;
    
while(h != father[h]) {
       t 
= t + depth[h];
       h 
= father[h];
       
    }

        
    
int y;
    
int tmp;
    
while(x != h) {
       t 
-= depth[x];
       depth[x] 
+= t;
       y 
= father[x];
       father[x] 
= h;
       x 
= y;
    }

    
return h;
}


void _union(int a,int b) {
     
     
int x = _find(a);
     
int y = _find(b);
     
       rank[y] 
+= rank[x];
       depth[x] 
= 1;
       father[x] 
= y;
}


char type;

int main() {
    
    
int cas;
    
while(scanf("%d",&cas) != EOF) {
    
for(int acase = 1; acase <= cas; acase++){
       scanf(
"%d%d",&n,&m);
       printf(
"Case %d:\n",acase);//<<":"<<endl;
       make();
       
for(int i = 0; i < m; i++{
          
          scanf(
"\n%c",&type);
          
if(type == 'T'{
             scanf(
"%d%d",&a,&b);
             _union(a,b);
            
          }

          
else {
             scanf(
"%d",&a);
             
int tmp = _find(a); 
             printf(
"%d %d %d\n",tmp,rank[tmp],depth[a]); 
            
// cout<<tmp<<" "<<rank[tmp]<<" "<<depth[a]<<endl;;
          }

       }

    }

    }

        
    
//system("pause");
    return 0;
}

posted @ 2011-09-09 11:39 成幸毅 阅读(110) | 评论 (0)编辑 收藏

最优比例生成树,分数规划
#include <iostream>
#include 
<cstdlib>
#include 
<cstdio>
#include 
<cmath>
using namespace std;

//0/1分数规划满足单调性,也就是比例生成树已经确定了,只要去猜l,让他满足Z(l)等于0 

const double eps = 1e-6;
int n;
struct node {
   
int x,y,z;
}
v[1010];
double g[1010][1010];
double opt[1010];
bool vis[1010];

double prim() {
   
   
double minn;
   memset(vis,
0,sizeof(vis));
   
int vex = 0;
   
double ans = 0.0;
   
for(int i = 1; i <= n; i++) opt[i] = g[1][i];
   vis[
1= true;
   
for(int i = 1; i < n; i++{
      minn 
= 1e9+1.0;
      
for(int j = 1; j <= n; j++{
         
if(opt[j] < minn && !vis[j]) {
            minn 
= opt[j];
            vex 
= j;
         }

      }

      vis[vex] 
= true;
      ans 
+= minn;
      
for(int j = 1; j <= n; j++{
         
if(!vis[j]) {
            opt[j] 
= opt[j] < g[vex][j]?opt[j]:g[vex][j]; 
         }

      }

   }

   
return ans;
}



int main() {
   
   
while(scanf("%d",&n) && n) {
      
      
for(int i = 1; i <= n; i++)
         
for(int j =1 ; j <= n; j++)
           g[i][j] 
= 1e9;
      
for(int i = 1; i <= n; i++
         scanf(
"%d%d%d",&v[i].x,&v[i].y,&v[i].z);
      
double l = 0,r = 1000000;
      
double mid;
      
double dis,cost;
      
while(r - l >= eps) {
         mid 
= (l+r)/2;
         
for(int i = 1;i <= n; i++)
            
for(int j = i + 1; j <= n; j++{
               dis 
= sqrt(1.0*(v[i].x - v[j].x)*(v[i].x - v[j].x) + 1.0*(v[i].y - v[j].y)*(v[i].y - v[j].y));
               cost 
= fabs(1.0*(v[i].z - v[j].z));
               g[i][j] 
= g[j][i] = cost - mid*dis;
            }

         
if(prim() <= 0.0)
            r 
= mid;
         
else 
            l 
= mid;
      }

      
      printf(
"%.3f\n",r);
   }

      
 
//  system("pause");
   return 0;
}




posted @ 2011-09-09 04:27 成幸毅 阅读(228) | 评论 (0)编辑 收藏

2011年9月8日

#include <iostream>
#include 
<cmath>
#include 
<queue>
using namespace std;

struct Edge {
   
int v,w,next;
}
edge[100010];

const int INF = 0x3fffffff
int sps,head[101],w[101],dist[101];
bool inq[101],n,m;
int f[100001];

void addedge(int u,int v, int w) {
     
     edge[sps].v 
= v;
     edge[sps].w 
= w;
     edge[sps].next 
= head[u]
     head[u] 
= sps++;
}


void spfa() {
   
   
for(int i = 0; i <= n; i++{
      dist[i] 
= ((i==0)?0:INF);
   }

   queue
<int> q;
   q.push(
0);
   memset(inq,
0,sizeof(inq));
   
   
while(!q.empty()) {
      
int u = q.front();q.pop();
      inq[u] 
= false;
      
for(int addr = head[u];addr != -1;addr = edge[addr].next) {
         
int v = edge[addr].v;
         
if(dist[v] > dist[u] + edge[addr].w) {
            dist[v]  
= dist[u] + edge[addr].w;
            
if(!inq[v]) {
               inq[v] 
= true;
               q.push(v);
            }

         }

      }

   }

}


int main() {
    
    
int cas;
    scanf(
"%d",&cas);
    
while(cas--{
       
       sps 
= 0;
       memset(head,
-1,sizeof(head));
       scanf(
"%d%d",&n,&m);
       
int a,b,c;
       
int tot = 0;
       
int cnt = 0;
       
for(int i = 0; i < m; i++{
          scanf(
"%d%d%d",&a,&b,&c);
          addedge(a,b,c);
          addedge(b,a,c);
       }

       
      
       
for(int i = 1; i <= n; i++
          scanf(
"%d",&w[i]);
          cnt 
+= w[i];
       }

       
       spfa();
       
int flag = 0;
       
for(int i = 1; i <= n; i++{
           tot 
+= dist[i];
           
if(dist[i] == INF) { cout<<"impossible"<<endl;flag = 1;break;}
       }

       
if(flag) continue;
      
       
       
for(int i = 0; i < 100001; i++)
          f[i] 
= 0;
       
       cnt 
= cnt/2 + 1;
    
       
for(int i = 1; i <= n;i++{
          
for(int j = tot; j >= dist[i]; j--{
             f[j] 
= max(f[j],f[j-dist[i]] + w[i]);
          }

       }

      
      
       
for(int i = 1; i <= tot; i++{
          
if(f[i] >= cnt) {
             cout
<<i<<endl;
             
break;
          }

       }

    }

        
  
//  system("pause");
    return 0;
}

posted @ 2011-09-08 13:21 成幸毅 阅读(160) | 评论 (0)编辑 收藏

2011年9月2日

#include <iostream>
#include 
<cstdio>
#include 
<cstring>
#include 
<cmath>
#include 
<cstdlib>
#include 
<algorithm>
using namespace std;
const int maxn = 1100;
typedef  __int64 bigint;
bigint gcd(bigint A,bigint B)
{
    
while(B)
    
{
        bigint C 
= A%B;
        A 
= B;
        B 
= C;
    }

    
return A;
}

bigint product_mod(bigint A,bigint B,bigint C)
{
    bigint R 
= 0,D = A;
    
while(B)
    
{
        
if(B&1)
        
{
            R 
= (R+D);
            
if(R>C)  R -= C;
        }

        D 
+= D;
        
if(D>C)  D -= C;
        B 
>>= 1;
    }

    
return R;
}

bigint power_mod(bigint A,bigint B,bigint C)
{
    bigint R 
= 1,D = A;
    
while(B)
    
{
        
if(B&1)  R = product_mod(R,D,C);
        D 
= product_mod(D,D,C);
        B 
>>= 1;
    }

    
return R;
}

int pri[] = {2,3,5,7,11,13,17,19,23,29};
bool Miller_Rabin(bigint n)
{
    
if(n<2)  return false;
    
if(n==2)  return true;
    
if(!(n&1))  return false;
    bigint k 
= 0,i,j,m,a;
    m 
= n-1;
    
while(!(m&1))  m = (m>>1),k++;
    
for(i=0;i<10;i++)
    
{
        
if(pri[i]>=n)  return true;
        a 
= power_mod(pri[i],m,n);
        
if(a==1)  continue;
        
for(j=0;j<k;j++)
        
{
            
if(a==n-1)  break;
            a 
= product_mod(a,a,n);
        }

        
if(j==k)  return false;
    }

    
return true;
}

bigint pollard_rho(bigint C,bigint N)
{
    bigint I,X,Y,K,D;
    I 
= 1;
    X
=Y=rand()%N;
    K 
= 2;
    
do{
        I
++;
        D 
= gcd(N+Y-X,N);
        
if(D>1&&D<N)  return D;
        
if(I==K)  Y=X,K<<=1;
        X
=(product_mod(X,X,N)+N-C)%N;
    }
while(Y!=X);
    
return N;
}

bigint allFactor[maxn];
int fn;
void rho(bigint N)
{
    
if(Miller_Rabin(N))
    
{
        allFactor[
++fn]=N;
        
return ;
    }

    bigint T 
= N;
    
while(T>=N) T = pollard_rho(rand()%(N-1)+1,N);
    rho(T);
    rho(N
/T);
}

int main()
{
    bigint n;
    
while(true)
    
{
        scanf(
"%I64d",&n);
        
if(n<=0)  break;
        
if(Miller_Rabin(n))   printf("    %I64d\n",n);
        
else
        
{
            fn
=0;
            rho(n);
            sort(allFactor
+1,allFactor+fn+1);
            
for(int i=1;i<=fn;i++)
            
{
                printf(
"    %I64d\n",allFactor[i]);
            }

        }

        cout
<<endl;
    }

    
return 0;
}


posted @ 2011-09-02 11:12 成幸毅 阅读(342) | 评论 (0)编辑 收藏

2011年8月31日

【转】http://blog.csdn.net/ggggiqnypgjg/article/details/6645824

On)回文子串算法

注:转载的这篇文章,我发现下面那个源代码有点bug。。。在下一篇博客中改正了。。

 

    这里,我介绍一下On)回文串处理的一种方法。Manacher算法.
原文地址:
http://zhuhongcheng.wordpress.com/2009/08/02/a-simple-linear-time-algorithm-for-finding-longest-palindrome-sub-string/
    其实原文说得是比较清楚的,只是英文的,我这里写一份中文的吧。
    首先:大家都知道什么叫回文串吧,这个算法要解决的就是一个字符串中最长的回文子串有多长。这个算法可以在On)的时间复杂度内既线性时间复杂度的情况下,求出以每个字符为中心的最长回文有多长,
    这个算法有一个很巧妙的地方,它把奇数的回文串和偶数的回文串统一起来考虑了。这一点一直是在做回文串问题中时比较烦的地方。这个算法还有一个很好的地方就是充分利用了字符匹配的特殊性,避免了大量不必要的重复匹配。
    算法大致过程是这样。先在每两个相邻字符中间插入一个分隔符,当然这个分隔符要在原串中没有出现过。一般可以用‘#’分隔。这样就非常巧妙的将奇数长度回文串与偶数长度回文串统一起来考虑了(见下面的一个例子,回文串长度全为奇数了),然后用一个辅助数组P记录以每个字符为中心的最长回文串的信息。Pid]记录的是以字符strid]为中心的最长回文串,当以strid]为第一个字符,这个最长回文串向右延伸了Pid]个字符。
    原串:    w aa bwsw f d
    新串:   # w# a # a # b# w # s # w # f # d #
辅助数组P:  1 2 1 2 3 2 1 2 1 2 1 4 1 2 1 2 1 2 1
    这里有一个很好的性质,Pid-1就是该回文子串在原串中的长度(包括‘#’)。如果这里不是特别清楚,可以自己拿出纸来画一画,自己体会体会。当然这里可能每个人写法不尽相同,不过我想大致思路应该是一样的吧。
    好,我们继续。现在的关键问题就在于怎么在On)时间复杂度内求出P数组了。只要把这个P数组求出来,最长回文子串就可以直接扫一遍得出来了。
    由于这个算法是线性从前往后扫的。那么当我们准备求Pi]的时候,i以前的Pj]我们是已经得到了的。我们用mx记在i之前的回文串中,延伸至最右端的位置。同时用id这个变量记下取得这个最优mx时的id值。(注:为了防止字符比较的时候越界,我在这个加了‘#’的字符串之前还加了另一个特殊字符‘$’,故我的新串下标是从1开始的)
好,到这里,我们可以先贴一份代码了。

复制代码

  1. void pk()
    {
        int i;
        int mx = 0;
        int id;
        for(i=1; i<n; i++)
        {
            if( mx > i )
                p[i] = MIN( p[2*id-i], mx-i );        
            else
                p[i] = 1;
            for(; str[i+p[i]] == str[i-p[i]]; p[i]++)
                ;
            if( p[i] + i > mx )
            {
                mx = p[i] + i;
                id = i;
            }
        }
    }

   代码是不是很短啊,而且相当好写。很方便吧,还记得我上面说的这个算法避免了很多不必要的重复匹配吧。这是什么意思呢,其实这就是一句代码。

if( mx > i)
    p[i]=MIN( p[2*id-i], mx-i);

就是当前面比较的最远长度mx>i的时候,Pi]有一个最小值。这个算法的核心思想就在这里,为什么P数组满足这样一个性质呢?
   (下面的部分为图片形式)




    看完这个算法,你有可能会觉得这种算法在哪会用到呢?其实回文串后缀数组也可以做。只是复杂度是On log n)的,而且一般情况下也不会刻意去卡一个log n的算法。可正好hdu就有这么一题,你用后缀数组写怎么都得T(当然应该是我写得太烂了)。不信的话大家也可以去试试这题。
        http://acm.hdu.edu.cn/showproblem.php?pid=3068
    另外,顺便附一份AC代码。
        http://acm.hust.edu.cn:8080/judge/problem/viewSource.action?id=140283

posted @ 2011-08-31 16:02 成幸毅 阅读(1050) | 评论 (0)编辑 收藏