标准程序1:
#include<bits/stdc++.h>
using namespace std;
int t,del,cha,flag[4],check[4];
string s;
unordered_map <char, int> pos;
int slove(int x,int y,int z,int d){
if(d>4) return 0;
else if(pos[s[x+z]]==y-z) return 1;
else if(!slove(pos[s[x+z]],y,z,d+1)) return 0;
flag[pos[s[x+z]]]=1;
return 1;
}
int main(){
ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
pos['J']=0,pos['K']=1,pos['F']=2,pos['Z']=3;
cin>>t;
while(t--){
cin>>s;
for(int i=0;i<s.length();i++){
if(s[i] == 'J') check[0]++;
if(s[i] == 'K') check[1]++;
if(s[i] == 'F') check[2]++;
if(s[i] == 'Z') check[3]++;
}
if(check[0]&&check[1]&&check[2]&&check[3]){
for(int i=0;i<=s.length()-4;i++){
for(int j=0;j<=3;j++)
if(!flag[j])
{cha+=slove(j,i+j,i,1);}
memset(flag,0,sizeof(flag));del=max(del,cha),cha=0;
}
cout<<s.length()-del<<endl;
}
else cout<<-1<<endl;
memset(check,0,sizeof(check));del=0;
}
return 0;
}
标准程序2:
#include <bits/stdc++.h>
#define PCI pair<char, int>
#define fi first
#define se second
using namespace std;
const int N = 1e4 + 10;
string s; int len;
int T, ans;
char goal[4] = {'J', 'K', 'F', 'Z'};
unordered_map <char, int> pos;
unordered_map <int, char> num; //是指这个位置上存的字母
PCI dif[5];//未归位
int cnt;
int check(string s){
//O(80Tn)
int len = s.length(), res = len - 4, ans = res;
int ch[5] = {};
num.clear(); cnt = 0;
if(res < 0) return -1;
for(int i = 0; i < len; i++){
if(s[i] == 'J') ch[1]++;
if(s[i] == 'K') ch[2]++;
if(s[i] == 'F') ch[3]++;
if(s[i] == 'Z') ch[4]++;
}
if(ch[1] < 1 || ch[2] < 1 || ch[3] < 1 || ch[4] < 1) return -1;
int mina = N;
for(int i = 0; i <= len - 4; i++){
memset(dif, 0, sizeof(dif));
res = ans, cnt = 0;
for(int j = 0; j < 4; j++){
num[j] = s[i + j];
if(s[i + j] != goal[j]){
++cnt, dif[cnt].fi = s[i + j], dif[cnt].se = j;
}
}
if(cnt == 0){
return res;
}else if(cnt == 1){
res++;
}else if(cnt == 2){
if(pos[num[pos[dif[1].fi]]] == dif[1].se) res++;
else res += 2;
}else if(cnt == 3){
if((pos[num[pos[num[pos[dif[1].fi]]]]] == dif[1].se) || (pos[num[pos[dif[1].fi]]] == dif[1].se || pos[num[pos[dif[2].fi]]] == dif[2].se || pos[num[pos[dif[3].fi]]] == dif[3].se)) res += 2;
else res += 3;
}else if(cnt == 4){
int a = 0;
if(pos[num[pos[dif[1].fi]]] == dif[1].se) a++;
if(pos[num[pos[dif[2].fi]]] == dif[2].se) a++;
if(pos[num[pos[dif[3].fi]]] == dif[3].se) a++;
if(pos[num[pos[dif[4].fi]]] == dif[4].se) a++;
if(a == 2 || a == 4){
if(a == 2) res += 3;
else res += 2;
}else if((pos[num[pos[num[pos[num[pos[dif[1].fi]]]]]]] == dif[1].se) || (pos[num[pos[num[pos[dif[1].fi]]]]] == dif[1].se || pos[num[pos[num[pos[dif[2].fi]]]]] == dif[2].se || pos[num[pos[num[pos[dif[3].fi]]]]] == dif[3].se || pos[num[pos[num[pos[dif[3].fi]]]]] == dif[3].se)) res += 3;
else res += 4;
}
mina = min(mina, res);
}
return mina;
}
int main(){
ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
pos['J'] = 0, pos['K'] = 1, pos['F'] = 2, pos['Z'] = 3; //pos是指字母应该在的位置
cin >> T;
while(T--){
cin >> s;
ans = check(s);
if(ans == -1) cout << -1 << endl;
else cout << ans << endl;
}
return 0;
}
标签:school,ch,return,int,题解,favorite,pos,++,ans
From: https://www.cnblogs.com/Seaniangel/p/17081208.html