2003/8 暑假集训解题报告
2001级计科系 尹思
<template>
题目：SOJ
分类：
讨论：
代码：
总结：
</template>
――――――――――――――――－
题目：SOJ1196 Set Me
分类：简单模拟
讨论：注意格式和逻辑判断式的正确性
代码：逻辑表达式的代码：
if ( !((cards[i][l] == cards[j][l] && cards[i][l] == cards[k][l])|| ( cards[i][l] != cards[j][l] && cards[i][l] != cards[k][l] && cards[j][l] != cards[k][l] )))
总结：这类题一定要一次通过。
――――――――――――――――
题目：SOJ1195 To The Max
分类：简单动态规划
讨论：这是动态规划的一个经典试题， 有个重要的思想就是降维， 这样将大大减小数据规模，本来为2维的矩阵图减少为1维的线性数组， 然后在求
数组的最大连续数和， 如何降？通过数组的记录累加遍历所有的行列和。
代码：降维的代码：
for (k=0; k<N; k++)
{ for (i=0; i+k<N; i++) { memset( b, 0, sizeof(b) ); for (j=0; j<=k; j++) { for (l=0; l<N; l++) b[l] += martrix[i+j][l]; } tmp = toMax(); if ( imax < tmp ) imax = tmp; } }求线性数组最大连续和的代码：
int toMax() { int sum = -1; int tmp = -100000; for (int i=0; i<N; i++) { if ( sum < 0 ) sum = b[i]; else sum += b[i]; if ( sum > tmp ) tmp = sum; } return tmp; }
总结：这类题一次完全写对的可能性还是有点小，写完后应该仔细写一些测试数据来测试。关于降维的思想应该在那种解决多维数据的题时想到。
―――――――――――――――――
题目：SOJ1194 Round and Round We Go
分类：字符串处理
讨论：字符串处理的题在竞赛中出现的几率非常大， 是必须要作对的题， 此题比较简单， 注意边界问题和字符串的末尾0的问题
代码：无
总结：做字符串题很不容易一次作对，需要仔细检查代码， 并且要记熟常用字符串函数和一些技巧， 如sscanf， strtok等函数。
―――――――――――――――――－
题目：SOJ1193 Microprocessor Simulation
分类：简单模拟
讨论：注意switch的条理和多组数据输入时的初始化问题
代码：无
总结：要一次通过， 大规模输入时要仔细， 调试时要有耐心。
―――――――――――――――――
题目：SOJ1191 Bode Plot
分类：简单数学， 推理
讨论：此题的特点是，从题目隐含的条件(t=0)中求出一个参数， 然后再代入求其结果， 这点不容易想到， 特别需要注意。
代码：无
总结：推公式时要细心， 注意输入输出精度。
――――――――――――――――――
题目：SOJ1188 Color Me Less
1189 P,MTHBGWB
分类：简单模拟
讨论：无
代码：无
总结：无
――――――――――――――――――－
题目：SOJ1187 Closest Common Ancestors
分类： 简单模拟
讨论：注意树的表示方法， 用数组是最简便的。
要善于利用标记来记录。
代码：标记代码
while ( a != 0 ) { flag[a] = 1; a = father[a]; } while ( flag[b] != 1 ) { b = father[b]; }
总结：无
―――――――――――――
题目：SOJ 1185 Rectangles
分类：简单几何题
讨论：无
代码：无
总结：不要想复杂了。
――――――――――――――
题目：SOJ 1182 Multiple
分类：复杂数学， 推理题
讨论：
数 a = k * M +r
所以
a % M = ( k * M + r ) % M
= r % M
在这里 r 的范围为 0 － 4998而且是有重复性的，所以在这里可以运用动态规划中的记录特性－利用标记。生成数的方法是用的BFS, 首先排序一次， 得到的第一个可行解就为最优解。
因为一次只能得到一个数字，所以设置节点的数据结构为
struct Node
{ int pre; int a; int num; };
代码: BFS部分
while ( head != rear ) { cur = que[head++]; for (int i=0; i<M; i++) { ta = cur.a % N * 10 + seq[i]; if ( ta == 0 ) continue; ta %= N; if ( flag[ta] == 1 ) continue; tmp.num = seq[i]; tmp.a = ta; tmp.pre = head - 1;que[rear++] = tmp;
flag[ta] = 1;if ( ta == 0 )
{ Output(); return true; } } }总结： 这道题难点有2个， 一个是构造出标记， 第二个是想到用生成数字而不是遍历数字， 最后就是数据结构的设计和BFS的应用。―――――――――――――――题目：SOJ 1180 Strategic Game分类： 简单贪心讨论： 该题有个地方值得注意， 就是该题所指的是棵树而不是图， 树是有层次的， 而图没有， 所以如果用图的数据结构就会出错。还有该题的输入方式也值得注意。代码： 无总结： 贪心是个很重要的方法， 但使用之前一定要确定其正确性。――――――――――――――――题目：SOJ 1178 Number Game分类： 博弈算法讨论： 改题本质是道博弈算法题， 遍历游戏的所有可能性来判断是否先手能够胜利。但是这道题总共的数的个数为20 个， 如果用DFS来搜索的话明显运算量太大而会超时， 所以这里需要优化。观察到在DFS的途中，数的序列会重复， 所以这里可以采用记录的方法来减小运算时间。
数据结构的设计在这道题也是个难点， 因为数的个数最大为20个， 所以可以用一个32bit的整形数， 用0－19位每位代表一个数是否被选过，是1代表选过， 0代表没有选过。
设数组bool F[2^20], 其中F[n]代表在数列n（32bit数表示当前数的序列状态）的这种情况下， 先走的玩家是否能够一定赢。
博弈树
F[n]
F[k1]
F[k2]
F[k3]
…
当F[n]为先手的状态时：
经过选择不同的数， 产生不同的状态k1,k2,k3…, 如果当F[k1], F[k2]…有任何一个为1时， 则F[n]＝0即状态N不能保证先手为0否则为0。
所以通过记录F[n]的值来减小计算的重复性并大大提高效率， 最后判断F[0]是否为0来得到结果。
代码：无
总结：该题难度有点大， 在各方面都有技巧。如数据结构的设计， 还有位运算都等。
该题有几个思想要注意：
1．采用数字位表达数列状态， 节约空间。
2．记录重复状态。
3．博弈的思想。
-----------------------------
题目：SOJ1173 Cog Wheels
分类：动态规划
讨论：此题属于动态规划的递推类的题
首先将不同size的Wheels可以生成的公因数存在一个数组中， 如序列 6， 12， 30， 24得到的序列为1，2，5。设定一个标记数组flag[n]
表示n是否能够被生成。
然后通过最小的这个序列，向后递推直到生成的数大于MAX为止。
然后把要求得的ratio放大直到其中一个数大于MAX为止， 如果放大到一个数的时候flag[n] = 1则有解
代码：生成序列的代码
while ( changed ) { changed = false; end = snum; for (i=beg; i<end; i++) { for (j=0; j<=i; j++){
sum = seq[i] * seq[j];if ( sum < MAX && flag[sum] == 0 )
{ changed = true; flag[sum] = 1; seq[snum++] = sum; } } } beg = end; }
总结：这道题初看可能会认为是道数学题，通过观察题目的本质其实发现是道动规题。
------------------------------
题目：SOJ1171 Area2
分类：复杂几何题
讨论：这道题题目首先暗示I, E, A之间有个公式， 从题目的输入中可以简单求出面积A, 和边上点数E, 该题就转换为求公式以得到I。
因为边上点所占的面积为：
面积 ＝ 点所占角度 / 360 * 边的长度
所以
题目中边所占面积为
多边形内角和 ＝ （ E – 2 ）* 180 然后乘以边长1得到
面积 ( E – 2 ) * 180 / 360 = ０.5 * ( E – 2 )
所以I所占的面积为
A – 0.5 * E + 1
又因为多边形内的边所占角度都为360度， 所以
I = ( A – 0.5 * E + 1 ) * 360 / 360
= A – 0.5 * E + 1
代码：无
总结：该题难， 特别是推公式部分需要大胆想象。
――――――――――――
题目：SOJ1169 Networking
分类：简单图论题
讨论：标准的求最小生成树的算法
代码：无
总结：无
――――――――――――－
题目：SOJ1168 Manager
分类：简单模拟
讨论：无
代码：无
总结：无
―――――――――――――
题目：SOJ1167 Game
分类：复杂模拟
讨论：需要仔细推出公试并且要细心观察关系
代码：无
总结：无
--------------------------
题目：SOJ1165 Boat
分类：简单动态规划
讨论：首先设计数据结构
struct Node
{ int money; bool flag[MAX]; };
代表在某天的一个可能的状态：
money : 状态所能够得到的钱
flag : 选择的client的情况
构建列表：
第N天
Node:可能状态1
Node:可能状态2
…
每遍历一个client时就从其deadline那天向前搜索，加入搜索的天的状态中， 并且要避免重复使用一个client(运用flag) 最后从最后一个deadline那天选出money最大的那个状态， 其money就为所求解。
代码：无
总结：比较标准的动规题。
-----------------------------
题目：SOJ1164
分类：复杂数学， 推理
讨论：这道题需要直接推出公式
代码：无
总结：无
------------------------------
题目：SOJ1163 Cash Machine
分类：简单动规
讨论：和1165相似， 构造数组F[M][N], 表示表达数M后第N个数还有几个可以用， 把可以生成的数向后递推， 最后查表即可。
代码： 无
总结：构造数组的方法奇特， 技巧性较强。
――――――――――――――――
题目：SOJ1159 Factorial
分类：简单数学， 推理
讨论：推出公式很重要
F( N ) = N / 5 + F( N / 5 )
代码：无
总结：做数学题关键在于能够细心推出公式求解。
―――――――――――――――――
题目：SOJ1158 Complete the sequence
分类：简单数学， 推理
讨论：逐步下降求解法推出后续数列
代码：无
总结：同上。
―――――――――――――――――
题目：SOJ1157 The Bulk
分类：简单几何题
讨论：无
代码：无
总结：关键在于理解题意。
―――――――――――――――
题目：SOJ1156 Complicated Expressions
分类：简单搜索
讨论：标准的表达式解析题
运用解析式
E --> I{+I} | I{-I} I --> F{*F} | F{/F} F --> T | (E)
递归搜索子表达式， 得到表达式树
然后遍历表达式得解
代码：无
总结：注意优先级的问题。
----------------------------------
题目：SOJ1154 Simple Arithmetics
分类：复杂的模拟题
讨论：无
代码：无
总结：恶心。
----------------------------------
题目：SOJ1153 Play on Words
分类：简单图论
讨论：将单词的关系图表达出来，然后根据欧拉图的判定条件来判定是否为欧拉图。注意这里可能出现多个子图， 需要每个图都判断一次。
代码：无
总结：注意欧拉图的判断条件。
--------------------------------
题目：SOJ1152 Lifting the Stone
分类：简单数学题
讨论：通过中心和重心公式来求得公式
代码：关键代码：
for (int i=2; i<N; i++) { scanf("%lf %lf", &dat[i][0], &dat[i][1]); area = 0.5 * (( dat[i][0] - dat[0][0] ) * ( dat[i-1][1] - dat[0][1] ) - ( dat[i-1][0] - dat[0][0] ) * ( dat[i][1] - dat[0][1] )); x0 = ( dat[i][0] + dat[0][0] + dat[i-1][0] ) / 3; y0 = ( dat[i][1] + dat[0][1] + dat[i-1][1] ) / 3; sum_x += x0 * area; sum_y += y0 * area; sum_area += area; } r_x = sum_x / sum_area; r_y = sum_y / sum_area;r_x = floor( r_x * 100 + 0.5 ) / 100;
r_y = floor( r_y * 100 + 0.5 ) / 100;
总结：注意结尾的四舍五入的写法。
-------------------------------
题目：SOJ1151 Piggy-Bank
分类：简单动规
讨论：用动规的生成方法产生出所要求的最小解
代码：无
总结：无
――――――――――――――――
题目：SOJ1150 Labyrinth
分类：复杂图论
讨论：这道题运用了一个图论的中的一个技巧：
首先从任意一点开始深度搜索最深的终点， 然后再用这个终点再深度搜索一遍，得到的最长的距离即为所求距离。
代码：无
总结：初看这道题会以为只是一道搜索题而不会把图论的知识结合起来， 这就
是该题的难点， 看来很有必要复习离散数学中的图论知识。
-------------------------
题目：SOJ1147 Equipment Box
分类：复杂几何
讨论：此题的关键在于能不能正确理解题意，该题可以将Box斜着放， 只要想到这点， 这道题可说难度减了一半。
设置方程求解。
代码：关键代码：
if ( Y >= B && X >= A )
return true; if ( X < A && Y < B ) return false; a1 = acos(Y / pow( pow(A,2) + pow(B,2), 0.5));a2 = atan(A / B);
if( X > A * cos(a1 + a2) + B * sin(a1 + a2)) return true; return false;
总结：对于几何题列方程， 可能性需要考虑周全， 如直线斜率除0等。
gmail.com
|