AOJ 708.序列匹配

141

题目


Time Limit: 5000 ms
Memory Limit: 128 MB
Total Submission: 146
Submission Accepted: 34

Description  


给定两个长度均为3的数字序列,每位上为一个范围是1-N的正整数,求有多少个仍然由3个1-N的整数构成的数字序列能与给定的两个序列中的任意一个匹配。
如果两个序列匹配,当且仅当两个序列中的每个对应数字的最近距离不超过2。
比如当N为9时,每一位数字可能是1,2,3,4,5,6,7,8,9,并且数字是循环的。也就是说9和1是相邻的。
数字之间的距离就是两个数字的位置之差。
也就是说在上面的例子中,9和1的最近距离是1,9和2的最近距离是2,2和5的最近距离是3。
比如现在给定两个序列组合为(1,2,3)和(4,5,6), (2,4,8)或者(1, N, 5) 是能和两个序列匹配中的至少一个匹配的,但是(1, 5, 6)是不能和给定的两个序列中的任何一个匹配的。



Input  


多组输入,以EOF结束。
每组输入包含三行第一行为一个整数N(1 <= N <= 50),第二行和第三行都是以三个空格分隔的整数。



Output  


对于每组输入,输出一个数字,表示能和给定的两个序列中的任意一个匹配的序列的个数。



Sample Input  


50
1 2 3
5 6 7



Sample Output  


249



Source  


Roll


题解



建立一个三维坐标系,把能覆盖到的地方全部标记上,然后计算数量

其中要注意小于等于0和大于N的情况(转换后还应该在0-N之间)。

代码


/*
By:OhYee
Github:OhYee
Email:oyohyee@oyohyee.com
*/
#include <cstdio>
using namespace std;

 
const int maxn = 55;
 
 
bool Do() {
    int N,a1,b1,c1,a2,b2,c2;
    int cnt = 0;
    if(scanf("%d%d%d%d%d%d%d",&N,&a1,&b1,&c1,&a2,&b2,&c2) == EOF)
        return false;
 
    bool map[maxn][maxn][maxn] = {0};
 
    for(int x = a1 - 2;x <= a1 + 2;x++)
        for(int y = b1 - 2;y <= b1 + 2;y++)
            for(int z = c1 - 2;z <= c1 + 2;z++) {
                int xx = x <= 0 ? N + x : x > N ? x - N : x;
                int yy = y <= 0 ? N + y : y > N ? y - N : y;
                int zz = z <= 0 ? N + z : z > N ? z - N : z;
                if(!map[xx][yy][zz] && xx > 0 && xx <= N&&yy > 0 && yy <= N&&zz > 0 && zz <= N)
                    cnt++;
                map[xx][yy][zz] = 1;
            }
    for(int x = a2 - 2;x <= a2 + 2;x++)
        for(int y = b2 - 2;y <= b2 + 2;y++)
            for(int z = c2 - 2;z <= c2 + 2;z++) {
                int xx = x <= 0 ? N + x : x > N ? x - N : x;
                int yy = y <= 0 ? N + y : y > N ? y - N : y;
                int zz = z <= 0 ? N + z : z > N ? z - N : z;
                if(!map[xx][yy][zz] && xx > 0 && xx <= N&&yy > 0 && yy <= N&&zz > 0 && zz <= N)
                    cnt++;
            }
    printf("%d\n",cnt);
    return true;
}
 
 
int main() {
    while(Do());
    return 0;
}
发布评论
  • 点击查看/关闭被识别为广告的评论