??xml version="1.0" encoding="utf-8" standalone="yes"?>狠狠人妻久久久久久综合蜜桃,精品多毛少妇人妻AV免费久久,久久香综合精品久久伊人http://www.shnenglu.com/guodongshan/zh-cnFri, 09 May 2025 14:45:59 GMTFri, 09 May 2025 14:45:59 GMT60ACM法http://www.shnenglu.com/guodongshan/archive/2010/10/13/129717.html孟v孟vWed, 13 Oct 2010 01:46:00 GMThttp://www.shnenglu.com/guodongshan/archive/2010/10/13/129717.htmlhttp://www.shnenglu.com/guodongshan/comments/129717.htmlhttp://www.shnenglu.com/guodongshan/archive/2010/10/13/129717.html#Feedback0http://www.shnenglu.com/guodongshan/comments/commentRss/129717.htmlhttp://www.shnenglu.com/guodongshan/services/trackbacks/129717.html一、数论算?/span>
1
Q求两数的最大公U数
2
Q求两数的最公倍数
3
Q素数的求法
A.
范围内判断一个数是否敎ͼ(x)
B.
判断longint范围内的数是否ؓ(f)素数Q包含求50000以内的素数表Q:(x)

二、图论算?/span>
1
Q最生成树(wi)
A.Prim
法Q?/span>
B.Kruskal
法Q?/span>(贪心(j))
按权值递增序删去图中的边Q若不Ş成回路则此边加入最生成树(wi)?/span>
2.
最短\?/span>
A.
标号法求解单源点最短\径:(x)
B.Floyed
法求解所有顶点对之间的最短\径:(x)
C. Dijkstra
法Q?/span>
3.
计算囄传递闭?/span>
4
Q无向图的连通分?/span>
A.
深度优先
B
宽度优先Q种子染色法Q?/span>
5
Q关键\?/span>
几个定义Q?/span> 1为源点,n为汇炏V?/span>
a.
点事g最早发生时?/span>Ve[j], Ve [j] = max{ Ve [j] + w[I,j] },其中Ve (1) = 0;
b.
点事g最晚发生时?/span> Vl[j], Vl [j] = min{ Vl[j] – w[I,j] },其中 Vl(n) = Ve(n);
c.
Ҏ(gu)动最早开始时?/span> Ee[I], 若边I?/span><j,k>表示Q则Ee[I] = Ve[j];
d.
Ҏ(gu)动最晚开始时?/span> El[I], 若边I?/span><j,k>表示Q则El[I] = Vl[k] – w[j,k];
?/span> Ee[j] = El[j] Q则zdj为关键活动,由关键活动组成的路径为关键\径?/span>
求解Ҏ(gu)Q?/span>
a.
从源点vtopsort,判断是否有回路ƈ计算Ve;
b.
从汇点vtopsort,?/span>Vl;
c.
?/span>Ee ?/span> El;
6
Q拓扑排?/span>
扑օ度ؓ(f)0的点Q删M其相q的所有边Q不断重复这一q程?/span>
?/span> L一数列Q其中Q意连l?/span>p之和ؓ(f)正,Lq 之和ؓ(f)负,若不存在则输?/span>NO.
7.
回\问题
Euler
回\(DFS)
定义Q经q图的每条边仅一ơ的回\。(充要条gQ图q同且无奇点Q?/span>
Hamilton
回\
定义Q经q图的每个顶点仅一ơ的回\?/span>
一W画
充要条gQ图q通且奇点个数?/span>0个或2个?/span>
9
Q判断图中是否有负权回\ Bellman-ford
x[I],y[I],t[I]
分别表示W?/span>I条边的v点,l点和权。共n个结点和m条边?/span>
10
Q第n最短\径问?/span>
*
W二最短\径:(x)每D最短\径上的每条边Q每ơ删除一条,然后求新囄最短\径,取这些\径中最短的一条即为第二最短\径?/span>
*
同理Q第n最短\径可在求解第n-1最短\径的基础上求解?/span>

三、背包问?/span>
*
部分背包问题可有贪心(j)法求解:(x)计算Pi/Wi
数据l构Q?/span>
w[i]:
W?/span>i个背包的重量Q?/span>
p[i]:
W?/span>i个背包的价|
1
Q?/span>0-1背包Q?/span> 每个背包只能使用一ơ或有限?/span>(可{化ؓ(f)一?/span>)Q?/span>
A.
求最多可攑օ的重量?/span>
B.
求可以放入的最大h(hun)倹{?/span>
F[I,j]
为容量ؓ(f)I时取?/span>j个背包所能获得的最大h(hun)倹{?/span>
F [i,j] = max { f [ i – w [ j ], j-1] + p [ j ], f[ i,j-1] }
C.
求恰好装满的情况数?/span>
2
Q可重复背包
A
求最多可攑օ的重量?/span>
F[I,j]
为前i个物品中选择若干个放入其体U正好ؓ(f)j的标志,为布?yu)(dng)型?/span>
状态{ULEؓ(f)
f[I,j] = f [ I-1, j – w[I]*k ] (k=1.. j div w[I])
B.
求可以放入的最大h(hun)倹{?/span>
f[i,j] = max { f [i- k*w[j], j-1] + k*p[j] } (0<=k<= i div w[j])
其中f[i,j]表示定w?/span>i时取?/span>jU背包所能达到的最大倹{?/span>
C.
求恰好装满的情况数?/span>
Ahoi2001 Problem2
求自然数n本质不同的质数和的表辑ּ的数目?/span>
思\一Q生成每个质数的pL的排列,在一一试Q这是通法?/span>
思\二,递归搜烦(ch)效率较高

思\三:(x)可用动态规划求?/span>
四、排序算?/span>
1.
快速排序:(x)
B.
插入排序Q?/span>
思\Q当?/span>a[1]..a[i-1]已排好序?jin),现要插?/span>a[i]?/span>a[1]..a[i]有序?/span>
C.
选择排序Q?/span>
D.
冒(chng)排序
E.
堆排序:(x)
F.
归ƈ排序
G.
基数排序
思想Q对每个元素按从低位到高位对每一位进行一ơ排?/span>
五、高_ֺ计算
高精度数的定义:(x)
1
Q高_ֺ加法
2
Q高_ֺ减法
3
Q高_ֺ乘以低精?/span>
4
Q高_ֺ乘以高精?/span>
5
Q高_ֺ除以低精?/span>
6
Q高_ֺ除以高精?/span>

六?/span> ?wi)的遍?/span>
1
Q已知前序中序求后序
2
Q已知中序后序求前序
3
Q已知前序后序求中序的一U?/span>

?/span> q制转换
1
L正整数进刉的互?/span>
?/span>n取余
2
实数L正整数进刉的互?/span>
?/span>n取整
3
负数q制Q?/span>
设计一个程序,d一个十q制数的基数和一个负q制数的基数Qƈ此十进制数转换为此?/span> q制下的敎ͼ(x)-R{-2Q?/span>-3Q?/span>-4,....-20}
?/span> 全排列与l合的生?/span>
1
排列的生成:(x)Q?/span>1..nQ?/span>
2
l合的生?/span>(1..n中选取k个数的所有方?/span>)

?/span>.查找法
1
折半查找
2
?wi)Ş查?/span>
二叉排序?wi)?x)每个l点的值都大于其左子树(wi)Ml点的D小于其叛_?wi)Q一l点的倹{?/span>
查找

十、贪?/span>
*
?x)议问?/span>
Q?/span>1Q?/span> n个活动每个活动有一个开始时间和一个结束时_(d)M时刻仅一Ҏ(gu)动进行,求满x动数最多的情况?/span>
解:(x)按每Ҏ(gu)动的l束旉q行排序Q排在前面的优先满?/span>
Q?/span>2Q会(x)议室I闲旉最?/span>
Q?/span>3Q每个客h一个愿付的U金Q求最大利润?/span>
Q?/span>4Q共R间会(x)议室Q第i个客户需使用i间会(x)议室Q费用相同,求最大利润?/span>
十一、回溯法框架
1. n
皇后问题
2.Hanoi Tower h(n)=2*h(n-1)+1 h(1)=1

十二?/span>DFS框架

十三?/span>BFS框架

十五、数据结构相关算?/span>
1
Q链表的定位函数

2Q单链表的插入操?/span>
3
Q单链表的删除操?/span>
4
Q双链表的插入操作(插入新结?/span>qQ?/span>
5
Q双链表的删除操?/span>


原文链接Q?a target=_blank>http://old.blog.edu.cn/user3/Hailer/archives/2006/1545396.shtml



孟v 2010-10-13 09:46 发表评论
]]>
计算几何题目ȝ?qing)分c?/title><link>http://www.shnenglu.com/guodongshan/archive/2010/10/12/129624.html</link><dc:creator>孟v</dc:creator><author>孟v</author><pubDate>Tue, 12 Oct 2010 09:36:00 GMT</pubDate><guid>http://www.shnenglu.com/guodongshan/archive/2010/10/12/129624.html</guid><wfw:comment>http://www.shnenglu.com/guodongshan/comments/129624.html</wfw:comment><comments>http://www.shnenglu.com/guodongshan/archive/2010/10/12/129624.html#Feedback</comments><slash:comments>0</slash:comments><wfw:commentRss>http://www.shnenglu.com/guodongshan/comments/commentRss/129624.html</wfw:commentRss><trackback:ping>http://www.shnenglu.com/guodongshan/services/trackbacks/129624.html</trackback:ping><description><![CDATA[     摘要: FOJ Hotter Colder http://acm.fzu.edu.cn/problem.php?pid=1014 求线D늚中位U,U段怺求交点,求凸多边形的面积Q?无归之室 http://acm.fzu.edu.cn/problem.php?pid=1016 本题_ֺ要求非常高,用三角函数的话,很容易就wa.. Reflections http://acm.fzu.e...  <a href='http://www.shnenglu.com/guodongshan/archive/2010/10/12/129624.html'>阅读全文</a><img src ="http://www.shnenglu.com/guodongshan/aggbug/129624.html" width = "1" height = "1" /><br><br><div align=right><a style="text-decoration:none;" href="http://www.shnenglu.com/guodongshan/" target="_blank">孟v</a> 2010-10-12 17:36 <a href="http://www.shnenglu.com/guodongshan/archive/2010/10/12/129624.html#Feedback" target="_blank" style="text-decoration:none;">发表评论</a></div>]]></description></item><item><title>L四面体体U公?以及(qing)几点计算几何注意事项http://www.shnenglu.com/guodongshan/archive/2010/10/12/129595.html孟v孟vTue, 12 Oct 2010 04:00:00 GMThttp://www.shnenglu.com/guodongshan/archive/2010/10/12/129595.htmlhttp://www.shnenglu.com/guodongshan/comments/129595.htmlhttp://www.shnenglu.com/guodongshan/archive/2010/10/12/129595.html#Feedback0http://www.shnenglu.com/guodongshan/comments/commentRss/129595.htmlhttp://www.shnenglu.com/guodongshan/services/trackbacks/129595.htmlEuler的Q意四面体体积公式Q已知边长求体积Q?br>



已知4点坐标求体积Q?/span>其中四个点的坐标分别为(x1,y1,z1Q?span lang=EN-US>,Q?span lang=EN-US>x2,y2,z2
Q?span lang=EN-US>,Q?span lang=EN-US>x3,y3,z3Q?span lang=EN-US>,Q?span lang=EN-US>x4,y4,z4Q?br>


注意事项Q?br>

1. 注意舍入方式(0.5的舍入方?span lang=EN-US>);防止输出-0.

2. 几何题注意多试不对U数?span lang=EN-US>.

3. 整数几何注意xmult?span lang=EN-US>dmult是否?x)出?span lang=EN-US>;

   W点几何注意eps的?span lang=EN-US>.

4. 避免使用斜率;注意除数是否?x)?f)0.

5. 公式一定要化简后再代入.

6. 判断同一?span lang=EN-US>2*PI域内两角度差应该?span lang=EN-US>

   abs(a1-a2)<beta||abs(a1-a2)>pi+pi-beta;

   相等应该?/span>

   abs(a1-a2)<eps||abs(a1-a2)>pi+pi-eps;

7. 需要的话尽量?/span>atan2,注意:atan2(0,0)=0,

   atan2(1,0)=pi/2,atan2(-1,0)=-pi/2,atan2(0,1)=0,atan2(0,-1)=pi.

8. cross product = |u|*|v|*sin(a)

   dot product = |u|*|v|*cos(a)

9. (P1-P0)x(P2-P0)l果的意?span lang=EN-US>:

   ?span lang=EN-US>: <P0,P1>?span lang=EN-US><P0,P2>时?span lang=EN-US>(0,pi)?span lang=EN-US>

   ?span lang=EN-US>: <P0,P1>?span lang=EN-US><P0,P2>逆时?span lang=EN-US>(0,pi)?span lang=EN-US>

   0 : <P0,P1>,<P0,P2>q,夹角?span lang=EN-US>0?span lang=EN-US>pi



孟v 2010-10-12 12:00 发表评论
]]>
读陈峰的《计几何算法概览?/title><link>http://www.shnenglu.com/guodongshan/archive/2010/10/12/129568.html</link><dc:creator>孟v</dc:creator><author>孟v</author><pubDate>Tue, 12 Oct 2010 02:18:00 GMT</pubDate><guid>http://www.shnenglu.com/guodongshan/archive/2010/10/12/129568.html</guid><wfw:comment>http://www.shnenglu.com/guodongshan/comments/129568.html</wfw:comment><comments>http://www.shnenglu.com/guodongshan/archive/2010/10/12/129568.html#Feedback</comments><slash:comments>0</slash:comments><wfw:commentRss>http://www.shnenglu.com/guodongshan/comments/commentRss/129568.html</wfw:commentRss><trackback:ping>http://www.shnenglu.com/guodongshan/services/trackbacks/129568.html</trackback:ping><description><![CDATA[原文链接Q?a target=_blank>http://cschf.spaces.live.com/blog/cns!E113B8D05D833E2B!140.entry</a><br>写几点不熟?zhn)?br>12. 判断Ҏ(gu)否在多边形中<br>13. 判断U段是否在多边Ş?br>25. 计算U段或直U与U段的交?br>27. 求线D|直线与圆的交?br><br><a><strong>判断Ҏ(gu)否在多边形中</strong></a><strong>Q?/strong> <p style="FONT-SIZE: 12pt">判断点P是否在多边Ş中是计算几何中一个非常基本但是十分重要的法。以点P为端点,向左方作线LQ由于多边Ş是有界的Q所以射UL的左端一定在多边形外Q考虑沿着L从无I处开始自左向右移动,遇到和多边Ş的第一个交点的时候,q入C(jin)多边形的内部Q遇到第二个交点的时候,d?jin)多边ŞQ?#8230;…所以很Ҏ(gu)看出当L和多边Ş的交Ҏ(gu)目C是奇数的时候,P在多边Ş内,是偶数的话P在多边Ş外?/p> <p>但是有些Ҏ(gu)情况要加以考虑。如图下?a)(b)(c)(d)所C。在?a)中,L和多边Ş的顶点相交,q时候交点只能计一个;在图(b)中,L和多边Ş点的交点不应被计算Q在?c)?d) 中,L和多边Ş的一条边重合Q这条边应该被忽略不计。如果L和多边Ş的一条边重合Q这条边应该被忽略不计?/p> <p><img style="WIDTH: 300px; HEIGHT: 600px" src="http://i3.6.cn/cvbnm/f2/cc/f0/81fb54609cf280e08ad583de8a667e02.jpg" width=300 height=600> </p> <p>Z(jin)l一赯Q我们在计算线L和多边Ş的交点的时候,1。对于多边Ş的水q不作考虑Q?。对于多边Ş的顶点和L怺的情况,如果该顶Ҏ(gu)其所属的边上U坐标较大的点Q则计数Q否则忽略;3。对于P在多边Ş边上的情形,直接可判断P属于多边行。由此得出算法的伪代码如下:(x) <br>    count ← 0; <br>    以P为端点,作从叛_左的线L;  <br>    for 多边形的每条边s <br>     do if P在边s?nbsp; <br>          then return true; <br>        if s不是水^?<br>          then if s的一个端点在L?<br>                 if 该端Ҏ(gu)s两端点中U坐标较大的端点 <br>                   then count ← count+1 <br>               else if s和L怺 <br>                 then count ← count+1; <br>    if count mod 2 = 1  <br>      then return true; <br>    else return false; <br>其中做射UL的方法是Q设P'的纵坐标和P相同Q横坐标为正无穷大(很大的一个正敎ͼ(j)Q则P和P'q定了(jin)线L?</p> <p>判断Ҏ(gu)否在多边形中的这个算法的旉复杂度ؓ(f)O(n)?/p> <p>另外q有一U算法是用带W号的三角Ş面积之和与多边Ş面积q行比较Q这U算法由于用QҎ(gu)q算所以会(x)带来一定误差,不推荐大家用?</p> <p><a><br><strong>判断U段是否在多边Ş?/strong></a><strong>Q?/strong></p> <p>U段在多边Ş内的一个必要条件是U段的两个端炚w在多边Ş内,但由于多边Ş可能为凹Q所以这不能成ؓ(f)判断的充分条件。如果线D和多边形的某条边内交(两线D内交是指两U段怺且交点不在两U段的端点)(j)Q因为多边Ş的边的左右两侧分属多边Ş内外不同部分Q所以线D一定会(x)有一部分在多边Ş?见图a)。于是我们得到线D在多边形内的第二个必要条gQ线D和多边形的所有边都不内交?</p> <p>U段和多边Ş交于U段的两端点q不?x)?jing)响线D|否在多边形内Q但是如果多边Ş的某个顶点和U段怺Q还必须判断两相M点之间的U段是否包含于多边Ş内部Q反例见图b)?</p> <p> <img src="http://i3.6.cn/cvbnm/a4/50/b0/79afe28e6ea3a00c4678214bc2083c4b.jpg"> </p> <p>因此我们可以先求出所有和U段怺的多边Ş的顶点,然后按照X-Y坐标排序(X坐标的排在前面Q对于X坐标相同的点QY坐标的排在前面Q这U排序准则也是ؓ(f)?jin)保证水q_垂直情况的判断正?Q这L(fng)?c)两个点就是在U段上相?c)两交点,如果L盔R两点的中点也在多边Ş内,则该U段一定在多边形内?</p> <p>证明如下Q?/p> <p>命题1Q?<br>如果U段和多边Ş的两盔R交点P1 QP2的中点P' 也在多边形内Q则P1, P2之间的所有点都在多边形内?/p> <p>证明Q?<br>假设P1,P2之间含有不在多边形内的点Q不妨设该点为QQ在P1, P'之间Q因为多边Ş是闭合曲U,所以其内外部之间有界,而P1属于多边行内部,Q属于多边性外部,P'属于多边性内部,P1-Q-P'完全q箋Q所以P1Q和QP'一定跨多边Ş的边界,因此在P1,P'之间臛_q有两个该线D和多边形的交点Q这和P1P2是相M交点矛盾Q故命题成立。证毕?</p> <p>由命?直接可得出推论:(x) <br>推论2Q?<br>讑֤边Ş和线DPQ的交点依ơؓ(f)P1,P2,……PnQ其中Pi和Pi+1是相M交点Q线DPQ在多边Ş内的充要条g是:(x)PQQ在多边Ş内且对于i =1, 2,……, n-1QPi ,Pi+1的中点也在多边Ş内?<br>在实际编E中Q没有必要计所有的交点Q首先应判断U段和多边Ş的边是否内交Q倘若U段和多边Ş的某条边内交则线D一定在多边形外Q如果线D和多边形的每一条边都不内交Q则U段和多边Ş的交点一定是U段的端Ҏ(gu)者多边Ş的顶点,只要判断Ҏ(gu)否在U段上就可以?jin)?<br>x我们得出法如下Q?<br>    if U端PQ的端点不都在多边形内  <br>      then return false; <br>    炚wpointSet初始化ؓ(f)I? <br>    for 多边形的每条边s <br>      do if U段的某个端点在s?<br>           then 该端点加入pointSet; <br>         else if s的某个端点在U段PQ?<br>           then 该端点加入pointSet; <br>         else if s和线DPQ怺 // q时候已l可以肯定是内交?<br>           then return false; <br>    pointSet中的Ҏ(gu)照X-Y坐标排序; <br>    for pointSet中每两个盔R?pointSet[i] , pointSet[ i+1] <br>      do if pointSet[i] , pointSet[ i+1] 的中点不在多边Ş?<br>           then return false; <br>    return true; <br>q个q程中的排序因ؓ(f)交点数目肯定q小于多边Ş的顶Ҏ(gu)目nQ所以最多是常数U的复杂度,几乎可以忽略不计。因此算法的旉复杂度也是O(n)?/p> <br> <p><strong><a><font style="COLOR: #000000" color=#0066a7>计算U段或直U与U段的交?/font></a>:</strong></p> <p>设一条线Dؓ(f)L0 = P1P2Q另一条线D|直线为L1 = Q1Q2 Q要计算的就是L0和L1的交炏V?<br>1Q?首先判断L0和L1是否怺Q方法已在前文讨Q,如果不相交则没有交点Q否则说明L0和L1一定有交点Q下面就L0和L1都看作直U来考虑?</p> <p>2Q?如果P1和P2横坐标相同,即L0q于Y?</p> <p>a) 若L1也^行于Y_(d) </p> <p>i. 若P1的纵坐标和Q1的纵坐标相同Q说明L0和L1qQ假如L1是直U的话他们有无穷的交点,假如L1是线D늚话可?计算两条qU段的交?的算法求他们的交点(该方法在前文已讨Q; <br>ii. 否则说明L0和L1qQ他们没有交点; </p> <p>b) 若L1不^行于Y_(d)则交Ҏ(gu)坐标为P1的横坐标Q代入到L1的直U方E中可以计算Z点纵坐标Q?</p> <p>3Q?如果P1和P2横坐标不同,但是Q1和Q2横坐标相同,即L1q于Y_(d)则交Ҏ(gu)坐标为Q1的横坐标Q代入到L0的直U方E中可以计算Z点纵坐标Q?</p> <p>4Q?如果P1和P2U坐标相同,即L0q于X?</p> <p>a) 若L1也^行于X_(d) </p> <p>i. 若P1的横坐标和Q1的横坐标相同Q说明L0和L1qQ假如L1是直U的话他们有无穷的交点,假如L1是线D늚话可?计算两条qU段的交?的算法求他们的交点(该方法在前文已讨Q; <br>ii. 否则说明L0和L1qQ他们没有交点; </p> <p>b) 若L1不^行于X_(d)则交点纵坐标为P1的纵坐标Q代入到L1的直U方E中可以计算ZҎ(gu)坐标Q?</p> <p>5Q?如果P1和P2U坐标不同,但是Q1和Q2U坐标相同,即L1q于X_(d)则交点纵坐标为Q1的纵坐标Q代入到L0的直U方E中可以计算ZҎ(gu)坐标Q?</p> <p>6Q?剩下的情况就是L1和L0的斜率均存在且不?的情?</p> <p>a) 计算出L0的斜率K0QL1的斜率K1 Q?</p> <p>b) 如果K1 = K2  </p> <p>i. 如果Q(jng)1在L0上,则说明L0和L1qQ假如L1是直U的话有无穷交点Q假如L1是线D늚话可?计算两条qU段的交?的算法求他们的交点(该方法在前文已讨Q; <br>ii. 如果Q(jng)1不在L0上,则说明L0和L1qQ他们没有交炏V?<br>c) 联立两直U的方程l可以解ZҎ(gu) <br>q个法q不复杂Q但是要分情况讨论清楚,其是当两条U段q的情况需要单独考虑Q所以在前文求两条qU段的算法单独写出来。另外,一开始就先利用矢量叉乘判断线D与U段Q或直线Q是否相交,如果l果是相交,那么在后面就可以线D全部看作直U来考虑。需要注意的是,我们可以直U或U段方程改写为ax+by+c=0的Ş式,q样一来上q过E的部分步骤可以合ƈQ羃短了(jin)代码长度Q但是由于先要求出参敎ͼq种法花Ҏ(gu)多的旉?<br></p> <p><strong><a><font style="COLOR: #000000" color=#0066a7>求线D|直线与圆的交?/font></a>:</strong></p> <p>讑֜?j)?f)OQ圆半径为rQ直U(或线D)(j)L上的两点为P1,P2?</p> <p>1. 如果L是线D且P1QP2都包含在圆O内,则没有交点;否则q行下一步?</p> <p>2. 如果Lq于Y_(d) </p> <p>a) 计算圆心(j)到L的距disQ?<br>b) 如果dis > r 则L和圆没有交点Q?<br>c) 利用勾股定理Q可以求Z交点坐标Q但要注意考虑L和圆的相切情c(din)?<br>3. 如果Lq于X_(d)做法与Lq于Y轴的情况cMQ?</p> <p>4. 如果L既不qX轴也不^行Y_(d)可以求出L的斜率KQ然后列出L的点斜式方程Q和圆方E联立即可求解出L和圆的两个交点; </p> <p>5. 如果L是线D,对于2Q?Q?中求出的交点q要分别判断是否属于该线D늚范围内?/p> <img src ="http://www.shnenglu.com/guodongshan/aggbug/129568.html" width = "1" height = "1" /><br><br><div align=right><a style="text-decoration:none;" href="http://www.shnenglu.com/guodongshan/" target="_blank">孟v</a> 2010-10-12 10:18 <a href="http://www.shnenglu.com/guodongshan/archive/2010/10/12/129568.html#Feedback" target="_blank" style="text-decoration:none;">发表评论</a></div>]]></description></item><item><title>二维下计几何分c?/title><link>http://www.shnenglu.com/guodongshan/archive/2010/10/12/129563.html</link><dc:creator>孟v</dc:creator><author>孟v</author><pubDate>Tue, 12 Oct 2010 01:52:00 GMT</pubDate><guid>http://www.shnenglu.com/guodongshan/archive/2010/10/12/129563.html</guid><wfw:comment>http://www.shnenglu.com/guodongshan/comments/129563.html</wfw:comment><comments>http://www.shnenglu.com/guodongshan/archive/2010/10/12/129563.html#Feedback</comments><slash:comments>0</slash:comments><wfw:commentRss>http://www.shnenglu.com/guodongshan/comments/commentRss/129563.html</wfw:commentRss><trackback:ping>http://www.shnenglu.com/guodongshan/services/trackbacks/129563.html</trackback:ping><description><![CDATA[<p style="FONT-SIZE: 12pt">一、点的基本运?<br>1. q面上两点之间距?1 <br>2. 判断两点是否重合 1 <br>3. 矢量叉乘 1 <br>4. 矢量点乘 2 <br>5. 判断Ҏ(gu)否在U段?2 <br>6. 求一炚w某点旋{后的坐标 2 <br>7. 求矢量夹?2 <br></p> <p style="FONT-SIZE: 12pt">二?nbsp;U段?qing)直U的基本q算 <br>1. 点与U段的关p?3 <br>2. 求点到线D|在直U垂U的垂 4 <br>3. 点到U段的最q点 4 <br>4. 点到U段所在直U的距离 4 <br>5. 点到折线集的最q距?4 <br>6. 判断圆是否在多边形内 5 <br>7. 求矢量夹角余?5 <br>8. 求线D之间的夹角 5 <br>9. 判断U段是否怺 6 <br>10.判断U段是否怺但不交在端点处(内交Q?6 <br>11.求线D|在直U的方程 6 <br>12.求直U的斜率 7 <br>13.求直U的倾斜?7 <br>14.求点关于某直U的对称?7 <br>15.判断两条直线是否怺?qing)求直线交?7 <br>16.判断U段是否怺Q如果相交返回交?7 <br><br><span style="FONT-SIZE: 12pt">三、多边Ş常用法模块 <br>1. 判断多边形是否简单多边Ş 8 <br>2. (g)查多边Ş点的凸Ҏ(gu)?9 <br>3. 判断多边形是否凸多边?9 <br>4. 求多边Ş面积 9 <br>5. 判断多边形顶点的排列方向Q方法一 10 <br>6. 判断多边形顶点的排列方向Q方法二 10 <br>7. 线法判断点是否在多边Ş?10 <br>8. 判断Ҏ(gu)否在凸多边Ş?11 <br>9. L炚w的graham法 12 <br>10.L炚w凸包的卷包裹?13 <br>11.判断U段是否在多边Ş?14 <br>12.求简单多边Ş的重?QHDU1115Q?5 <br>13.求凸多边形的重心(j) 17 <br>14.求肯定在l定多边形内的一个点 17 <br>15.求从多边形外一点出发到该多边Ş的切U?18 <br>16.判断多边形的核是否存?19 <br><br>四?圆的基本q算 <br>1 .Ҏ(gu)否在圆内 20 <br>2 .求不q的三Ҏ(gu)定的圆 21 <br><br>五、矩形的基本q算 <br>1.已知矩Ş三点坐标Q求W?点坐?22 <br><br>六、常用算法的描述 22 <br><br>七、补?<br>1Q两圆关p:(x) 24 <br>2Q判断圆是否在矩形内Q?24 <br>3Q点到^面的距离Q?25 <br>4Q点是否在直U同侧:(x) 25 <br>5Q镜面反线Q?25 <br>6Q矩形包含:(x) 26 <br>7Q两圆交点:(x) 27 <br>8Q两圆公共面U:(x) 28 <br>9. 圆和直线关系Q?29 <br>10. 内切圆:(x) 30 <br>11. 求切点:(x) 31 <br>12. U段的左xQ?31 <br>13Q公式:(x) 32 <br><br>附上一博客:(x)</span><a target=_blank><span style="FONT-SIZE: 12pt">计算几何法概览</span></a><span style="FONT-SIZE: 12pt"> <br><br>  </p> <p align=left><a ></a><span>zoj</span><span>上的计算几何?/span><span><br>Vol I <br>1010 by pandahyx <br>1032 by javaman <br>1037 by Vegetable Bird <br>1041 by javaman <br>1081 by Vegetable Bird <br>1090 by Vegetable Bird <br><br>Vol II <br>1104 by javaman <br>1123 by javaman <br>1139 by Vegetable Bird <br>1165 by javaman <br>1199 by Vegetable Bird <br><br>Vol V <br>1426 by Vegetable Bird <br>1439 by Vegetable Bird <br>1460 by Vegetable Bird <br>1472 by Vegetable Bird <br><br>Vol VI <br>1597 by Vegetable Bird <br><br>Vol VII <br>1608 by Vegetable Bird <br>1648 by Vegetable Bird <br><br>Vol XII <br>2102 by pandahyx <br>2107 by pandahyx <br>2157 by pandahyx <br><br>Vol XIII <br>2234 by pandahyx <br><br>Vol XIV <br>2318 by ahyangyi <br>2394 by qherlyt <br><br>Vol XV <br>2403 by Vegetable Bird </span></span></p> <img src ="http://www.shnenglu.com/guodongshan/aggbug/129563.html" width = "1" height = "1" /><br><br><div align=right><a style="text-decoration:none;" href="http://www.shnenglu.com/guodongshan/" target="_blank">孟v</a> 2010-10-12 09:52 <a href="http://www.shnenglu.com/guodongshan/archive/2010/10/12/129563.html#Feedback" target="_blank" style="text-decoration:none;">发表评论</a></div>]]></description></item><item><title>判断Ҏ(gu)否在三角形内http://www.shnenglu.com/guodongshan/archive/2010/10/12/129558.html孟v孟vTue, 12 Oct 2010 01:40:00 GMThttp://www.shnenglu.com/guodongshan/archive/2010/10/12/129558.htmlhttp://www.shnenglu.com/guodongshan/comments/129558.htmlhttp://www.shnenglu.com/guodongshan/archive/2010/10/12/129558.html#Feedback0http://www.shnenglu.com/guodongshan/comments/commentRss/129558.htmlhttp://www.shnenglu.com/guodongshan/services/trackbacks/129558.html        ׃个顶点向所求的点引出矢量(注意方向Q,然后L用其中两个矢量Ş成^面,再用q个q面和剩下的矢量叉乘Q得Z个新矢量Q方向向里,则在三角形外Q反之在里面?
2.用面U方?br>
#include<stdio.h>
#include
<math.h>
struct TPoint {
    
float x;
    
float y;
}
;

//求叉U?/span>
float mul(struct TPoint p1, struct TPoint p2, struct TPoint p0) {
    
return ((p1.x - p0.x)*(p2.y - p0.y)-(p2.x - p0.x)*(p1.y - p0.y));
}

/*׃个顶点向所求的点引出矢量(注意方向Q,然后L用其中两个矢量Ş成^面,
 * 再用q个q面和剩下的矢量叉乘Q得Z个新矢量Q方向向里,则在三角形外Q反之在里面?br> 
*/

int inside(struct TPoint tr[], struct TPoint p) {
    
int i;
    
for (i = 0; i < 3; i++)
        
if (mul(p, tr[i], tr[(i + 1% 3]) * mul(p, tr[(i + 2% 3], tr[(i + 1% 3]) > 0)
            
return 0;
    
return 1;
}


float area(struct TPoint p1, struct TPoint p2, struct TPoint p3) {
    
return fabs((p1.x - p3.x)*(p2.y - p3.y)-(p2.x - p3.x)*(p1.y - p3.y));
}

//用面U判断p是否在三角Ş?/span>
int inside2(struct TPoint tr[], struct TPoint p) {
    
if (fabs(area(tr[0], tr[1], tr[2]) -
            area(p, tr[
1], tr[2]) -
            area(tr[
0], p, tr[2]) -
            area(tr[
0], tr[1], p)) < 1.0e-20)
        
return 1;
    
else
        
return 0;
}


int main() {
    
struct TPoint tr[3= {{-11},{10},{30}},  p = {12};

    
//Ҏ(gu)一
    printf("algorithm   1:");
    
if (inside(tr, p))
        printf(
"In\n");
    
else
        printf(
"Out\n");

    
//Ҏ(gu)一
    printf("algorithm   2:");
    
if (inside2(tr, p))
        printf(
"In\n");
    
else
        printf(
"Out\n");
}


孟v 2010-10-12 09:40 发表评论
]]>
HDU1292 "下沙野骆?ACM夏o(h)?递推http://www.shnenglu.com/guodongshan/archive/2010/10/11/129497.html孟v孟vMon, 11 Oct 2010 12:03:00 GMThttp://www.shnenglu.com/guodongshan/archive/2010/10/11/129497.htmlhttp://www.shnenglu.com/guodongshan/comments/129497.htmlhttp://www.shnenglu.com/guodongshan/archive/2010/10/11/129497.html#Feedback0http://www.shnenglu.com/guodongshan/comments/commentRss/129497.htmlhttp://www.shnenglu.com/guodongshan/services/trackbacks/129497.html递推式是Qa[i][j]=a[i-1][j-1]+a[i-1][j]*j;

而且。a[i][0]应该是ؓ(f)0Q不?的?/p>

此外q得注溢出。要用__int64cd?br>http://acm.hdu.edu.cn/showproblem.php?pid=1292

#include<stdio.h>
int main() {
    
int t, n, i, j;
    __int64 a[
26][26];
    a[
1][1= 1;
    a[
1][0= 0;
    
for (i = 2; i <= 25; i++) {
        a[i][
0= 0;
        a[i][i] 
= 1;
        
for (j = 1; j < i; j++)
            a[i][j] 
= a[i - 1][j - 1+ a[i - 1][j] * j;
    }
    scanf(
"%d"&t);
    
while (t--) {
        scanf(
"%d"&n);
        __int64 sum 
= 1;
        
for (i = 2; i <= n; i++)
            sum 
+= a[n][i];
        printf(
"%I64d\n", sum);
    }
    
return 0;
}


孟v 2010-10-11 20:03 发表评论
]]>
上v交大ACM队长--谈谈ACM比赛中的代码能力 http://www.shnenglu.com/guodongshan/archive/2010/10/11/129461.html孟v孟vMon, 11 Oct 2010 09:37:00 GMThttp://www.shnenglu.com/guodongshan/archive/2010/10/11/129461.htmlhttp://www.shnenglu.com/guodongshan/comments/129461.htmlhttp://www.shnenglu.com/guodongshan/archive/2010/10/11/129461.html#Feedback0http://www.shnenglu.com/guodongshan/comments/commentRss/129461.htmlhttp://www.shnenglu.com/guodongshan/services/trackbacks/129461.html
一、如何定义代码能?

Comars曄l代码能力作q一个比较准的定义?004q暑假时QComars曄说过Q他认ؓ(f)150行以内的题目Q他?Y率非帔RQƈ且保持稳定;而当代码长度过150行以后,1Y率就开始急速下降了(jin)。如果我们画Z?Y率的曲线的话Q?50行就是一个{折点。我们不妨认为,150行就是Comars当时的代码能力。一q以后,l过努力QComars把代码能力提高到?50行。不q,q已l是后话?jin)?

二、如何提高代码能?

我一直觉得写E序和写文章是一个对很好的类比?

写文章需要先从宏观入手,构思文章的l构。写E序同样需要。一个好的结构,是一个好的开始。一个好的开始,是成功的一半?
一好的文章需要各U句式和词藻的合理组合。体现到写程序上来,是一些单句以?qing)三五行的小l构的熟l用。这些都是需要^时ȝ和积累的?

但凡文章写得好的人,一定看q很多别人写的文章。同L(fng)道理Q多看别人的E序Q用?j)地ȝQ也可以提高自己的代码能力?
我鼓励队员去看别人写的程序,特别是像Comarsq样的选手写的E序。从优秀的程序中Q我们可以体?x)别好的E序l构Q同时也可以学到很多写程序的技巧――三五行的小技巧。在和Comars做队友的两年旉里,我通过看Comars的程序,学会(x)?jin)很多小技巧。逐渐圎ͼ我觉得我写的某些E序已经和Comars有点相像?jin)?
那么Q如果nҎ(gu)有Comarsq样优秀的选手可以借鉴Q该怎么办呢Q其实没关系。Q何一个程序都是可以看的。一个程序,q写得再差Q总还?x)有一两个闪光点,要想办法把它们找出来。另外,E序里写得不好的地方Q也要一一扑և来?
ȝ序,从某U角度来看,像d。好的历史是用来借鉴的;不好的历史则应该引以为戒。读E序也是一P择其善者而从之,其不善者而改之?

三、}慎地对待STL和SCL

STL - Standard Template Library。在ICPC的选手中,STL是相当受Ƣ迎的。的,如果STL用得好,E序可以_很多。既提高?jin)编E的速度Q也提高?jin)编E的准确性?
SCL - Standard Code LibraryQ就是标准程序库。对很多选手来说QSCL可是命根子啊

我觉得STL和SCL都不是坏东西Q但是需要}慎地使用?

我向来不d队员一q队开始用STLQ虽然这U现象普遍存?Q。我认ؓ(f)QSTL的作用是锦上添花Q而不是雪中送炭。比方说Q一个heap写得很熟l的队员Q我觉得他可以偷hQ用一下STL。但是,那些不太?x)写heap的队员,׃应该用STL里的heap。因为,他们真正应该做的是掌握写heap的能力――这才是最本质的代码能力?
学会(x)用STL是g很爽的事情。但是须知有所得必有所失。如果过早地接触STLQ会(x)让你失去很多ȝ代码能力的机?x)?

至于SCLQ我的主张是量不用?
不可否认Q队里确实有一些hSCL用得很好。但是,我至今仍然没有见q一个SCL用得很好Q同时有拥有很强的代码能力的人。同h有所得必有所失,你^时习(fn)惯了(jin)LE序Q必然少?jin)很多自己构思程序的Z(x)Q从而媄(jing)响代码能力的提高?
当然Q我也不是完全反对去使用SCLQ偶?dng)用一下也是可以的Q例如在比赛中。但是,需要注意的是,一定要用自己整理的SCL。我见过有h拿着一本别人整理的SCLQ虽然内容很齐整Q但是我没见他用对过。因本SCL不是他整理的Q他自己都不知道每个E序在用的时候应该注意些什么,于是一用就错?br>

法名言(含义深刻?

1.法的灵――数据结?法=E序

2.剪枝是搜索的关键?

3.可贪则贪?

4.枚D是最Ҏ(gu)实现的,但也是最慢的?

5.N往往需要另辟蹊径?

6.法q不是孤立的Q而是可以l合在一L(fng)?

7.不做烂题水^也会(x)下降Q但不想N永远不会(x)提高?/div>

孟v 2010-10-11 17:37 发表评论
]]>直线分空间问?/title><link>http://www.shnenglu.com/guodongshan/archive/2010/10/11/129414.html</link><dc:creator>孟v</dc:creator><author>孟v</author><pubDate>Mon, 11 Oct 2010 02:45:00 GMT</pubDate><guid>http://www.shnenglu.com/guodongshan/archive/2010/10/11/129414.html</guid><wfw:comment>http://www.shnenglu.com/guodongshan/comments/129414.html</wfw:comment><comments>http://www.shnenglu.com/guodongshan/archive/2010/10/11/129414.html#Feedback</comments><slash:comments>0</slash:comments><wfw:commentRss>http://www.shnenglu.com/guodongshan/comments/commentRss/129414.html</wfw:commentRss><trackback:ping>http://www.shnenglu.com/guodongshan/services/trackbacks/129414.html</trackback:ping><description><![CDATA[<span>问题是这L(fng)Q问?span>n</span>条直U最多能^面分成多个区域Q?span> <br></span>q也是一个很单的递归问题Q?span> L[n] = L[n-1] + n;    (L[0] = 1)<br>    </span>通项公式如下Q?span>L[n] = n * (n + 1) / 2 + 1     ( n>= 0 )<br><br></span></span> <p align=left><span>如果不用直线的话Q用一个一般的折线Q那?span>n</span>个这L(fng)折线最多可以拆分^?span>: <br>         D[n] = L[2*n] - 2 * n;<br>         D[n] = 2 * n ^ 2 - n + 1;<br></span></span></p> <span><br>如果?span>"Z"</span>字型的线Q?span>n</span>个折U最可拆分^面:(x)<span><br><a href="" target=_blank href_cetemp><a href="http://www.shnenglu.com/guodongshan/admin/href_cetemp=" target=_blank href_cetemp ?><a target=_blank>http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=652</a></a><br>         Z[n] = Z[n-1] + 9*n - 8; <br>         Z[n] = (9*n^2 - 7*n + 2) / 2; <br> <div style="BORDER-BOTTOM: #cccccc 1px solid; BORDER-LEFT: #cccccc 1px solid; PADDING-BOTTOM: 4px; BACKGROUND-COLOR: #eeeeee; PADDING-LEFT: 4px; WIDTH: 98%; PADDING-RIGHT: 5px; FONT-SIZE: 13px; WORD-BREAK: break-all; BORDER-TOP: #cccccc 1px solid; BORDER-RIGHT: #cccccc 1px solid; PADDING-TOP: 4px"><span style="COLOR: #008080">1</span> <span style="COLOR: #000000">#include</span><span style="COLOR: #000000"><</span><span style="COLOR: #000000">stdio.h</span><span style="COLOR: #000000">></span><span style="COLOR: #000000"><br></span><span style="COLOR: #008080">2</span> <span style="COLOR: #000000"></span><span style="COLOR: #0000ff">int</span><span style="COLOR: #000000"> main()<br></span><span style="COLOR: #008080">3</span> <span style="COLOR: #000000">{<br></span><span style="COLOR: #008080">4</span> <span style="COLOR: #000000">    </span><span style="COLOR: #0000ff">int</span><span style="COLOR: #000000"> n;<br></span><span style="COLOR: #008080">5</span> <span style="COLOR: #000000">    </span><span style="COLOR: #0000ff">while</span><span style="COLOR: #000000">(scanf(</span><span style="COLOR: #000000">"</span><span style="COLOR: #000000">%d</span><span style="COLOR: #000000">"</span><span style="COLOR: #000000">,</span><span style="COLOR: #000000">&</span><span style="COLOR: #000000">n)</span><span style="COLOR: #000000">!=</span><span style="COLOR: #000000">EOF){<br></span><span style="COLOR: #008080">6</span> <span style="COLOR: #000000">        printf(</span><span style="COLOR: #000000">"</span><span style="COLOR: #000000">%d\n</span><span style="COLOR: #000000">"</span><span style="COLOR: #000000">,(</span><span style="COLOR: #000000">9</span><span style="COLOR: #000000">*</span><span style="COLOR: #000000">n</span><span style="COLOR: #000000">*</span><span style="COLOR: #000000">n</span><span style="COLOR: #000000">-</span><span style="COLOR: #000000">7</span><span style="COLOR: #000000">*</span><span style="COLOR: #000000">n</span><span style="COLOR: #000000">+</span><span style="COLOR: #000000">2</span><span style="COLOR: #000000">)</span><span style="COLOR: #000000">/</span><span style="COLOR: #000000">2</span><span style="COLOR: #000000">);<br></span><span style="COLOR: #008080">7</span> <span style="COLOR: #000000">    }<br></span><span style="COLOR: #008080">8</span> <span style="COLOR: #000000">    </span><span style="COLOR: #0000ff">return</span><span style="COLOR: #000000"> </span><span style="COLOR: #000000">0</span><span style="COLOR: #000000">;<br></span><span style="COLOR: #008080">9</span> <span style="COLOR: #000000">}</span></div> </span></span> <img src ="http://www.shnenglu.com/guodongshan/aggbug/129414.html" width = "1" height = "1" /><br><br><div align=right><a style="text-decoration:none;" href="http://www.shnenglu.com/guodongshan/" target="_blank">孟v</a> 2010-10-11 10:45 <a href="http://www.shnenglu.com/guodongshan/archive/2010/10/11/129414.html#Feedback" target="_blank" style="text-decoration:none;">发表评论</a></div>]]></description></item><item><title>HDU2510 W号三角?/title><link>http://www.shnenglu.com/guodongshan/archive/2010/10/11/129404.html</link><dc:creator>孟v</dc:creator><author>孟v</author><pubDate>Mon, 11 Oct 2010 01:13:00 GMT</pubDate><guid>http://www.shnenglu.com/guodongshan/archive/2010/10/11/129404.html</guid><wfw:comment>http://www.shnenglu.com/guodongshan/comments/129404.html</wfw:comment><comments>http://www.shnenglu.com/guodongshan/archive/2010/10/11/129404.html#Feedback</comments><slash:comments>0</slash:comments><wfw:commentRss>http://www.shnenglu.com/guodongshan/comments/commentRss/129404.html</wfw:commentRss><trackback:ping>http://www.shnenglu.com/guodongshan/services/trackbacks/129404.html</trackback:ping><description><![CDATA[<span>        每个W号三角形都是由它的W一?#8220;</span><span>+,-</span><span>”号分布决定的Q据此可演算出所有分布的三角形,对其q行l计卛_?/span> <p><span>        同时一?/span><span>n</span><span>行三角Ş</span><span>T</span><span>?/span><span>+</span><span>Q?/span><span>-</span><span>号个数分别记?/span><span>pos_num(n),neg_num(n)</span><span>Q其W一行中?/span><span>+</span><span>Q?/span><span>-</span><span>号个数记?/span><span>x(n),y(n)</span><span>Q则可得C式:(x)</span></p> <p><span>        pos_num(n)=x(n)+pos_num(n-1)</span></p> <p><span>        neg_num(n)=y(n)+neg_num(n-1)</span></p> <p><span>        由此Q我们可以从</span><span>n=1</span><span>开始,利用前面</span><span>n=k-1</span><span>的结果,q代求出</span><span>n=k</span><span>的分布情形,然后?/span><span>n=k</span><span>的所有分布统计?br></p> <div style="BORDER-BOTTOM: #cccccc 1px solid; BORDER-LEFT: #cccccc 1px solid; PADDING-BOTTOM: 4px; BACKGROUND-COLOR: #eeeeee; PADDING-LEFT: 4px; WIDTH: 98%; PADDING-RIGHT: 5px; FONT-SIZE: 13px; WORD-BREAK: break-all; BORDER-TOP: #cccccc 1px solid; BORDER-RIGHT: #cccccc 1px solid; PADDING-TOP: 4px"><img align=top src="http://www.shnenglu.com/Images/OutliningIndicators/None.gif"><span style="COLOR: #000000">#include</span><span style="COLOR: #000000"><</span><span style="COLOR: #000000">iostream</span><span style="COLOR: #000000">></span><span style="COLOR: #000000"><br><img align=top src="http://www.shnenglu.com/Images/OutliningIndicators/None.gif">#include</span><span style="COLOR: #000000"><</span><span style="COLOR: #000000">vector</span><span style="COLOR: #000000">></span><span style="COLOR: #000000"><br><img align=top src="http://www.shnenglu.com/Images/OutliningIndicators/None.gif">#include</span><span style="COLOR: #000000"><</span><span style="COLOR: #000000">cmath</span><span style="COLOR: #000000">></span><span style="COLOR: #000000"><br><img align=top src="http://www.shnenglu.com/Images/OutliningIndicators/None.gif"></span><span style="COLOR: #0000ff">using</span><span style="COLOR: #000000"> </span><span style="COLOR: #0000ff">namespace</span><span style="COLOR: #000000"> std;<br><img id=Codehighlighter1_86_159_Open_Image onclick="this.style.display='none'; Codehighlighter1_86_159_Open_Text.style.display='none'; Codehighlighter1_86_159_Closed_Image.style.display='inline'; Codehighlighter1_86_159_Closed_Text.style.display='inline';" align=top src="http://www.shnenglu.com/Images/OutliningIndicators/ExpandedBlockStart.gif"><img style="DISPLAY: none" id=Codehighlighter1_86_159_Closed_Image onclick="this.style.display='none'; Codehighlighter1_86_159_Closed_Text.style.display='none'; Codehighlighter1_86_159_Open_Image.style.display='inline'; Codehighlighter1_86_159_Open_Text.style.display='inline';" align=top src="http://www.shnenglu.com/Images/OutliningIndicators/ContractedBlock.gif"></span><span style="COLOR: #0000ff">struct</span><span style="COLOR: #000000"> record</span><span style="BORDER-BOTTOM: #808080 1px solid; BORDER-LEFT: #808080 1px solid; BACKGROUND-COLOR: #ffffff; DISPLAY: none; BORDER-TOP: #808080 1px solid; BORDER-RIGHT: #808080 1px solid" id=Codehighlighter1_86_159_Closed_Text><img src="http://www.shnenglu.com/Images/dot.gif"></span><span id=Codehighlighter1_86_159_Open_Text><span style="COLOR: #000000">{<br><img align=top src="http://www.shnenglu.com/Images/OutliningIndicators/InBlock.gif">    </span><span style="COLOR: #0000ff">int</span><span style="COLOR: #000000"> pos,neg;<br><img id=Codehighlighter1_128_157_Open_Image onclick="this.style.display='none'; Codehighlighter1_128_157_Open_Text.style.display='none'; Codehighlighter1_128_157_Closed_Image.style.display='inline'; Codehighlighter1_128_157_Closed_Text.style.display='inline';" align=top src="http://www.shnenglu.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif"><img style="DISPLAY: none" id=Codehighlighter1_128_157_Closed_Image onclick="this.style.display='none'; Codehighlighter1_128_157_Closed_Text.style.display='none'; Codehighlighter1_128_157_Open_Image.style.display='inline'; Codehighlighter1_128_157_Open_Text.style.display='inline';" align=top src="http://www.shnenglu.com/Images/OutliningIndicators/ContractedSubBlock.gif">    record(</span><span style="COLOR: #0000ff">int</span><span style="COLOR: #000000"> a,</span><span style="COLOR: #0000ff">int</span><span style="COLOR: #000000"> b)</span><span style="BORDER-BOTTOM: #808080 1px solid; BORDER-LEFT: #808080 1px solid; BACKGROUND-COLOR: #ffffff; DISPLAY: none; BORDER-TOP: #808080 1px solid; BORDER-RIGHT: #808080 1px solid" id=Codehighlighter1_128_157_Closed_Text><img src="http://www.shnenglu.com/Images/dot.gif"></span><span id=Codehighlighter1_128_157_Open_Text><span style="COLOR: #000000">{<br><img align=top src="http://www.shnenglu.com/Images/OutliningIndicators/InBlock.gif">        pos</span><span style="COLOR: #000000">=</span><span style="COLOR: #000000">a;  neg</span><span style="COLOR: #000000">=</span><span style="COLOR: #000000">b;<br><img align=top src="http://www.shnenglu.com/Images/OutliningIndicators/ExpandedSubBlockEnd.gif">    }</span></span><span style="COLOR: #000000"><br><img align=top src="http://www.shnenglu.com/Images/OutliningIndicators/ExpandedBlockEnd.gif">}</span></span><span style="COLOR: #000000">;<br><img align=top src="http://www.shnenglu.com/Images/OutliningIndicators/None.gif"></span><span style="COLOR: #0000ff">int</span><span style="COLOR: #000000"> main()<br><img id=Codehighlighter1_173_1996_Open_Image onclick="this.style.display='none'; Codehighlighter1_173_1996_Open_Text.style.display='none'; Codehighlighter1_173_1996_Closed_Image.style.display='inline'; Codehighlighter1_173_1996_Closed_Text.style.display='inline';" align=top src="http://www.shnenglu.com/Images/OutliningIndicators/ExpandedBlockStart.gif"><img style="DISPLAY: none" id=Codehighlighter1_173_1996_Closed_Image onclick="this.style.display='none'; Codehighlighter1_173_1996_Closed_Text.style.display='none'; Codehighlighter1_173_1996_Open_Image.style.display='inline'; Codehighlighter1_173_1996_Open_Text.style.display='inline';" align=top src="http://www.shnenglu.com/Images/OutliningIndicators/ContractedBlock.gif"></span><span style="BORDER-BOTTOM: #808080 1px solid; BORDER-LEFT: #808080 1px solid; BACKGROUND-COLOR: #ffffff; DISPLAY: none; BORDER-TOP: #808080 1px solid; BORDER-RIGHT: #808080 1px solid" id=Codehighlighter1_173_1996_Closed_Text><img src="http://www.shnenglu.com/Images/dot.gif"></span><span id=Codehighlighter1_173_1996_Open_Text><span style="COLOR: #000000">{<br><img align=top src="http://www.shnenglu.com/Images/OutliningIndicators/InBlock.gif">    </span><span style="COLOR: #0000ff">int</span><span style="COLOR: #000000"> n,i,j,k,sum;vector</span><span style="COLOR: #000000"><</span><span style="COLOR: #000000">record</span><span style="COLOR: #000000">></span><span style="COLOR: #000000"> v;<br><img align=top src="http://www.shnenglu.com/Images/OutliningIndicators/InBlock.gif">    </span><span style="COLOR: #0000ff">for</span><span style="COLOR: #000000">(</span><span style="COLOR: #0000ff">int</span><span style="COLOR: #000000"> m</span><span style="COLOR: #000000">=</span><span style="COLOR: #000000">1</span><span style="COLOR: #000000">;m</span><span style="COLOR: #000000"><=</span><span style="COLOR: #000000">24</span><span style="COLOR: #000000">;m</span><span style="COLOR: #000000">++</span><span style="COLOR: #000000">)<br><img id=Codehighlighter1_244_1980_Open_Image onclick="this.style.display='none'; Codehighlighter1_244_1980_Open_Text.style.display='none'; Codehighlighter1_244_1980_Closed_Image.style.display='inline'; Codehighlighter1_244_1980_Closed_Text.style.display='inline';" align=top src="http://www.shnenglu.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif"><img style="DISPLAY: none" id=Codehighlighter1_244_1980_Closed_Image onclick="this.style.display='none'; Codehighlighter1_244_1980_Closed_Text.style.display='none'; Codehighlighter1_244_1980_Open_Image.style.display='inline'; Codehighlighter1_244_1980_Open_Text.style.display='inline';" align=top src="http://www.shnenglu.com/Images/OutliningIndicators/ContractedSubBlock.gif">    </span><span style="BORDER-BOTTOM: #808080 1px solid; BORDER-LEFT: #808080 1px solid; BACKGROUND-COLOR: #ffffff; DISPLAY: none; BORDER-TOP: #808080 1px solid; BORDER-RIGHT: #808080 1px solid" id=Codehighlighter1_244_1980_Closed_Text><img src="http://www.shnenglu.com/Images/dot.gif"></span><span id=Codehighlighter1_244_1980_Open_Text><span style="COLOR: #000000">{<br><img align=top src="http://www.shnenglu.com/Images/OutliningIndicators/InBlock.gif">        n</span><span style="COLOR: #000000">=</span><span style="COLOR: #000000">m;<br><img id=Codehighlighter1_285_350_Open_Image onclick="this.style.display='none'; Codehighlighter1_285_350_Open_Text.style.display='none'; Codehighlighter1_285_350_Closed_Image.style.display='inline'; Codehighlighter1_285_350_Closed_Text.style.display='inline';" align=top src="http://www.shnenglu.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif"><img style="DISPLAY: none" id=Codehighlighter1_285_350_Closed_Image onclick="this.style.display='none'; Codehighlighter1_285_350_Closed_Text.style.display='none'; Codehighlighter1_285_350_Open_Image.style.display='inline'; Codehighlighter1_285_350_Open_Text.style.display='inline';" align=top src="http://www.shnenglu.com/Images/OutliningIndicators/ContractedSubBlock.gif">        </span><span style="COLOR: #0000ff">if</span><span style="COLOR: #000000">((n</span><span style="COLOR: #000000">*</span><span style="COLOR: #000000">(n</span><span style="COLOR: #000000">+</span><span style="COLOR: #000000">1</span><span style="COLOR: #000000">))</span><span style="COLOR: #000000">%</span><span style="COLOR: #000000">4</span><span style="COLOR: #000000">!=</span><span style="COLOR: #000000">0</span><span style="COLOR: #000000">)</span><span style="BORDER-BOTTOM: #808080 1px solid; BORDER-LEFT: #808080 1px solid; BACKGROUND-COLOR: #ffffff; DISPLAY: none; BORDER-TOP: #808080 1px solid; BORDER-RIGHT: #808080 1px solid" id=Codehighlighter1_285_350_Closed_Text><img src="http://www.shnenglu.com/Images/dot.gif"></span><span id=Codehighlighter1_285_350_Open_Text><span style="COLOR: #000000">{<br><img align=top src="http://www.shnenglu.com/Images/OutliningIndicators/InBlock.gif">            cout</span><span style="COLOR: #000000"><<</span><span style="COLOR: #000000">n</span><span style="COLOR: #000000"><<</span><span style="COLOR: #000000">"</span><span style="COLOR: #000000"> 0</span><span style="COLOR: #000000">"</span><span style="COLOR: #000000"><<</span><span style="COLOR: #000000">endl;<br><img align=top src="http://www.shnenglu.com/Images/OutliningIndicators/InBlock.gif">            </span><span style="COLOR: #0000ff">continue</span><span style="COLOR: #000000">;<br><img align=top src="http://www.shnenglu.com/Images/OutliningIndicators/ExpandedSubBlockEnd.gif">        }</span></span><span style="COLOR: #000000"><br><img align=top src="http://www.shnenglu.com/Images/OutliningIndicators/InBlock.gif">        vector</span><span style="COLOR: #000000"><</span><span style="COLOR: #000000">record</span><span style="COLOR: #000000">></span><span style="COLOR: #000000"> v;<br><img align=top src="http://www.shnenglu.com/Images/OutliningIndicators/InBlock.gif">        record r1(</span><span style="COLOR: #000000">0</span><span style="COLOR: #000000">,</span><span style="COLOR: #000000">1</span><span style="COLOR: #000000">);</span><span style="COLOR: #008000">//</span><span style="COLOR: #008000">n=1的情?/span><span style="COLOR: #008000"><br><img align=top src="http://www.shnenglu.com/Images/OutliningIndicators/InBlock.gif"></span><span style="COLOR: #000000">        v.push_back(r1);<br><img align=top src="http://www.shnenglu.com/Images/OutliningIndicators/InBlock.gif">        record r2(</span><span style="COLOR: #000000">1</span><span style="COLOR: #000000">,</span><span style="COLOR: #000000">0</span><span style="COLOR: #000000">);<br><img align=top src="http://www.shnenglu.com/Images/OutliningIndicators/InBlock.gif">        v.push_back(r2);<br><img align=top src="http://www.shnenglu.com/Images/OutliningIndicators/InBlock.gif">        </span><span style="COLOR: #0000ff">for</span><span style="COLOR: #000000">(i</span><span style="COLOR: #000000">=</span><span style="COLOR: #000000">2</span><span style="COLOR: #000000">;i</span><span style="COLOR: #000000"><=</span><span style="COLOR: #000000">n;i</span><span style="COLOR: #000000">++</span><span style="COLOR: #000000">)</span><span style="COLOR: #008000">//</span><span style="COLOR: #008000">计算到n的所有情?/span><span style="COLOR: #008000"><br><img id=Codehighlighter1_529_1545_Open_Image onclick="this.style.display='none'; Codehighlighter1_529_1545_Open_Text.style.display='none'; Codehighlighter1_529_1545_Closed_Image.style.display='inline'; Codehighlighter1_529_1545_Closed_Text.style.display='inline';" align=top src="http://www.shnenglu.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif"><img style="DISPLAY: none" id=Codehighlighter1_529_1545_Closed_Image onclick="this.style.display='none'; Codehighlighter1_529_1545_Closed_Text.style.display='none'; Codehighlighter1_529_1545_Open_Image.style.display='inline'; Codehighlighter1_529_1545_Open_Text.style.display='inline';" align=top src="http://www.shnenglu.com/Images/OutliningIndicators/ContractedSubBlock.gif"></span><span style="COLOR: #000000">        </span><span style="BORDER-BOTTOM: #808080 1px solid; BORDER-LEFT: #808080 1px solid; BACKGROUND-COLOR: #ffffff; DISPLAY: none; BORDER-TOP: #808080 1px solid; BORDER-RIGHT: #808080 1px solid" id=Codehighlighter1_529_1545_Closed_Text><img src="http://www.shnenglu.com/Images/dot.gif"></span><span id=Codehighlighter1_529_1545_Open_Text><span style="COLOR: #000000">{<br><img align=top src="http://www.shnenglu.com/Images/OutliningIndicators/InBlock.gif">            </span><span style="COLOR: #0000ff">int</span><span style="COLOR: #000000"> </span><span style="COLOR: #000000">*</span><span style="COLOR: #000000"> trip</span><span style="COLOR: #000000">=</span><span style="COLOR: #0000ff">new</span><span style="COLOR: #000000"> </span><span style="COLOR: #0000ff">int</span><span style="COLOR: #000000">[i];<br><img align=top src="http://www.shnenglu.com/Images/OutliningIndicators/InBlock.gif">            </span><span style="COLOR: #0000ff">int</span><span style="COLOR: #000000"> sum_i</span><span style="COLOR: #000000">=</span><span style="COLOR: #000000">(</span><span style="COLOR: #0000ff">int</span><span style="COLOR: #000000">)pow(</span><span style="COLOR: #000000">2.0</span><span style="COLOR: #000000">,i</span><span style="COLOR: #000000">*</span><span style="COLOR: #000000">1.0</span><span style="COLOR: #000000">);<br><img align=top src="http://www.shnenglu.com/Images/OutliningIndicators/InBlock.gif">            </span><span style="COLOR: #0000ff">for</span><span style="COLOR: #000000">(j</span><span style="COLOR: #000000">=</span><span style="COLOR: #000000">0</span><span style="COLOR: #000000">;j</span><span style="COLOR: #000000"><</span><span style="COLOR: #000000">sum_i;j</span><span style="COLOR: #000000">++</span><span style="COLOR: #000000">)</span><span style="COLOR: #008000">//</span><span style="COLOR: #008000">WjU分?/span><span style="COLOR: #008000"><br><img id=Codehighlighter1_661_1522_Open_Image onclick="this.style.display='none'; Codehighlighter1_661_1522_Open_Text.style.display='none'; Codehighlighter1_661_1522_Closed_Image.style.display='inline'; Codehighlighter1_661_1522_Closed_Text.style.display='inline';" align=top src="http://www.shnenglu.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif"><img style="DISPLAY: none" id=Codehighlighter1_661_1522_Closed_Image onclick="this.style.display='none'; Codehighlighter1_661_1522_Closed_Text.style.display='none'; Codehighlighter1_661_1522_Open_Image.style.display='inline'; Codehighlighter1_661_1522_Open_Text.style.display='inline';" align=top src="http://www.shnenglu.com/Images/OutliningIndicators/ContractedSubBlock.gif"></span><span style="COLOR: #000000">            </span><span style="BORDER-BOTTOM: #808080 1px solid; BORDER-LEFT: #808080 1px solid; BACKGROUND-COLOR: #ffffff; DISPLAY: none; BORDER-TOP: #808080 1px solid; BORDER-RIGHT: #808080 1px solid" id=Codehighlighter1_661_1522_Closed_Text><img src="http://www.shnenglu.com/Images/dot.gif"></span><span id=Codehighlighter1_661_1522_Open_Text><span style="COLOR: #000000">{<br><img align=top src="http://www.shnenglu.com/Images/OutliningIndicators/InBlock.gif">                </span><span style="COLOR: #0000ff">int</span><span style="COLOR: #000000"> temp1</span><span style="COLOR: #000000">=</span><span style="COLOR: #000000">j, temp2</span><span style="COLOR: #000000">=</span><span style="COLOR: #000000">i;<br><img align=top src="http://www.shnenglu.com/Images/OutliningIndicators/InBlock.gif">                </span><span style="COLOR: #0000ff">int</span><span style="COLOR: #000000"> x</span><span style="COLOR: #000000">=</span><span style="COLOR: #000000">0</span><span style="COLOR: #000000">,  y</span><span style="COLOR: #000000">=</span><span style="COLOR: #000000">0</span><span style="COLOR: #000000">; </span><span style="COLOR: #008000">//</span><span style="COLOR: #008000">记录+Q?的个?/span><span style="COLOR: #008000"><br><img align=top src="http://www.shnenglu.com/Images/OutliningIndicators/InBlock.gif"></span><span style="COLOR: #000000">                </span><span style="COLOR: #0000ff">while</span><span style="COLOR: #000000">(temp1)<br><img id=Codehighlighter1_788_1036_Open_Image onclick="this.style.display='none'; Codehighlighter1_788_1036_Open_Text.style.display='none'; Codehighlighter1_788_1036_Closed_Image.style.display='inline'; Codehighlighter1_788_1036_Closed_Text.style.display='inline';" align=top src="http://www.shnenglu.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif"><img style="DISPLAY: none" id=Codehighlighter1_788_1036_Closed_Image onclick="this.style.display='none'; Codehighlighter1_788_1036_Closed_Text.style.display='none'; Codehighlighter1_788_1036_Open_Image.style.display='inline'; Codehighlighter1_788_1036_Open_Text.style.display='inline';" align=top src="http://www.shnenglu.com/Images/OutliningIndicators/ContractedSubBlock.gif">                </span><span style="BORDER-BOTTOM: #808080 1px solid; BORDER-LEFT: #808080 1px solid; BACKGROUND-COLOR: #ffffff; DISPLAY: none; BORDER-TOP: #808080 1px solid; BORDER-RIGHT: #808080 1px solid" id=Codehighlighter1_788_1036_Closed_Text><img src="http://www.shnenglu.com/Images/dot.gif"></span><span id=Codehighlighter1_788_1036_Open_Text><span style="COLOR: #000000">{<br><img id=Codehighlighter1_824_892_Open_Image onclick="this.style.display='none'; Codehighlighter1_824_892_Open_Text.style.display='none'; Codehighlighter1_824_892_Closed_Image.style.display='inline'; Codehighlighter1_824_892_Closed_Text.style.display='inline';" align=top src="http://www.shnenglu.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif"><img style="DISPLAY: none" id=Codehighlighter1_824_892_Closed_Image onclick="this.style.display='none'; Codehighlighter1_824_892_Closed_Text.style.display='none'; Codehighlighter1_824_892_Open_Image.style.display='inline'; Codehighlighter1_824_892_Open_Text.style.display='inline';" align=top src="http://www.shnenglu.com/Images/OutliningIndicators/ContractedSubBlock.gif">                    </span><span style="COLOR: #0000ff">if</span><span style="COLOR: #000000">(temp1</span><span style="COLOR: #000000">%</span><span style="COLOR: #000000">2</span><span style="COLOR: #000000">==</span><span style="COLOR: #000000">0</span><span style="COLOR: #000000">)</span><span style="BORDER-BOTTOM: #808080 1px solid; BORDER-LEFT: #808080 1px solid; BACKGROUND-COLOR: #ffffff; DISPLAY: none; BORDER-TOP: #808080 1px solid; BORDER-RIGHT: #808080 1px solid" id=Codehighlighter1_824_892_Closed_Text><img src="http://www.shnenglu.com/Images/dot.gif"></span><span id=Codehighlighter1_824_892_Open_Text><span style="COLOR: #000000">{<br><img align=top src="http://www.shnenglu.com/Images/OutliningIndicators/InBlock.gif">                        trip[</span><span style="COLOR: #000000">--</span><span style="COLOR: #000000">temp2]</span><span style="COLOR: #000000">=</span><span style="COLOR: #000000">0</span><span style="COLOR: #000000">; y</span><span style="COLOR: #000000">++</span><span style="COLOR: #000000">;<br><img align=top src="http://www.shnenglu.com/Images/OutliningIndicators/ExpandedSubBlockEnd.gif">                    }</span></span><span style="COLOR: #000000"><br><img id=Codehighlighter1_919_988_Open_Image onclick="this.style.display='none'; Codehighlighter1_919_988_Open_Text.style.display='none'; Codehighlighter1_919_988_Closed_Image.style.display='inline'; Codehighlighter1_919_988_Closed_Text.style.display='inline';" align=top src="http://www.shnenglu.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif"><img style="DISPLAY: none" id=Codehighlighter1_919_988_Closed_Image onclick="this.style.display='none'; Codehighlighter1_919_988_Closed_Text.style.display='none'; Codehighlighter1_919_988_Open_Image.style.display='inline'; Codehighlighter1_919_988_Open_Text.style.display='inline';" align=top src="http://www.shnenglu.com/Images/OutliningIndicators/ContractedSubBlock.gif">                    </span><span style="COLOR: #0000ff">else</span><span style="COLOR: #000000"> </span><span style="BORDER-BOTTOM: #808080 1px solid; BORDER-LEFT: #808080 1px solid; BACKGROUND-COLOR: #ffffff; DISPLAY: none; BORDER-TOP: #808080 1px solid; BORDER-RIGHT: #808080 1px solid" id=Codehighlighter1_919_988_Closed_Text><img src="http://www.shnenglu.com/Images/dot.gif"></span><span id=Codehighlighter1_919_988_Open_Text><span style="COLOR: #000000">{<br><img align=top src="http://www.shnenglu.com/Images/OutliningIndicators/InBlock.gif">                        trip[</span><span style="COLOR: #000000">--</span><span style="COLOR: #000000">temp2]</span><span style="COLOR: #000000">=</span><span style="COLOR: #000000">1</span><span style="COLOR: #000000">;  x</span><span style="COLOR: #000000">++</span><span style="COLOR: #000000">;<br><img align=top src="http://www.shnenglu.com/Images/OutliningIndicators/ExpandedSubBlockEnd.gif">                    }</span></span><span style="COLOR: #000000"><br><img align=top src="http://www.shnenglu.com/Images/OutliningIndicators/InBlock.gif">                    temp1</span><span style="COLOR: #000000">/=</span><span style="COLOR: #000000">2</span><span style="COLOR: #000000">;<br><img align=top src="http://www.shnenglu.com/Images/OutliningIndicators/ExpandedSubBlockEnd.gif">                }</span></span><span style="COLOR: #000000"><br><img align=top src="http://www.shnenglu.com/Images/OutliningIndicators/InBlock.gif">                </span><span style="COLOR: #0000ff">for</span><span style="COLOR: #000000">(k</span><span style="COLOR: #000000">=</span><span style="COLOR: #000000">0</span><span style="COLOR: #000000">;k</span><span style="COLOR: #000000"><</span><span style="COLOR: #000000">temp2;k</span><span style="COLOR: #000000">++</span><span style="COLOR: #000000">)<br><img align=top src="http://www.shnenglu.com/Images/OutliningIndicators/InBlock.gif">                    y</span><span style="COLOR: #000000">++</span><span style="COLOR: #000000">,  trip[k]</span><span style="COLOR: #000000">=</span><span style="COLOR: #000000">0</span><span style="COLOR: #000000">;<br><img align=top src="http://www.shnenglu.com/Images/OutliningIndicators/InBlock.gif">                </span><span style="COLOR: #0000ff">int</span><span style="COLOR: #000000"> idx</span><span style="COLOR: #000000">=</span><span style="COLOR: #000000">0</span><span style="COLOR: #000000">;<br><img align=top src="http://www.shnenglu.com/Images/OutliningIndicators/InBlock.gif">                </span><span style="COLOR: #0000ff">for</span><span style="COLOR: #000000">(k</span><span style="COLOR: #000000">=</span><span style="COLOR: #000000">0</span><span style="COLOR: #000000">;k</span><span style="COLOR: #000000"><</span><span style="COLOR: #000000">i</span><span style="COLOR: #000000">-</span><span style="COLOR: #000000">1</span><span style="COLOR: #000000">;k</span><span style="COLOR: #000000">++</span><span style="COLOR: #000000">)<br><img id=Codehighlighter1_1190_1327_Open_Image onclick="this.style.display='none'; Codehighlighter1_1190_1327_Open_Text.style.display='none'; Codehighlighter1_1190_1327_Closed_Image.style.display='inline'; Codehighlighter1_1190_1327_Closed_Text.style.display='inline';" align=top src="http://www.shnenglu.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif"><img style="DISPLAY: none" id=Codehighlighter1_1190_1327_Closed_Image onclick="this.style.display='none'; Codehighlighter1_1190_1327_Closed_Text.style.display='none'; Codehighlighter1_1190_1327_Open_Image.style.display='inline'; Codehighlighter1_1190_1327_Open_Text.style.display='inline';" align=top src="http://www.shnenglu.com/Images/OutliningIndicators/ContractedSubBlock.gif">                </span><span style="BORDER-BOTTOM: #808080 1px solid; BORDER-LEFT: #808080 1px solid; BACKGROUND-COLOR: #ffffff; DISPLAY: none; BORDER-TOP: #808080 1px solid; BORDER-RIGHT: #808080 1px solid" id=Codehighlighter1_1190_1327_Closed_Text><img src="http://www.shnenglu.com/Images/dot.gif"></span><span id=Codehighlighter1_1190_1327_Open_Text><span style="COLOR: #000000">{<br><img align=top src="http://www.shnenglu.com/Images/OutliningIndicators/InBlock.gif">                    </span><span style="COLOR: #0000ff">if</span><span style="COLOR: #000000">(trip[k]</span><span style="COLOR: #000000">+</span><span style="COLOR: #000000">trip[k</span><span style="COLOR: #000000">+</span><span style="COLOR: #000000">1</span><span style="COLOR: #000000">]</span><span style="COLOR: #000000">==</span><span style="COLOR: #000000">1</span><span style="COLOR: #000000">)<br><img align=top src="http://www.shnenglu.com/Images/OutliningIndicators/InBlock.gif">                        idx</span><span style="COLOR: #000000">*=</span><span style="COLOR: #000000">2</span><span style="COLOR: #000000">;<br><img align=top src="http://www.shnenglu.com/Images/OutliningIndicators/InBlock.gif">                    </span><span style="COLOR: #0000ff">else</span><span style="COLOR: #000000">   idx</span><span style="COLOR: #000000">*=</span><span style="COLOR: #000000">2</span><span style="COLOR: #000000">,idx</span><span style="COLOR: #000000">+=</span><span style="COLOR: #000000">1</span><span style="COLOR: #000000">;<br><img align=top src="http://www.shnenglu.com/Images/OutliningIndicators/ExpandedSubBlockEnd.gif">                }</span></span><span style="COLOR: #000000"><br><img align=top src="http://www.shnenglu.com/Images/OutliningIndicators/InBlock.gif">                x</span><span style="COLOR: #000000">+=</span><span style="COLOR: #000000">v[</span><span style="COLOR: #000000">2</span><span style="COLOR: #000000">*</span><span style="COLOR: #000000">((</span><span style="COLOR: #0000ff">int</span><span style="COLOR: #000000">)pow(</span><span style="COLOR: #000000">2.0</span><span style="COLOR: #000000">,i</span><span style="COLOR: #000000">-</span><span style="COLOR: #000000">2.0</span><span style="COLOR: #000000">)</span><span style="COLOR: #000000">-</span><span style="COLOR: #000000">1</span><span style="COLOR: #000000">)</span><span style="COLOR: #000000">+</span><span style="COLOR: #000000">idx].pos;<br><img align=top src="http://www.shnenglu.com/Images/OutliningIndicators/InBlock.gif">                y</span><span style="COLOR: #000000">+=</span><span style="COLOR: #000000">v[</span><span style="COLOR: #000000">2</span><span style="COLOR: #000000">*</span><span style="COLOR: #000000">((</span><span style="COLOR: #0000ff">int</span><span style="COLOR: #000000">)pow(</span><span style="COLOR: #000000">2.0</span><span style="COLOR: #000000">,i</span><span style="COLOR: #000000">-</span><span style="COLOR: #000000">2.0</span><span style="COLOR: #000000">)</span><span style="COLOR: #000000">-</span><span style="COLOR: #000000">1</span><span style="COLOR: #000000">)</span><span style="COLOR: #000000">+</span><span style="COLOR: #000000">idx].neg;<br><img align=top src="http://www.shnenglu.com/Images/OutliningIndicators/InBlock.gif">                record r(x,y);<br><img align=top src="http://www.shnenglu.com/Images/OutliningIndicators/InBlock.gif">                v.push_back(r);    <br><img align=top src="http://www.shnenglu.com/Images/OutliningIndicators/ExpandedSubBlockEnd.gif">            }</span></span><span style="COLOR: #000000"><br><img align=top src="http://www.shnenglu.com/Images/OutliningIndicators/InBlock.gif">            <br><img align=top src="http://www.shnenglu.com/Images/OutliningIndicators/ExpandedSubBlockEnd.gif">        }</span></span><span style="COLOR: #000000"><br><img id=Codehighlighter1_1555_1739_Open_Image onclick="this.style.display='none'; Codehighlighter1_1555_1739_Open_Text.style.display='none'; Codehighlighter1_1555_1739_Closed_Image.style.display='inline'; Codehighlighter1_1555_1739_Closed_Text.style.display='inline';" align=top src="http://www.shnenglu.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif"><img style="DISPLAY: none" id=Codehighlighter1_1555_1739_Closed_Image onclick="this.style.display='none'; Codehighlighter1_1555_1739_Closed_Text.style.display='none'; Codehighlighter1_1555_1739_Open_Image.style.display='inline'; Codehighlighter1_1555_1739_Open_Text.style.display='inline';" align=top src="http://www.shnenglu.com/Images/OutliningIndicators/ContractedSubBlock.gif">        </span><span style="BORDER-BOTTOM: #808080 1px solid; BORDER-LEFT: #808080 1px solid; BACKGROUND-COLOR: #ffffff; DISPLAY: none; BORDER-TOP: #808080 1px solid; BORDER-RIGHT: #808080 1px solid" id=Codehighlighter1_1555_1739_Closed_Text>/**/</span><span id=Codehighlighter1_1555_1739_Open_Text><span style="COLOR: #008000">/*</span><span style="COLOR: #008000">if(n==3){<br><img align=top src="http://www.shnenglu.com/Images/OutliningIndicators/InBlock.gif">            int star=2*((int)pow(2.0,n-1.0)-1);<br><img align=top src="http://www.shnenglu.com/Images/OutliningIndicators/InBlock.gif">            for(j=0;j<(int)pow(2.0,n*1.0);j++)<br><img align=top src="http://www.shnenglu.com/Images/OutliningIndicators/InBlock.gif">                printf("---%d %d\n",v[star+j].pos,v[star+j].neg);<br><img align=top src="http://www.shnenglu.com/Images/OutliningIndicators/ExpandedSubBlockEnd.gif">        }</span><span style="COLOR: #008000">*/</span></span><span style="COLOR: #000000"><br><img align=top src="http://www.shnenglu.com/Images/OutliningIndicators/InBlock.gif">        </span><span style="COLOR: #0000ff">int</span><span style="COLOR: #000000"> </span><span style="COLOR: #0000ff">base</span><span style="COLOR: #000000">=</span><span style="COLOR: #000000">2</span><span style="COLOR: #000000">*</span><span style="COLOR: #000000">((</span><span style="COLOR: #0000ff">int</span><span style="COLOR: #000000">)pow(</span><span style="COLOR: #000000">2.0</span><span style="COLOR: #000000">,n</span><span style="COLOR: #000000">-</span><span style="COLOR: #000000">1.0</span><span style="COLOR: #000000">)</span><span style="COLOR: #000000">-</span><span style="COLOR: #000000">1</span><span style="COLOR: #000000">);<br><img align=top src="http://www.shnenglu.com/Images/OutliningIndicators/InBlock.gif">        </span><span style="COLOR: #0000ff">int</span><span style="COLOR: #000000"> num</span><span style="COLOR: #000000">=</span><span style="COLOR: #000000">(</span><span style="COLOR: #0000ff">int</span><span style="COLOR: #000000">)pow(</span><span style="COLOR: #000000">2.0</span><span style="COLOR: #000000">,n</span><span style="COLOR: #000000">*</span><span style="COLOR: #000000">1.0</span><span style="COLOR: #000000">);<br><img align=top src="http://www.shnenglu.com/Images/OutliningIndicators/InBlock.gif">        sum</span><span style="COLOR: #000000">=</span><span style="COLOR: #000000">0</span><span style="COLOR: #000000">;<br><img id=Codehighlighter1_1863_1941_Open_Image onclick="this.style.display='none'; Codehighlighter1_1863_1941_Open_Text.style.display='none'; Codehighlighter1_1863_1941_Closed_Image.style.display='inline'; Codehighlighter1_1863_1941_Closed_Text.style.display='inline';" align=top src="http://www.shnenglu.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif"><img style="DISPLAY: none" id=Codehighlighter1_1863_1941_Closed_Image onclick="this.style.display='none'; Codehighlighter1_1863_1941_Closed_Text.style.display='none'; Codehighlighter1_1863_1941_Open_Image.style.display='inline'; Codehighlighter1_1863_1941_Open_Text.style.display='inline';" align=top src="http://www.shnenglu.com/Images/OutliningIndicators/ContractedSubBlock.gif">        </span><span style="COLOR: #0000ff">for</span><span style="COLOR: #000000">(i</span><span style="COLOR: #000000">=</span><span style="COLOR: #000000">0</span><span style="COLOR: #000000">;i</span><span style="COLOR: #000000"><</span><span style="COLOR: #000000">num;i</span><span style="COLOR: #000000">++</span><span style="COLOR: #000000">)</span><span style="BORDER-BOTTOM: #808080 1px solid; BORDER-LEFT: #808080 1px solid; BACKGROUND-COLOR: #ffffff; DISPLAY: none; BORDER-TOP: #808080 1px solid; BORDER-RIGHT: #808080 1px solid" id=Codehighlighter1_1863_1941_Closed_Text><img src="http://www.shnenglu.com/Images/dot.gif"></span><span id=Codehighlighter1_1863_1941_Open_Text><span style="COLOR: #000000">{<br><img align=top src="http://www.shnenglu.com/Images/OutliningIndicators/InBlock.gif">            </span><span style="COLOR: #0000ff">if</span><span style="COLOR: #000000">(v[</span><span style="COLOR: #0000ff">base</span><span style="COLOR: #000000">+</span><span style="COLOR: #000000">i].pos</span><span style="COLOR: #000000">==</span><span style="COLOR: #000000">v[</span><span style="COLOR: #0000ff">base</span><span style="COLOR: #000000">+</span><span style="COLOR: #000000">i].neg)<br><img align=top src="http://www.shnenglu.com/Images/OutliningIndicators/InBlock.gif">                sum</span><span style="COLOR: #000000">++</span><span style="COLOR: #000000">;<br><img align=top src="http://www.shnenglu.com/Images/OutliningIndicators/ExpandedSubBlockEnd.gif">        }</span></span><span style="COLOR: #000000"><br><img align=top src="http://www.shnenglu.com/Images/OutliningIndicators/InBlock.gif">        cout</span><span style="COLOR: #000000"><<</span><span style="COLOR: #000000">n</span><span style="COLOR: #000000"><<</span><span style="COLOR: #000000">"</span><span style="COLOR: #000000"> </span><span style="COLOR: #000000">"</span><span style="COLOR: #000000"><<</span><span style="COLOR: #000000">sum</span><span style="COLOR: #000000"><<</span><span style="COLOR: #000000">endl;<br><img align=top src="http://www.shnenglu.com/Images/OutliningIndicators/ExpandedSubBlockEnd.gif">    }</span></span><span style="COLOR: #000000"><br><img align=top src="http://www.shnenglu.com/Images/OutliningIndicators/InBlock.gif">    </span><span style="COLOR: #0000ff">return</span><span style="COLOR: #000000"> </span><span style="COLOR: #000000">0</span><span style="COLOR: #000000">;<br><img align=top src="http://www.shnenglu.com/Images/OutliningIndicators/ExpandedBlockEnd.gif">}</span></span></div> </span> <p style="TEXT-INDENT: 21pt; MARGIN: 0cm 0cm 0pt" class=MsoNormal><span style="FONT-FAMILY: 宋体; mso-ascii-font-family: 'Times New Roman'; mso-hansi-font-family: 'Times New Roman'">题中Q?/span><span lang=EN-US>n<=24</span><span style="FONT-FAMILY: 宋体; mso-ascii-font-family: 'Times New Roman'; mso-hansi-font-family: 'Times New Roman'">Q时间空间均有限Ӟ我们可以先求出所有结果,然后保存到数l直接取来输出。这?/span><span lang=EN-US>ACM</span><span style="FONT-FAMILY: 宋体; mso-ascii-font-family: 'Times New Roman'; mso-hansi-font-family: 'Times New Roman'">题中很常见的情况?/span></p> <div style="BORDER-BOTTOM: #cccccc 1px solid; BORDER-LEFT: #cccccc 1px solid; PADDING-BOTTOM: 4px; BACKGROUND-COLOR: #eeeeee; PADDING-LEFT: 4px; WIDTH: 98%; PADDING-RIGHT: 5px; FONT-SIZE: 13px; WORD-BREAK: break-all; BORDER-TOP: #cccccc 1px solid; BORDER-RIGHT: #cccccc 1px solid; PADDING-TOP: 4px"><span style="COLOR: #008080"> 1</span> <span style="COLOR: #000000">#include</span><span style="COLOR: #000000"><</span><span style="COLOR: #000000">stdio.h</span><span style="COLOR: #000000">></span><span style="COLOR: #000000"><br></span><span style="COLOR: #008080"> 2</span> <span style="COLOR: #000000"></span><span style="COLOR: #0000ff">int</span><span style="COLOR: #000000"> res[</span><span style="COLOR: #000000">25</span><span style="COLOR: #000000">]</span><span style="COLOR: #000000">=</span><span style="COLOR: #000000">{</span><span style="COLOR: #000000">0</span><span style="COLOR: #000000">,</span><span style="COLOR: #000000">0</span><span style="COLOR: #000000">,</span><span style="COLOR: #000000">0</span><span style="COLOR: #000000">,</span><span style="COLOR: #000000">4</span><span style="COLOR: #000000">,</span><span style="COLOR: #000000">6</span><span style="COLOR: #000000">,</span><span style="COLOR: #000000">0</span><span style="COLOR: #000000">,</span><span style="COLOR: #000000">0</span><span style="COLOR: #000000">,</span><span style="COLOR: #000000">12</span><span style="COLOR: #000000">,</span><span style="COLOR: #000000">40</span><span style="COLOR: #000000">,</span><span style="COLOR: #000000">0</span><span style="COLOR: #000000">,</span><span style="COLOR: #000000">0</span><span style="COLOR: #000000">,</span><span style="COLOR: #000000">171</span><span style="COLOR: #000000">,</span><span style="COLOR: #000000">410</span><span style="COLOR: #000000">,<br></span><span style="COLOR: #008080"> 3</span> <span style="COLOR: #000000">    </span><span style="COLOR: #000000">0</span><span style="COLOR: #000000">,</span><span style="COLOR: #000000">0</span><span style="COLOR: #000000">,</span><span style="COLOR: #000000">1896</span><span style="COLOR: #000000">,</span><span style="COLOR: #000000">5160</span><span style="COLOR: #000000">,</span><span style="COLOR: #000000">0</span><span style="COLOR: #000000">,</span><span style="COLOR: #000000">0</span><span style="COLOR: #000000">,</span><span style="COLOR: #000000">32757</span><span style="COLOR: #000000">,</span><span style="COLOR: #000000">59984</span><span style="COLOR: #000000">,</span><span style="COLOR: #000000">0</span><span style="COLOR: #000000">,</span><span style="COLOR: #000000">0</span><span style="COLOR: #000000">,</span><span style="COLOR: #000000">431095</span><span style="COLOR: #000000">,</span><span style="COLOR: #000000">822229</span><span style="COLOR: #000000">};<br></span><span style="COLOR: #008080"> 4</span> <span style="COLOR: #000000"></span><span style="COLOR: #0000ff">int</span><span style="COLOR: #000000"> main()<br></span><span style="COLOR: #008080"> 5</span> <span style="COLOR: #000000">{<br></span><span style="COLOR: #008080"> 6</span> <span style="COLOR: #000000">    </span><span style="COLOR: #0000ff">int</span><span style="COLOR: #000000"> n;<br></span><span style="COLOR: #008080"> 7</span> <span style="COLOR: #000000">    </span><span style="COLOR: #0000ff">while</span><span style="COLOR: #000000">(scanf(</span><span style="COLOR: #000000">"</span><span style="COLOR: #000000">%d</span><span style="COLOR: #000000">"</span><span style="COLOR: #000000">,</span><span style="COLOR: #000000">&</span><span style="COLOR: #000000">n),n)<br></span><span style="COLOR: #008080"> 8</span> <span style="COLOR: #000000">    {<br></span><span style="COLOR: #008080"> 9</span> <span style="COLOR: #000000">        printf(</span><span style="COLOR: #000000">"</span><span style="COLOR: #000000">%d %d\n</span><span style="COLOR: #000000">"</span><span style="COLOR: #000000">,n,res[n]);<br></span><span style="COLOR: #008080">10</span> <span style="COLOR: #000000">    }<br></span><span style="COLOR: #008080">11</span> <span style="COLOR: #000000">    </span><span style="COLOR: #0000ff">return</span><span style="COLOR: #000000"> </span><span style="COLOR: #000000">0</span><span style="COLOR: #000000">;<br></span><span style="COLOR: #008080">12</span> <span style="COLOR: #000000">}</span></div> <img src ="http://www.shnenglu.com/guodongshan/aggbug/129404.html" width = "1" height = "1" /><br><br><div align=right><a style="text-decoration:none;" href="http://www.shnenglu.com/guodongshan/" target="_blank">孟v</a> 2010-10-11 09:13 <a href="http://www.shnenglu.com/guodongshan/archive/2010/10/11/129404.html#Feedback" target="_blank" style="text-decoration:none;">发表评论</a></div>]]></description></item></channel></rss> <footer> <div class="friendship-link"> <p>лǵվܻԴȤ</p> <a href="http://www.shnenglu.com/" title="精品视频久久久久">精品视频久久久久</a> <div class="friend-links"> </div> </div> </footer> <a href="http://www.xiangzen.cn" target="_blank">99þþƷѾƷһ</a>| <a href="http://www.wxyuyang.com.cn" target="_blank">þպƬ</a>| <a href="http://www.yylsax.cn" target="_blank">þþƷAVũ帾Ů</a>| <a href="http://www.xingezhijia.cn" target="_blank">ó˾þAvѸ</a>| <a href="http://www.haolook.cn" target="_blank">97Ʒ˾þô߽app </a>| <a href="http://www.by2043.cn" target="_blank">þˬˬƬAV鷳</a>| <a href="http://www.kfak.cn" target="_blank">ԭƷ99þþƷ66</a>| <a href="http://www.52yydy.cn" target="_blank">ƷþþþjkƷ</a>| <a href="http://www.marsit.cn" target="_blank">þþþƷþþþþ</a>| <a href="http://www.smscx.cn" target="_blank">þݺҹҹ96׽ </a>| <a href="http://www.hunxiaodansang.cn" target="_blank">99þþƷѿ</a>| <a href="http://www.hybdh.cn" target="_blank">ձƷþþþӰԺձ</a>| <a href="http://www.hxstone.com.cn" target="_blank">ҹƷþþþþ99</a>| <a href="http://www.hjte.cn" target="_blank">ľƷþþþùַ</a>| <a href="http://www.huiseng.cn" target="_blank">һɫþ88ۺ޾Ʒ </a>| <a href="http://www.yxwelding.com.cn" target="_blank">þþþþþ97</a>| <a href="http://www.seese.cn" target="_blank">þñþۺ</a>| <a href="http://www.liushishipin.cn" target="_blank">þۺɫˮ99ž</a>| <a href="http://www.aigoua.cn" target="_blank">պŷۺϾþӰԺDs</a>| <a href="http://www.2jg.com.cn" target="_blank">˾þۺ2020</a>| <a href="http://www.qzlhscqt.cn" target="_blank">ۺҹҹþ</a>| <a href="http://www.bachou.com.cn" target="_blank">Ʒþˬۺ</a>| <a href="http://www.594n.cn" target="_blank">Ʒþþþav</a>| <a href="http://www.deshizhai.cn" target="_blank">ŷ츾XXXXԾþþ </a>| <a href="http://www.etcaisn.cn" target="_blank">þþƷŷƬ</a>| <a href="http://www.gay2000.cn" target="_blank">ƷžžþƵ </a>| <a href="http://www.shejia.net.cn" target="_blank">99þþƷһ</a>| <a href="http://www.07ww.cn" target="_blank">þþƷAV뽿ɫ</a>| <a href="http://www.guangmingtyre.cn" target="_blank">97þùۺϾƷŮ</a>| <a href="http://www.debtee.cn" target="_blank">ɫۺϾþۺ</a>| <a href="http://www.ode.net.cn" target="_blank">þ99Ʒþþþ</a>| <a href="http://www.265z.cn" target="_blank">þùɫavѿ</a>| <a href="http://www.f1-zone.cn" target="_blank">þþþavӰ</a>| <a href="http://www.bulaozhen.cn" target="_blank">þþþƷר</a>| <a href="http://www.020xyk.cn" target="_blank">ƷžžþƵ </a>| <a href="http://www.hybtw.cn" target="_blank">ٸþĻ</a>| <a href="http://www.guhm.cn" target="_blank">ŷպ˾Ʒþþѿ</a>| <a href="http://www.sz5111.cn" target="_blank">þþþAVۺϲҰ </a>| <a href="http://www.rjlmd.cn" target="_blank">ƷۺרƬþþ </a>| <a href="http://www.maituogangwan.cn" target="_blank">AVþþþò</a>| <a href="http://www.sypt59.cn" target="_blank">ղƷþþþþþɫ</a>| <script> (function(){ var bp = document.createElement('script'); var curProtocol = window.location.protocol.split(':')[0]; if (curProtocol === 'https') { bp.src = 'https://zz.bdstatic.com/linksubmit/push.js'; } else { bp.src = 'http://push.zhanzhang.baidu.com/push.js'; } var s = document.getElementsByTagName("script")[0]; s.parentNode.insertBefore(bp, s); })(); </script> </body>