习题选讲习题选讲2011-10-202第三章第三章n1152 1153 马周游马周游n1093 Air Expressn1134 积木分发积木分发n1140 国王的遗产国王的遗产n1438 Shopaholicn1028 Hanoi Tower Sequencen1029 Rabbitn1381 a*bn1206 1012 Stacking Cylindersn1172 Queens, Knights and Pawnsn1034 Forest2011-10-203第三章第三章n1193 Up the Stairsn1004 I Conduit!n1017 Rate of Returnn1059 Exocenter of a Triann1003 Hit or Missn1018 A Card Trickn1052 Candy Sharing Gamen1041 Pushing Boxesn1211 商人的宣传商人的宣传n1071 Floorsn1082 MANAGER2011-10-2041152 1153 马周游马周游n题目大意题目大意:n一个有限大小的棋盘一个有限大小的棋盘上有一只马，马只能上有一只马，马只能按日字方式走，如图按日字方式走，如图所示。所示。n给出初始时马的位置，给出初始时马的位置，找出一条马移动的路找出一条马移动的路线，经过所有格子各线，经过所有格子各一次。一次。2011-10-2051152 1153 马周游马周游n解题思路：解题思路：n枚举马能走的所有路径，直至找到一条完枚举马能走的所有路径，直至找到一条完成周游的路径；成周游的路径；n递归，回溯。递归，回溯。2011-10-2061152 1153 马周游马周游nbool solve(int x, int y, int lev) nroutelev = x * N + y;nif (lev = M * N - 1) print_route();return true;nvisitedxy = true;ngrid grids8;nint n=get_grid(grids,x,y);nfor (i=0; in; i+) n if (solve(gridsi.x, gridsi.y, lev+1) n return true;nvisitedxy = false;nreturn false;n2011-10-2071152 1153 马周游马周游nint get_grid(grid grids, int x,int y) n int n=0;nfor (int i=0; i=0&yy=0&xxM&yyN&!visitedxxyy) ngridsn.x = xx;ngridsn.y = yy;nn+;n nnreturn n;n2011-10-2081152 1153 马周游马周游n以上程序速度过慢。以上程序速度过慢。n优化：改变搜索顺序。优化：改变搜索顺序。先搜索可行格较少的格子。先搜索可行格较少的格子。其他顺序。其他顺序。n修改修改get_grid()函数。函数。2011-10-2091152 1153 马周游马周游nint get_grid(grid grids, int x,int y) nint n=0;nfor (int i=0; i=0&yy=0&xxM&yyN&!visitedxxyy) ngridsn.x = xx; gridsn.y = yy;ngridsn.count = get_count(xx, yy);nn+;nnnsort(grids,grids+n);nreturn n;n2011-10-20101152 1153 马周游马周游nbool operator (const grid &a, const grid &b) nreturn a.count b.count;nnint get_count(int x, int y) nint i, xx, yy, count = 0;nfor (i=0; i=0&yy=0&xxM&yyN&!visitedxxyy) n count+;nnreturn count;n2011-10-20111093 Air Expressn题目大意：题目大意：n给出给出4个重量区间以及在每个区间的单位重个重量区间以及在每个区间的单位重量运输价格，再给出一个背包重量，可以量运输价格，再给出一个背包重量，可以往背包里添加任意多重量，求最低的总运往背包里添加任意多重量，求最低的总运输价格。输价格。n所有数字不超过所有数字不超过1000。2011-10-20121093 Air Expressn解题思路：解题思路：n最小运输价格必定出现在：最小运输价格必定出现在：1、不添加任何重量；、不添加任何重量；2、添加重量刚好到达某个区间的下界；、添加重量刚好到达某个区间的下界；n因此枚举这些情况，并求出其中的最小值因此枚举这些情况，并求出其中的最小值即是答案。即是答案。2011-10-20131093 Air Expressnint cal(int weight) nint price=INF;nfor (int i=0;i=li&weight=ri) nif (weigth*rateiprice)nprice=weight*ratei;n else if (weightli) nif (li*rateiprice)nprice=li*ratei;nnnreturn price;n2011-10-20141134 积木分发积木分发n题目大意：题目大意：n一个人手上有一个人手上有s块积木，一共有块积木，一共有n个小朋友，个小朋友，每个小朋友手上有每个小朋友手上有a块积木，还需要块积木，还需要b块积块积木才能完成。当一个小朋友的积木完成后木才能完成。当一个小朋友的积木完成后则全部回收利用。问是否所有小朋友都能则全部回收利用。问是否所有小朋友都能完成。完成。ns=1000000,n=10000,a,b=1092011-10-20151134 积木分发积木分发n解题思路：解题思路：n尽量先满足需求少的小朋友，以回收得到尽量先满足需求少的小朋友，以回收得到更多积木；更多积木；n因此按小朋友的需求排序，贪心求解。因此按小朋友的需求排序，贪心求解。2011-10-20161134 积木分发积木分发n若两个小朋友分别已有和需求为若两个小朋友分别已有和需求为a1,b1和和a2,b2，且且a1=a1 & s+b1=a2，即，即s = max(a1, a2-b1);先给第二个小朋友则先给第二个小朋友则s应该满足应该满足s=a2 & s+b2=a1，即，即s=max(a2,a1-b2)=a2。因为。因为a2max(a1,a2-b1)，所以先给第二个小朋友的要，所以先给第二个小朋友的要求求s更多，因此应先给第一个小朋友。更多，因此应先给第一个小朋友。2011-10-20171134 积木分发积木分发nstruct childn int a,b; ;nbool operator (const child &x,cont child &y)n return x.ay.a; nbool check(child children,int s,int n) nsort(children, children+n);nfor (int i=0;in;i+) nif (schildreni.a)nreturn false;ns+=childreni.b;nnreturn true;n2011-10-20181140 国王的遗产国王的遗产nn块金块组成一棵树，总共块金块组成一棵树，总共k个人，每个人个人，每个人选择树里的一条边去掉，得到不超过当前选择树里的一条边去掉，得到不超过当前金块的一半的部分，并且分割使自己得到金块的一半的部分，并且分割使自己得到尽量多的金块，如果相等则使金块组编号尽量多的金块，如果相等则使金块组编号最小。输出每个人得到的金块数量。最小。输出每个人得到的金块数量。nn=30000,kb.count;nelse if (a.type=ans:withroot) nif (b.type=ans:withoutroot)nreturn true;nelsenreturn a.minb.min;n else nif (b.type=ans:withroot)nreturn false;nelsenreturn a.minb.min;nn2011-10-20221140 国王的遗产国王的遗产nvector cal(int n,int k) nint x=1,total=n,temp;nvector ret;nfor (;k1;k-) nbest.count=-1;nx=predfs(x,-1); dfs(x,-1,temp);nerase(edgebest.x,best.y);nerase(edgebest.y,best.x);nif (best.type=ans:withroot) x=best.x;ntotal-=best.count;nret.push_back(best.count);nnret.push_back(total);nreturn ret;n2011-10-20231140 国王的遗产国王的遗产nint predfs(int cur,int parent) nint min=cur;nfor (int i=0;iedgecur.size();i+) nif (edgecuri=parent)ncontinue;nint temp=predfs(edgecuri,cur);nif (tempmin)nmin=temp;nnreturn min;n2011-10-20241140 国王的遗产国王的遗产nint dfs(int cur,int parent,int &low) nint subtree=1,templow=0;nlow=cur;nfor (int i=0;iedgecur.size();i+) nif (edgecuri=parent)ncontinue;nsubtree+=dfs(edgecuri,cur,templow);nif (templowlow)nlow=templow;nntempans.x=cur;ntempans.y=parent;ntempans.min=low;n/ 以上找到当前节点与父节点的边的信息以上找到当前节点与父节点的边的信息2011-10-20251140 国王的遗产国王的遗产n/ 以下更新答案以下更新答案nif (subtree=total-subtree) ntempans.count=subtree;ntempans.type=ans:withoutroot;nif (better(tempans,best)nbest=tempans;nnif (total-subtree=subtree&subtree!=total) ntempans.count=total-subtree;ntempans.type=ans:withroot;nif (better(tempans,best)nbest=tempans;nnreturn subtree;n2011-10-20261438 Shopaholicn题目大意：题目大意：n买东西每买三件东西则最便宜的一件免费。买东西每买三件东西则最便宜的一件免费。给出给出n个需要买的东西的价格，问最多能免个需要买的东西的价格，问最多能免费多少？费多少？nn=0;i-=3)ns+=pricei;2011-10-20281028 Hanoi Tower Sequencen题目大意：题目大意：n定义汉诺塔，共有三个柱子和很多的大小定义汉诺塔，共有三个柱子和很多的大小两两不同的盘子放在一个柱子上，要求把两两不同的盘子放在一个柱子上，要求把它们移到另一个柱子上，每次只能移动一它们移到另一个柱子上，每次只能移动一个放在柱子最顶端的盘子，并且每次移动个放在柱子最顶端的盘子，并且每次移动后需保证较小的盘子在较大的盘子上面。后需保证较小的盘子在较大的盘子上面。给出步数给出步数p，求第，求第p步移动的盘子的大小。步移动的盘子的大小。np1)个盘子需要个盘子需要f(k)=f(k-1)+1+f(k-1)步。步。n即得到即得到f(k)=2k-1。因此第。因此第2k步移动的是步移动的是k+1个个盘子。在移动第盘子。在移动第k+1个盘子后，左右对移地移动个盘子后，左右对移地移动k个盘子。个盘子。2011-10-20301028 Hanoi Tower Sequencen把把p化成二进制数，假设现在化成二进制数，假设现在p里有超过里有超过1个个位为位为1，设最高位为，设最高位为k，则在，则在2k步前和步前和2k步后对称，因此第步后对称，因此第p步移的盘子与第步移的盘子与第p-2k步移的盘子一样。步移的盘子一样。n直到直到p里只有里只有1个位为个位为1，设此时，设此时p=2m，则，则此步移动的是第此步移动的是第m+1个盘子。个盘子。n因此题目转化成二进制数因此题目转化成二进制数p，从低位起连续，从低位起连续0的位数，加的位数，加1，为答案。，为答案。2011-10-20311028 Hanoi Tower Sequencenint cal(int a,int n) nint cnt=1;nwhile (an-1%2=0) ncnt+;nfor (int i=0,temp=0;in;i+) ntemp=temp*10+ai;nai=temp/2;ntemp%=2;nnnreturn cnt;n2011-10-20321029 Rabbitn题目大意：题目大意：n开始有一对大兔子。每对大兔子每个月产开始有一对大兔子。每对大兔子每个月产生一对小兔子。每对小兔子经过生一对小兔子。每对小兔子经过m个月变成个月变成大兔子。问经过大兔子。问经过d个月后有多少兔子。个月后有多少兔子。n1=m=10, 1=d=1002011-10-20331029 Rabbitn解题思路：解题思路：n思考，当思考，当m=1时，每个月的兔子数量是上个月的时，每个月的兔子数量是上个月的两倍，经过两倍，经过d=100个月兔子将有个月兔子将有2100个兔子，个兔子，超过超过64位整数表示的范围，因此要用高精度。位整数表示的范围，因此要用高精度。n每个月的兔子数量，为上一个月的兔子数量，加每个月的兔子数量，为上一个月的兔子数量，加上上一个月的大兔子数量，即上上一个月的大兔子数量，即m个月前的兔子数个月前的兔子数量，即量，即an=an-1+an-m。n注意当注意当n-m为负数时，也有初始时存大的一对大为负数时，也有初始时存大的一对大兔子。兔子。2011-10-20341029 Rabbitnstruct BigInteger n int x100;n BigInteger()n BigInteger(int a) memset(x,0,sizeof(x); x0=a; n BigInteger operator +(const BigInteger &that) const n BigInteger c(0);n for (int i=0;ixi+that.xi;n c.xi+1+=c.xi/10; c.xi%=10;n n return c;n n;2011-10-20351029 Rabbitnint cal(int m,int d) n a0=BigInteger(1);n for (int i=1;i=d;i+) n if (im)n ai=ai-1+BigInteger(1);n elsen ai=ai-1+ai-m;n n2011-10-20361381 a*bn题目大意：题目大意：n给出两个整数给出两个整数a和和b，求，求a*b的结果。（题目的结果。（题目描述有误，可能有零）描述有误，可能有零）n0=a=10100,0=b=10000。2011-10-20371381 a*bn解题思路：解题思路：n高精度，模拟竖式乘法。高精度，模拟竖式乘法。n从低位向高位逐位计算。从低位向高位逐位计算。n输出时注意结果为输出时注意结果为0的情况。的情况。2011-10-20381381 a*bnstruct BigInteger n int x110;n BigInteger(int a) memset(x,0,sizeof(x); x0=a; n BigInteger operator *(int b) const n BigInteger c(0);n for (int i=0;i110;i+) n c.xi+=xi*b;n c.xi+1+=c.xi/10;n c.xi%=10;n n return c;n n;2011-10-20391206 1012 Stacking Cylindersn题目大意：题目大意：n如图所示，给出最底如图所示，给出最底层的层的n个球的位置，求个球的位置，求最顶层的球的位置。最顶层的球的位置。n1=n=102011-10-20401206 1012 Stacking Cylindersn解题思路：解题思路：n关键点在于已知两个圆的圆心坐标，求放关键点在于已知两个圆的圆心坐标，求放在这两个圆上的圆的圆心坐标。在这两个圆上的圆的圆心坐标。n向量向量+勾股定理。勾股定理。2011-10-20411206 1012 Stacking Cylindersnstruct point ndouble x,y;n;nbool operator (point a,point b) nreturn a.x=0;i-)nfor (int j=0;j=i;j+)naj=cal(aj,aj+1);nreturn a0;n2011-10-20421206 1012 Stacking Cylindersnpoint cal(point a,point b) npoint c;ndouble x1,y1,x2,y2,temp;nx1=(b.x-a.x)/2;ny1=(b.y-a.y)/2;ntemp=x1*x1+y1*y1;ntemp=sqrt(4-temp)/sqrt(temp);nx2=-y1*temp;ny2=x1*temp;nc.x=a.x+x1+x2;nc.y=a.y+y1+y2;nreturn c;n2011-10-20431172 Queens, Knights and Pawnsn题目大意：题目大意：n给出棋盘大小，给出每个后、马和兵的位给出棋盘大小，给出每个后、马和兵的位置，求棋盘上有多个个没被占领的格子不置，求棋盘上有多个个没被占领的格子不会受到后也不会受到马的攻击。会受到后也不会受到马的攻击。n棋盘大小最多为棋盘大小最多为1000*1000，每种棋子最多，每种棋子最多100个。个。2011-10-20441172 Queens, Knights and Pawnsn解题思路：解题思路：n用二维数组表示一个棋盘，标记每个棋子用二维数组表示一个棋盘，标记每个棋子的位置，再标记每个棋子能攻击的位置，的位置，再标记每个棋子能攻击的位置，最后计算有多少个位置不会被攻击。最后计算有多少个位置不会被攻击。2011-10-20451172 Queens, Knights and Pawnsnenum grid_state empty,occupied,attacked;ngrid_state grid10011001;nint cal(vector q, vector k, vector p) nnmemset(grid,0,sizeof(grid);noccupy(q); occupy(k); occupy(p);nattackQ(q); attackK(k);nint s=0;nfor (int i=1;i=row;i+)nfor (int j=1&p.x=1&p.y=col)nreturn gridp.xp.y!=occupied;nreturn false;nnvoid occupy(vector v) nfor (int i=0;iv.size();i+)ngridvi.xvi.y=occupied;n2011-10-20471172 Queens, Knights and Pawnsnint dQ82=1,0,1,-1,0,-1,-1,-1,-1,0,-1,1,0,1,1,1;nvoid attackQ(vector q) n for (int i=0;iq.size();i+)n for (int dir=0;dir8;dir+) n point temp(qi.x+dQdir0,qi.y+dQdir1);n while (in_board_and_unoccupied(temp) n gridtemp.xtemp.y=attacked;n temp=point(temp.x+dQdir0,temp.y+dQdir1;n n n2011-10-20481172 Queens, Knights and Pawnsnint dK82=1,2,1,-2,2,-1,-2,-1,-1,-2,-1,2,-2,1,2,1;nvoid attackK(vector k) n for (int i=0;ik.size();i+)n for (int dir=0;dir8;dir+) n point temp(ki.x+dKdir0,ki.y+dKdir1);n if (in_board_and_unoccupied(temp)n gridtemp.xtemp.y=attacked;n n2011-10-20491034 Forestn题目大意：题目大意：n给出给出n个节点和个节点和m条有向边，判断是否组成条有向边，判断是否组成森林，如果是则求出它的最大深度和最大森林，如果是则求出它的最大深度和最大宽度。宽度。n所有数不超过所有数不超过1002011-10-20501034 Forestn解题思路：解题思路：n先判断是否为森林：先判断是否为森林：没有一个节点有两条入边，直接统计所有节点没有一个节点有两条入边，直接统计所有节点的入度；的入度；没有环，求图的闭包。没有环，求图的闭包。n再求解：再求解：枚举所有根，枚举所有根，dfs得到最深节点和每个深度的得到最深节点和每个深度的节点数。节点数。2011-10-20511034 Forestnbool is_forest(int n) nbool closure101101;nfor (i=1;i=n;i+) nfor (j=1,cnti=0;j1) return false;nnmemcpy(closure,edge,sizeof(edge);nfor (i=1;i=n;i+) for (j=1;j=n;j+) for (k=1;k=n;k+)nif (closureki&closureij)nclosurekj=true;nfor (i=1;i=n;i+) if (closureii) return false;nreturn true;n2011-10-20521034 Forestnint width101;nvoid dfs(int k,int lev,int n) nwidthlev+;nfor (int i=1;i=n;i+) if (edgeki)ndfs(i,lev+1,n);nnvoid cal(int n) nfor (int i=1;i=n;i+) if (cnti=0)ndfs(i,0,n);n2011-10-20531193 Up the Stairsn题目大意：题目大意：nN个人在个人在F层之间搬箱子，开始时每个人在某层楼层之间搬箱子，开始时每个人在某层楼上，有些手上已有箱子有些没有。在第上，有些手上已有箱子有些没有。在第0层上还有层上还有B个箱子。拿着箱子的人向上走，没拿箱子的向个箱子。拿着箱子的人向上走，没拿箱子的向下走，当两个相遇时拿着箱子的人把箱子交给没下走，当两个相遇时拿着箱子的人把箱子交给没箱子的人，互换方向继续。走到箱子的人，互换方向继续。走到F层的人把箱子放层的人把箱子放下，走到下，走到0层的人拿起箱子。问经过多少时间所有层的人拿起箱子。问经过多少时间所有箱子都在箱子都在F层。层。n1=N,F=1000,1=B=10000002011-10-20541193 Up the Stairsn解题思路：解题思路：n两个人交换箱子互换方向，相当于没有交换。两个人交换箱子互换方向，相当于没有交换。n当经过当经过2F时间后，所有人的状态没有改变，时间后，所有人的状态没有改变，0层层的其中的其中N个箱子搬到了个箱子搬到了F层，因此先把层，因此先把B对对N取模。取模。n求出每个人从当前状态把求出每个人从当前状态把0层的一个箱子搬到层的一个箱子搬到F层层需要的时间，排序，需要的时间，排序，B对对N取模的余数就由最快的取模的余数就由最快的部分人来搬。部分人来搬。2011-10-20551193 Up the Stairsnint cal() nfor (i=0;in;i+) nif (bi=0) tii=fi+F;nelse tii=3*F-fi;nnsort(ti,ti+N);nint s=B/N*2*F;nB%=N;nif (B=0) nB+=N;ns-=2*F;nns+=tiB-1;nreturn s;n2011-10-20561004 I Conduit!n题目大意：题目大意：n一个二维坐标平面上有一个二维坐标平面上有n条边，如果两条边条边，如果两条边有重叠部分，则可以合并成一条边。问合有重叠部分，则可以合并成一条边。问合并后的边的数量。并后的边的数量。nn=10000，坐标范围为，坐标范围为0.0, 1000.02011-10-20571004 I Conduit!n解题思路：解题思路：n对平面上所有线段排序，保证在同一直线上的线对平面上所有线段排序，保证在同一直线上的线段会集中在一段区间内，并且它们按照从直线的段会集中在一段区间内，并且它们按照从直线的一个方向到另一个方向排序。一个方向到另一个方向排序。n线段：所在直线为线段：所在直线为y=kx+b或或x=b，分情况讨论。，分情况讨论。n排序后判断在同一直线上的线段哪些有重叠部分，排序后判断在同一直线上的线段哪些有重叠部分，一个线段的结束位置在另一个线段的起始位置之一个线段的结束位置在另一个线段的起始位置之前，则它们有重叠。前，则它们有重叠。2011-10-20581004 I Conduit!n#define INF1e+15n#define EPS1e-7ninline int dcmp( double x, double y )nnif ( x - y EPS ) return 1 ;nreturn 0;n2011-10-20591004 I Conduit!nstruct Tline n double k, b, pstart, pend;n Tline toline (double x1, double y1, double x2, double y2) n if ( dcmp ( x1, x2 ) = 0 ) n k = INF, b = x1;n pstart = min ( y1, y2 ) ;n pend = max ( y1, y2 ) ;n else n k = ( y2 - y1 ) / ( x2 - x1 ), b = y1 - k * x1 ; n pstart = min ( x1, x2 ) ;n pend = max ( x1, x2 ) ;n n n;2011-10-20601004 I Conduit!nbool line_cmp ( const Tline& x, const Tline& y )nnif (dcmp(x.k, y.k) != 0)nreturn dcmp(x.k, y.k) 0;nif (dcmp(x.b, y.b) != 0)nreturn dcmp(x.b, y.b) 0;nreturn dcmp(x.pstart, y.pstart) 0;n2011-10-20611004 I Conduit!nint cal() n sort(lines, lines + n, line_cmp);n int i, ans = n;n double maxreached = lines0.pend;n for (i = 1; i n; i +)n if (dcmp(linesi.k, linesi-1.k) = 0n & dcmp(linesi.b, linesi-1.b) = 0)n n if (dcmp(linesi.pstart, maxreached) = 0) ans -;n maxreached = max( maxreached, linesi.pend );n else n maxreached = linesi.pend;n n return ans;n2011-10-20621017 Rate of Returnn题目大意：题目大意：n给出一个人在某些月份的开始时增加的投资额，给出一个人在某些月份的开始时增加的投资额，并给出在某个月份结束时本金和利润的总和。每并给出在某个月份结束时本金和利润的总和。每个月的利润率是固定的。每个月增加的利润会自个月的利润率是固定的。每个月增加的利润会自动加入投资额。求利润率。利润率在动加入投资额。求利润率。利润率在0,1之间。之间。n例如例如1月和月和3月开始时各投资月开始时各投资100元，元，4月底共得到月底共得到210元，设利润率为元，设利润率为x，则有方程：，则有方程：n100*(1+x)4 + 100*(1+x)2 = 2102011-10-20631017 Rate of Returnn解题思路：解题思路：n当利润率在当利润率在0,1之间，假设投资额和时间之间，假设投资额和时间不变，则利润率越高，最后的本金和利润不变，则利润率越高，最后的本金和利润总和越大。总和越大。n因此对利润率进行二分查找，检查在假设因此对利润率进行二分查找，检查在假设的利润率下，比较最后的本金和利润总和的利润率下，比较最后的本金和利润总和与实际值，调整二分上下界，直到达到某与实际值，调整二分上下界，直到达到某个精度。个精度。2011-10-20641017 Rate of Returnndouble find(double left,double right,int m,double x)nndouble center,s=0;ncenter=(left+right)/2;nif (right-left=0.000000005)nreturn center;nfor (int i=1;i=m;i+)ns+=ai*pow(1.0+center,m+1-i);nif (sx)nreturn find(center,right,m,x);nelsenreturn find(left,center,m,x);n2011-10-20651059 Exocenter of a Triann题目大意：题目大意：n给出三角形给出三角形ABC三点坐标，三点坐标，如图所示，作正方形如图所示，作正方形ABDE，正方形，正方形BCHJ，正方形正方形CAGF，L为为DG中中点，点，M为为EJ中点，中点，N为为FH中点，直线中点，直线LA，MB，NC交于同一点交于同一点O，求点，求点O的的坐标。坐标。2011-10-20661059 Exocenter of a Triann解题思路：解题思路：n按照题意求出所有点的坐标。按照题意求出所有点的坐标。n需要的函数：向量旋转，两点中点，直线需要的函数：向量旋转，两点中点，直线相交。相交。n辅助函数：向量叉积。辅助函数：向量叉积。2011-10-20671059 Exocenter of a Triann向量叉积的意义：两个向量向量叉积的意义：两个向量u1和和u2，若叉积小于，若叉积小于0，表示，表示u1在在u2逆时针方向，叉积为逆时针方向，叉积为0表示共线，表示共线，叉积大于叉积大于0表示表示u1在在u2顺时针方向。顺时针方向。ndouble crossProduct(const Point& u1, const Point& u2) n return u1.x * u2.y - u1.y * u2.x;n2011-10-20681059 Exocenter of a Triann向量旋转：把向量分解成平行于向量旋转：把向量分解成平行于x坐标轴和坐标轴和y坐标坐标轴的向量，再分别旋转，最合把旋转结果合并。轴的向量，再分别旋转，最合把旋转结果合并。nPoint rotate(const Point& v, double angle) n Point res;n res.x = p.x * cos(angle) - p.y * sin(angle);n res.y = p.x * sin(angle) + p.y * cos(angle);n return res;n2011-10-20691059 Exocenter of a Triann两点中点：两点中点：x和和y坐标的平均值。坐标的平均值。nPoint middle(const Point &a,const Point &b)nnPoint c;nc.x=(a.x+b.x)/2.0;nc.y=(a.y+b.y)/2.0;nreturn c;n2011-10-20701059 Exocenter of a Triann直线相交：把直线用直线相交：把直线用y=kx+b的形式表示，再解方程组。的形式表示，再解方程组。n分为斜率存在和不存在讨论。分为斜率存在和不存在讨论。nPoint intersection(const Point &p1,const Point &p2,const Point &p3,const Point &p4) nPoint o;nif (fabs(p1.x-p2.x)1e-6)no=withoutslope(p1.x,p3,p4);nelse if (fabs(p3.x-p4.x)1e-6)no=withoutslope(p3.x,p1,p2);nelseno=withslope(p1,p2,p3,p4);nreturn o;n2011-10-20711059 Exocenter of a TriannPoint withoutslope(double x,const Point& p1, const Point& p2) nPoint o;ndouble k=(p1.y-p2.y)/(p1.x-p2.x);ndouble b=p1.y-p1.x*k;no.x=x;no.y=k*x+b;nreturn o;n2011-10-20721059 Exocenter of a TriannPoint withslope(const Point& p1, const Point& p2, const Point& p3, const Point& p4) nPoint o;ndouble k1=(p1.y-p2.y)/(p1.x-p2.x);ndouble b1=p1.y-p1.x*k1;ndouble k2=(p3.y-p4.y)/(p3.x-p4.x);ndouble b2=p3.y-p3.x*k2;no.x=(b1-b2)/(k2-k1);no.y=k1*x+b1;nreturn o;n2011-10-20731059 Exocenter of a TriannPoint cal() nD=rotate(B-A, pi/2)+A;nG=rotate(C-A,-pi/2)+A;nL=middle(D,G);nE=rotate(A-B,-pi/2)+B;nJ=rotate(C-B, pi/2)+B;nM=middle(E,J);nO=intersection(L,A,M,B);nreturn O;n2011-10-20741003 Hit or Missn题目大意：题目大意：n一共有一共有n个人，第一个人开始时以一定顺序拿着标个人，第一个人开始时以一定顺序拿着标有有1到到13各各4张的卡片堆。每个人分别执行以下两张的卡片堆。每个人分别执行以下两个步骤：个步骤：1、如果手上有卡，每次轮到自己则数一个数，从、如果手上有卡，每次轮到自己则数一个数，从1开开始，在始，在113内循环，如果数的数刚好和自己的卡片堆内循环，如果数的数刚好和自己的卡片堆最顶的卡片一样，则丢弃这张卡片，否则把这张卡片最顶的卡片一样，则丢弃这张卡片，否则把这张卡片放到卡片堆底；放到卡片堆底；2、除了第、除了第1个人，如果每个人前面的一个人有卡片丢个人，如果每个人前面的一个人有卡片丢弃，则把丢弃的卡片放到自己卡片堆底。弃，则把丢弃的卡片放到自己卡片堆底。n如此循环，直到每个人手上都没有卡片，或不能如此循环，直到每个人手上都没有卡片，或不能终止。如果可以结束，则输出每个人最后丢弃的终止。如果可以结束，则输出每个人最后丢弃的卡片。卡片。2011-10-20751003 Hit or Missn解题思路：解题思路：n认真阅读题意，按照题意直接模拟。认真阅读题意，按照题意直接模拟。n当循环次数超过最大卡片张数（当循环次数超过最大卡片张数（52）仍没）仍没有人抛弃卡片，则判断不能终止。有人抛弃卡片，则判断不能终止。2011-10-20761003 Hit or Missnstruct player nqueue cards;nint lastcard, count;nint step1() nint discard=-1;nif (!(cards.empty() nint cur=cards.front();ncards.pop();nif (cur=count) lastcard=discard=cur;nelse cards.push(cur);nif (count=13) count=1;nelse count+;nnreturn discard;nn;2011-10-20771003 Hit or Missnvoid run() nint lastround = 0;nfor (int round=1;round-lastround=52;round+) nfor (int i=0; in; i+) ndiscardsi = pi.step1();nif (discardsi != -1)nlastround=round;nnfor (int i=1; in; i+)nif (discardsi-1 != -1)npi.cards.push(discardsi-1);nn2011-10-20781018 A Card Trickn题目大意：题目大意：n一个魔术，助手把五张扑克的其中四张按一个魔术，助手把五张扑克的其中四张按一定顺序给魔术师，魔术师可能通过一定一定顺序给魔术师，魔术师可能通过一定的规则计算出剩余的一张扑克。的规则计算出剩余的一张扑克。n给出五张扑克，求出它们给魔术师的顺序。给出五张扑克，求出它们给魔术师的顺序。2011-10-20791018 A Card Trickn解题思路：解题思路：n枚举五张扑克的顺序，找出其中合法的。枚举五张扑克的顺序，找出其中合法的。n按照题目描述的规则模拟。按照题目描述的规则模拟。nstruct card nint num;nchar suit;n;nbool operator (const card &a,const card &b) nif (a.num!=b.num)nreturn a.numb.num;nelsenreturn a.suitb.suit;n2011-10-20801018 A Card Tricknbool check() n if (cards0.suit!=cards1.suit)n return false;n int result=0,min=2,max=2;n for (int i=3;i5;i+) n if (cardsicardsmax)n max=i;n n int middle=2+3+4-min-max;n result+=min-1;n if (middlemax)n result+=3;n return cards0.num%13=(cards1.num+result)%13;n2011-10-20811018 A Card Tricknvoid run()nnsort(cards,cards+5);nwhile (true)nnif (check()nbreak;nnext_permutation(cards,cards+5);nn2011-10-20821052 Candy Sharing Gamen题目大意：题目大意：nM个学生围成一圈，开始时所有学生都有偶个学生围成一圈，开始时所有学生都有偶数的糖。每个回合，所有学生同时把手里数的糖。每个回合，所有学生同时把手里的一半糖传给右边的学生，如果某个学生的一半糖传给右边的学生，如果某个学生的糖数为奇数，则老师多给他一个糖。直的糖数为奇数，则老师多给他一个糖。直到所有学生的糖数目相等则结束。求回合到所有学生的糖数目相等则结束。求回合数和每个学生手里的糖数。数和每个学生手里的糖数。2011-10-20831052 Candy Sharing Gamen解题思路：解题思路：n直接按照题目模拟。直接按照题目模拟。nfor (round=0;!allsame();round+) nfor (int i=0;im;i+)nbi=ai=ai/2;nfor (int i=0;im;i+) na(i+1)%m+=bi;na(i+1)%m+=a(i+1)%m%2;nn2011-10-20841041 Pushing Boxesn题目大意：题目大意：n一间长方形房间里有一些箱子，每次操作一间长方形房间里有一些箱子，每次操作为房间的其中一面墙向里移动，把其中的为房间的其中一面墙向里移动，把其中的箱子推到新的位置。求最后箱子的位置。箱子推到新的位置。求最后箱子的位置。2011-10-20851041 Pushing Boxesn解题思路：解题思路：n思路思路1：分上下左右四种情况分别考虑。分上下左右四种情况分别考虑。按照题目描述模拟。按照题目描述模拟。n思路思路2：只考虑一个方向。只考虑一个方向。在移动其它方向时，把房间旋转至默认方向，在移动其它方向时，把房间旋转至默认方向，移动后再旋转回原来的方向。移动后再旋转回原来的方向。2011-10-20861041 Pushing Boxesnbool cmpright(const pos &a,const pos &b) nif (a.x!=b.x) return a.xb.x;nelse return a.yb.y;nnvoid moveright(int m) nsort(box,box+n,cmpright);nint x=-1,y;nfor (int i=0;in;i+) nif (boxi.x!=x) nx=boxi.x;ny=m;nnelse y+;nif (boxi.yy) boxi.y=y;nn2011-10-20871211 商人的宣传商人的宣传n题目大意：题目大意：n有有n个州，个州，m条单向边，规定天数为条单向边，规定天数为L。n共有共有q个询问，每个询问为从州个询问，每个询问为从州A到州到州B刚刚好为好为L步的方案数。步的方案数。2011-10-20881211 商人的宣传商人的宣传n解题思路：解题思路：n第第0天，每个州到自己的方案数为天，每个州到自己的方案数为1。n第第n+1天，每个州天，每个州A到另一个州到另一个州B的方案数的方案数为，对所有州为，对所有州C，第，第n天从天从A到到C的方案数与的方案数与一天内从一天内从C到到B的方案数的积，再对所有州的方案数的积，再对所有州求和。（即第求和。（即第n天通过州天通过州C作中转的方案）作中转的方案）2011-10-20891211 商人的宣传商人的宣传nint cal(int A,int B) n int i,j,k;n memset(ans,0,sizeof(ans);n ans0AA=1;n for (k=1;k=L;k+) n for (i=1;i=n;i+)n for (j=1;j=n;j+)n anskAi+=ansk-1Aj*edgeji;n return ansLAB;n2011-10-20901071 Floorsn题目大意：题目大意：n一块长方形地板是由很多长方形瓷砖组成一块长方形地板是由很多长方形瓷砖组成的，每次可以从中选一块，沿着瓷砖的边的，每次可以从中选一块，沿着瓷砖的边缘按直线切成两块，直到没有任何块可以缘按直线切成两块，直到没有任何块可以继续此操作。求出此时最大的块的面积。继续此操作。求出此时最大的块的面积。2011-10-20911071 Floorsn解题思路：解题思路：n对于每一块，尝试平行于长方形的两边分对于每一块，尝试平行于长方形的两边分别切割。对于分出来的小块，递归进行重别切割。对于分出来的小块，递归进行重复操作。复操作。n判断是否可切割：按垂直于切割方向对瓷判断是否可切割：按垂直于切割方向对瓷砖进行排序，切割线所切出来的块的面积砖进行排序，切割线所切出来的块的面积与所在一侧的瓷砖总面积之和相等，则可与所在一侧的瓷砖总面积之和相等，则可切割。切割。2011-10-20921071 Floorsnvoid cal(int x1,int y1,int x2,int y2,int l,int r) nint s=(x2-x1)*(y2-y1);nif (sans)nans=s;n2011-10-20931071 Floorsnbool cmpx(const rect &a,const rect &b) return a.xlb.xl; nbool cutx(int x1,int y1,int x2,int y2,int l,int r) n sort(a+l,a+r+1,cmpx);n int x=x1,s=0;n for (i=l;ix) x=ai.xh;n if (s=(x-x1)*(y2-y1) n cal(x1,y1,x,y2,l,i);n cal(x,y1,x2,y2,i+1,r);n return true;n n n return false;n2011-10-20941082 MANAGERn题目大意：题目大意：n现在有一个进程序列，每个进程都有消耗。有以现在有一个进程序列，每个进程都有消耗。有以下几种操作：下几种操作：a x 在序列中放进消耗为在序列中放进消耗为x的进程的进程r 在序列中移除一个进程，根据策略可能是消耗最小在序列中移除一个进程，根据策略可能是消耗最小或最大的或最大的p i 设定策略设定策略n给出一些输出序号，当执行的移除操作的次数和给出一些输出序号，当执行的移除操作的次数和序号一致时，输出这次移除的进程的消耗。序号一致时，输出这次移除的进程的消耗。2011-10-20951082 MANAGERn解题思路：解题思路：n建立二叉查找树，可以动态进行插入，删建立二叉查找树，可以动态进行插入，删除，查找最大除，查找最大/最小值。可以使用最小值。可以使用stl里的里的map。n记录每次移除的进程消耗，查询时直接输记录每次移除的进程消耗，查询时直接输出。出。2011-10-20961082 MANAGERnvoid append(int x) nprocess_mapx+;nnint remove() nif (p=1) it=process_map.begin();nelse it=process_map.end(); it-; nint x=it-first;nif (it-second=1)nprocess_map.erase(it);nelsenit-second-;nrecordcnt+=x;nreturn x;n2011-10-2097谢谢！谢谢！