首页 > ACM题库 > HDU-杭电 > HDU 3470-Chinese Paper Folding[解题报告]HOJ
2014
03-31

HDU 3470-Chinese Paper Folding[解题报告]HOJ

Chinese Paper Folding

问题描述 :

Chinese Paper Folding, or Zhezhi, is the art of folding paper that originated in China. It is the predecessor of origami.

Here we only consider a simplified problem. You are given a paper L cm by W cm in size and a list of operations to fold it.

Four types of operation are listed below:
1.  L v , fold the left part of paper along the straight line x = v.
2.  R v , fold the right part of paper along the straight line x = v.
3.  U v , fold the upper part of paper along the straight line y = v.
4.  D v , fold the lower part of paper along the straight line y = v.
Note that v is always an integer.

We define the left-lower corner of current paper as (0, 0) at every step (refer to the picture below). It is guaranteed that each operation is legal, that is, each operation is asked to fold paper of a positive area.

It is obvious that folding will make the straight lines into creases. We wonder the total length of all creases when paper is completely unfolded.

输入:

In the first line there is an integer T, indicates the number of test cases. (T <= 50)

For each case, the first line is a pair of integers L and W (1 <= L, W <= 1,000,000), which stands for the length and width of the paper. In the second line, an integer K stands for the number of operations. (K <= 100000) Then K lines follow, each stands for an operation described above.

输出:

In the first line there is an integer T, indicates the number of test cases. (T <= 50)

For each case, the first line is a pair of integers L and W (1 <= L, W <= 1,000,000), which stands for the length and width of the paper. In the second line, an integer K stands for the number of operations. (K <= 100000) Then K lines follow, each stands for an operation described above.

样例输入:

2
50 50
4
L 30
D 5
R 3
U 5
65536 1
16
L 32768
L 16384
R 8192
R 4096
L 2048
R 1024
L 512
R 256
R 128
L 64
R 32
R 16
L 8
R 4
L 2
R 1

样例输出:

Case 1: 250
Case 2: 65535

#include <stdio.h>
#include <cstring>
#include <algorithm>
#define maxn 1000010
using namespace std;

typedef long long LL;

int width,height,n;
int L,R,U,D,v;
bool diffx,diffy;
int idx[maxn],idy[maxn];
char ch[10];

void init(int id[],int n)
{
	id[0]=id[n]=0;
	for (int i=1;i<n;i++)
		id[i]=1;
}

int fold(int id[], int &L, int &R, int v, bool &diff)
{
	bool dir=false;
	int ret;
	v+=L;
	ret=id[v];
	if (abs(L-v)>abs(R-v)) diff=!diff,dir=true;
	for (int x=v,y=v;x!=L&&y!=R;x--,y++)
	{
		if (!dir)
		{
			id[y]+=id[x];
			id[x]=0;
		}
		else
		{
			id[x]+=id[y];
			id[y]=0;
		}
	}
	if (!dir) L=v;
	else R=v;
	return ret;
}

int main()
{
	int test;
	scanf("%d",&test);
	for (int ii=1;ii<=test;ii++)
	{
		scanf("%d%d",&width,&height);
		scanf("%d",&n);
		diffx=diffy=0;
		L=D=0;U=height;R=width;
		init(idx,width);
		init(idy,height);
		LL ans=0;
		for (int i=1;i<=n;i++)
		{
			scanf("%s%d",ch,&v);
			if (ch[0]=='L'||ch[0]=='R')
			{
				if (diffx) v=R-L-v;
				if (!diffx && ch[0]=='R') diffx=!diffx;
				if (diffx && ch[0]=='L') diffx=!diffx;
				ans+=(LL)height*fold(idx, L, R, v, diffx);
			}
			else
			{
				if (diffy) v=U-D-v;
				if (!diffy && ch[0]=='U') diffy=!diffy;
				if (diffy && ch[0]=='D') diffy=!diffy;
				ans+=(LL)width*fold(idy, D, U, v, diffy);
			}
		}
		printf("Case %d: %I64d\n",ii,ans);
	}
	return 0;
}

  1. 第二个方法挺不错。NewHead代表新的头节点,通过递归找到最后一个节点之后,就把这个节点赋给NewHead,然后一直返回返回,中途这个值是没有变化的,一边返回一边把相应的指针方向颠倒,最后结束时返回新的头节点到主函数。