King's Phone

Accepts: 310

Submissions: 2980

Time Limit: 2000/1000 MS (Java/Others)

Memory Limit: 65536/65536 K (Java/Others)

问题描述

阅兵式上，国王见到了很多新奇东西，包括一台安卓手机。他很快对手机的图形解锁产生了兴趣。

解锁界面是一个  $\times 3$  的正方形点阵，第一行的三个点标号  $1, 2, 3$ ，第二行的三个点标号  $4, 5, 6$ ，第三行的三个点标号  $7, 8, 9$ 。密码本身是一段序列，表示经过点的先后顺序，但遵循如下规则：

1. 密码至少经过四个点。

2. 不能重复经过同一个点。

3. 路径上的中间点不能跳过，除非已经被经过（ $3427$  是合法的，但  $3724$  不合法）。

他想设置的密码的长度为正整数  $k(1\le k\le 9)$ ，密码序列为  $s_1 s_2...s_k(0\le s_i < INT\_MAX)$ ，他想知道这个密码序列是否合法，这个问题交给了你。

输入描述

第一行一个整数表示测试组数： $T\le100000)$  。

每组数据占一行，每行第一个数  $k$ ，设置密码的长度；接着  $k$  个正整数，之间用空格隔开，表示密码序列  $s_1s_2...s_k$ 。

输出描述

共  $T$  行。对每组数据，若合法输出 `valid`，否则输出 `invalid`。

输入样例

输出样例

invalid
valid
valid

Hint

对于第一组数据， $1$  到  $3$  跳过了路径上的点  $2$ ，所以不合法。

对于第二组数据， $1$  到  $3$  时点  $2$  已经被经过了，所以合法。

对于第三组数据， $8\rightarrow 1 \rightarrow 6 \rightarrow 7$  路径均没有中间点，所以合法。

生命不息，坑点不断啊。今天的的bc第二题真的好坑。

AC代码：

#include<iostream>
#include<functional>
#include<algorithm>
#include<cstring>
#include<string>
#include<vector>
#include<cstdio>
#include<queue>
#include<cmath>
#include<map>
using namespace std;
#define CRL(a) memset(a,0,sizeof(a))
#define QWQ ios::sync_with_stdio(0)
#define inf 0x3f3f3f3f
typedef unsigned long long LL;
typedef  long long ll;

const int T = 500000+50;
const int mod = 1000000007;

int xy[20][2] = {{0,0},{1,1},{1,2},{1,3},{2,1},{2,2},{2,3},{3,1},{3,2},{3,3}};
bool vis[50][50],vi[50];

bool jugde(int n,int m)
{
    if(n==m)return false;
    if(xy[n][0]==xy[m][0]){
        if(abs(xy[n][1]-xy[m][1])>1){
            if(!vis[xy[n][0]][(xy[n][1]+xy[m][1])/2])
                return false;
        }
    }
    if(xy[n][1]==xy[m][1]){
        if(abs(xy[n][0]-xy[m][0])>1){
            if(!vis[(xy[n][0]+xy[m][0])/2][xy[n][1]])
                return false;
        }
    }
    if(n==1&&m==9||m==1&&n==9||n==3&&m==7||m==3&&n==7){
        if(!vis[xy[5][0]][xy[5][1]]){
            return false;
        }
    }
    return true;
}

int main()
{

#ifdef zsc
    freopen("input.txt","r",stdin);
#endif

    int n,m,i,j;
    scanf("%d",&n);
   while(n--)
   {
     memset(vis,false,sizeof(vis));
      memset(vi,false,sizeof(vi));
      scanf("%d",&m); 
      bool flag = false;
      int tmp=0;//一开始没付值运行出错了
      if(m<4){
           flag =true;
      }
      for(i=1;i<=m;++i){
          scanf("%d",&j);
		  if(j<=0||j>9){
			  flag = true;
			  continue;//没结束也越界了
		  }
          if(!vi[j]) vi[j] = true;
          else flag = true;
         vis[xy[j][0]][xy[j][1]] = true;
          if(i>1&&!jugde(tmp,j))
          {
              flag = true;
          }
          tmp = j;
      }
     if(flag){
         printf("invalid\n");
     }
     else {
         printf("valid\n");
     }
   }

    return 0;
}

秒客网

BestCoder Round #75-King's Cake（模拟）

King's Phone

相关文章