to be myself
分类： C/C++
2013-03-02 18:24:49
马上第五届校赛就要开始了，鸭梨大啊! 到现在才零零散散掌握些数据结构、算法的一些东西。总被其它的事打断，有的时间长了还真的都忘了。POJ去年持续一段时间，第二次开始从2011-3-6 到 2011-4-9的一段时间，今天写这个已经是2011-5-5，竟不知中间快一个月没做题了。怎么这么长时间啊，中间我都干什么去了。本来打算POJ到50题再搞个总结的，还差一点， 算是为后天的校赛热身吧。
POJ 1006 Biorhythms（中国剩余定理 最小公倍数）
此题关键还是要找一下规律
中国剩余定理的补充资料
已知m1、m2、m3是两两互质的正整数，求最小正整数x，使它被m1、m2、m3除所得余数分别为C1、C2、C3 。
孙子定理的思想便是先分别找出被其中数mi除余1而被另二数整除的数Mi(i=1，2，3)，则所求的数之一便是 C1M1+C2M2+C3M3；
若欲求的是最小的符合要求的数，则将上面的得数减去m1、m2、m3的整数倍(0，1，2，…)即可.
在古算题中，m1=3，m2=5，m3=7；C1=2，C2=3，C3=2；M1=70，M2=21，M3=15.
其中 ： M1=70=3×23+1=5×7×2；
M2=21=5×4+1=3×7×1；
M3=15=7×2+1=3×5×1；
而 C1M1+C2M2+C3M3=2×70+3×21+2×15=233
∵233>2×3×5×7=2×105，故所求最小数为 233-2×105=23
孙子定理可以推广到对任意n个数mi的情形，n≥2，n∈N，国外称此定理为“中国剩余定理”。
----------------------------------------------------------------------------
POJ 1007 DNA Sorting（QSORT 排序）
关键的排序代码，按结构体某数据给结构体排序。
顺便复习下qsort：
快排qsort函数应用大全
qsort函数应用大全(转)七种qsort排序方法
<本文中排序都是采用的从小到大排序>
一、对int类型数组排序
int num[100];
Sample:
int cmp ( const void *a , const void *b )
{
return *(int *)a - *(int *)b;
}
qsort(num,100,sizeof(num[0]),cmp);
二、对char类型数组排序（同int类型）
char word[100];
Sample:
int cmp( const void *a , const void *b )
{
return *(char *)a - *(int *)b;
}
qsort(word,100,sizeof(word[0]),cmp);
三、对double类型数组排序（特别要注意）
double in[100];
int cmp( const void *a , const void *b )
{
return *(double *)a > *(double *)b ? 1 : -1;
}
qsort(in,100,sizeof(in[0]),cmp)；
四、对结构体一级排序
struct In
{
double data;
int other;
}s[100]
//按照data的值从小到大将结构体排序,关于结构体内的排序关键数据data的类型可以很多种，参考上面的例子写
int cmp( const void *a ,const void *b)
{
return (*(In *)a)->data > (*(In *)b)->data ? 1 : -1;
}
qsort(s,100,sizeof(s[0]),cmp);
五、对结构体二级排序
struct In
{
int x;
int y;
}s[100];
//按照x从小到大排序，当x相等时按照y从大到小排序
int cmp( const void *a , const void *b )
{
struct In *c = (In *)a;
struct In *d = (In *)b;
if(c->x != d->x) return c->x - d->x;
else return d->y - c->y;
}
qsort(s,100,sizeof(s[0]),cmp);
六、对字符串进行排序
struct In
{
int data;
char str[100];
}s[100];
//按照结构体中字符串str的字典顺序排序
int cmp ( const void *a , const void *b )
{
return strcmp( (*(In *)a)->str , (*(In *)b)->str );
}
qsort(s,100,sizeof(s[0]),cmp);
七、计算几何中求凸包的cmp
int cmp(const void *a,const void *b) //重点cmp函数，把除了1点外的所有点，旋转角度排序
{
struct point *c=(point *)a;
struct point *d=(point *)b;
if( calc(*c,*d,p[1]) < 0) return 1;
else if( !calc(*c,*d,p[1]) && dis(c->x,c->y,p[1].x,p[1].y) < dis(d->x,d->y,p[1].x,p[1].y)) //如果在一条直线上，则把远的放在前面
return 1;
else return -1;
}
PS:
其中的qsort函数包含在
typedef struct record
{
int index;
int total;
} record;
int cmp(const void *a ,const void *b)
{
return (*(record *)a).total > (*(record *)b).total ? 1 : -1;
}
----------------------------------------------------------------------------
POJ 2159 Ancient Cipher QSORT（快排古代密码）
先QSORT一下dst串和src串
ABBCFEA（假设为dst） 变成 AABBCEF
CCGGHJB（假设为src） 变成 BCCGGHJ
然后
AABBCEF变成22111再次QSROT为11122
BCCGGHJ变成12211再次QSROT为11122
输出YES
----------------------------------------------------------------------------
poj 2739 Sum of Consecutive Prime Numbers（素数和）
为了节约时间，做了个1230个素数的表
然后从后往前减去相邻素数，找有多少种组合。
----------------------------------------------------------------------------
POJ 1083 Moving Tables（移桌子）
可将量纲缩小，偶数除以2，奇数除以2+1，注意s应该小于f。求同一时间，经过i的数，用count[i]计算, 将最大值放入time.
----------------------------------------------------------------------------
poj 2262 Goldbach's Conjecture（哥德巴赫猜想）
从2开始判断m是否为i和m-i的和，且i和m-i都是素数。
判断素数：
typedef unsigned int uint;
int IsPrime(uint a)
{
uint i;
if(1 == a)
{
return 0;
}
for(i=2;i*i<=a;i++)
{
if(0 == a % i)
{
return 0;
}
}
return 1;
}
----------------------------------------------------------------------------
poj 3006 Dirichlet's Theorem on Arithmetic Progressions（a+xd中，枚举x，找第n个素数）
a+xd中，枚举x，找第n个素数
还是关于素数问题
----------------------------------------------------------------------------
poj 1753 Flip Game (翻棋，队列+位运算)
利用XOR（异或）位运算来改变某数的某个二进制位：
num ^= (1 << x);
每次枚举改变状态后用循环队列保存，每次检查出队元素，符和全'b'或全'w'就输出step。
设一个状态记录数组used判重。
----------------------------------------------------------------------------
poj 2965 The Pilots Brothers' refrigerator (飞行员开冰箱, 队列+位运算+打表)
和poj1753状态改变类似，也需要记录状态判重。但也需要一个fa数组，记录上一步的步骤，以便达到成功后递归回溯到起点后输出步骤。
----------------------------------------------------------------------------
poj 1328 Radar Installation 快排+贪婪(雷达测小岛，快排+贪心)
找岛屿可被侦测到的极左和极右坐标。贪婪选择最右坐标作为比较点。下个岛屿的最左可被侦测坐标大于当前最右可被侦测坐标cur，则新增雷达，更新cur为下一个岛屿的最右可被侦测坐标，若下个岛屿的最右坐标小于当前最右可被侦测坐标 ，直只更新cur为下一个岛屿的最右可被侦测坐标。
----------------------------------------------------------------------------
POJ 2109 Power of Cryptography double精度(double精度，pow函数)
输入x，y。求x的多少次方为y，应该用高精度解决。
最终用库函数pow（y，1/x）解决。
----------------------------------------------------------------------------
解1：POJ 2586 Y2K Accounting Bug 贪心
尽可能的让亏损的月份共享，这样总的亏损就小，盈利大。用的是贪心的思想。注意的是用数组做不同的标记表示不同的意思。
----------------------------------------------------------------------------
解2：POJ 2586 Y2K Accounting Bug 枚举(贪心，枚举，月亏损)
"ssssdssssdss",
"sssddsssddss",
"ssdddssdddss",
"sddddsddddsd",
"dddddddddddd"
12个月也就上面五中情况，d表示亏损，s表示盈利。枚举之后求最大盈利（或者都亏损）。
----------------------------------------------------------------------------
poj 3295 Tautology 栈 KANCE pqrst 恒真式(栈，恒真式)
pqrst共有2^5=32种组合，需要依依枚举。将KANCE组成的表达式从最后一个字母开始想串首每次取一个字母和变量参与运算，并将结果立即入栈，当到达串首（表达式结束），查看栈内是否为1，即可判定是否为恒真式。
----------------------------------------------------------------------------
POJ 1068 Parencodings 括号匹配 模拟 规律(括号匹配，规律)
P数组表示每个数字所在处及其前面有多少个左括号。
W表示数字所在位置的右括号能和左边的第几个左括号匹配。
由P求W只需找到另一个数组a存储每个右括号前面有多少个左括号。
然后按照b数组中的下标递增，在a数组中找左括号匹配。移动的位数改变b数组，即为W。
----------------------------------------------------------------------------
poj 2632 Crashing Robots 模拟题(机器人指令crash)
纯模拟题，注意题目中的坐标方向与自己定义的数组的方向，方便正确的纠正机器人行动后的坐标。
----------------------------------------------------------------------------
poj 1573 Robot Motion 模拟 机器人(机器人指令step)
也是模拟题，设置移动偏移量，注意机器人越界。还必须用数组记录是否走过某坐标，以记录出现loop。当出现loop后要根据fa数组回到loop的起始点计算loop走过的步数最后输出。
----------------------------------------------------------------------------
poj 2996 Help Me with the Game 模拟 黑白棋(棋盘->黑白描述)
棋盘变描述语句。
注意自己定义数组和棋盘的方向问题，方便查找和算column和row。。我是按照数组争做表01234567, 76543210的顺序分别找white和black的。
----------------------------------------------------------------------------
POJ 2993 Emag eht htiw Em Pleh 模拟 逆2996题(逆2996，黑白描述->棋盘)
是2996的反面题：根据表述语句求棋盘。
个人觉得这个情况比2996稍稍复杂。还要考虑BLACK和WHITE哪个语句在前，它们是否没有棋子。其中还用到了memchr函数查找逗号，就可以找到前面的字母，其中P较特殊需注意。
----------------------------------------------------------------------------
至此有题解的题目就讨论完了，其中还有一些没题解的：
poj2255（树的遍历）,poj3094（字母加法，A为1，B为2等），poj1503（高精度加法），poj3299（公式输出TDH）
大概回顾了下自己的想法。题解写详细还是很有用的，方便大家也方便自己。不然，当自己回顾的时候，有些确实还要再次揣摩下呀。
预祝自己这次校赛能取得好成绩吧，再接再厉！！！！！
2011-05-05 19:33 发表于百度空间，今搬至CU。
