题目:http://acm.scs.bupt.cn/onlinejudge/showproblem.php?problem_id=1095 题意：这题要在一个无向正权图上找单源最短路，找到目标点后，还要求出到达这个点的最短路径的数量。有重边。 解法：dijkstra+DP。正权图找最短路首先想到dijkstra，然后考虑如何获得最短路数量和怎样处理重边。因为两点间只需一条最的路径就够了，因此记录图的时候可以考虑忽略其他权比较高的路径，只记录最短的那条。并且增加一个二元数组记录相邻点间的最短路径条数。此外有数组d记录起点到各点的最短距离，count记录到达这点的最短路径数。在dijkstra过程中，加入新节点后松弛没找到最短路的点的过程中，考虑如果松弛过程中d[i]==d[pos]+map[pos][i]，则count[i]+=count[pos]*p[pos][i]（此处之前错误写成了count[i]++，-_-!），如果d[i]>d[pos]+map[pos][i]，则count[i]=count[pos]*p[pos][i]。最后输出d[b],count[b]就行，注意各数组初始化，并且注意是两组输出之间有空行，最后一组输出后不用空行，仅换行，这里我也悲剧了一次。

问：随机在0到1之间取数，当第n次取到的数小于等于前n-1次取到的数中的任何一个时停止，求n的期望。 答案：e。解释：另Pn为停止时次数为n的概率，则这个E(n)=1*P1+2*P2+3*P3+…+n*Pn+…。下面将这组数分组，化为:E(n)=(P1+P2+P3+…)+(P2+P3+P4+…)+(P3+P4+P5+…) …。这样就得到了E(n)=P(n>=1)+P(n>=2)+P(n>=3)+…。考虑到前两项的值应为1，因为无论如何游戏进行的次数不可能小于二次。而P(n>=3)=1/2!。原因是若n>=3则前两个数必须单调递减，因此前两个数排列方式有2!种，因而概率为1/2!。n>=k时同理，若n>=k,则前k-1项必须单调递减，因此概率为1/(k-1)!。因此E(n)=1+1/1!+1/2!+1/3!+…=e。这个神奇的结论就得到了，貌似原题叙述的停止条件是第n个数小于前n-1个数中的任何一个，但如果这样叙述，前k个数单调的可能情况就不是1因此概率也就不数1/k!。因而改成小于等于。原文地址是:http://mindyourdecisions.com/blog/2010/11/16/an-interesting-probability-game/

题目:http://poj.org/problem?id=1753题意:在一个4*4的方格阵里，每格里有一个一面白一面黑的棋子，初始状态由输入给出。游戏开始后，每次选择16格中的任何一个，然后将它以及它周围紧相邻的4个棋子翻转（超出边缘的不计）。游戏的目的是将所有色块翻成同一种颜色。问能不能达到游戏目的，如果能输出最少需要的翻拍次数。解法:bfs枚举每种情况。BYR论坛算法版给出的分类是枚举，但这题枚举要采取广搜策略。另外，注意到一共只有16个格，因此可以用一个16位的int存储状态，这样内存就不会超。存储每个状态是否被访问过可以直接用一个2^16个元素的flag数组完成。模拟翻牌过程用位运算即可。代码: Source CodeProblem: 1753 User: gp2593Memory: 1120K Time: 32MSLanguage: GCC Result: Accepted * Source Code #include<stdio.h> #include<stdlib.h> typedef struct node { int box; int time; int max; }NODE; turn(int bo,int positio) { int k,t; t=1<<positio; bo=bo^t; if(positio+4<=15) { k=t<<4; bo=bo^k; } if(positio-4>=0) { k=t>>4; bo=bo^k; } if(positio%4!=0) { k=t>>1; bo=bo^k; } if(positio%4!=3) { k=t<<1; bo=bo^k; […]

昨天开始感冒，浑身无力，感觉不爽。今天写了两个，第一个是单调子序列，就不贴了。第二个是这个DP。题目:http://acm.scs.bupt.cn/onlinejudge/showproblem.php?problem_id=1094题目意思是求一个序列，这个序列满足三个一组，并且每组有一个属性m，这个m=min((a-b)^2+(b-c)^2+(a-c)^2)，其中a，b，c为序列中这组数的值。求得的序列是在N个元素的序列中的K组，使得这K组的m值和最小。解法：DP。考虑到如果abc顺序排列，则m只能取得(a-b)^2或(b-c)^2之一。类似01背包，将每个数当作每个物品，这个物品重量是1。因为决定一组数的m值尽取决于两个元素，因此第三个元素可以在没被选择的数里任意选择。状态转移：dp[i][j]=min(dp[i-2][j-1]+(a[i]+a[i-1])^2,dp[i-1][j-1])。这个状态转移的意思是，当考察了a中前i项并且最多组k队时的最小m值。这里实际上是在决定将a[i],a[i-1]加入组队，还是保持不变。因为这里每个人的重量为1，而最大容量相当于2*K因此，一定可以将背包装满。因此可以得到K组人。代码：点击下载

这个周末很颓废，几乎什么也没干。谴责一下自己。题目:http://acm.scs.bupt.cn/onlinejudge/showproblem.php?problem_id=1036这题就是要求一个稠密图上的最小生成树，并且求在这个生成树上的一个点，要求这个点到其余所有点的距离和最小。题目条件保证生成树唯一。解法：首先求最小生成树，用prim。每加入一个新的节点时，计算这个点到已经加入的所有点的距离。因为最小生成树中任意亮点的通路唯一，因此可以直接与prim中pre数组中的点到其余点做和求出。代码:依然点击这里下载

昨天看牟小盆友的状态里转了个算24的题，题里给了两种结果。题目是10 10 3 2，两个结果是2^-10^3=24，10+10+3!-2=24。看了之后没多想，觉着好玩，就转了，结果白天的时候同学回复了那条状态，才发现，原来这个可以有挺多解法的，当然前提是不能只限制在四则运算中。虽然很无聊，我还是决定把今天跟人一块算出来的各种24都写在下面。(10-3)*2+10=24 这个应该是正常的解法了。(2+3-10/10)! =24 这个是当我发现4!竟然奇迹般的等于24时做的。(10/2-10%3)! =24 看到这个的时候我凌乱了一下。3

今天心情不错，早上起来按部就班收拾自己，收拾书包，启程去苏州街75号，鼎钧大厦，考我希望是最后一次的GRE AW test。九点出发，到明光桥北等公交，490先于304到了，于是决定坐490转地铁，放弃等那个不知道多久能来一趟的304。9点45到达考场休息室，等着开始，9点56分左右进来三个奇形怪状的非主流，怎么看都不像GRE的，果不其然，他们是考护士的。于是我更担心的事情出现了：他们考上护士了是不是很危险。10点17分的时候后来被发现很NICE的考官甲出现了，叫我们领表和钥匙。之后是存包，交表，听考官乙用京腔讲的注意事项。之后是排队等着进场，我本来排在第四位，在一位记者朋友同志前面。结果我刚坐到登记用的电脑前就被告知我还要等等，因为前面那场用我即将使用的那台电脑的同学还在答题。于是我想到了两件事：第一，那个同学一定详细的填好了前面的22道令人不安且愤慨的背景调查部分，并且在选校环节异常纠结（因为随后当我被告知她/他还有两所学校要选之后，我又等了15分钟才被准许进场。当然，按照arguement精神，我还没排除他/她是否错点了remove all selected schools按钮，并重新选择了4所学校，或者他/她中间有什么不适晕过去了15分钟的可能性，我不能说他/她选校很纠结）；第二，ETS的机考每个考生所用的机器是事先安排好并不能随时更换的，否则应该是由排在队尾的那个面相狰狞的女同学来承担最后进场的等待的煎熬。在等待的过程中，那个考官甲在看到我来回踱步并嘴里默念着什么的时候对我投来了nice的笑容。当我终于进场时，我发现很多人的issue几乎已经写完了。不过，不过，这个不过很重要，不过，随后我的人品就爆发了，issue两题都很熟悉，并读过范文，做过练习，选择其中一个感觉逻辑更清晰的飞快的敲了出来，之后arguement是那个经典的west egg，不知道为什么，我就是对这个west egg很有印象。之后happy happy的敲完了arguement的5个正文段落。我想说的是，这学期以来积攒的人品终于爆发了。还有很重要的一点是，baidu终于收录了我的16个页面，yahoo也开始有了收录。心情这么好，就废话了一大堆，下面是正文：题目:poj2195,最小费用最大流。poj2195 Going Home。http://poj.org/problem?id=2195题意:求几个原点到几个终点的最小费用最大流。有可能输出最小费用，不可能输出不可能。每个终点可接收1个单位的流，每个起点释放1个单位的流。解法：最小费用最大流。这题poj2195是费用流的一个变形，我们加入两个超级节点，起点连接每个图中的源点，容量1，长度0，终点的处理方法相同。于是在这张图上费用流之。代码: #include<iostream>#include<queue>using namespace std;int n,m,k,s,t,ans;int xm[250],ym[250],xh[250],yh[250];int map[520][520],c[520][520],f[520][520],d[520],p[520];bool v[520];char in[250][250];int getpath(){ int cur,i; memset(d,127,sizeof(d)); memset(v,0,sizeof(v)); queue<int> q; d[s]=0; for(i=0;i<=t;i++) p[i]=-1; q.push(0); v[0]=1; while(!q.empty()) { cur=q.front(); q.pop(); v[cur]=0; for(i=0;i<=t;i++) { if(c[cur][i]>f[cur][i]&amp;&amp;d[i]>d[cur]+map[cur][i]) { d[i]=d[cur]+map[cur][i]; p[i]=cur; if(!v[i]) { q.push(i); v[i]=1; } } } } if(p[t]==-1) return 0; return 1;}void […]

题目:http://poj.org/problem?id=3349题意:输入n个含6个整数的数组，判断这些数组是否有相同的。相同的条件为：正向或者反向相应顺序相同，如1 2 3 4 5 6 与 4 3 2 1 6 5就是相同的。解法:哈希表。今天上午重新看了眼哈希表各种性质的证明，感觉有所启发，就决定找到哈希的题写写看。哈希的h函数为6个数之和。首先判断输入各组的输入之和是否有相同的，如果有相同的，则具体分情况判断。哈希表解决冲突的方法为拉链。本来想模拟个链表，但发现，这样反而超时，于是决定直接给每个槽100个单元，因为每个key相同的元素个数的期望为不到10个，因而决定碰运气，希望不出现最坏情况。结果AC了。代码: #include<stdio.h>#include<stdlib.h>struct Node{ int flag; int len; int next[100][6];};Node t[15000];int compare(int a[],int b[]){ int i,j; for(i=0;i<6;i++) { for(j=0;j<6;j++) { if(a[(i+j)%6]!=b[j%6]) break; } if(j==6) return 1; for(j=0;j<6;j++) { if(a[(i+j)%6]!=b[5-j]) break; } if(j==6) return 1; } return 0;}int main(){ int ll,flag,sum,n,i,j,k,temp[6]; scanf(“%d”,&n); flag=0; for(i=0;i<14999;i++) { […]

题目:http://poj.org/problem?id=1328题意:这题是说，在一条直线两侧分别是海跟陆地，也就是说这条线是海岸线。在海里有若干个用x,y坐标标示位置的岛屿，岸上安排雷达站，每个雷达站有覆盖范围。要求求出最少需要多少个雷达站覆盖所有岛屿。解法:贪心。这题就是在一条直线上画最少的覆盖直线一侧所有点的一系列圆。首先对每个点求出能覆盖到这个点的在直线上左右两极限位置的坐标。然后按照左极限位置对这些点排序。然后从左到右找到每个雷达最多能覆盖的岛屿数。最后就得到了所需的雷达数。当有岛屿离海岸的距离大于雷达覆盖半径，则输出不可能。代码: #include<stdio.h>#include<math.h>#include<stdlib.h>typedef struct node{ double l; double r;}ISLAND;int cmp(const void *a,const void *b){ return (*(ISLAND *)a).l>(*(ISLAND *)b).l?1:-1;}main(){ int i,j,k,x,y,n,d,num,time=1; double temp; ISLAND a[1100]; scanf(“%d%d”,&n,&d); while(n!=0||d!=0) { num=0; for(i=0;i<n;i++) { scanf(“%d%d”,&x,&y); if(y>d) {num=-1;} temp=sqrt((double)d*d-(double)y*y); a[i].l=(double)x-temp; a[i].r=(double)x+temp; } if(d<=0||num==-1){printf(“Case %d: -1n”,time);time++;scanf(“%d%d”,&n,&d);continue;} qsort(a,n,sizeof(a[0]),cmp); for(i=0;i<n;i=j,num++) { for(j=i+1;j<n;j++) { if(a[j].l>a[i].r) break; { if(a[i].r>a[j].r) {a[i].r=a[j].r;} } } } printf(“Case %d: %dn”,time,num); […]

如上图，H为角A的角平分线和底边BC的垂直平分线的交点，因而有HE等于HF，AH＝AH因此三角形AEH与AFH全等，因此AE＝AF。又BH＝CH，HE=HF，因而三角形EHB与FHC全等，因而BE＝CF，因此AB＝AC，证毕。这个证明很荒谬，但却体现数学证明中的一个很诡异的问题，发现它的错误吧。