poj 1009

刺骨的言语ヽ痛彻心扉 2021-11-02 00:46 241阅读 0赞

参考自大神思路：[POJ 1009][]  
首先，暴力必挂，这是题目的善意提醒。  
于是，一直在想不暴力的各种判断计算方法，关于各种跳跃移动，后来都无奈想用STL。原谅我的蒟蒻。  
再然后就思维混乱了。于是看网上各位大神的解题报告。很神奇的一个搞法。瞬间被震惊。发现了一个道理，有时候从这个角度搞不通的时候，换一个更直接的角度往往一下就搞通了。是的。  
首先可以看出来，这个最终的答案中，肯定会有某些连续段，答案是不变的，这些连续段又和原图有关。我自己的思路就是，先找出在原图的某一连续段中，答案值可能改变的几个像素（做标记），再一次次跳跃到这几个像素中计算它们的答案值，但是问题就是，怎么样的像素才是需要计算的像素。  
如图的一个map：  
![在这里插入图片描述][20190812212311314.]

第一个x显然是需要标记的。然后，可以直接跳跃到第4个x，因为此时它的周围多了一个z，答案可能改变，而第二、三个x显然答案和第一个是一样的。再然后，y的第一个也肯定要标记，因为主体变了。然后到了坐标为(2,3)的y，它需要标记是因为它的周围多了一个m。于是以此类推完成。虽然这个搞法看似可以，但这么多的细节要考虑，况且格子数是10^9，以我的水平注定挂。该怎么办呢。在看了各位大神的题解之后，发现其实我只要把需要标记的格子标记出来，并且把每一连续段的分段画出来，就可以发现很神奇的东西：  
![在这里插入图片描述][20190812212349514.]

紫色标注的都是要标记的格子，红色边框的代表这一个连续段的起始格。我们可以发现，每个连续段的起始格，都是要标记的格子，同时，每个要标记的格子，都是一个连续段起始格的周围8个格子中的一个。所以，改进的搞法就很清楚了：只需要一个个枚举每个连续段的起始格，并计算它和它四周8个格子的答案值，最后统计答案的时候按照位置先后排序，答案中相同的连续段就合并。因为最多只有1000个连续段，所以不管是时间还是空间都不会超。

注意的细节：最后一个位置也为标记的格子。（有关代码在代码行63行）

![在这里插入图片描述][20190812213536766.]  
为什么最后一个格子是特殊情况？拿上面这个为例子：红色边框的为连续段的起始格，绿色背景的为标注的格子（没考虑最后一个格子）  
输入为:  
5  
10 9  
20 11  
0 0

如果没有考虑最后一个格子也为标记格子的情况，则有错误输出：  
5  
0 3  
10 17  
0 0

考虑最后一个格子的情况，则有正确输出：  
5  
0 3  
0 3  
10 12  
0 5  
0 0

大家可以好好考虑上面这个例子

上代码：

#include<iostream>
    #include<cmath>
    #include<algorithm>
    const int maxn=1005;
    using namespace std;
    int width,tot;
    struct pix
    {
    	int pos;
    	int ans;
    }outmap[maxn*8];//记录每个起始格及其8个方向 
    int intmap[maxn][2];//[0]存数值，[1]存长度 
    int cmp(struct pix p1,struct pix p2)
    {
    	return p1.pos<p2.pos;
    }
    int getshu(int p)
    {
    	int po=0,i=0;
    	while(po<=p)
    	{
    		po+=intmap[i++][1];
    	}
    	return intmap[i-1][0];
    }
    int getans(int p)
    {
    	int r=p/width;
    	int c=p%width;
    	int ans=0,num=getshu(p);
    	for(int i=r-1;i<=r+1;i++)
    	{
    		for(int j=c-1;j<=c+1;j++)
    		{
    			int tpos=i*width+j;
    			if(j<0||i<0||j>=width||tpos>(tot-1)||tpos==p)
    				continue;
    			int tmp1=abs(num-getshu(tpos)); 
    			if(tmp1>ans) ans=tmp1;
    		}
    	}
    	return ans;
    }
    int main()
    {
    	while(cin>>width&&width!=0)
    	{
    		int num,len,k=0;tot=0;//tot是元素个数 
    		while(cin>>num>>len)//录入所有的起始格 
    		{
    			if(num==0&&len==0)
    				break;
    			intmap[k][0]=num;
    			intmap[k++][1]=len;
    			tot+=len;
    		}
    		//for(int i=0;i<k;i++)
    		//	cout<<intmap[i][0]<<" "<<intmap[i][1]<<endl;
    		//cout<<k<<endl<<tot<<endl;
    		//开始处理
    		//cout<<getans(10995)<<endl;
    		int post=0,p=0;//pos为起始格的位置 ,p为记录outmap个数 
    		for(int i=0;i<=k;i++)//遍历所有的起始格!!!**要考虑最后一个也为标记格子，就要是<=k,而不是<k,为什么是这样，自己拿上面那个例子举例**
    		{
    			int r=(post)/width;
    			int c=(post)%width;
    			//cout<<r<<" "<<c<<endl;
    			//枚举8个方向
    			for(int j=r-1;j<=r+1;j++)
    			{
    				for(int z=c-1;z<=c+1;z++)
    				{
    					int tpos=j*width+z;
    					if(j<0||z<0||z>=width||tpos>(tot-1))
    						continue;
    					//没有出界
    					outmap[p].pos=tpos;
    					outmap[p++].ans=getans(tpos);
    					//cout<<tpos<<" "<<getans(tpos)<<endl;
    				}
    			}
    			//更新post
    			post+=intmap[i][1]; 
    		}
    		//将标记格排序 :按位置从小到大排序 
    		sort(outmap,outmap+p,cmp);
    		//for(int i=0;i<k;i++)
    		//	printf("%d %d\n",outmap[i].pos,outmap[i].ans); 
    		struct pix tmp=outmap[0];
    		cout<<width<<endl;
    		for(int i=1;i<p;i++)
    		{
    			if(outmap[i].ans==tmp.ans)
    				continue;
    			printf("%d %d\n",tmp.ans,outmap[i].pos-tmp.pos);
    			tmp=outmap[i];
    		}  
    		printf("%d %d\n",tmp.ans,tot-tmp.pos);
    		printf("0 0\n");
    	}
    	printf("0\n");
    	return 0; 
    }

[POJ 1009]: http://blog.sina.com.cn/s/blog_6e63f59e01012mxb.html
[20190812212311314.]: /images/20211101/e5bdec5d8c284d75a6f574818ff681b9.png
[20190812212349514.]: /images/20211101/2ccb7707aaf0434d90690b6a5f4770fd.png
[20190812213536766.]: /images/20211101/45fc5c4891454702bf2cb55eb113659b.png