首页 > ACM题库 > HDU-杭电 > hdu 2353 The Screen Behind the Mirror-字符串-[解题报告]C++
2014
01-05

hdu 2353 The Screen Behind the Mirror-字符串-[解题报告]C++

The Screen Behind the Mirror

问题描述 :

Dr. Evil has contracted your valuable services to build for him the world’s most powerful "laser". Of course before you spend one billion dollars
building the thing, you want to run some simulations first to make sure everything will work as designed. For this phase of the project, you will be
simulating part of the aiming system which uses mirrors and other optics to change the direction of the laser beam.

The simulation consists of a flat square table with mirrors, beam splitters, and beam detectors arranged on the tabletop, and with each object
represented by a one dimensional line segment. The list below describes each of the object types in detail:

mirror : A mirror object will reflect any laser beam striking its surface. The reflected beam leaves at the same angle of incidence as the
incoming beam. Note that both sides of a mirror object are reflective.

detector : A detector is an opaque object which absorbs any laser beam striking it. The simulation must also keep track of which detectors are
struck by a laser for program output purposes. Note that a laser beam strike on either side of a detector counts as a "hit".

splitter : When a laser beam strikes a splitter, it divides into two beams. One of the new beams will reflect from the splitter surface (as with a
mirror), and the other beam will pass through the splitter without changing direction. A splitter will function the same way regardless which
side of it is struck by a laser beam.

See the figures below for examples of a laser beam’s interaction with each of the possible object types:

For each simulation, a single laser beam enters the tabletop area. The program must compute the path taken by the laser beam (including secondary beams due to splitters), and it must determine which detectors are struck by a laser beam.

You can make the following assumptions in the program:

1. The tabletop surface is a 100 by 100 square, and unless otherwise specified all coordinates in the program’s input are given as integers within
the tabletop area (i.e. between 0 and 100 inclusive).
2. There will be no overlaps between the line 2. segment objects.
3. The laser which enters the tabletop area always starts from the edge of the table.
4. The simulation of each data set ends when all laser beams have either exited the table top area or have terminated at a detector.
5. For each data set there will be no more than 100 total reflections among all laser beams in that data set.
6. A laser beam will never intersect any object on a vertex and will never be collinear with an object’s line segment.
7. Each data set will contain at least one detector object.

输入:

Input to this problem will begin with a line containing a single integer N (1 ≤ N ≤ 100) indicating the number of data sets. Each data set consists of
the following components:

A single line with four numbers "x,y i,j" where x,y is a point along the table edge at which the laser beam enters, and i,j is a vector with integer
components(-1024 ≤ i,j ≤ 1024) specifying the direction of the incoming laser beam, where i corresponds to the x-axis direction and j
corresponds to the y-axis direction.
A line with a single integer P (1 ≤ P ≤ 100) giving the total number of objects in this data set.
A series of P lines, each representing one object, with the first line describing object 1, the second line describing object 2, and so on. Each
line begins with a single letter specifying the object type where a "M" indicates a mirror object, "S" a splitter, and "D" a detector. This is
followed by two coordinate pairs of the form "x,y", specifying the two end points of the object’s line segment.

输出:

Input to this problem will begin with a line containing a single integer N (1 ≤ N ≤ 100) indicating the number of data sets. Each data set consists of
the following components:

A single line with four numbers "x,y i,j" where x,y is a point along the table edge at which the laser beam enters, and i,j is a vector with integer
components(-1024 ≤ i,j ≤ 1024) specifying the direction of the incoming laser beam, where i corresponds to the x-axis direction and j
corresponds to the y-axis direction.
A line with a single integer P (1 ≤ P ≤ 100) giving the total number of objects in this data set.
A series of P lines, each representing one object, with the first line describing object 1, the second line describing object 2, and so on. Each
line begins with a single letter specifying the object type where a "M" indicates a mirror object, "S" a splitter, and "D" a detector. This is
followed by two coordinate pairs of the form "x,y", specifying the two end points of the object’s line segment.

样例输入:

1
50,100 0,-1
6
D 0,40 20,20
M 40,20 60,40
D 80,20 100,40
D 0,70 20,90
S 40,90 60,70
D 80,90 100,70

样例输出:

DATA SET #1
1
6

Trie

插入一个串:

void insert(char *s, int w) {//这样就实现了字符作下标↓

int cur = 0;//0是根节点,里面存放着一些指针, 存放的位置代表儿子的id,

//值为儿子的地址

    for (int i = 0; s[i]; i++) {//地址是顺序排列的,和节点数保持同步-1

        if (!chd[cur][ID[s[i]]])//i个字符不是当前节点的儿子

//儿子可以认为是住在父节点的数组里,他自己的家却住着他自己的儿子 囧 啃老串

            chd[cur][ID[s[i]]] = ++sz;//就插入这个儿子

        cur = chd[cur][ID[s[i]]];//指向下一个节点[第一维]

}//节点按照插入的顺序存在数组的每一行,同时儿子就是指向下一节点的指针; //初始化为0

    v[cur] = w;//cur为节点序号

}

HOJ2353 Card Hands

题意:每组case有若干手牌,均由不相同的52张组成,若a和b手牌末尾的m张完全相同,则可以合并存储.问每组case的所有牌可以用多少个节点存储.

思路:直接按照Trie的结构存,每个节点有52个儿子(一维的话编码转换一下,二维直接对应).由于题意是tail相同可以合并,因此倒着插入Trie.只需最后输出size即可.注意10号牌是两位数,需要特殊判断.

坑:1.写了clear函数忘记调用了..多组就错了

2.10特殊判断,但是由于编码的时候个位数全部减一,A->0, 2->1..但是10的时候一激动就对应了10,导致重复.

细节最后还是慢慢看出来的= =

#include <cstdio>
#include <cstring>
using namespace std;
const int MAX = 100005;
const int MAXC = 52;
//int id[MAXC];
int chd[MAX][MAXC];
int sz;
void clear()
{
    memset(chd,0,sizeof(chd));
    sz = 0;
}
int change(char c)
{
    if(c=='S') return 0;
    if(c=='H') return 13;
    if(c=='D') return 13*2;
    if(c=='C') return 13*3;
    if(c=='A') return 0;
    if(c>'1'&&c<='9') return c-'1';
    if(c=='J') return 10;
    if(c=='Q') return 11;
    return 12;
}
int GetID(char *s)
{
    if(s[1]=='0') return 9+change(s[2]);
    return change(s[0])+change(s[1]);
}
void insert(int *id,int len)
{
    int cur = 0;
    for(int i=len-1;i>=0;i--)
    {
        if(!chd[cur][id[i]])
            chd[cur][id[i]] = ++sz;
        cur = chd[cur][id[i]];
    }
}

int main()
{
    int hand,card;
    char s[4];
    int OneHand[MAX];
    while(scanf("%d",&hand))
    {
        if(!hand) break;
        clear();
        for(int i=0;i<hand;i++)
        {
            scanf("%d",&card);
            for(int j=0;j<card;j++)
            {
                scanf("%s",s);
                OneHand[j] = GetID(s);
            }
            insert(OneHand,card);
        }
        printf("%d\n",sz);
    }
    return 0;
}

解题转自:http://blog.csdn.net/iyundi/article/details/9719667


  1. Hello Web Admin, I noticed that your On-Page SEO is is missing a few factors, for one you do not use all three H tags in your post, also I notice that you are not using bold or italics properly in your SEO optimization. On-Page SEO means more now than ever since the new Google update: Panda. No longer are backlinks and simply pinging or sending out a RSS feed the key to getting Google PageRank or Alexa Rankings, You now NEED On-Page SEO. So what is good On-Page SEO?First your keyword must appear in the title.Then it must appear in the URL.You have to optimize your keyword and make sure that it has a nice keyword density of 3-5% in your article with relevant LSI (Latent Semantic Indexing). Then you should spread all H1,H2,H3 tags in your article.Your Keyword should appear in your first paragraph and in the last sentence of the page. You should have relevant usage of Bold and italics of your keyword.There should be one internal link to a page on your blog and you should have one image with an alt tag that has your keyword….wait there's even more Now what if i told you there was a simple WordPress plugin that does all the On-Page SEO, and automatically for you? That's right AUTOMATICALLY, just watch this 4minute video for more information at.

  2. 站长,你好!
    你创办的的网站非常好,为我们学习算法练习编程提供了一个很好的平台,我想给你提个小建议,就是要能把每道题目的难度标出来就好了,这样我们学习起来会有一个循序渐进的过程!

  3. 这道题目的核心一句话是:取还是不取。
    如果当前取,则index+1作为参数。如果当前不取,则任用index作为参数。