POJ

2011-08-20
[逆序]POJ_3761

想看题目?

题目大致意思就是:求1,2,3…..N有多少个排列是用冒泡排序只需要k轮就好的.给定一个n和一个k,然后让你输出答案模上一个数.因为答案是在太大了

这里首先给出公式吧对给定的n和k,答案是k!*((k+1)^(n-k)-k^(n-k)).

ps:以下分析借助了<计算机程序设计艺术>和这篇博文

首先我们知道对于每个排列和其逆序对是一一对应的.也就是说一个逆序对对应一个排列,一个排列对应一个逆序对,相同排列的逆序是一样的,同一个逆序对的排列也是一样的.下面我们来看看这个和逆序对有啥关系.这里以4 5 3 1 2这个排列为例.那么逆序对为3 3 2 0 0.也就是1的逆序数为3,2的为3,依次下去.那么我们来看下依次冒泡排序会改变什么,首先第一趟我们会发现变成了4 3 1 2 5.那么逆序对变成了2 2 1 0 0也就是所有逆序数>0的都-1了,这个是偶然吗?不是的,因为对于每一趟冒泡,都有一个当前未排好序的最大的沉到最下面去,这样就会导致这个当前最大的数的后面的那些数的逆序数都会-1.上面的当前最大就是5,5后面的是3 1 2,所以3 1 2这几个数的逆序数都会-1.OK,现在我们知道,对于每趟冒泡排序,所有逆序数不为1的都会-1,那么体重要求的我们可以转化成求这样的排列的个数:也就是逆序数的最大值为k的n个数的一个排列.这样我们就得到了一个冒泡最多需要k次的一个排列,而且逆序数和排列是一一对应的,所以我们得到的”逆序数的最大值为k的n个数的排列”的个数就是本题的答案.

现在的问题变成了求逆序数的最大值为k的n个数的排列的个数,也就是给你n个位置,这n个位置上可以放置一系列数,但是最大为k,最小0的排列的数目,而且我们这里要求的是至少要有一个数=k(不然不需要k趟就排完了).那么我们可以考虑用最大的为k减去最大的为k-1的排列,剩下的就是至少有一个最大值为k的了.现在我们求最大值为k,但不一定有最大值为k的排列的数目.我们可以这么想:对于1,有逆序数为0,1…..k这些选择,也就是它的位置可以选择为0 1 2…k(位置从0开始),放置好1之后,我们再放2,同理可以得到一系列的位置,也就是2也可以有k+1中选择,知道某个数不可能出现逆序数为k为止,那么我们知道一个数的最大逆序数位n-i(i是这个数,这里的环境都是1,2….n这样的排列).那么最大的i就是k了.所以这里有(k+1)^(n-k),然后剩下的就自己选位置吧,有k!种方案,所以就是k!((k+1)^(n-k)).那么我们的结果就是k!(k+1)^(n-k)-(k-1)!k^(n-k+1)然后化简就变成了k!((k+1)^(n-k)-k^(n-k))到这里这题也结束了,不过还有一点,在保证不会越界的情况下,能不用mutil_mod(算a*b%c),这类的函数就不用,所有函数都是有开销的,别到时TLE了还找不到原因

2011-07-25
[计算几何]半平面交 POJ_2451 1474 1279 3335

半平面交,一开始以为很神奇的东西,看zzy的论文,看了好久,发现思路还好懂,不会写代码= =,只是觉得和melkman有点像.后来网上膜拜了各位牛人的代码,自己终于写出来了,A了2451,不过1474&1279的时候发现了自己代码的错误,如果有多条直线平行那么我的代码会错,后来又在3335发现如果有反向平行且不共线的两条直线那么我的会错.于是各种改过之后,觉得现在的代码应该没啥问题了= =||

主要思路就是先对边进行排序[按极角序],然后去重,把平行同向的直线只保留规约最紧的一条.然后对留下来的进行半平面交.现在觉得单独的半平面交不难,难的是把题目转化为半平面交

2451代码如下[如有错误还请指出]



1. /
2. 注意事项:
3. 1.单独的点是否是符合条件的
4. 2.对于输入边有没有两条反向的
5.
6. 对于1需要改变的是check里面判断时是>还是>=
7. 如果是>那么会忽略掉点 否则会留下
8.
9. 对于2的话需要特判一下是不是有两条边方向且不共线
10. 这里需要在排序然后去重之后做
11. /
12. #include
13. #include
14. #include
15. #include
16. #include
17.
18. using namespace std;
19. /点的结构体/
20. typedef struct
21. {
22. double x,y;
23. }TPoint;
24. /直线的结构体 angle是和X轴正方向的夹角/
25. typedef struct
26. {
27. TPoint p1,p2;
28. double angle;
29. }TLine;
30. / ax+by+c=0直线中的a b c/
31. typedef struct
32. {
33. double a,b,c;
34. }abcLine;
35.
36. const int maxnum=20016
37. const double eps=1e-8
38.
39. int n;
40. /pg存半平面最后的点/
41. TPoint pg[maxnum];
42. /line存输入的边 dq是双端队列/
43. TLine line[maxnum],dq[maxnum+2];
44. int idx;/the index of pg;/
45.
46. /加边 所有的边都表示的是的左手边/
47. void Add_line(int idx,double x1,double y1,double x2,double y2)
48. {
49. line[idx].p1.x = x1;
50. line[idx].p1.y = y1;
51. line[idx].p2.x = x2;
52. line[idx].p2.y = y2;
53. line[idx].angle = atan2(y2-y1,x2-x1);
54. }
55. /输入/
56. void input()
57. {
58. int i;
59. double x1,y1,x2,y2;
60. for(i=0i
61. {
62. scanf(“%lf%lf%lf%lf”,x1,&y1,&x2,&y2);
63. Add_line(i,x1,y1,x2,y2);
64. }
65. /加外面的限制区域/
66. Add_line(n,0,0,10000,0);
67. Add_line(n+1,10000,0,10000,10000);
68. Add_line(n+2,10000,10000,0,10000);
69. Add_line(n+3,0,10000,0,0);
70. n+=4
71. }
72. /
73. 把一个double转化到一个int上
74. <-esp 的转化为-1
75. >eps 的转化为1
76. 其他的为0
77. /
78. int dou2int(double x)
79. {
80. if(x>eps)
81. return 1
82. if(x<-eps)
83. return -1
84. return 0
85. }
86.
87. /
88. 计算和<a,c>的叉积
89. /
90. double cross(TPoint a,TPoint b,TPoint c)
91. {
92. return (b.x-a.x)(c.y-a.y)-(b.y-a.y)(c.x-a.x);
93. }
94.
95. /
96. 多边形排序的模板函数
97. 首先按照极角序排列,如果极角序一样的话
98. 那么限制宽的排在前面
99. /
100. bool cmp(TLine l1,TLine l2)
101. {
102. int ret = dou2int(l1.angle-l2.angle);
103. if(ret > 0)
104. return true
105. if(ret < 0)
106. return false
107. if(dou2int(cross(l2.p1,l2.p2,l1.p2))>0)
108. return false
109. return true
110. }
111.
112. /
113. 由直线上的两点得到ax+by+c=0中的a b c
114. /
115. abcLine Get_line(TPoint p1,TPoint p2)
116. {
117. abcLine ret;
118. ret.a = p1.y-p2.y;
119. ret.b = p2.x-p1.x;
120. ret.c = p1.xp2.y-p2.xp1.y;
121. return ret;
122. }
123. /
124. 得到TLine结构体定义的两条直线的交点
125. /
126. TPoint Get_jiao(TLine l1,TLine l2)
127. {
128. TPoint ret;
129. abcLine A,B;
130. A = Get_line(l1.p1,l1.p2);
131. B = Get_line(l2.p1,l2.p2);
132. ret.x = (B.bA.c-A.bB.c)/(B.aA.b-A.aB.b);
133. ret.y = (A.aB.c-B.aA.c)/(B.aA.b-A.aB.b);
134. return ret;
135. }
136. /
137. 半平面交的时候判断当前平面是否合法
138. 是否需要退栈等
139. 如果单独的点不符合条件的话那么if语句
140. 的判断直接>0就行了,否则写成>=0
141. /
142. bool check(TLine l1,TLine l2,TLine l3)
143. {
144. TPoint cro = Get_jiao(l1,l2);
145. if(dou2int(cross(l3.p1,l3.p2,cro))>0)//加上等于0那么后来的直线过交点的时候不会退出
146. return false
147. return true
148. }
149. /
150. 判断两条直线是否平行反向且不共线
151. 下面的代码中需要加上不共线 需要对出去之后的直线进行判断
152. /
153. bool overline(TLine l1,TLine l2)
154. {
155. int ret;
156. int a,b,c,d;
157. a = (l1.p1.y-l1.p2.y)(l2.p1.x-l2.p2.x);
158. b = (l1.p1.x-l1.p2.x)(l2.p1.y-l2.p2.y);
159. c = l1.p1.x-l1.p2.x;
160. d = l2.p1.x-l2.p2.x;
161. ret = dou2int(cross(l1.p1,l1.p2,l2.p1));
162. if((a==b) & (cd<0) && (0 != ret))
163. {
164. //printf(“%f %f %f %f\n”,l1.p1.x,l1.p1.y,l1.p2.x,l1.p2.y);
165. //printf(“%f %f %f %f\n”,l2.p1.x,l2.p1.y,l2.p2.x,l2.p2.y);
166. return true
167. }
168. return false
169. }
170.
171. /
172. work 求半平面交 最后的顶点存在pg数组里面
173. 用到上面的TPoint TLine abcLine结构体
174. 会用到上面的
175. check :判断当前测试的直线是否在一直区域的范围内
176. dou2int :double转int <-eps对应-1 >eps 对应1 否则为0
177. cross :算叉积
178. Get_jiao :由两条直线得到交点
179. Get_line :由直线上的两个点得到直线的一般式
180. cmp等函数:sort用的比较函数,首先是旋转角,如果旋转角
181. 一样的话,那么要求松的放到前面,这样后面好写点
182. /
183. void work()
184. {
185. sort(line,line+n,cmp);
186. /首先对所有直线进行排序/
187. /
188. 把平行且限制宽的直线去掉
189. /
190. for(int i=1i
191. {
192. if(dou2int(line[i].angle-line[i-1].angle)==0)
193. {
194. memmove(line+i-1,line+i,(n-i)sizeof(line[0]));
195. n–;
196. i–;/防止多条直线平行/
197. }
198. }
199. /上面的for循环对直线进行”去重”/
200. int top,bot;
201. bot = 1
202. top=2
203. dq[bot]=line[0];
204. dq[top]=line[1];
205.
206. /
207. 半平面交核心算法
208. 和melkman算法有点像,每次考虑当前直线
209. 然后把这条直线加入到双端队列中
210. /
211. for(int i=2i
212. {
213. while(top>bot & check(dq[top-1],dq[top],line[i]))
214. top–;
215. while(top>bot & check(dq[bot+1],dq[bot],line[i]))
216. bot++;
217.
218. dq[++top]=line[i];
219.
220. }
221.
222. while(top>bot & check(dq[top-1],dq[top],dq[bot]))
223. top–;
224. while(top>bot & check(dq[bot+1],dq[bot],dq[top]))
225. bot++;
226. dq[–bot]=dq[top];/把最后一条直线加到最前面 这样方便计算/
227.
228. /
229. 输出由题目决定 这里表示无闭合区域
230. /
231. if(top-bot<3)
232. {/因为上面加了一条直线 所以这里是3/
233. printf(“0.0\n”);
234. return ;
235. }
236. idx=0
237. for(int i=bot;i
238. pg[idx++] = Get_jiao(dq[i],dq[i+1]);
239. idx–;
240. /下面用叉积算面积/
241. double ans=pg[idx].xpg[0].y-pg[0].xpg[idx].y;
242. for(int i=0i
243. ans += pg[i].xpg[i+1].y-pg[i+1].xpg[i].y;
244. ans /= 2.0
245. if(ans < 0)/如果是负的话转为正的/
246. ans = -ans;
247. /
248. 这里ans = -ans要注意别把0转化为-0了
249. 比如写成ans=ans>0?ans:-ans;的话会把0变成-0;
250. /
251. printf(“%.1f\n”,ans);
252. }
253.
254. int main(void)
255. {
256. #ifndef ONLINE_JUDGE
257. freopen(“2451.in”,“r”,stdin);
258. freopen(“2451.out”,“w”,stdout);
259. #endif
260. scanf(“%d”,n);
261. input();
262. work();
263. return 0
264. }

2011-05-12
[数论]POJ 3358

传送门
这题首先你要知道化成二进制的小数可以每次分子2,再对分母求余,然后分母不变,这样就能得到所有的二进制小数了.知道了这一点之后,剩下的就只是一个欧拉函数的问题了.
题中给出p/q.需要求出r和s,那么按照上面的思想,可以转化成p2^(r+s)=p2^r(mod q)继续化变成
q|p2^r(2^s-1).到了这里我们就基本没啥问题了,首先可以把p和q都除掉gcd(p,q)使之变成p’,q’.那么就变成了q’|p’2^r(2^s-1)—–>q’|2^r(2^s-1)(I)[因为没有p’和q’公因子了可以直接忽略p’],这里我们再把q’和2^r的最大公约数除掉,也就是q’一直除2知道不能除尽位置,这里就可以算法r了.算出r之后上面的式子I就再次变成了q’|(2^s-1)这里就熟悉了,我们转化成2^s=1(mod q’),首先我们知道gcd(2,q’)=1,然后2^phi(q’)=1(mod q’),对于k|q’,2^k=1(mod q’)也是有可能的,这里可以参照原根,因为如果对于2^k=1(mod q’)中最小的k==phi(q’)那么2就是q’的一个原根.好了,到这里本题基本就结束了.只需要求出q’的欧拉函数,然后对phi(q’)的每个因子都去试验下p2^(r+k) ?= p*2^r(mod q)如果等式成立,那么k就是答案(这里的k是phi(q’)的最小约数)代码如下:



1. #include
2. #include
3. #include
4. #include
5. int64 p,q,s,pr,r;
6. int64 prime[6760],idx;
7. int64 my_map[36][2],total;
8. /初始化素数 用来分解一个数/
9. void init_prime()
10. {
11. int64 i,j;
12. char p[65536];
13. memset(p,0,sizeof(p));
14. prime[0]=2;
15. idx = 1;
16. for(i=4;i<65536;i+=2) <="" span="">
17. {
18. p[i]=1;
19. }
20. for(i=3;i<65536;i +="2)" <="" span="">
21. {
22. if(0 == p[i])
23. {
24. prime[idx]=i;
25. idx++;
26. for(j = ii;j <65536; j += 2i)
27. {
28. p[j]=1;
29. }
30. }
31. }
32. }
33. /两个数的最大公约数/
34. int64 gcd(int64 a,int64 b)
35. {
36. int64 t;
37. while(b)
38. {
39. t = a;
40. a = b;
41. b = t%b;
42. }
43. return a;
44. }
45. /求n的欧拉函数/
46. int64 get_phi(int64 n)
47. {
48. int64 ret=1;
49. int64 i;
50. for(i=2;ii<=n;i++)
51. {
52. if(0 == (n%i))
53. {
54. n /= i;
55. ret = i-1;
56. while(0 == (n%i))
57. {
58. n /= i;
59. ret = i;
60. }
61. }
62. }
63. if(n > 1)
64. ret = (n-1);
65. return ret;
66. }
67. /快速幂取模/
68. int64 pow_mod(int64 a,int64 b,int64 c)
69. {
70. int64 ret=1;
71. while(b)
72. {
73. if(b1)
74. ret = (reta)%c;
75. b >>= 1;
76. a = (aa)%c;
77. }
78. return ret;
79. }
80. /dfs枚举q’的所有因子/
81. void dfs(int64 val,int64 now)
82. {
83. int64 t,j;
84. if(now == total)
85. {
86. t = pow_mod(2,r+val,q);
87. if((pt)%q == pr)
88. {
89. if(val < s)
90. s = val;
91. }
92. return ;
93. }
94. j = 1;
95. for(t = 0;t<=my_map[now][1];t++)
96. {
97. dfs(valj,now+1);
98. j = jmy_map[now][0];
99. }
100. }
101. /算法主体/
102. void work()
103. {
104. int64 p1,q1,tq;
105. int64 e,i;
106. tq = gcd(p,q);
107. p1 = p/tq;
108. q1 = q/tq;
109. tq = q;
110. r = 1;
111. /求r的值/
112. while(0 == (tq1))
113. {
114. r++;
115. tq >>= 1;
116. }
117.
118. e = get_phi(tq);
119. total = 0;
120. s = e;
121. /分解phi(tq)/
122. for(i=0;i
123. {
124. if(0 == (e%prime[i]))
125. {
126. my_map[total][0] = prime[i];
127. my_map[total][1] = 0;
128. while(0 == (e%prime[i]))
129. {
130. e /= prime[i];
131. my_map[total][1]++;
132. }
133. total++;
134. }
135. }
136. pr = (ppow_mod(2,r,q))%q;
137. dfs(1,0);
138. printf(“%I64d,%I64d\n”,r,s);
139. }
140.
141. int main(void)
142. {
143. int i=1;
144. init_prime();
145. while(EOF != scanf(“%I64d/%I64d”,p,&q))
146. {
147. //printf(“%I64d\n”,(p*pow_mod(2,8,q))%q);
148. printf(“Case #%d: “,i);
149. i++;
150. work();
151. }
152. return 0;
153. }

2011-04-30
原根的个数 POJ_1284

首先e[m,a]表示使得a^e[m,a]=1(mod m)的最小的正整数.那么我们有e[m,a^k]=e[m,a]/gcd(e[m,a],k)(k>0).证明如下:记x=e[m,a],x’=x/gcd(x,k);x’’=e[m,a^k];先证明x’|x’’.

由题意可知a^x=1(mod m) (a^k)^x’’=1(mod m)

由性质又因为e[m,a]|kx’’,所以 x’=(x/gcd(x,k)) | (kx’’/(gcd(x,k)).又gcd(x/gcd(x,k),k/gcd(x,k))=1.所以x’|x’’.

再证明x’’|x’

a^(kx’)=(a^k)^x’=1(mod m)—>x’’|x’

所以x’=x’’;

推论如果gcd(k,e[m,a])=1,e[m,a^k]=e[m,a];我们可以用这个来求原根的个数.假设一个数n存在原根,且最小的原根等于g.n的欧拉函数为phi[n].那么n的原根的个数就是phi[phi[n]].也就是g的t次方[gcd(t,phi[n])=1 1<=t<phi[n])也是一个原根,当然这里也包含了所有的原根[想想为什么?似乎只能说明原根数至少是phi[phi[n]]个?再好好想想就出来了.注意a^k != 1(mod m)(k<e[m,a])]

那么1284就直接求一个数的欧拉函数了.代码如下:



1. /
2. ID:klion26
3. LANG:C
4. TASK:POJ_1284
5. /
6. #include
7. #include
8. #include
9. #include
10.
11. int eular[65540];
12. void init()
13. {
14. int i,j;
15. memset(eular,0,sizeof(eular));
16. for(i=2;i<65536;i++) <="" span="">
17. {
18. if(0 == eular[i])
19. {
20. for(j=i;j<65536;j+=i) <="" span="">
21. {
22. if(0 == eular[j])
23. eular[j]=j;
24. eular[j] /= i;
25. eular[j] = (i-1);
26. }
27. }
28. }
29. }
30. int main(void)
31. {
32. int p;
33. init();
34. while(EOF != scanf(“%d”,p))
35. {
36. printf(“%d\n”,eular[eular[p]]);
37. }
38. return 0;
39. }

2011-04-11
POJ 2823 单调队列+IO优化

传送门
在网上逛的时候,看到一个博主说里下单调队列,然后说这题是单调队列的直接应用.就做了下,发现单调队列其实也很容易嘛.不过这题在WS的POJ上需要加上IO优化,不然就一直TLE.或许是我的程序写措了.不可能吧^-^
具体的单调队列介绍还是请看这位博主的.单调队列保证队列的首元素是最优的,如果队首元素”已过期”就”出队”,在考虑新元素时,弹出队列中每当前这个元素优的所有元素,然后这个元素入队.一直这样操作,就能保证队首元素一直是最优的.下面给出IO优化的两个函数:

:



int get_int()

{

int ret=0

char c

char flag=0

c=getchar();

while(‘ ‘ == c || ‘\n’ == c)

c=getchar();

if(‘-‘ == c)

{

flag=1

c=getchar();

}

while(isdigit(c))

{

ret = ret*10+c-‘0’

c=getchar();

}

if(1==flag)

ret = -ret

return ret

}

void put_char(int n)

{

if(n>=10)

put_char(n/10);

putchar(n%10 + ‘0’);

}

2011-03-17
POJ 1704 博弈

传送门

这题看懂了就是一个staircase nim,没看懂就比较难做了.对于staircase nim的理解,你可以这样想.把每两个chess的距离算出来,那么移动任何一个chess的话,会同时改变和这个chess相关的两个距离,左边的减少,右边的增加,这样你就可以把右边的看成是低的梯子,左边是高的梯子.然后用staircase nim来解决就OK了,staircase nim只与奇数层的梯子上的石子数有关,这个可以用P-positon和N-position的定义归纳来证明[每一个P-position只能到达N-position和每个N-position都能达到至少一个P-position].具体关系就是把所有的奇数层上的石子单独拿出来,做一般的nim游戏,如果某个点使P-position的话,那么还原之后的这个staircase nim也处于一个P-position的状态上.反之亦然.
代码如下:

/
ID:qcx97811
LANG:C
TASK:POJ_1704
/
#include
#include
#include
#include

int n,t
int num[1006],nim[1006],idx
int cmp(const void a,const void b)
{
if(((int )a) > ((int )b))
return 1
if(((int )a) < ((int )b))
return -1
return 0
}
int main(void)
{
int i,j,k
scanf(“%d”,t);
while(t–)
{
scanf(“%d”,n);
for(i=0i<n;i++)
scanf(“%d”,num[i]);
num[n]=0
qsort(num,n+1,sizeof(num[0]),cmp);
for(i=n,j=0i>;0;i–,j++)
{
nim[j]=num[i]-num[i-1]-1
}
k=0
for(i=0i<j;i+=2)
k^=nim[i];
if(0==k)
printf(“Bob will win\n“);
else
printf(“Georgia will win\n“);
}
return 0
}
▲