题(SCU SOJ)1049：这是一道典型的贪心算法题。依次放入尺寸为6*6,5*5,4*4,3*3,2*2,1*1的包，计算出剩余空格即可。
题(SCU SOJ)1073：对于每一格上的点共有八个方向可扩展。要求最少的移马步数，即是求每一对顶点之间的最短路径。使用Floyd算法可求得该带权有向图的每一对顶点之间的最短路径长度。主循环如下：
for(k=1;k<=64;k++)
{
for(i=1;i<=64;i++)
{
for(j=1;j<=64;j++)
{
if(knight[i][j]>knight[i][k]+knight[k][j])
knight[i][j]=knight[i][k]+knight[k][j];
}
}
}
题(SCU SOJ)1075：找出所有组的数据中没有出现在较小重量列中那个苹果，说明已没有比它更大的苹果存在。然后删去它所在的那组数据，继续按以上方法寻找次大的苹果。依次类推，得到结果。
题(SCU SOJ)1079：
思想：计算出休息0次的所有路程; 然后计算出在0次的基础上又跑一次--即休息1次的所有路程; 再计算出在1次的基础上又跑一次--即休息2次的所有路程......依次类推，直到找到要跑的路程。
方法：动态规划。如果使用搜索，则超时。
题(SCU SOJ)1092：根据题目给出的求解过程，设置四个数组,以保留在求解过程中的系数,可以模拟得到结果。
注意：1.通过while(p>n)p=p-n;不会改变p%n的值，但可以减少计算量。
2.在分解至某数与1相加的过程中，必须保证进行了偶数次的操作。
题(SCU SOJ)1093：先按从大到小顺序对船的长度进行排序，然后从大到小深度搜索。并设置一个bool变量，一旦搜索失败，则使其为false，回到上一级继续搜索。
题(SCU SOJ)1103：使用sscanf示例如下：
if(sscanf(str,"%d.%d.%d.%d%n",&a,&b,&c,&d,&n)==4
&& n==strlen(str)
&& a>=0 && a<=255
&& b>=0 && b<=255
&& c>=0 && c<=255
&& d>=0 && d<=255)
但是不能识别整数中有前导零存在，如001这种情况。
题(SCU SOJ)1106：本题使用深度搜索，剪枝如下：在到达每一处时记下其被淋湿的值wet，当再次来到此处时，如果新的wet大于等于原来的值时，则无需进行扩展而返回。
题(SCU SOJ)1133：小球从球桌的中点出发。其在水平方向碰撞的次数乘以桌宽，即为它在垂直方向运动的总距离。同理可知它在水平方向的总距离。最终得到角度值和速度值。
小结：const double pi=acos(-1);
题(SCU SOJ)1134：采取分治的思想。
price[G][L]=price[G-1][L]+price[G-1][L-1]+1;
如上式，把price[G][L]分作两个部分，分治求解，并加上分点1。
题(SCU SOJ)1135：求阶层的除法。如果先乘后除，结果可能越界得到错误答案。
思想：要求p!s!(r-s)!/q!(p-q)!r!, 分为三个部份相除，即p!/q!,s!/r!,(r-s)!/(p-q)!,分别计算其值。直到p-q或r-s已经减为1。
最后补充另外两项:(r-s)!/r!或者p!/(p-q)!剩余的乘积。
题(SCU SOJ)1136：因式分解程序如下：
void YSFJ(_int64 x)
{
_int64 i;
pnum=0;
i=2;
while( x>1 && i*i<=x )
{
if(x%i==0)
{
pnum++;
p[pnum]=i;
x=x/i;
while( x%i==0 )
{
pnum++;
p[pnum]=i;
x=x/i;
}
}
if(i==2)i=i+1;
else i=i+2;
}
if(x>1)
{
pnum++;
p[pnum]=x;
}
}
题(SCU SOJ)1140：本题需要输入字符串，字符串中含有回车。可将字符串作为一个个字符，单个输入，遇回车跳过。另，静态数组可以避免内存泄漏。
题(SCU SOJ)1142：题目直接搜索N即可。有两点可注意：
1. “N was set to some integer number from 1 to 10000 inclusive and array A was filled with a nondescending integer sequence.”
此处说明 1<=N<=10000,且A数组是一个从0开始的整数数组。
2. 在子程序中可能出现无返回值的分支，在程序编译给出警告后应当修正。
题(SCU SOJ)1147：首先排除三种不可能的情况。对于第四种情况，令box以90度开始旋转，采用二分搜索法，寻找一个角度可以使box置于tile内。如果两个边界之差近似为0了，则说明没有这样的角度可以放下box。
题(SCU SOJ)1150：The labyrinth is designed in such a way that there is exactly one path between any two free blocks.题目要求迷宫中两个端点的距离的最大值。
结论：从一点遍历到最远处的一点必定是两个端点中的一点，因此经过两次深度搜索，可以得解。
注意：1、表示四个方向
int dir[2][4]={{0,1,-1,0},{1,0,0,-1}};
for(k=0;k<4;k++)
{
a=aa+dir[0][k];
b=bb+dir[1][k];
}
2、深度搜索中传递参数L,以确定每次搜索的深度。
3、在输入二维字符数组时，每行结束应输入回车字符。否则回车字符会被作为有效字符读入。
题(SCU SOJ)1151：使重量从1开始递增至所求值。递推地求得最后解。对于每一种重量，求出所需钱币价值的最小值。该最小值可能来自于某一种钱币的面值，也可能来自于由小于该重量的钱币的最小面值加上某一种钱币的面值所得。
题(SCU SOJ)1152：题目要求多边形的重心。
本题的多边形各边不会交叉，且多边形面积不为0。同时多边形可能不为凸边形。
1.先求多边形的面积：分解为求解三角形的面积。先输入得到两个固定点，然后再逐个输入一点，作为一个三角形的第三个顶点，从而由公式求得三角形面积。
area=0.5*( (p1.x-p0.x)*(p2.y-p0.y)-(p1.y-p0.y)*(p2.x-p0.x) );
2.多边形的面积等于对各个三角形重心与面积的乘积求和，再除以该多边形面积。
3.本题要求two digits after the decimal point (0.005 rounds up to 0.01).
程序可以如下：
center.x=floor(center.x*100+0.5)/100;
对于floor功能的描述如下：
Returns the largest integer less than or equal to the given numeric expression.
题(SCU SOJ)1153：可以看作是求一个最多含有26个结点（26个字母）的有向欧拉图或欧拉道路。
定理：连通有向图G含有有向欧拉道路当且仅当除最多两个结点外，其余每个结点的入度等于其出度，而这两个结点中一个结点的入度比其出度多1，另一结点的入度比其出度少1.
算法：1.将图G看作无向图，判断其是否连通。
2.判断其点的度数是否满足定理的条件。
题(SCU SOJ)1156：根据题目给出的数字序列，求出相邻数字的差，如果这些差组成的新的数列不为常数数列，则求解新的数列中相邻数字的差，直到该差满足上述条件为止。
然后在常数数列末尾增加相同的常数，对相邻数字求和，即执行上述操作的逆操作,经过与求差相同次数的求和后，可以得到需要的新数列。
题(SCU SOJ)1163：建立一个二维数组，dd[10][100000]；dd[i][j]表示得到i元的现金时，第j种币的数量。采用动态规划算法。注意在每一次得到i元的现金后，应将各个币的数量进行重新计算。
题(SCU SOJ)1165：每输入一组新的选择，求出这种选择的可能开始时间。对于每一个时间，搜索之前以该时间作为结束时间的各种选择，得到这些选择中最大的money值，并求与新的选择的money和。最后在各个和中求得最大值，即为最大利益值。
题(SCU SOJ)1171：这是一道关于网格上的多边形的求解问题,且多边形的各边不相交。
设in为多边形内的点数，out为多边形边上的点数，area为多边形的面积，则有公式：
in=int(area+1-0.5*out);
题(SCU SOJ)1176：这是一道化简后的旅行商人问题。路线呈矩形，且道路之间的间隔相等。分为两种情况讨论：行数或列数为偶数；行数和列数均为奇数。
题(SCU SOJ)1177：某一前缀的权值等于包括它的各个单词的权值之和。
思路：查找到与按键区配的前缀后搜索所有单词，得到它的权值。重复上述操作，得到权值最大的前缀，即为所求结果。
注意：在每行读入各个字符时，使用scanf("\n%c",&cc);这样可以避免读入回车。
题(SCU SOJ)1180及1087: 这是一道求最小战略的问题。其主要思想是，先先序遍历生成树，然后从后往前确定战略点。需要一个保存父亲结点的数组、一个先序遍历树组、一个是否已经访问的数组。
注意，这是边的覆盖，不是点的覆盖。需考虑特殊情况，及一个点和无点的时候。
题(SCU SOJ)1189：这是一道简单的密码转换题。注意：
1.二维表的建立：
char key[30][5]={{".-"},{"-..."},{"-.-."},{"-.."},{"."},{"..-."},......};
2.在使用函数 strcpy,strcmp 等时，必须是对字符串操作。如果之前是字符的单个输入，则应在字符输入结束时加上结束符号。
题(SCU SOJ)1193:题目要求是“The input will consist of several lines of exactly 256 hex characters. The end of the input is indicated by a memory state that has a stop instruction (an "8") at address 00.”
我使用以下输出，超时：
for(i=0;i<256;i++)
{
if(i!=0 && i%64==0)scanf("\n");
scanf("%c",&mem[i]);
}
改为：gets(mem);
即不能单个字符输入，而应该一次性读入字符串。
题(SCU SOJ)1194：这是一道类似大数乘法的题。但由于乘数较小(<=60),可以不分解乘数，直接与被乘数的每一位相乘，得到结果。
题(SCU SOJ)1195：这是求解二维的最大子矩阵和的问题。采用动规算法。
求二维数组连续的n行和(n=1,2,3,...)，然后对于和，按照求一维的最大子段和的算法求解。从而达到降维的目的。
gmail.com
|