集训第七天了。心里有些感慨

有些想家了。给家里打了电话，我想也快了把，就要回到开化了。想来，已经半年不在开化了，整整半年。

今天写了两道题，一个是poj2559,一个事poj1751

poj2559:维护一个单调栈。

如果后期有空我会贴点报告。现在只贴个代码把。

核心思想在于，利用单调栈，找出每个pop的元素的最大可拓展边界，把复杂度从o(n^2)弄到o(n)

代码如下：

#include 
    
     #include 
     
      using namespace std;#define MAXSIZE 1000000/* * poj2559,维护一个单调栈就可以了。 * 第一次用栈，逻辑不是很清楚 * 大概这样：每次弹出元素的时候，计算这个元素形成的面积。跟最值比较。 * 再写点，，之前弄懂后来又忘了。 * 就是，每次出栈，栈顶元素肯定是不比他在栈里下面那个元素低的，这是他能拓展的左边最长的地方 * 既然出栈，必然新的元素比栈顶元素低，因为出栈元素无法向右拓展（新的元素是第一个让他无法拓展的元素） * 这样就能求出他能拓展的最大面积了。 * new.index-stack[top-1].index-1就是宽度*stach[top].height就行了 * (new.index-stack[top].index) + (stack[top].index-stack[top-1].index) * */typedef struct{	int index;	long long height;}node;node stack[MAXSIZE];int top;node pop(){	top--;	return stack[top+1];}void push(node x){	top++;	stack[top] = x;	return;}void initialise(){	node t;	t.index = 0;	t.height=-1;	top=0;	push(t);	return;}node getTop(){	return stack[top];}int main(){	int N;	int i,j,k;	node t,curNode;	long long ans;	long long curAns;	while(scanf("%d",&N),N!=0)	{		ans = -1;		initialise();		for(i=1;i<=N+1;i++)		{			if(i==N+1)			{				t.index = N+1;				t.height=-1;			}			else			{				scanf("%lld",&t.height);				t.index=i;			}			while(getTop().height > t.height)			{				curNode = pop();			/*	printf("pop the node, Index:%d,Height:%d\n",curNode.index,curNode.height);*/				curAns = (long long)(t.index - getTop().index -1) * (curNode.height);				/*printf("i:%d,curAns:%d\n",i,curAns);*/				if(curAns > ans)					ans = curAns;			}			push(t);			/*printf("push the node which index is %d height is%d\n",t.index,t.height);*/			/*			 * 别忘了把所有元素pop出来。否则会漏掉计算			 * */		}		cout<
      
       <
      
     
    

然后是poj1751,,一个最小生成树。。

同上，，后期如果写结题报告会加入传送门。

现在只贴代码。

记录一点，显然是prim，但是关键在于，，把已经修好路的点之间距离设为0

但是！，但是！，还是一样的prim,

绝对不是把那些已经修好的路直接标记成visited，这点很重要。

我们应该做的是，把距离改成0，然后按照prim的流程正常进行求最小生成树。

记得用一个pre数组，在更新low数组的时候，这个数组可以更新跟他连接的最短边的另一个定点

AC代码如下：

#include	
    
     #include 
     
      #define INF 300000000typedef struct{	int x;	int y;}node;node nodes[751];double a[751][751];double low[751];int vis[751]={0};int pre[751]={0};/*----------------------------------------------------------------------------- *  计算距离。 *-----------------------------------------------------------------------------*/double calcDistance(node *i,node *j){	return (sqrt(  ( (*i).x-(*j).x)*((*i).x-(*j).x)  +  ((*i).y-(*j).y)*((*i).y-(*j).y)  ));}int main ( int argc, char *argv[] ){	node n;	int N,M;	int i,j,k;	scanf("%d",&N);	for(i=1;i<=N;i++)	{		scanf("%d%d",&n.x,&n.y);		nodes[i] = n;	}	for(i=1;i<=N;i++)	{		for(j=1;j
      
       low[i])			{				min = low[i];				pos = i;			}		}		vis[pos] = 1;		if(a[pos][pre[pos]] != 0)			printf("%d %d\n",pre[pos],pos);		/* 然后根据pos更新low数组 */		for(i=1;i<=N;i++)		{			if(vis[i]==0 && a[pos][i] < low[i])			{				pre[i] = pos;				low[i] = a[pos][i];			}		}	}	return 0;}				/* ----------  end of function main  ---------- */
      
     
    

当然，其实不需要做sqrt，因为不需要真的计算，只需要比较，，这是多余的

因此low和邻接矩阵其实不用开double数组。

今天和别人聊天，所以晚了点，就只写这么些把。。今天的另外一个收获是看懂了quickSort并且自己写了个。

然后看了看qsort的使用方法。