Dominos 2

Dominos 2

时间: 1ms        内存:128M

描述:

Dominos are lots of fun. Children like to stand the tiles on their side in long lines. When one domino falls, it knocks down the next one, which knocks down the one after that, all the way down the line. However, sometimes a domino fails to knock the next one down. In that case, we have to knock it down by hand to get the dominos falling again.

Given a set of dominos that are knocked down by hand, your task is to determine the total number of dominos that fall.

输入:

The first line of input contains one integer specifying the number of test cases to follow. Each test case begins with a line containing three integers n, m, l no larger than 10 000, followed by m+l additional lines. The first integer n is the number of domino tiles. The domino tiles are numbered from 1 to n. Each of the m lines after the first line contains two integers x and y indicating that if domino number x falls, it will cause domino number y to fall as well. Each of the following l lines contains a single integer z indicating that the domino numbered z is knocked over by hand.

输出:

For each test case, output a line containing one integer, the total number of dominos that fall over.

示例输入:

1
3 2 1
1 2
2 3
2

示例输出:

2

提示:

参考答案(内存最优[1008]):

#include <math.h>
#include <stdio.h>
#include <stdlib.h>
#define EPS 0.0000001

char buf[100000];
char cmd[1100];
char dist[1100][100];

double X, Y;

double HD;

void FD(int d) {
    X += d*cos(HD/180*M_PI);
    Y += d*sin(HD/180*M_PI);
    //printf("FD %d to %lf %lf\n", d, X, Y);
}

void LT(int d) {
    HD+=d;
}

void HOME() {
    HD = 0;
    X = 0;
    Y = 0;
}

int myatoi(char* st, int other) {
    if(st[0] == '?') return other;
    return atoi(st);
}



int main() {
    int CASES;
    scanf("%d ", &CASES);
    while(CASES--) {
       // int cnt;
        int i;
        int turn = 0;
        int n;
        scanf("%d", &n);
       
        for(i=0;i<n;i++) {
			
            scanf("%s%s", buf,dist[i]);
            cmd[i] = buf[0];
        }
        for(i=0; i<n; i++) {
            if(dist[i][0] != '?') continue;
            if(cmd[i] == 'l') turn = 1;
            if(cmd[i] == 'r') turn = 1;
        }
        if(turn) {
            int ang;
            for(ang = 0; ang < 360; ang++) {
                    //printf("angle: %d\n", ang);
                HOME();
                for(i=0; i<n; i++){
                    switch(cmd[i]) {
                        case 'f': FD(atoi(dist[i])); break;
                        case 'b': FD(-atoi(dist[i])); break;
                        case 'l': LT(myatoi(dist[i],ang)); break;
                        case 'r': LT(-myatoi(dist[i],ang)); break;
                    }
                }
                if(fabs(X)+fabs(Y) < EPS) {
                    printf("%d\n", ang);
                    goto next;
                }
            }
                puts("no angle worked");
        } else {
            HOME();
            for(i=0; i<n; i++){
                switch(cmd[i]) {
                    case 'f': FD(myatoi(dist[i],0)); break;
                    case 'b': FD(-myatoi(dist[i],0)); break;
                    case 'l': LT(atoi(dist[i])); break;
                    case 'r': LT(-atoi(dist[i])); break;
                }
            }
            printf("%.0lf\n", sqrt(X*X+Y*Y));
        }
next:;
    }
    return 0;
}

参考答案(时间最优[0]):

#include <math.h>
#include <stdio.h>
#include <stdlib.h>
#define EPS 0.0000001

char buf[100000];
char cmd[1100];
char dist[1100][100];

double X, Y;

double HD;

void FD(int d) {
    X += d*cos(HD/180*M_PI);
    Y += d*sin(HD/180*M_PI);
    //printf("FD %d to %lf %lf\n", d, X, Y);
}

void LT(int d) {
    HD+=d;
}

void HOME() {
    HD = 0;
    X = 0;
    Y = 0;
}

int myatoi(char* st, int other) {
    if(st[0] == '?') return other;
    return atoi(st);
}



int main() {
    int CASES;
    scanf("%d ", &CASES);
    while(CASES--) {
       // int cnt;
        int i;
        int turn = 0;
        int n;
        scanf("%d", &n);
       
        for(i=0;i<n;i++) {
			
            scanf("%s%s", buf,dist[i]);
            cmd[i] = buf[0];
        }
        for(i=0; i<n; i++) {
            if(dist[i][0] != '?') continue;
            if(cmd[i] == 'l') turn = 1;
            if(cmd[i] == 'r') turn = 1;
        }
        if(turn) {
            int ang;
            for(ang = 0; ang < 360; ang++) {
                    //printf("angle: %d\n", ang);
                HOME();
                for(i=0; i<n; i++){
                    switch(cmd[i]) {
                        case 'f': FD(atoi(dist[i])); break;
                        case 'b': FD(-atoi(dist[i])); break;
                        case 'l': LT(myatoi(dist[i],ang)); break;
                        case 'r': LT(-myatoi(dist[i],ang)); break;
                    }
                }
                if(fabs(X)+fabs(Y) < EPS) {
                    printf("%d\n", ang);
                    goto next;
                }
            }
                puts("no angle worked");
        } else {
            HOME();
            for(i=0; i<n; i++){
                switch(cmd[i]) {
                    case 'f': FD(myatoi(dist[i],0)); break;
                    case 'b': FD(-myatoi(dist[i],0)); break;
                    case 'l': LT(atoi(dist[i])); break;
                    case 'r': LT(-atoi(dist[i])); break;
                }
            }
            printf("%.0lf\n", sqrt(X*X+Y*Y));
        }
next:;
    }
    return 0;
}

题目和答案均来自于互联网,仅供参考,如有问题请联系管理员修改或删除。

点赞

发表评论

电子邮件地址不会被公开。必填项已用 * 标注