Archive

Archive for November, 2009

URAL 1023

November 18, 2009 Leave a comment

Background

  Yekaterinburg获得了2032年夏季奥运会的举办权。由于允许举办国对竞赛项目进行一些小的修改。现
打算修改“Button”这个新项目的规则。规则很简单,在2个对手前有一堆扣子(k个),2人轮流取走扣
子,同一时间,某人能取走1至L个扣子。取走最后一个扣子的为胜者。作为奥运会项目,规则应该比通常
玩的要难一点。先走者可以设定数K(就是总共有k个扣子),3<=K<=100 000 000.后走者可以设定数
L,2 <= L < K

[编辑] Problem

  现在要紧的问题是,请你写一个程序,帮助后走者做出抉择。换言之,当给出K后,你的程序
能给出数L,使到后走者能获胜。例如, 如果只有3个扣子,后走者把L定为2,有必胜把握。事实
上,如果先走者取了1个扣子,那么后走者可以取剩下的2个扣子,后走者胜。如果先走者取了2个
扣子,那么后走者取1个,也是后走者胜。

Input

输入只包含一个整数K,扣子的总数。

Output

输出L。每次最多能取走的扣子总数,要求保证后走者必胜。假如有多个答案,输出最小的。如果 不存在保证能必胜的L,则输出0。

Sample Input

3

Sample Output

2

可以证明,一定存在这样的L,使后走者胜
事实上,若设L=K-1,则当先走者取完后,剩下的扣子数<=K-1,这样后走者一定能取完,从而得胜
另外,我们可以得到L的一个充分条件:(L+1)|K且L>=2。证明:若先走者取x个棋子,则后走者取L+1-x个棋子,这样循环进行下去,后走者一定取胜。
事实上,这也是一个必要条件,若(L+1)不能整除K,设m = K mod (L+1),第一步先走者取m个棋子,以后后走者若取x个棋子,则先走者取L+1-x个棋子,先走者一定取胜。
综上所述,这道题就转化为:求出K的大于2的最小因数,减1输出。另外对于偶数需要特判。

#include<stdio.h>
#include<math.h>
int main()
{
	int k;
	scanf("%d",&k);
	for(int i=3;i<=sqrt((double)k)*2;++i)
		if(!(k%i))
		{
			printf("%d\n",i-1);
			return 0;
		}
	if(k&1) printf("%d\n",k-1);
	else printf("%d\n",(k>>1)-1);
	return 0;
}
Advertisements
Categories: Old Blog Posts

《算法艺术与信息学竞赛》题目-提交方式对照表

November 18, 2009 Leave a comment

id title how2submit source page
1 盒子里的气球 8
2 图书馆 ural1188 9
3 钓鱼 uva757 pas 13
4 照亮的山景 13
5 镜子盒 15
6 折纸痕 uva177 pas 19
7 三色多边形 ural1181 20
8 聪明的学生 20
9 丢失的数 23
10 月亮之眼 28
11 Yanghee的数表 29
12 原子链 31
13 铁轨 uva514 c 36
14 小球钟——时间与运动 uva239 * 38
15 笑脸 40
16 猜猜我想说什么 44
17 勇士Ilya的故事 ural1088 50
18 蚂蚁和瓢虫 52
19 隔三遍历 54
20 拯救大兵瑞恩的故事 61
21 英雄和公主的故事 uva258 * 62
22 电气工程师 64
23 爱丽丝和精灵的故事 67
24 电缆 ural1184 68
25 黑白按钮 69
26 煎饼 uva120 pas 70
27 傻瓜Ivanushka的故事 ural1082 72
28 士兵排队 75
29 最小可靠交换 zju1388 76
30 代码等式 80
31 团伙 81
32 银河英雄传说 81
33 可爱的猴子 82
34 蜗牛 83
35 积水 89
36 赛车 89
37 可怜的奶牛 uva10273 * 90
38 最轻巧的语言 91
39 马尔可夫链 97
40 促销 99
41 采矿 102
42 火星地图 108
43 最长回文子串 110
44 括号序列 ural1183 113
45 棋盘分割 116
46 决斗 117
47 舞蹈家怀特先生 117
48 积木游戏 119
49 方块消除 uva10559 * 123
50 公路巡逻 123
51 并行期望值 zju1022 125
52 高性能计算机 126
53 模板匹配 130
54 不可分解的编码 131
55 青蛙的烦恼 ural1143 133
56 排列问题 134
57 最优排序二叉树 135
58 Bugs公司 138
59 迷宫统计 uva10531 * 139
60 贪吃的九头龙 142
61 最长公共子序列问题 150
62 排列的LCS问题 150
63 最长上升子序列问题 uva10534(slightly modified) * 151
64 最优二分检索树 uva10304 pas 151
65 任务调度问题 152
66 序列分割 155
67 加密网格 160
68 最优程序 uva656 c/pas 162
69 旋转的玩具 uva704 pas 164
70 编辑书稿 169
71 埃及分数 171
72 三角形大战 uva751 pas 175
73 L游戏 178
74 带宽 uva140 pas 180
75 小木棍 uva307 pas 181
76 生日蛋糕 181
77 汽车问题 183
78 Betsy的旅行 184
79 外公的难题 189
80 篮球冠军赛 193
81 麻烦 ural1155 204
82 沙漠 ural1170 204
83 浪人苏比 205
84 好动的佳佳 ural1130 206
85 细菌 207
86 X行星 208
87 佳佳的困惑 ural1095 220
88 除法表达式 220
89 数字游戏 uva10164 pas 221
90 fibonacci质数 uva10236 * 221
91 神秘数 222
92 自动取款机 225
93 人类学家的烦恼 uva701 pas 226
94 征服者的军营 226
95 仓库问题 ural1107 233
96 二进制Stirling zju1385 233
97 荒岛野人 uva10413 * 234
98 单色三角形 240
99 互不攻击的象 uva10237 * 243
100 传球游戏 245
101 无聊的排序 247
102 多边形 252
103 装饰栅栏 257
104 Pibonacci 258
105 巧克力 zju1363 259
106 绣花 ural1035 274
107 漆门 ural1129 275
108 原始基因 275
109 超级翻转 276
110 地图的五着色 281
111 滑雪 282
112 水平可见线段的三角形 zju1391 283
113 往返路 287
114 连通图编号问题 287
115 跳舞蝇 287
116 参观洞穴 289
117 公主和英雄 zju1384 291
118 通讯员 293
119 幼儿园小朋友分组 ural1128 295
120 岛国 299
121 野餐计划 300
122 地震 303
123 罗密欧与朱丽叶 304
124 出纳员的雇佣 zju1420 306
125 瘦陀陀与胖陀陀 uva10246 pas 308
126 新桥 309
127 穿越沙漠 310
128 隐型石头 uva10381 * 311
129 双调路径 312
130 奶牛的新年晚会 315
131 航天计划问题 317
132 终极情报网 318
133 圆桌吃饭问题 uva10249 pas 323
134 数字游戏 uva10546 * 324
135 混合图的欧拉回路 zju1992 324
136 家园 325
137 道路扩容 326
138 神奇的魔术师 329
139 任务安排 zju1364 331
140 棋盘上的骑士 332
141 丘比特的烦恼 333
142 魔术球问题 uva10276 * 333
143 皇家卫士 334
144 固定分区的内存管理 336
145 玩具兵 uva10418 * 336
146 千年盛典 338
147 房间最短路问题 uva393 pas 353
148 管道问题 uva303 pas 359
149 篱笆问题 387
150 合金制造问题 388
151 点集的直径 401
152 最小外接矩形 uva10173 * 402
153 点集分割 uva10256 * 404
154 锡刀 uva308 c 410
155 奇怪的问题 11
156 售货员 ural1011 12
157 翻硬币 12
158 离散函数 ural1010 12
159 超长数字串 ural1165 12
160 喷水装置 uva10382 * 18
161 最优布车方案 18
162 潜水比赛 19
163 蚂蚁的递归访问 27
164 整数对 ural1189 33
165 寻找魔法豌豆 33
166 锁链 33
167 银行抢劫 uva707 pas 34
168 狂风刮进办公室 34
169 时区 34
170 位图的块 42
171 矩形分划 42
172 程序复杂度 43
173 项链 49
174 病毒 50
175 树重建 uva10410 * 58
176 树分割 58
177 毛毛虫 58
178 与非门电路 zju1390 65
179 比较网络 66
180 推门游戏 uva10384 * 67
181 千年庆典——赤道大篝火 78
182 鸡蛋 78
183 窗户 87
184 奇数偶数 ural1003 88
185 方格 94
186 仓库 95
187 天上的星星 ural1024 104
188 围棋 105
189 10-20-30游戏 106
190 方块堆砌的小镇 107
191 最长弱重复子串 112
192 暗室里的油画 112
193 太空物质吸收器 112
194 最长重复子串 112
195 艺术馆的火灾 121
196 机器人的名字 122
197 快乐的蜜月 144
198 移动机器人 145
199 佳佳的筷子 uva10271 * 145
200 偷懒的工人 146
201 铁路调度 146
202 平板涂色 zju1424 146
203 道路重建 147
204 圆和多边形 zju1679 147
205 铁球落地 148
206 免费糖果 uva10118 pas 148
207 丢三落四的老鼠 148
208 多排列的LCS 157
209 回文词 157
210 友好城市 157
211 邮局 uva662 c 157
212 基因串 157
213 奶牛转圈 158
214 元件折叠 uva10239 * 158
215 DNA序列 158
216 超级天平 165
217 奶牛的加密术 USACO Gateway 166
218 智力玩具 166
219 平分资源 167
220 百慕大魔鬼三角的蛋糕 zju1017 167
221 新别墅 uva321 c 168
222 赶时间 173
223 永别了,朋友! uva10119 c 174
224 智破连环阵 174
225 算符破译 187
226 破坏正方形 zju1031 187
227 列车调度 188
228 机场跑道 196
229 采矿 197
230 灌溉 197
231 Gnome Tetravex zju1008 198
232 智慧方块 198
233 最优逻辑电路设计 199
234 加密 zju1020 201
235 马戏团入场券 201
236 清洁公司 202
237 序列 210
238 反等差数列 210
239 幂的和 uva766 pas 210
240 奇怪的数列 ural1175 211
241 三臂起重机 211
242 中央暖气 ural1042 211
243 奶牛和多边形 211
244 矩阵法 212
245 迸裂的豌豆 212
246 公平外交 213
247 GPA排名系统 213
248 超级幻方 uva10538 * 214
249 移位寄存器 214
250 礼物?! uva10120 pas 215
251 反素数 228
252 神奇的数对 sgu119 pas 228
253 灯泡 228
254 Farey序列 228
255 玻璃弹珠 uva10090 pas 235
256 庆典的日期 236
257 超级马 237
258 火柴问题 237
259 石子问题 237
260 质数游戏 237
261 旋转盘 zju1028 237
262 牛场围栏 238
263 电子锁 245
264 彩票 uva10288 * 245
265 三维数码难题 uva716 pas 253
266 同构计数 253
267 手镯 uva10294 * 254
268 掷色子 uva10238 * 260
269 和施瓦辛格共进晚餐 uva10217 * 261
270 串并联网络 uva10253 * 261
271 奶牛计数 262
272 数字不干胶 262
273 带标号连通图计数 267
274 数字接力 268
275 广场上的地板砖 278
276 骑士周游 uva10255 pas 278
277 Gridland zju1037 278
278 邮递员 279
279 城市观光 280
280 赌博机 280
281 n维城市 uva10240 * 296
282 远程通信 296
283 旅行路线 ural1077 297
284 龙穴迷宫 297
285 追捕游戏 298
286 魔法车 uva10457 * 313
287 观光路线 ural1004 313
288 奶牛接力 313
289 路的最小公倍数 313
290 货币兑换 ural1162 313
291 速度限制 314
292 会议呼叫 314
293 公平会面 315
294 开发计划 327
295 因特网带宽 328
296 出题者的烦恼 uva10092 pas 328
297 马戏团 328
298 锦标赛 uva10380 * 328
299 机器人规划 328
300 方格取数 340
301 团队分组 ural1182 341
302 调皮的导盲犬 uva670 pas 341
303 会议 ural1109 341
304 神秘之山 uva10122 pas 342
305 棋盘游戏 342
306 代表团 uva10511 * 342
307 加号和减号 ural1092 342
308 动物园 343
309 Unix插头 uva753 pas 344
310 整数因子团问题 344
311 迷宫寻宝 uva754 cpp 360
312 自行车路线 uva248 * 360
313 篱笆视角问题 uva667 cpp 360
314 凸多边形的本影和半影 uva746 cpp 382
315 极品牛奶 uva10117 pas 382
316 载油问题 383
317 导弹和王国 uva109 pas 409
318 咖啡 uva10089 * 409
319 GIF混合 409
320 圆盘问题 zju1696 423
321 最大内空凸多边形 zju1562 423

Categories: Old Blog Posts

USACO 5.4.3 Character Recognition

November 13, 2009 Leave a comment

这应该是USACO最不像DP的DP了。这是啥类型,统计DP?
设f[i]为前i行匹配的最小差距值,对应的字符串可以在求f[i]时求得
则f[i]=min(f[i-19]+cmp[i,19],f[i-20]+cmp[i,20],f[i-21]+cmp[i,21])
其中求cmp[i,j]:
若j=20,显然这时刚好匹配,只要直接计算就行了
若j=19,枚举添加的那一行,取差距最小的
若j=21,枚举删除的那一行,取差距最小的
由于每行20个字符,可以在读入时用整型变量压缩存储,计算a与b的差距值即计算a xor b的1的个数,对提速有一定的效果

/*
ID: dementr1
PROG: charrec
LANG: C++
*/
#include
#include
#define MAX 100000
using namespace std;
ifstream fin("charrec.in");
ifstream font("font.in");
ofstream fout("charrec.out");
int n,N;
int text[30][30]={};
int s[2000]={};
int f[2000];
string symbol[2000];
char word[27];
bool vis[2000]={false};
void init()
{
	char tmp;
	word[0]=' ';
	for(int i=1;i>N;
	for(int i=0;i<=26;i++)
		for(int j=1;j<=20;j++)
			for(int k=1;k>tmp;
				text[i][j]=(text[i][j]<>n;
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j>tmp;
			s[i]=(s[i]<<1)+tmp-'0';
		}
	}
	for(int i=1;i>1)&0x55555555);
	x=(x&0x33333333)+((x>>2)&0x33333333);
	x=(x&0x0F0F0F0F)+((x>>4)&0x0F0F0F0F);
	x=(x&0x00FF00FF)+((x>>8)&0x00FF00FF);
	x=(x&0x0000FFFF)+((x>>16)&0x0000FFFF);
	return x;
}
int compare(int from, int length, int id)
{
	int ans=0;
	if(length==20)
	{
		for(int i=from;i<from+length;i++)
			ans+=cmp(s[i],text[id][i-from+1]);
		return ans;
	}
	if(length==19)
	{
		ans=MAX;
		for(int i=1;i<=20;i++)
		{
			int now=0;
			int a=1;
			for(int j=1;j<=20;j++)
			{
				if(i!=j)
				{
					now+=cmp(s[from+a-1],text[id][j]);
					a++;
				}
			}
			if(now<ans)
				ans=now;
		}
		return ans;
	}
	if(length==21)
	{
		ans=MAX;
		for(int i=1;i<=21;i++)
		{
			int now=0;
			int a=1;
			for(int j=1;j<=21;j++)
			{
				if(j!=i)
				{
					now+=cmp(s[from+j-1],text[id][a]);
					a++;
				}
			}
			if(now<ans)
				ans=now;
		}
		return ans;
	}
}
void dp(int h)
{
	vis[h]=true;
	if(0<=h&&h=19)
	{
		if(!vis[h-19])
			dp(h-19);
		if(f[h-19]!=MAX)
			for(int i=0;i<=26;i++)
			{
				tmp=compare(h-18,19,i)+f[h-19];
				if(tmp=20)
	{
		if(!vis[h-20])
			dp(h-20);
		if(f[h-20]!=MAX)
			for(int i=0;i<=26;i++)
			{
				tmp=compare(h-19,20,i)+f[h-20];
				if(tmp=21)
	{
		if(!vis[h-21])
			dp(h-21);
		if(f[h-21]!=MAX)
			for(int i=0;i<=26;i++)
			{
				tmp=compare(h-20,21,i)+f[h-21];
				if(tmp240)
		symbol[h][symbol[h].length()-1]='?';
}
void work()
{
	int tmp;
	string empty="";
	if(f[n]==MAX)
		dp(n);
}
void print()
{
	fout<<symbol[n]<<endl;
}
int main()
{
	init();
	work();
	print();
	return 0;
}



Categories: Old Blog Posts

USACO 5.3.4 Big Barn

November 13, 2009 Leave a comment

这题直接把3.3.4的方程套过来就行了……

f[i][j] = 0                    !a[i][j]

min(f[i-1][j],f[i][j-1],f[i-1][j-1])+1 a[i][j]

/*
ID: dementr1
PROG: bigbrn
LANG: C++
*/
#include
#include
using namespace std;
ifstream fin("bigbrn.in");
ofstream fout("bigbrn.out");
int n,t,f[1000][1000]={};
bool v[1000][1000];
void init()
{
	int i,j,a,b;
	fin>>n>>t;
	for(i=0;i<n;i++)
		for(j=0;j<n;j++)
			v[i][j]=true;
	for(i=0;i>a>>b;
		v[a-1][b-1]=false;
	}
	fin.close();
}
void work()
{
	int i,j,max=0;
	for(i=0;i<n;i++)
	{
		if(v[0][i])
		{
			f[0][i]=1;
			max=1;
		}
		if(v[i][0])
		{
			f[i][0]=1;
			max=1;
		}
	}
	for(i=1;i<n;i++)
		for(j=1;j<n;j++)
		{
			if(v[i][j])
				f[i][j]=1;
			if(v[i][j])
			{int tmp=f[i-1][j];

			if(f[i-1][j-1]<tmp)
				tmp=f[i-1][j-1];
			if(f[i][j-1]f[i][j])
				f[i][j]=tmp+1;}
			if(f[i][j]>max)
				max=f[i][j];
		}
	fout<<max<<endl;
}
int main()
{
	init();
	work();
	return 0;
}
Categories: Old Blog Posts

USACO 3.1.5 Contact

November 13, 2009 Leave a comment

可以设置一个长度为B的队列,这样可以避免存储200000个字符的繁长序列,边读入边存储就行了
存储时,可以在每种字串前加一个1,这样就避免了不同长度有一串前导0的重复情况

<此题缺代码>

Categories: Old Blog Posts

USACO 3.3.2 Shopping Offers

November 13, 2009 Leave a comment

这是一道很蛋疼的五维完全背包题
设f[a1][a2][a3][a4][a5]为分别买ai(1<=i<=5)种编号为i的商品,所需要的最少金额
初始化:f[a1][a2][a3][a4][a5]=prize[1]*a1+prize[2]*a2+prize[3]*a3+prize[4]*a4+prize[5]*a5
状态转移方程: f[a1][a2][a3][a4][a5]=min{f[a1-count[k][1]][a2-count[k][2]][a3-count[k][3]][a4-count[k][4]][a5-count[k][5]]+cost[k]},其中count[i][j]代表第i种优惠方案所需第j种商品的件数,cost[i]代表第i种优惠方案的总金额

/*
ID: dementr1
PROG: shopping
LANG: C++
*/
#include
#include
using namespace std;
ifstream fin("shopping.in");
ofstream fout("shopping.out");
struct news
{
	int num,c[5],k[5],p;
} fees[100],real[100];
int code[10],amount[10],prize[10],s,b;
bool canuse[100];
void swap(int *a, int *b)
{
	int x;
	x=*a,*a=*b,*b=x;
}
void init()
{
	int i,j;
	memset(fees,0,sizeof(fees));
	memset(canuse,true,sizeof(canuse));
	fin>>s;
	for(i=0;i>fees[i].num;
		for(j=0;j>fees[i].c[j]>>fees[i].k[j];
		fin>>fees[i].p;
	}
	fin>>b;
	for(i=0;i>code[i]>>amount[i]>>prize[i];
	for(i=0;i<b;i++)
		for(j=i+1;jcode[j])
			{
				swap(&code[i],&code[j]);
				swap(&amount[i],&amount[j]);
				swap(&prize[i],&prize[j]);
			}
}
int search(int i)
{
	int j;
	for(j=0;j<b;j++)
		if(code[j]==i)
			return j;
	return -1;
}
void change()
{
	int i,j;
	for(i=0;i<s;i++)
	{
		real[i].num=fees[i].num;
		real[i].p=fees[i].p;
		for(j=0;j<real[i].num;j++)
		{
			int tmp=search(fees[i].c[j]);
			if(tmp==-1)
			{
				canuse[i]=false;
				break;
			}
			real[i].c[tmp]=fees[i].c[j];
			real[i].k[tmp]=fees[i].k[j];
		}
	}
}
void dp()
{
	int f[6][6][6][6][6],a0,a1,a2,a3,a4,i;
	for(a0=0;a0<=amount[0];a0++)
		for(a1=0;a1<=amount[1];a1++)
			for(a2=0;a2<=amount[2];a2++)
				for(a3=0;a3<=amount[3];a3++)
					for(a4=0;a4<=amount[4];a4++)
						f[a0][a1][a2][a3][a4]=prize[0]*a0+prize[1]*a1+prize[2]*a2+prize[3]*a3+prize[4]*a4;
	for(a0=0;a0<=amount[0];a0++)
		for(a1=0;a1<=amount[1];a1++)
			for(a2=0;a2<=amount[2];a2++)
				for(a3=0;a3<=amount[3];a3++)
					for(a4=0;a4<=amount[4];a4++)
						for(i=0;i=0&&
								a1-real[i].k[1]>=0&&
								a2-real[i].k[2]>=0&&
								a3-real[i].k[3]>=0&&
								a4-real[i].k[4]>=0)
								{
									int tmp=f[a0-real[i].k[0]][a1-real[i].k[1]][a2-real[i].k[2]][a3-real[i].k[3]][a4-real[i].k[4]];
									if(tmp+real[i].p<f[a0][a1][a2][a3][a4])
										f[a0][a1][a2][a3][a4]=tmp+real[i].p;
								}
	fout<<f[amount[0]][amount[1]][amount[2]][amount[3]][amount[4]]<<endl;
}
int main()
{
	init();
	change();
	dp();
	return 0;
}
Categories: Old Blog Posts

USACO 5.4.2 Canada Tour

November 13, 2009 Leave a comment

我看到这题就立马傻眼了,以下是自己对Nocow上题解的理解
这题的叙述(纯指叙述)有些类似于NOIP2008提高组第3题传纸条,都是兜一圈再回来,我们可以用类似的方法,将求一条回路转化为求两条不相交的路径(两个人分别从最西边的城市出发,到达最东边的城市的路径)
设状态f[i][j]表示第一个人已经走到第i个城市,第二个人走到第j个城市时所访问的城市数目的最大值,则
f[i][j]=max{f[i][k]+1} (link[k][j]&&f[i][k]>0)
+1写在max里是因为如果没有满足条件的k的话,f[i][j]=0
另外,显然有f[i][j]=f[j][i]
最终的结果就是max{f[N][i]} (link[i][N])

/*
ID: dementr1
PROG: tour
LANG: C++
*/
#include
#include
using namespace std;
ifstream fin("tour.in");
ofstream fout("tour.out");
int n;
string name[101];
bool v[101][101]={false};
int ans=-1;
int f[101][101]={};
int search(string s)
{
	for(int i=1;i>n>>num;
	for(int i=1;i>name[i];
	for(int i=0;i>tmp1>>tmp2;
		from=search(tmp1);
		to=search(tmp2);
		v[from][to]=v[to][from]=true;
	}
	fin.close();
}
void work()
{
	f[1][1]=1;
	for(int i=1;i<=n;i++)
		for(int j=i+1;j<=n;j++)
			if(i!=1||j!=1&&f[i][j]==0)
			{
				int max=-1;
				for(int k=1;k0)
						if(f[i][k]+1>max)
							max=f[i][k]+1;
				f[i][j]=f[j][i]=max;
			}
	for(int i=1;ians)
			ans=f[i][n];
}
void print()
{
	if(ans<=1)
		fout<<1<<endl;
	else
		fout<<ans<<endl;
}
int main()
{
	init();
	work();
	print();
	return 0;
}

Categories: Old Blog Posts