鏈接：https://ac.nowcoder.com/acm/contest/1/C
來源：牛客網

安卓圖案解鎖 時間限制：C/C++ 1秒，其他語言2秒
空間限制：C/C++ 131072K，其他語言262144K
64bit IO Format: %lld

題目描述

栗主席(lizi)是某xxxx大學的一個不得了的程序猿，然而沒想到吧，他竟然有女盆友，我們假設為QAQ！！！ 那天，QAQ問栗子：你的小米5s的圖像解鎖密碼到底是多少？ 栗子：嘛？我仔細想想...? ? QAQ：你仿佛在逗我... ... 栗子：我的圖像解鎖用過好多次密碼，后來都是用指紋解鎖，所以忘記密碼辣。但是我記得可能是那幾個密碼 QAQ：那你務必告訴我... 栗子: ...
然后，栗子就寫下了一堆可能的密碼，安卓圖案解鎖中，數字對應的位置已經標出。 但是栗子當然不想把真正的密碼告訴QAQ，所以給QAQ的一系列的密碼中，甚至有一些密碼，是不符合安卓圖案解鎖的規則的。 QAQ也知道栗子肯定不老實，給了很多錯的密碼，甚至不符合規則的密碼，所以想請你來找出，哪些密碼是不符合規則的。
安卓圖案解鎖的密碼有這樣的一些特點： 1.每個數字最多只會被使用一次。 2.如果想直接連接兩個數字，但是線段中會經過另一個數字，當且僅有那個數字已經在之前就被使用過了，才會合法。(比如你想從1直接連接到9，那么要么是1->3->9,要么是3在之前已經被使用過了，然后才能直接從1->9)

輸入描述:

多組輸入 每組輸入占一行，包含一串數字(1~9)，長度不超過30

輸出描述:

輸出這個安卓圖案解鎖是否合法，如果合法輸出"YES",反之輸出"NO" (請參照樣例輸出，不要輸出引號) 示例1

輸入

復制 14569 1953 15963 15953

輸出

復制 YES NO YES NO


思路：
建立 一個二維數組 isok[i][j] 代表 從i走到j是否能走。
用一個數組 cnt[i] 來記錄數字i在字符串中出現的次數。

然后直接模擬即可。
（題目中有錯誤的描述， 1-3-9 應該是 1-5-9 ） 出題人也不改題面，無奈啊。
細節見代碼：
#include <iostream> #include <cstdio> #include <cstring> #include <algorithm> #include <cmath> #include <queue> #include <stack> #include <map> #include <set> #include <vector> #include <iomanip> #define ALL(x) (x).begin(), (x).end() #define rt return #define sz(a) int(a.size()) #define all(a) a.begin(), a.end() #define rep(i,x,n) for(int i=x;i<n;i++) #define repd(i,x,n) for(int i=x;i<=n;i++) #define pii pair<int,int> #define pll pair<long long ,long long> #define gbtb ios::sync_with_stdio(false),cin.tie(0),cout.tie(0) #define MS0(X) memset((X), 0, sizeof((X))) #define MSC0(X) memset((X), '\0', sizeof((X))) #define pb push_back #define mp make_pair #define fi first #define se second #define eps 1e-6 #define gg(x) getInt(&x) #define db(x) cout<<"== [ "<<x<<" ] =="<<endl; using namespace std; typedef long long ll; ll gcd(ll a,ll b){return b?gcd(b,a%b):a;} ll lcm(ll a,ll b){return a/gcd(a,b)*b;} ll powmod(ll a,ll b,ll MOD){ll ans=1;while(b){if(b%2)ans=ans*a%MOD;a=a*a%MOD;b/=2;}return ans;} inline void getInt(int* p); const int maxn=1000010; const int inf=0x3f3f3f3f; /*** TEMPLATE CODE * * STARTS HERE ***/ char s[200]; int isok[11][11]; int cnt[11]; int main() {// freopen("D:\\code\\text\\input.txt","r",stdin);//freopen("D:\\code\\text\\output.txt","w",stdout);while(cin>>s){int len=strlen(s);// if(len>9)// {// cout<<"NO"<<endl;// continue;// }int flag=1;repd(i,1,9){cnt[i]=0;repd(j,1,9){isok[i][j]=1;}}isok[1][3]=isok[3][1]=0;isok[9][3]=isok[3][9]=0;isok[9][7]=isok[7][9]=0;isok[1][7]=isok[7][1]=0;isok[1][9]=isok[9][1]=0;isok[7][3]=isok[3][7]=0;isok[4][6]=isok[6][4]=0;isok[2][8]=isok[8][2]=0;int last=s[0]-'0';int x;x=last;cnt[x]++;if(x==2){isok[1][3]=isok[3][1]=1;}else if(x==4){isok[1][7]=isok[7][1]=1;}else if(x==5){isok[4][6]=isok[6][4]=1;isok[2][8]=isok[8][2]=1;isok[3][7]=isok[7][3]=1;isok[1][9]=isok[9][1]=1;}else if(x==6){isok[3][9]=isok[9][3]=1;}else if(x==8){isok[7][9]=isok[9][7]=1;}rep(i,1,len){x=s[i]-'0';cnt[x]++;if(!isok[last][x]){flag=0;break;}else{if(x==2){isok[1][3]=isok[3][1]=1;}else if(x==4){isok[1][7]=isok[7][1]=1;}else if(x==5){isok[4][6]=isok[6][4]=1;isok[2][8]=isok[8][2]=1;isok[3][7]=isok[7][3]=1;isok[1][9]=isok[9][1]=1;}else if(x==6){isok[3][9]=isok[9][3]=1;}else if(x==8){isok[7][9]=isok[9][7]=1;}}last=x;}repd(i,1,9){if(cnt[i]>1){flag=0;}}if(flag){cout<<"YES"<<endl;}else{cout<<"NO"<<endl;}}return 0; }inline void getInt(int* p) {char ch;do {ch = getchar();} while (ch == ' ' || ch == '\n');if (ch == '-') {*p = -(getchar() - '0');while ((ch = getchar()) >= '0' && ch <= '9') {*p = *p * 10 - ch + '0';}}else {*p = ch - '0';while ((ch = getchar()) >= '0' && ch <= '9') {*p = *p * 10 + ch - '0';}} }

?

轉載于:https://www.cnblogs.com/qieqiemin/p/10994855.html

總結

以上是生活随笔為你收集整理的长沙理工大学第十二届ACM大赛-重现赛C安卓图案解锁 （模拟）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。