首页 > ACM题库 > HDU-杭电 > HDU 1349 Fold-up Patterns-线段树-[解题报告] C++
2013
12-09

HDU 1349 Fold-up Patterns-线段树-[解题报告] C++

Fold-up Patterns

问题描述 :

Fold-up patterns for solids like cubes or octahedrons can be found in many books on geometry, but without actually folding them it is hard to tell whether the constructions really work. In this problem, we will consider a special class of such patterns.
Given a fold-up pattern built from unit squares in the plane, together with a description along what edges it should be folded in what direction, decide whether it will result in a closed surface of a solid in three dimensions. If it does, find the volume of the solid.

More precisely, the pattern consists of a connected set of unit squares in the plane. For any edge between connected sides you are told whether to fold forward, backward (always at a right angle), or not at all along that edge. If an edge between two adjacent squares in the pattern is not mentioned in the input, you may assume that the squares are not connected and can be ripped apart when folding. However, connected edges must always be folded according to the description.

For our purposes a closed surface is one where every square in the pattern separates the inside from the outside. When folded, the squares of the pattern lie on a rectangular, 3-dimensional grid, and each separates a cell (cubes of side length one unit) on the inside from one on the outside. For every cell it must be clear whether it is inside or outside. The following sketch illustrates this rule in two dimensions.

Note that even the second pattern above satisfies our definition of a closed surface, but the interior is not connected.

Two different squares may not occupy exactly the same position in space, though they may (and will for a closed surface) touch at edges and vertices. Make sure that the pattern does not interpenetrate itself through connected edges. Apart from that, do not worry about the process of folding, e.g. what edges are folded first or whether part of the structure is in the way for the rest.

输入:

The input file consists of several test cases.For each test case, the first line contains two integers n and e. These are the number n (1 <= n <= 200) of squares in the pattern and the number e (0 <= e <= 300) of edges. Squares are labelled by the integers 0 to n – 1. The following e lines describe one edge each using the four numbers s1; s2; p; f :

The two numbers s1 and s2 (with 0 <= s1 < s2 < n) of the squares that are joined by the edge.

The position p of the square s2 with respect to the square s1 in the pattern. Here p = 0;1;2;3 mean above, to the left, below, or to the right of s1, respectively (see sketch below).

The number f =0;1;2 tells you to fold along the edge either not at all, forward, or back, respectively (see sketch).

You can also assume that the pattern is connected and can be drawn in the plane without overlapping.

At the end of the input file, there will be a line containing two zeros (instead of n and e). Do not process that line.

输出:

For each scenario print “Test case #k:”, where k is the number of the test case (starting from 1).Then, on the same line, print either “not a closed surface” if the pattern does not form a closed surface or “closed surface, volume=” and the volume as an integer if it does.

样例输入:

6 5
0 2 2 1
1 2 3 1
2 3 3 1
2 4 2 1
4 5 2 1
5 4
0 2 2 1
1 2 3 1
2 3 3 1
2 4 2 1
0 0

样例输出:

Test case #1: closed surface, volume=1
Test case #2: not a closed surface

用线段树求逆序数。。。没插入一个数时候 询问这个数与最大数之间的区间 你要找的肯定是比这个数大的有几个 更新的时候把包括这个数的区间值都加1

#include <iostream>
 #include <cstring>
 #include <string>
 #include <stack>
 #define lson l,mid,rt<<1
 #define rson mid+1,r,rt<<1|1
 #define maxn 5010
 using namespace std;

 int num[maxn*4];
 int n;
 int val[maxn];

 int query(int L,int R,int l,int r,int rt)
 {
     if(L==l&&r==R)
     {
         return num[rt];
     }
     int mid=l+r>>1;
     if(R<=mid) return query(L,R,lson);
     else if(L>mid) return query(L,R,rson);
     else
     {
         return query(L,mid,lson)+query(mid+1,R,rson);
     }
 }

 void update(int L,int R,int l,int r,int rt)
 {
     num[rt]++;
     if(L==l&&r==R)
     {
         return;
     }
     int mid=l+r>>1;
     if(R<=mid)  update(L,R,lson);
     else if(L>mid)  update(L,R,rson);
     else
     {
          update(L,mid,lson);
          update(mid+1,R,rson);
     }
 }

 int main()
 {
     freopen("input.txt","r",stdin);
     int i,j;
     while(scanf("%d",&n)!=EOF)
     {
         memset(num,0,sizeof(num));
         int ret=0;
         for(i=0;i<n;i++)
         {
             int temp;
             scanf("%d",&temp);
             val[i]=temp;
             ret+=query(temp,n-1,0,n-1,1);
             update(temp,temp,0,n-1,1);
         }
         int ans=ret;
         for(i=0;i<n;i++)
         {
             ret=ret-val[i]+(n-val[i]-1);
             ans=min(ans,ret);
         }
         printf("%d\n",ans);
     }
     return 0;
 }

解题报告转自:http://www.cnblogs.com/woaishizhan/archive/2012/10/12/2722010.html


  1. #include <stdio.h>
    int main(void)
    {
    int arr[] = {10,20,30,40,50,60};
    int *p=arr;
    printf("%d,%d,",*p++,*++p);
    printf("%d,%d,%d",*p,*p++,*++p);
    return 0;
    }

    为什么是 20,20,50,40,50. 我觉得的应该是 20,20,40,40,50 . 谁能解释下?

  2. L(X [0 .. M-1],Y [0 .. N-1])= 1 + L(X [0 .. M-2],Y [0 .. N-1])这个地方也也有笔误
    应改为L(X [0 .. M-1],Y [0 .. N-1])= 1 + L(X [0 .. M-2],Y [0 .. N-2])