ACM

2012-03-29
一个博弈题的证明

看Game Theory的时候看到的这个题目:

一共有N堆石子,每堆石子的数目告诉你,然后两个人轮流从中取石子,每次最多从K堆中取,每堆取的石子数任意,每次最少取一颗石子.假设两个人都足够聪明的话,最后没石子可取的人算输,问先手和后手谁输谁赢.

以前看到这个题目的时候只是按照提示证了一下,知道这个是正确的,但是如果不知道结果的话,可能就不知道怎么想了.后来给别人讲这题的时候,突然想起其实这个题就是两个简单的博弈题的结合:报数问题,和简单的取石子游戏问题.

首先我们知道报数问题是给一个数N,每个人每次最多报K个数,最少报1个数,先报道N的算赢,问谁会赢.这个大家都会了,就是算N%(K+1)的结果就行了.

简单的取石子游戏就是上面的取石子游戏中K=1.也就是每次只能从1堆中取石子.这个题目大家也知道了,就是把所有的石子数目抑或起来,看结果是否为0.其实抑或就是先化成2进制,然后看相应的为加起来是否能整除2.

OK,那么如果我们每次最多取K堆石子的话,也就是说两个人每次都可以改变K+1堆石子(就像报数中两个人每次都可以报K+1个数)这样的话,我们就只要把N堆石子的数目化成2进制之后,然后对每一位都加起来,看是否整除K+1就行了.

2011-11-27
[模拟]HDU_4121

地址

福州赛区的A题,我们队因为没有过这个题导致最后的悲剧,废话不多说了，下面是简单的分析+代码.

首先我们可以设置一个map[][]数组记录某个点有没有子,然后让将做四个方向，再判断是否会被吃掉，如果有一个方向不会被吃掉，那么就不是死棋，否则就是。

判断是否会被吃掉的时候，如果是帅，就判断y坐标相等，且中间无子，车的判断类似。炮的判断可以变为炮和将中间有几个子，一个的话就ok，否则炮吃不了将。马的话，考虑不能走就行了。

代码如下:



1. #include
2. #include
3. #include
4. #include
5.
6. char role[30];
7. int x[30],y[30];
8. int dir[4][2]={{0,1},{1,0},{0,-1},{-1,0 }} ;
9. int hdir[8][2]= {{ -1,2},{1,2},{2,1},{2,-1},{1,-2},{-1,-2},{-2,-1},{-2,1 }} ;
10. int X,Y;
11. int n;
12. bool have[30][30];
13.
14. int min(int a,int b)
15. {
16. return a
17. }
18. int max(int a,int b)
19. {
20. return a>b?a:b;
21. }
22.
23. bool can(int X,int Y)
24. {
25. int i,j;
26. int cnt;
27. int tx,ty;
28. for(i=0i
29. {
30. if(!have[x[i]][y[i]])
31. continue
32. //G
33. if(‘G’==role[i])
34. {
35. if(y[i]==Y)
36. {
37. for(j=min(X,x[i])+1j
38. {
39. if(have[j][Y])
40. break
41. }
42. if(j==max(X,x[i]))
43. return false
44. }
45. }
46. //R
47. if(‘R’==role[i])
48. {
49. if(Y==y[i])
50. {
51. for(j=min(X,x[i])+1j
52. {
53. if(have[j][Y])
54. break
55. }
56. if(j==max(X,x[i]))
57. return false
58. }
59. if(X==x[i])
60. {
61. for(j=min(Y,y[i])+1j
62. if(have[X][j])
63. break
64. if(j==max(Y,y[i]))
65. return false
66. }
67. }
68. //C
69. if(‘C’==role[i])
70. {
71. if(X==x[i])
72. {
73. cnt=0
74. for(j=min(Y,y[i])+1j
75. if(have[X][j])
76. ++cnt;
77. if(1==cnt)
78. return false
79. }
80. if(Y==y[i])
81. {
82. cnt=0
83. for(j=min(X,x[i])+1j
84. if(have[j][Y])
85. ++cnt;
86. if(1==cnt)
87. return false
88. }
89. }
90. //H
91. if(‘H’==role[i])
92. {
93. for(j=0j<8;++j)
94. {
95. tx = x[i]+hdir[j][0];
96. ty = y[i]+hdir[j][1];
97. if(tx<1||tx>10||ty<1||ty>9)
98. continue
99. int sbx,sby;
100. sbx = x[i]+hdir[j][0]/2
101. sby = y[i]+hdir[j][1]/2
102. if(have[sbx][sby])
103. continue
104. if(tx==X&ty==Y)
105. return false
106. }
107. }
108. }
109. return true
110. }
111.
112. int main(void)
113. {
114. #ifndef ONLINE_JUDGE
115. freopen(“1001.in”,“r”,stdin);
116. freopen(“1001.out”,“w”,stdout);
117. #endif
118. int i;
119. int tx,ty;
120. bool tmp;
121. char ch;
122. while(EOF!=scanf(“%d%d%d”,n,&X,&Y))
123. {
124. if(0==n&0==X&&0==Y)
125. break
126.
127. memset(have,false,sizeof(have));
128. for(i=0i
129. {
130. ch=getchar();
131. while(!(ch>=’A’&ch<=’Z’))
132. ch=getchar();
133. role[i]=ch;
134. scanf(“%d%d”,x[i],&y[i]);
135. have[x[i]][y[i]]=true
136. }
137. for(i=0i<4;++i)
138. {
139. tx = X+dir[i][0];
140. ty = Y+dir[i][1];
141. if(tx<1||tx>3||ty<4||ty>6)
142. continue
143. tmp = have[tx][ty];
144. have[tx][ty]=false
145. if(can(tx,ty))
146. {
147. break
148. }
149. have[tx][ty]=tmp;
150. }
151.
152. if(4==i)
153. {
154. printf(“YES\n”);
155. }
156. else
157. {
158. printf(“NO\n”);
159. }
160. }
161. return 0
162. }

2011-05-30
华中南邀请赛 by klion26

我们队的第二次正式比赛,下一次正式比赛应该就是省赛了.
[由于29号早上3点左右有欧冠决赛,所以我被吵醒了好几次,从3点到5点一直没睡着.]
下面是比赛记录.基本纯流水账.
首先是A F J,由于我们一开始开题不对(A),加上写A的不是对计算几何不是特别熟悉,所以我们的A是53’时过的,但是中间,知道J更容易,确没有及时的抢过机器来写.A是1A,然后是J,悲剧的是J不知为何TLE了,怎么想都不可能的事情啊.TLE两次之后就换人写了.3A.[J换人写一共浪费了两个人40’左右,加上罚时40’,也就是说J一共浪费了80’左右的时间],然后20分钟后,F 1A.还以为接下来就是我们的show time了,结果就悲剧了,一个G(gcd_depth),一个D(dp),一个H(找规律/组合)D由于认为不可能出成恶心的高精度,认为转移方程错了,放弃.H和G就不知道是为啥错了,后面3小时一直在调这两个题(赛后问了下裁判,思路基本是对的,看来又tm是实现问题).还有就是E居然就是一个裸的离散对数,而且a^x=b(mod c),c还是个素数,我去啊.不过这些都是后话了,比赛已经过去了.反正就是被各种踩,我们是各种送,送成狗了.
下面说点关于我的,其实J我也想早早的抢过机器来写,可是我又怕不1A,又怕耽误时间,反正就是各种怕,然后就只能干等着,关于J的两次TLE,我也不知道是怎么了,应该是我的程序风格的问题,但是队友检查时也没看出什么可以TLE的东西,可是tm的重写就过了,关于后面的E,在还有90’左右的时候,我看过榜之后,还是看了下E的,只是没有自己分析,不过心里知道,肯定是个裸的数论题,但是由于G的Wa,和其他一系列原因,就”忘”了E,只有在讲解题报告时才想起还有一道裸的离散对数,这tm和不知道离散对数不是一样的结果么.我觉得我最大的问题不是知识的不足,而是信心的不足,不知道从什么时候开始,已经没有了那种舍我其谁的霸气了,已经被完全钝化了,接下来的几个月,首要任务是找回那种霸气,其次才是弥补知识的不足.

昨天,今天虐我的,明天我会虐回来的

2011-05-23
Mon-monsterkill湘潭行by klion26

===本来是去湖大校赛的,后来由于某些原因,我们就去了湘潭(当然我更倾向于去湘潭)===

我们队应该说还是不成熟,个人(我)能力不行,团队配合不是很好,有时另外两个人根本听不懂剩下的那个人在说什么(或者说根本没在听),代码能力还有待加强.1A率不高.下面是流水账,按出题顺序来写.(由于湘潭周二还会挂网络赛,所以就不说算法了,等网络赛完了之后再补吧)

A,水题,然后写了交上去,由于没加stdio ce了,FB没了.
B, 1A C,1A D, 1A F, 3A(4A?) J. 1A

E,两个人理解错题意,一开始想着随机水(因为过的人已经不少了),后来Azuki看题后,才发现其他两个人看错题了,囧啊.让后Gamor敲之,这期间其他两个人在邪恶的吃着中餐(香喷喷的鸡腿-_-||),这题由于一些细节问题TLE了一次,2A.

接下来就成了垃圾时间了,其实这个时候,我们还是有优势的,不过后面差不多两个小时就没有一点作为,首先是Azuki的H,一直WA,然后三人一直搞这个,思路怎么想都没问题,数据也测了好多,居然没测出问题.然后这题最后也没过,赛后谢大说只错了小数据(他们还手算了我们出错的数据,太谢谢了),这个应该是实现问题了.还有一个G,由于H和G题题意不是很清楚的缘故,没敢上去写,其实给半个小时,G题应该没啥问题.然后郭嘉三国杀那题,确实没想到算法,最后一题Azuki说他会做,还有主要程序段的模板,可是他没看题,然后其他两个看过题的不懂算法= =||。然后就悲剧的收场了.然后没有拿到monsterkill

比赛结束后我去湘大逛了一圈,不过时间太紧了,然后就回科大了,结果在科大还等了好久-_-||,然后就回来了,这次湘大之行郁闷的占6/10,高兴的占4/10吧,郁闷的是被再踩(这个还好),没有monsterkill.

解题报告上给的是:
A&&B C语言
C 想法题
D GCD
E 想法
F 数学
G 模拟
H DP
I 高斯消元
J AC自动机/Trie图
K 插头DP

2011-05-08
gcj_2011前三题

第四题没看题目,当时就想着反正25分就可以进r1了.所以第四题没看.前三题应该说还是好做的.第一题直接模拟,用两个变量存下在对方走的过程中,自己可以走多远,然后到自己走的时候,算上刚才的时间就行了.注意不管怎么样每人每轮至少需要一秒的时间,这1s是用来按按钮的.

第二题:直接模拟,每次清空的是整个字符串,所以这里注意下,每次合并的时候只需要考虑最后两个就行了,但是冲突的却要考虑所有已经在字符串里面的字符和当前新加入的字符.

第三题,一开始时想水的,因为3个small已经超过25分了,后来水过之后还是想了下,发现直接把所有的数异或起来,如果等于0就表示有方案,否则就是no solution.因为等于0的话,就可以把一些数分出来,然后两堆数分别的异或值一样[这样才能保证最后异或是0].然后求最大值,只需要用总值减去最小值就行了.这样就能保证每次都能拿到最大值.

还有就是gcj可以下代码,有兴趣的可以去下那些大牛的代码来看看.官方也有analysis.最后希望今年能rp爆发拿件衣服吧~~~

2011-05-02
球体积并[ZOJ_3350]

传送门

题意就是给出两个球的参数,求这两个球的体积并.

做法:积分.

首先模拟球的体积积分,我们可以知道只需要算出球交的那一部分,然后用两个球冠的体积加就行了.不过中间我自己考虑到一点复杂的东西,一直以为会影响结果,其实是不会的,比如下图:

klion26

我是算AF和CF然后积分的,如果A和C[两个球心]在ED两边的话,肯定是AF+CF=dis[球心距],但是上面这个图,两球心在同一边呢?其实是没有影响的,因为我们用AF+CF=dis和AF^2-CF^2=r1^2-r2^2这里并没有什么不可逆的,如果出现上面的情况我们会得到AF是负的,这样照样会得到正确的结果.那么程序就简单了.


2011-04-23
第五届中南大学校赛-klion26

这次校赛应该是最后一次以参赛队员参加了,明年就算弄也应该不是参赛队员了.可是还是有很多不如意之处啊.虽然拿了个较好的成绩,但是比赛实在是……,可以用惨不忍睹来形容.首先这套题出的还算可以的,当然除了几个陈题,难度应该是A-E,I水体,然后K是一个巨难但是可以直接水的题.F,G,H,J都还是比较难的.可是最后我们是已5题结束比赛,I是我最后画错图了,然后一直在分N(非常非常大)中情况讨论.其实不画错图的话,一转化就变成了4中情况.然后这题我们还一直没看sample - -||.表示这次我们队配合的也不是挺好,至少没有达到那种1+1+1>=3,甚至是2都没有.[不过后面我们队换了个人,希望配好要好,我理想中的配合是1+1+1至少要&gt;=2.5]我们是2小时的时候过了5题,然后后面3小时一直浪费了,然后三个人一人一个题,可是三个题都没出- -|.如果三个人一起攻一个题的话,应该还是有希望过题的,可是这就是后话了.我觉得我们这次这么惨的原因有:配合不好,基本是单兵作战,除了I基本讨论很少;不够冷静,前面被水体卡了,然后就有点慌了;最后的时间分配上有点问题,这个和配合有一定关系;题目没有多人读[赛前我们都讨论过要多人读题- -|],由于这个被C卡了,后来在100分钟的时候看懂题意,然后20分钟过掉.当时那个汗啊- -|.最最不爽的是后面三小时浪费了.

  现在我们队的三个人["这怎么好意思"大婶,czw加我.]还没一起做过题.等五一的时候一起做做题,应该锻炼锻炼配合,不然不行啊.吃饭的时候"这怎么好意思"大婶说了个很欠扁的队名"这怎么好意思".[我邪恶的认为如果有实力的话还是可以这么取名的- -|],那么接下来就看我们三个的实力能达到什么水平了,其实我一直认为小小概率事件也是有发生的可能的.加油吧.最后希望实训可以代替实习吧.

2011-04-18
POJ 2480

传送门
题意就是求Σgcd(i,n)[1<=i<=n].首先我们知道,如果枚举的话肯定是会超时的.那么现在我们可以这么想.假设k=gcd(i,n).f1=i/k.f2=n/k;那么gcd(f1,f2)=1&f1<f2.看到这是不是想起什么.欧拉函数？对.就是它了.OK.我们再从头开始.现在,假设某个k|n.那么f2=n/k.则存在phi(f2)个数和n的gcd=k.这样的话,这题就好做了.我们只需要求Σk*phi(f2);其中k|n,f2=n/k;到了这一步之后,还有一点就是不能直接枚举所有的k.这样也是会超时的.我们只要筛出n的所有素因子,然后dfs就ok了.这里的素数只需要筛到2^16次就OK了.而且一个<=2^31的数的素因子的个数最多是10个.这样的话,dfs就会非常快了.下面是我的代码:

/
ID:klion26
LANG:C
TASK:POJ_2480 欧拉函数
/
#include
#include
#include
#include

int n;
int eular[46500];
int idx,prime[5200];
int num[20][2],total
__int64 ans
void init(int n)//n是需要求欧拉函数的最大值
{//结果存在eular数组中
int i,j
memset(eular,0,sizeof(eular));
eular[1]=1
idx=0
for(i=2i<=n;i++)
{
if(0 == eular[i])
{//i是素数
prime[idx]=i
idx++
for(j=ij<=n;j += i)//j从i到n
{
if(0 == eular[j])
eular[j]=j
eular[j] = eular[j]/i(i-1);
}
}
}
}

int get_eular(int n)
{
int ret
int i,k
if(n<46342)
return eular[n];
for(i=0i<idx;i++)
{
if(0 == (n%prime[i]))
break
}
if(i == idx)
return n-1
k = n/prime[i];
if(0 == (k%prime[i]))
ret = prime[i]get_eular(k);
else
ret = (prime[i]-1)get_eular(k);
return ret
}
void make(int n)
{
int i,j
total=0
for(i=0i<idx;i++)
{
if(0 == (n%prime[i]))
{
num[total][0]=prime[i];
j=0
while(0 == (n%prime[i]))
{
n /= prime[i];
j++
}
num[total][1]=j
total++
}
if(1 == n)
break
}
if(n>1)
{
num[total][0]=n;
num[total][1]=1
total++
}
return ;
}
void dfs(int now,int dep)
{
int i,j
if(dep==total)
{
i = get_eular(n/now);
ans += inow
return ;
}
j=1
for(i=0i<=num[dep][1];i++)
{
now = j
dfs(now,dep+1);
now /= j
j = num[dep][0];
}
}
void work(int n)
{
make(n);
ans=0
dfs(1,0);
printf(“%I64d\n“,ans);

}
int main(void)
{
init(46341);
while(EOF != scanf(“%d”,n))
work(n);
return 0
}

2011-04-15
欧拉函数2

记得前面自己写的那个欧拉函数,自己以为应该能够应付所有的和欧拉函数有关的题了.可是这两天遇到的题让我知道.远远还不够.首先欧拉函数可以写的更快.用的是和筛素数一样的筛法.然后就是如果我需要求1-1e9的所有数的欧拉函数的话,那么,对于OJ上的题来说,内存是不够的.怎么办呢？我的做法是:求出从1-sqrt(n)的所有数的欧拉函数,然后求出1-sqrt(n)以内的所有素数.接下来,如果需要求phi(n),n1[i<n],那么gcd(n-i,n)>1.这个应用可以做HDU3501.下面给出筛法的欧拉函数和只求1-sqrt(n)的欧拉函数的代码

void init(int n)//n是需要求欧拉函数的最大值
{//结果存在eular数组中
int i,j
memset(eular,0,sizeof(eular));
eular[1]=1
idx=0
for(i=2i<=n;i++)
{
if(0 == eular[i])
{//i是素数
prime[idx++]=i
for(j=ij<=n;j += i)//j从i到n
{
if(0 == eular[j])
eular[j]=j
eular[j] = eular[j]/i(i-1);
}
}
}
}
int get_eular(int n)
{
int ret
int i,k
if(n<31623)//这里的31623是sqrt(n);
return eular[n];
for(i=0i<idx;i++)
{
if(0 == (n%prime[i]))
break
}
if(i==idx)//n是素数
return n-1
k = n/prime[i];
if(0 == (k%prime[i]))
ret=get_eular(k)prime[i];
else
ret=get_eular(k)*(prime[i]-1);
return ret
}

2011-03-31
POJ 2478 欧拉函数

题目
这题的实际就是求欧拉函数,也就是给你一个n,然后求从2-n的所有数的欧拉函数的和,至于不知道欧拉函数的还请google之.下面给出两个求欧拉函数的模板,一个是求从1-n的所有数的欧拉函数,一个是求单个数的欧拉函数.这两个函数都是由phi(n)=n(p1-1)(p2-1)……(pn-1)/(p1p2……*pn)这个式子来的.
第一个求所有数的欧拉函数

void eular()
{
int i,j
memset(p,1,sizeof(p));
for(i=0i<1000001;i++)
e[i]=i//初始化
for(i=2i<1000001;i++)
{
if(1==p[i])
{
e[i]–//如果是素数 那么等于n-1
for(j=2ij<1000001;j+=i)
{
p[j]=0//这里就是那个公式的应用,这里的P[j]数组是表示这个数是否是素数
e[j]=(i-1);
e[j]/=i
}
}
}
}

第二个,求单个数的欧拉函数:
int eular(int n)
{
int ret=1,i
for(i=2ii<=n;i++)
{
if(n%i==0)
{
n/=i
ret=i-1
while(0==n%i)
{//这里还是那个公式的应用
n/=i
ret=i
}
}
}
if(n>1)//如果剩下的n是素数
ret=n-1
return ret
}
▲