Contest

ACM Contest

ZOJ Monthly, January 2011小结

12
475 天
by in ACM, Contest

回家后就堕落了,没能在家里宅满一整天,天天出去玩,只做了一场TC,而且还扣分了(本来接近的红又越来越远,欲哭无泪啊).
11点半被叫醒,本来今天也不会做的,说好了和一个MM到外边骑马去,午饭都还没来得及吃,和晓立打了声招呼说不做了,不过匆匆扫了一眼题目发现竟然有一道插头DP,而且还是非常规六边形的.我去,当时我就想这道题除了我之外世上还有多少人能在比赛的时候AC它啊(容老衲自恋一番,捏哈哈哈哈哈哈),内心十分矛盾,一方面是和MM的约会,一方面是彰显我插头功底的时候.当时心内还是准备和MM出去玩的>_<
好在这的时候MM打电话过来说那个骑马场过年关门了,要到年后才能开,一个外在的因素让我不用做抉择使得我如释重负.

于是开始做这次的月赛:
J:首先在刷牙洗脸上厕所的时候想了想这六边形的独特之处:有六个边,不过和常规的一样只能有两个度.
好在这题的宽是确定的8，不过却是左边对齐,而不是上边对齐,而长度可能会有10,这又显的稍稍麻烦一点
在纸上画了画(家里笔和纸都没,翻了半天找到小学时候的作业本的铅笔,好在一样好用^_^),发现轮廓线都会变,OMG,这么神奇.
0246列的时候轮廓线只有15个单位,到1357就变成了17个单位,并且是从中间多出来的,不好搞不好搞…
并且0246的时候只有两个已知插头,1357有四个(关键就是那多出来的两个).
于是细心分解后把插头的对应转移关系理清楚,我多设置了两个bit来保持多出来的轮廓,万事准备OK,开始coding.
足足敲了250行,差不多是我写过的插头里边短时间敲出来的最长的代码了,主要是奇偶列还要分出来写,情况还真的是很多.
好在sample给的还算和谐,没有给超级简单没用的sample,还是让我找到了很多个编码时的bug.自己出了几个验证性sample也过了,提交结果是WA,修改了几个漏洞之后发现题目竟然还读错了,多加了一个条件(圈的长度要大于3,题目说的是至少是3,但是小于3也够不成圈啊)我还为这条件想了好久,加了好多个判断,于是反斜杠反斜杠,终于返回了一个期待N久的Accept,哇靠,那敢情,比进finals了还激动..

接下去就正常了,晓立已经把H和I搞定,我看了下过的人最多的D,推敲一下是网络流(小菊花在吃年夜饭,我好久没搞网络流,不过也只好我自己上了),由于笔记本没装dropbox,叫晓立那边仍个模板过来,结果网络流模板太多,丢了好几个才丢中,边界RE TLE了几次后也顺利过了.
接着A过的人比较多,一看就是打表的题,于是马上叫晓立写个暴力的,我去看G,属于比较简单的DP,手指5和9那里的关系(当时我就想不通为什么5个手指可以按9个键=.=)搞了一会后出sample就1A了,晓立接着也搞定了A
还剩15分钟,挣扎着看了一下B,和小丽讨论一下发现没希望了….后来AC大牛说我们OJ有个简化版的(当时还是他教天涯的,而我又是请教天涯的,当时印象中他和我说了两个方法,我就记得一个特殊的递推的方法.残念)

哈哈,今天做出了J题还是蛮开心的,虽然没能和MM出去玩T^T,晚上出去找朋友逛去,坚决不再家里宅一整天时间
附上J题代码(算是插头的一个模板,本来想寒假整理的,不过资源全在实验室电脑里没带回家,还是等回去再发完全版插头dp好了,有兴趣的可以先研究下下面代码):

?View Code CPP
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275

#include <cstdio>
#include <string>
#include <algorithm>
#include <cstring>
using namespace std;
 
#define LL long long
int n , m = 8;
bool maze[11][9];
 
const int HashSize = 300007;
struct HashMap {
	int HashChart[HashSize] , sz;
	int MSK[HashSize];
	bool A[HashSize];
	bool B[HashSize];
	LL dp[HashSize];
	int next[HashSize];
	void clear() {
		sz = 0;
		memset(HashChart, -1, sizeof(int) * HashSize);
	}
	inline void push(int msk, bool a, bool b,LL val) {
		int x = (msk * 4 + a * 2 + b) % HashSize;
		for (int it = HashChart[x] ; it != -1 ; it = next[it]) {
			if (MSK[it] == msk && A[it] == a && B[it] == b) {
				dp[it] += val;
				return ;
			}
		}
		MSK[sz] = msk;
		dp[sz] = val;
		A[sz] = a;
		B[sz] = b;
		next[sz] = HashChart[x];
		HashChart[x] = sz ++;
	}
} HM[2];
HashMap *src = HM;
HashMap *des = HM + 1;
 
LL plugDP() {
	src->clear();
	src->push(0,0,0,1);
	for (int i = 0 ; i < n ; i ++) {
		for (int j = 0 ; j < m ; j ++) {
			des->clear();
			for (int k = 0 ; k < src->sz ; k ++) {
				int msk = src->MSK[k];
				LL val = src->dp[k];
				bool a = src->A[k];
				bool b = src->B[k];
				//printf("%d %d %d %d {",i,j,a,b);
				//for (int it = 0 ; it < 15 ; it ++) {
				//	printf("%d ",(msk >> it) & 1);
				//}
				//puts("}");
				if (j & 1) {
					bool p = ((msk >> (j*2)) & 1);
					bool q = (j == m - 1) ? false : ((msk >> (j*2+1)) & 1);
					int cnt = 0;
					if (p) cnt ++;
					if (q) cnt ++;
					if (a) cnt ++;
					if (b) cnt ++;
					if (maze[i][j] == true) {
						if (cnt == 0) {
							msk &= ~(1 << (j*2));
							msk &= ~(1 << (j*2+1));
							des->push(msk , false , false , val);
						}
						continue;
					}
					if (cnt > 2) continue;
					if (cnt == 2) {
						msk &= ~(1 << (j*2));
						msk &= ~(1 << (j*2+1));
						des->push(msk , false , false , val);
					} else if (cnt == 1) {
						//1
						int nmsk = msk;
						if (i != n - 1 && !maze[i+1][j]) {
			//				if (b && ((msk>>(j*2-1)) & 1))continue;//length 3
							nmsk |= (1 << (j*2));
							nmsk &= ~(1 << (j*2+1));
							des->push(nmsk , false , false , val);
						}
						//2
						if (j != m - 1 && !maze[i][j+1]) {
			//				if (q && ((msk>>(j*2+2)) & 1)) continue;//length 3
							msk &= ~(1 << (j*2));
							msk |= (1 << (j*2+1));
							des->push(msk , false , false , val);
						}
					} else if (cnt == 0) {
						if (j != m - 1 && i != n - 1 && !maze[i+1][j] && !maze[i][j+1]) {
							msk |= (1 << (j*2));
							msk |= (1 << (j*2+1));
							des->push(msk , false , false , val);
						}
					}
				} else {
					bool p = (j == 0) ? 0 : ((msk >> (j*2-1)) & 1);
					bool q = ((msk >> (j*2)) & 1);
					a = ((msk >> (j*2+1)) & 1);
					if (maze[i][j]) {
						if (!p && !q) {
							b = false;
							msk &= ~(1 << (j*2));
							msk &= ~(1 << (j*2+1));
							if (j) msk &= ~(1 << (j*2-1));
							des->push(msk , a , b , val);
						}
						continue;
					}
					if (p && q) {
						b = false;
						msk &= ~(1 << (j*2));
						msk &= ~(1 << (j*2+1));
						if (j) msk &= ~(1 << (j*2-1));
						des->push(msk,a,b,val);
					} else if (p || q) {
						//1
						int nmsk = msk;
						if (!maze[i][j+1]) {
			//				if (q && a) continue; //length 3
							b = true;
							nmsk &= ~(1 << (j*2));
							nmsk &= ~(1 << (j*2+1));
							if (j) nmsk &= ~(1 << (j*2-1));
							des->push(nmsk , a , b , val);
						}
						if (i == n - 1) continue;
						//2
						if (!maze[i+1][j]) {
							nmsk = msk;
							b = false;
							nmsk |= (1 << (j*2));
							nmsk &= ~(1 << (j*2+1));
							if (j) nmsk &= ~(1 << (j*2-1));
							des->push(nmsk , a , b , val);
						}
						//3
						if (!maze[i+1][j+1]) {
							nmsk = msk;
							b = false;
							nmsk &= ~(1 << (j*2));
							nmsk |= (1 << (j*2+1));
							if (j) nmsk &= ~(1 << (j*2-1));
							des->push(nmsk , a , b , val);
						}
						//4
						if (j && !maze[i+1][j-1]) {
			//				if (p && ((msk >> (j*2-2)) & 1)) continue;//length 3
							nmsk = msk;
							b = false;
							nmsk |= (1 << (j*2-1));
							nmsk &= ~(1 << (j*2));
							nmsk &= ~(1 << (j*2+1));
							des->push(nmsk , a , b , val);
						}
					} else {
						if (i == n - 1) continue;
						//1
						int nmsk = msk;
						if (!maze[i][j+1] && !maze[i+1][j]) {
							b = true;
							nmsk |= (1 << (j*2));
							nmsk &= ~(1 << (j*2+1));
							if (j) nmsk &= ~(1 << (j*2-1));
							des->push(nmsk , a , b , val);
						}
						//2
						if (!maze[i+1][j+1] && !maze[i+1][j]) {
							nmsk = msk;
							b = false;
							nmsk |= (1 << (j*2));
							nmsk |= (1 << (j*2+1));
							if (j) nmsk &= ~(1 << (j*2-1));
							des->push(nmsk , a , b , val);
						}
						//3
						if (!maze[i+1][j+1] && !maze[i][j+1]) {
							nmsk = msk;
							b = true;
							nmsk &= ~(1 << (j*2));
							nmsk |= (1 << (j*2+1));
							if (j) nmsk &= ~(1 << (j*2-1));
							des->push(nmsk , a , b , val);
						}
						if (j && !maze[i+1][j-1]) {
							//4
							if (!maze[i][j+1]) {
								nmsk = msk;
								b = true;
								nmsk &= ~(1 << (j*2));
								nmsk &= ~(1 << (j*2+1));
								nmsk |= (1 << (j*2-1));
								des->push(nmsk , a , b , val);
							}
							//5
							if (!maze[i+1][j]) {
								nmsk = msk;
								b = false;
								nmsk |= (1 << (j*2));
								nmsk &= ~(1 << (j*2+1));
								nmsk |= (1 << (j*2-1));
								des->push(nmsk , a , b , val);
							}
							//6
							if (!maze[i+1][j+1]) {
								nmsk = msk;
								b = false;
								nmsk &= ~(1 << (j*2));
								nmsk |= (1 << (j*2+1));
								nmsk |= (1 << (j*2-1));
								des->push(nmsk , a , b , val);
							}
						}
					}
				}
			}
			swap(src,des);
		}
	}
	for (int i =0 ; i < src->sz ; i ++) {
		if (src->MSK[i] == 0 && src->A[i] == false && src->B[i] == false) return src->dp[i];
	}
	return 0;
}
int main() {
	int m;
	while (~scanf("%d%d",&n,&m)) {
		memset(maze , false , sizeof(maze));
		for (int i = 0 ; i < m ; i ++) {
			char str[3];
			scanf("%s",str);
			maze[ str[0] - 'A' ][ str[1] - 'A' ] = true;
		}
		printf("%lld\n",plugDP());
	}
	return 0;
}
/*
2 12
AC BC
AD BD
AE BE
AF BF
AG BG
AH BH
2 13
AB
AC BC
AD BD
AE BE
AF BF
AG BG
AH BH
3 7
BB AD BD CD BF AH CG
3 15
AA BA CA
AB BB CB
AC BC CC
AD BD CD 
BF AH CG
3 16
BB 
AD BD CD
AE BE CE
AF BF CF
AG BG CG
AH BH CH
*/

Popularity: 15% [?]

HDOJ Monthly Contest – 2010.01.02

11
868 天
by in Contest

HDU的第一次月赛,本来lcy打算给我们队多练习一场,所以题目交给小丽和ch测了.比赛前5分钟通知了我的两个队友发现他们不知道-_-一个自习,一个在家…替刘老师汗一个.于是就只能孤军奋战了

1001The Diophantine Equation

水题,字符解析我脑残了一会才想出来,而且没注意是非负解,错了一次

1005City Planning

ch的题目.感觉描述比较简单,但是我方法没想完全就敲,结果途中换了N多个方法,spfa,并查,最后还WA了,当时我很浮躁,于是不停的提交,最后用dfs过了 6Y

1008Marriage Match III

网络流,难点在于女孩的K(every girl can accept any K boys),用拆点的方法可以解决这个限制,前段时间做过类似的,详见这篇文章的第二题 两题男孩的限制又不一样,所以男孩不用拆点,1Y

1006Light

从左到右遍历,如果是偶数的话那么后面k-1个灯要+1,用线段树可以实现这个功能,处理k=0,1的时候错了一次

1003Mission Impossible

直接dfs,H->B->C->H和H->C->B->H的两种方法连线,连线的同时还枚举了是否经过x轴和y轴(用镜面反色的方法)1Y

1002SNIBB

AC大牛的神题,还硬是把我的名字扯上去small HH,不做都不好意思.还好这次不是数论,而是一个比较恶心的DP,2的操作加一个二分答案,边界的时候很难处理,勉强可以应付,用暴力验证了一下我方法的正确性后交了,惊讶的返回Accepted,看别人错了这么多次本以为自己至少也要十次八次.1Y

1009Puzzle

这是一道我擅长的搜索,当时还没人AC,而1007Star有 人过了,但是对那题没有思路,第一感觉要什么线性规划做,没接触过,于是放弃了…这题开始感觉状态很难表示,于是IDA*,毫无悬念的超时了.后来发现如果把其中一个当成要移到中间的颜色,而另外两种就可以看成同一个颜色了,这样状态就小了很多,2^24,而且只有8个1,没有具体计算多少复杂度(应该是C(8,24)),直接开了 3000007的散列表进行hash,旋转的地方没有多少时间思考(只剩25分钟了),直接暴力写,然后本地测试,等了好几秒跑不出来…这时候我觉得 vs用队列很慢,而这个复杂度服务器是可以接受的,于是在没有测过sample的情况下交了,返回一个 Accepted哈哈…最后发现跑了2984MS,差一点点就超时了- -,惊险卡过

其实临近期末好久没敲过代码了,但是复习不进去,于是给了自己堕落的借口,今天能捧杯实在是连自己都感到意外.哈哈,得意的笑笑

Popularity: 3% [?]

Page 1 of 11
Go to Top