ZISUOJ 2023秋季综合训练(八)

说明

 博主是ZISU在校学生，刚学C/C++才2个多月，为了记录自己的学习过程和分享思路，故写一些博客。当然我的代码许多时候不是最优解，欢迎大家评论留言一起学习。如果有友友想提交这些题试试自己的思路啥的，可以私我，因为外校友友应该是登陆不进咱们的平台的。

题目列表

 问题 A: 字符串加密

思路：数据读进来遍历即可。

注意：考虑到字符串会存在空格，所以不能用cin或scanf来读

参考题解：

#include <bits/stdc++.h>
using namespace std;
int main(){
	//问题 A: 字符串加密
	int ans = 0;
	char s[10005];gets(s);
	int len = strlen(s);
	for(int i = 0;i<len;i++){
		if(s[i] >= 'a' && s[i] <= 'z') ans += s[i]-'a';
		else if(s[i] >= '0' && s[i] <= '9') ans += (s[i]-'0')*i;
		else ans++;
	}
	cout << ans;
	return 0;
}

问题 B: k步排序

思路：题目只要求我们判断三种状态，并不是让我们用k步排序实际去做。因此，我们只需要判断数组num[i]与下标i同时对k求模是否相等。若所有数都相等，则输出0即可以直接k步排序；若有且仅有两个数不相等，则输出1即需要做一次预处理才能用k步排序实现效果；否则其他情况均输出-1即不能通过k步排序实现效果或做一次预处理后仍不能通过k步排序实现效果。

参考题解：

#include <bits/stdc++.h>
using namespace std;
int main(){
	//问题 B: k步排序
	int t;cin >> t;
	while(t--){
		int n,k,count = 0;
		cin >> n >> k;
		int num[20010];
		for(int i = 1;i<=n;i++){
			cin >> num[i];
			if(num[i]%k!=i%k) count++;
		}
		if(!count) cout << 0 << endl;
		else if(count == 2) cout << 1 << endl;
		else cout << -1 << endl;
	}
	return 0;
}

问题 C: 兔兔的快餐店

 

思路：暴力寻找同个时间出现最多的次数

参考代码：

#include <bits/stdc++.h>
using namespace std;
int main(){
	//问题 C: 兔兔的快餐店
	int n,index = 0,max = 0;cin >> n;
	int m[100005] = {0},count[2000] = {0},hour;
	while(n--){
		cin >> hour >> m[index];
		m[index] += hour*60;
		count[m[index]]++;
		index++;
	}
	for(int i = 0;i<2000;i++) if(count[i] > max && count[i]!=0) max = count[i];
	cout << max << endl;
	return 0;
}

问题 D: 解锁

 

思路： 很明显得用深度搜索算法bfs，但是这里因为锁长度只有4，我们直接暴力寻找即可

参考代码：

#include <bits/stdc++.h>
using namespace std;
set<string> ban;	//集合ban用于存放锁的引爆状态
string init,res;	//init为锁的初始状态，res为锁的解锁状态
struct node
{
    string s;
    int step;
}t,t1;
map<string,int> mp;//相当于bfs模板中的vis[]数组
queue<node> q;
void bfs(){
	t.s = init;t.step = 0; 
    q.push(t);
    while(!q.empty()){
        t=q.front();q.pop();
        if(t.s==res){
            cout << t.step;
            return;
        }
        if(mp.count(t.s)) continue;
        mp[t.s]=1;
        if(!ban.count(t.s)){
            for(int i=0;i<t.s.length();i++){
                if(t.s[i]=='9'){		//字符'9'特殊处理 
                    t1.s = t.s;t1.s[i]--;t1.step = t.step + 1;
                    q.push(t1);
                    t1.s[i]='0';
                    q.push(t1);
                }
                else if(t.s[i]=='0'){	//字符'0'特殊处理 
                    t1.s = t.s;t1.s[i]++;t1.step = t.step + 1;
                    q.push(t1);
                    t1.s[i]='9';
                    q.push(t1);
                }
                else{
					t1.s = t.s;t1.s[i]--;t1.step = t.step + 1;
                    q.push(t1);
                    t1.s[i] += 2;
                    q.push(t1);
                }
            }
        }
    }
}
int main(){
	//问题 D: 解锁
    cin >> init >> res;
    int w = init.length();
    string ss;
    cin >> ss;
    int t = 0;
    for(int i=0;i<ss.length();i++){
        if(ss[i]==',') {
            string s=ss.substr(t,i-t);
            ban.insert(s);
            t=i+1;
        }
    }
	ban.insert(ss.substr(t,ss.length()-1));
    bfs();
    return 0;
}

问题 E: 相似数组

 

思路：读入数组a[]，b[]，对两个数组升序排序。判断如果a[]与b[]有相同数据则消去该若干对数据即都置0。对于剩下的元素，如果有值大于9的数据则对其做一次f()运算，每做一次f()运算则操作次数+1，再次判断是否有相同数据，如果有则消去该若干对数据。最后判断剩下的元素的值，如果等于1则跳过即不做任何处理，因为后续另外一个数组里其他的数字可以再进行一次f()运算后与这个值1抵消；剩下的每遇到不等于1且不等于0的数，操作次数+1，意味着它们可以通过一次f()变成1相等后消去，但是这次我们不需要做f()运算了。

参考题解：

#include <bits/stdc++.h>
using namespace std;
int f(int x){										//求数字长度函数 
	int temp = x,count = 0;
	while(temp != 0){
		count++;
		temp /= 10;
	}
	return count;
} 
int main(){
	//问题 E: 相似数组
	int t;cin >> t;
	while(t--){
		int n,count = 0;cin >> n;
		int a[200010],b[200010];
		for(int i = 0;i<n;i++) cin >> a[i];	//读a[]数组
		for(int i = 0;i<n;i++) cin >> b[i];	//读b[]数组 
		sort(a,a+n);sort(b,b+n);					//排序，目的是加快后续找相同元素的速度 
		for(int i = 0;i<n;i++){						//抵消两个数组中相同的元素即置0 
			for(int j = 0;j<n;j++){
				if(a[i] == b[j]){
					a[i] = 0;b[j] = 0;break;
				}
			}
		}
		for(int i = 0;i<n;i++){	//如果两个数组中有大于9的数字，则count++，并且对该数字求长度 
			if(a[i]!=0&&a[i]>9){
				count++;
				a[i] = f(a[i]);
			}
			if(b[i]!=0&&b[i]>9){
				count++;
				b[i] = f(b[i]);
			}
		}
		for(int i = 0;i<n;i++){	//再次消去两个数组中相同的数字即置0 
			for(int j = 0;j<n;j++){
				if(a[i] == b[j]){
					a[i] = 0;b[j] = 0;break;
				}
			}
		}
		for(int i = 0;i<n;i++){	//最后找小于10且不等于0且不等于1的数字，找到一个就count++ 
			if(a[i] != 0&&a[i] != 1) count++;
			if(b[i] != 0&&b[i] != 1) count++;
		}
		cout << count << endl;
	}
	return 0;
} 

问题 F: 兔兔的平均值 

思路：观察X与Y的值，如果X与Y相等，那么对于数字来说无论选择X还是Y，最终的平均值之和还是相等的，于是结果先输入1保证字典序最小；如果X与Y不相等，两个集合中较小的那个集合应该选择更大的数来确保最终的平均值之和最大。

该题思路来自于bu-fan：https://www.cnblogs.com/bu-fan/p/17904710.html

参考题解：

#include <bits/stdc++.h>
using namespace std;
struct node{
    int sum,id;
}a[100005];
int n,x,y;
bool cmp1(node x,node y){
    return x.sum==y.sum?x.id<y.id:x.sum>y.sum;
}
bool cmp2(node x,node y){
    return x.sum==y.sum?x.id>y.id:x.sum>y.sum;
}
int main(){
	//问题 F: 兔兔的平均值
    cin >> n;
    cin >> x >> y;
    for(int i=1;i<=n;i++){
        cin >> a[i].sum;
        a[i].id=i;
    }
    vector<int> b(n+1);
    if(x==y){
        for(int i=1;i<=n;i++){
            if(i<=n/2) cout << "1 ";
            else cout << "2 ";
        }
		cout << endl;
        return 0;
    }
    else if(x<y){
        sort(a+1,a+1+n,cmp1);
        for(int i=1;i<=x;i++){
            b[a[i].id]=1;
        }
        for(int i=x+1;i<=n;i++) {
            b[a[i].id]=2;
        }
    }
    else{
        sort(a+1,a+1+n,cmp2);
        for(int i=1;i<=y;i++){
            b[a[i].id]=2;
        }
        for(int i=y+1;i<=n;i++) {
            b[a[i].id]=1;
        }
    }
    for(int i=1;i<=n;i++) 
    cout << b[i] << " ";
    cout << endl;
    return 0;
}