首页 > 其他分享 >【题解】favorite school

【题解】favorite school

时间:2023-01-31 23:55:26浏览次数:50  
标签:school ch return int 题解 favorite pos ++ ans

标准程序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

相关文章

  • Acwing 周赛88 题解
    比赛链接A题题目描述给定一个整数\(x\),请你找到严格大于\(x\)且各位数字均不相同的最小整数\(y\)。\(1000\lex\le9000\)做法分析发现数据范围很小,那么我们可以直......
  • 【题解】USACO 2023 January Sliver
    因为Glod打寄了,就来写写Sliver的题解吧,现在应该比赛结束了吧。A.FindAndReplace题目分析:我们可以对给定的串建出一种关系,也就是如果在上面的字符串中是字符\(c_1......
  • CF1098D 题解
    题意传送门对于一个元素个数大于\(1\)的可重集,每次取出两个数\(x,y\)合并。若\(x\ley\le2x\),则称其为危险合并。重复上述操作至无法合并。给你一个初始为空的可......
  • 【题解】[LNOI2022] 盒
    题目分析:我们可以对每一条边单独计算贡献,这样会发现贡献很好算:\[ans=\sum_{i=0}^{n-1}w_i\sum_{j=0}^S|j-s_i|\binom{i+j-1}{i-1}\binom{S-j+n-i-1}{n......
  • 【题解】P5169 xtq的异或和
    再强没有xtq!!!1思路多项式的正确用法。首先根据P4151[WC2011]最大XOR和路径的神秘结论,这里只需要任意求出原图的一棵生成树,以及所有只包含一条非树边的简单环就可以维......
  • 调用后台接口实现Excel导出功能以及导出乱码问题解决
    实现效果在导出表格数据的时候,通常分为两种情况页面列表数据导出接口返回数据导出这里主要介绍接口返回数据导出,关于页面的列表数据导出,请看另一篇:vue3+element表格......
  • CF1400E Clear the Multiset 题解 贪心+分治
    题目链接:http://codeforces.com/problemset/problem/1400/E题目大意:给定一个长度为\(n\)数列\(\{a_n\}\),你可以进行如下操作:操作1:任意选择一个区间\([l,r]\),使区间内......
  • P6327 区间加区间sin和 题解
    P6327区间加区间sin和题解第一道Ynoi(捂脸题目描述给出一个长度为\(n\)的整数序列\(a_1,a_2,\ldots,a_n\),进行\(m\)次操作,操作分为两类。操作\(1\):给出\(l,r,v......
  • [SDOI2008] 仪仗队【题解】
    题目描述作为体育委员,C君负责这次运动会仪仗队的训练。仪仗队是由学生组成的\(N\timesN\)的方阵,为了保证队伍在行进中整齐划一,C君会跟在仪仗队的左后方,根据其视线所......
  • Luogu P4145 上帝造题的七分钟 2 / 花神游历各国 题解
    Luogu链接:上帝造题的七分钟2/花神游历各国${\scr\color{Orchid}{\text{Solution}}}$题目大意支持两种操作:区间开方(向下取整)区间求和分析发现线段树容易实......