题解-2020USST算法竞赛练习场5 ABC

题解系列

• 自己写的题解

2020年上海理工大学算法竞赛训练场5 A~C

A. Ones

题意：给定一个不能被2和5整除的数n，求出它的一个 全由1组成的 最小倍数的位数

算法：暴力枚举

从1、11、111…这样枚举下去，但是这样下去会爆(long long)，因此考虑模运算的性质，如果没找到答案则只要用(上一次的答案%n)*10+1即可

#include<bits/stdc++.h>
using namespace std;

int main(){
	int n;
	while(scanf("%d",&n)!=EOF){
		int giao=1;
		int ans=1;
		while(giao%=n){
			giao=giao*10+1;
			ans++;
		}
		cout<<ans<<endl;
	}
	return 0;
}

B. Robotopia

题意：分别给出拼成一个A机器人和一个B机器人所需要的 手零件个数（l1、a1） 和 腿零件个数（l2、a2），再给出当前你所拥有的全部的 手零件个数（lt） 和 腿零件个数（at），问恰好用完这些零件能拼成几个A机器人和几个B机器人？如果不能拼成或者有多种方案，则输出”？”

算法：枚举

数据范围很小，真的只是枚举即可，一定要注意判断条件 以及 不要搞错边界

详细题解：

我们很容易可以想到，这就是解一个如下的方程组的正整数解（注意，题目要求输出正整数解（positive integers））：

$$l_1*x+l_2*y=lt\\ a_1*x+a_2*y=at$$

那么我们可以从1开始（0被pass掉）枚举x，遇到边界就停止，判断是否同时有

$$l_t-x*l_1能被l_2整除\\ a_t-x*a_1能被a_2整除\\ 且 这两个整除的商相等$$

记录有效答案及其次数，如果枚举完之后有且仅有一种有效答案，则输出该答案，否则输出”?”

#include<bits/stdc++.h>
using namespace std;
int main(){
	int  t;
	cin>>t;
	while(t--){
		int l1,a1,l2,a2,lt,at;
		cin>>l1>>a1>>l2>>a2>>lt>>at;
		int cnt=0,ansx=0,ansy=0;
		for(int i=1;i*l1<lt&&i*a1<at;i++){
			int giaol=lt-i*l1;
			int giaoa=at-i*a1;
			if(giaol%l2==0&&giaoa%a2==0&&giaol/l2==giaoa/a2){
				ansx=i;
				ansy=giaol/l2;
				cnt++;
			}
		}
		if(cnt==1){
			cout<<ansx<<" "<<ansy<<endl;
		}else{
			cout<<"?"<<endl;
		}
	}
	return 0;
}

C. What does the fox say?

题意：给出t组测试数据，每组的第1行是需要判断的叫声字符串（每个叫声由空格隔开），接下来若干行以“xx goes xx”的形式呈现出“某动物 发出 某叫声”，最后以“what does the fox say?”结束，要求从第1行的叫声字符串中找出下面若干行没有出现过的叫声

算法：先用vector把需要判断的叫声存入，然后再用set标记每个出现了的叫声，最后一个个判断有没有出现即可，需要注意一下字符串处理

#include<bits/stdc++.h>
using namespace std;
int main(){
	int t;cin>>t;getchar();
	while(t--){
		vector<string> vec;
		set<string> se;
		string temp;
		while(cin>>temp){
			if(temp=="goes"){ //如果出现了goes说明出现了第二行输入
				cin>>temp; //goes后面肯定还有一个输入，这是出现的第一个叫声
				se.insert(temp);//存进set
				vec.pop_back(); //goes之前有个无用的字符串，删掉它
				break;
			}
			vec.push_back(temp);
		}
		string giao,giaogiao;
		while(cin>>giao>>temp>>giaogiao){//xx goes xx
			if(temp!="goes"){
				cin>>temp>>giao; //因为最后一次输入没用，但它有五个字符串，所以我都吃掉，然后break
				break;
			}
			se.insert(giaogiao); //存入set
		}
		for(int i=0;i<vec.size();i++){
			if(se.find(vec[i])==se.end()){
				cout<<vec[i];
				if(i==vec.size()-1) cout<<endl;
				else cout<<" ";
			}
		}
	}
	return 0;
}