QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#823982 | #9834. Keyboard Chaos | 0x3f# | WA | 1ms | 3624kb | C++14 | 1.4kb | 2024-12-21 11:24:29 | 2024-12-21 11:24:30 |
Judging History
answer
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int N=1010;
int n,c,lim;
string s[N];
bool g[26][26];
struct node {
string nw;int step;
bool operator < (const node &o) const {
return step>o.step;
}
};
map<node,bool> mp;
string bfs(int c) {
bool flg=false;
for(int i=1;i<=n;i++)
if(c==s[i][0]-'a'+1) {
flg=true;
break;
}
if(flg==false) {
string ans="";
ans+=c+'a'-1;
return ans;
}
priority_queue<node> q;
string nw;
nw+=c+'a'-1;
q.push({nw,1});
while(!q.empty()) {
node u=q.top();
q.pop();
if(mp.count(u)) continue;
mp[u]=true;
if(u.nw.size()>lim) continue;
int back=u.nw[u.nw.size()-1]-'a'+1;
for(int i=1;i<=c;i++)
if(g[back][i]==false) {
string ans=u.nw;
ans+=i+'a'-1;
return ans;
} else {
string nxt=u.nw;
nxt+=i+'a'-1;
q.push({nxt,u.step+1});
}
}
return "!!!";
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
cin>>n>>c;
for(int i=1;i<=n;i++) {
cin>>s[i];
lim+=s[i].size();
for(int j=0;j<(int)s[i].size();j++) {
int u=s[i][j]-'a'+1;
int v=s[i][(j+1)%((int)s[i].size())]-'a'+1;
g[u][v]=true;
}
}
int len=0x3f3f3f3f;
string ans="";
for(int i=1;i<=c;i++) {
string nw_ans=bfs(i);
if(nw_ans.size()<len&&nw_ans!="!!!") {
len=nw_ans.size();
ans=nw_ans;
}
}
if(len==0x3f3f3f3f) cout<<"NO\n";
cout<<ans<<"\n";
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 1ms
memory: 3624kb
input:
1 26 win
output:
a
result:
ok Got unprintable string of length 1
Test #2:
score: 0
Accepted
time: 0ms
memory: 3588kb
input:
3 3 abc bca cab
output:
aa
result:
ok Got unprintable string of length 2
Test #3:
score: 0
Accepted
time: 0ms
memory: 3584kb
input:
4 2 aab bb a bab
output:
NO
result:
ok ok, can print any string
Test #4:
score: -100
Wrong Answer
time: 0ms
memory: 3624kb
input:
7 3 c ba acc bcb ab bac ac
output:
aa
result:
wrong answer pa="aa" can be typed by pressing next keys: "3,5"