[C++知识库]系列题解二

高中运动会(sports)

问题描述：

A市每年为全市高中生举办一次运动大会。为促进各校同学之间的交流，采用特别的分队方式：每一个学校的同学，必须被均匀分散到各队，使得每一队中该校的人数皆相同。为增加比赛的竞争性，希望分成越多队越好。输入各校的人数，编程求出最多可分成的队数。

输入格式：

第一行为正整数t(≤10)，表示数据组数；每组数据中，第一行为一个正整数n，代表学校的个数(≤500)，第二行一共有n个正整数ai(≤10000)，分别代表这N个学校的人数。

输出格式：

对于每组数据，输出最多可分成的队数。

赋值问题(let)

问题描述：

在很多程序设计语言中，忘记给变量赋初值的错误常令人头疼。为了简化起见，在下面的问题中，使用这样的赋值语句，其格式为：<变量名>=<变量名>|<常量>，其中变量名为单个小写字母，常量则为一位正整数(包括0)。如：b=4或c=b均为合理的赋值语句。请编程求出含N行的程序段运行以后有哪些变量中有具有确定的值。

输入格式：

第一行是正整数N (≤104), 以下N行，每行为一条赋值语句（3个字符）。

输出格式：

如果没有变量有确定的值，输出“none”；否则按字母顺序给出所有有确定值的变量名及其值（用“:”分隔），一个变量一行。

样例解释

第2个条赋值语句没有意义，因为d没有初值，同样，第4条赋值语句也没有意义。因此，只有b和d获得值。

银行排队(bank)

问题描述：

在银行里的一个柜台窗口前，有n个人在排队办理业务，已知每个人办理业务的时间分别为ti，而当他排队的时间超过ti时，他就会变得很不满意（他就会立刻转身离开，并向银行主管投诉）。下面帮助银行的工作人员，改变排队的顺序，使得队伍里不满意的人数最少。假定所有的人到达银行的时间一致。

输入格式：

第一行为正整数t(≤5)，表示数据组数；每组数据中，第一行为正整数n(≤105)，第二行为以空格隔开的n个正整数ti(≤106)。

输出格式：

对于每组数据，输出一个正整数，表示满意人数的最大值。

同构字符串(same)

问题描述：

给定一个字符串s，可以把s的任意两个字符交换位置，也可以交换任意多次，经过交换之后的字符串被称为s的同构串。

例如s=”abac”，则”aabc”,”aacb”,”baac”等都是s的同构串，而”baab”,”bcab”等都不是s的同构串。

输入字符串s和t，求t有多少个子串与s同构。

输入格式：

第一行为字符串s，长度不超过1000；第二行为字符串t，长度不超过5000000；所有输入只包含小写字母。

输出格式：

仅一个整数，表示同构子串的个数。

数据规模：

40%数据中，s串长不超过200，t串长不超过100000；

100%数据中，s串长不超过1000，t串长不超过5000000。

第一题高中运动会

一.题目大意

这道题就是要求把每个学校分成若干组，要求学校之间不能混合产生一组，必须整除

那也就是求这n个数的最大公约数

二.算法思路

就是辗转相除法最大公约数，gcd(a,b,c,d)=gcd(a,gcd(b,gcd(c,d)))

辗转相除法证明

1.演化

它是由更像减损转变而来，就是说如果a=m*k,b=n*k,k=gcd(a,b)那么k<=a-b

然后问题转变成gcd(a-b,b)这个时候如果a>2b(a-b>b)那么就继续见。。。

但这样就很慢，于是我们发现只需要取余数，具体的商是多少不用管

所以直接用模法

2.实现

为了方便实现，我们首先强调a<b

那么

int gcd(int a,int b)

然后

if(a==0)return b;if(a==1)return 1;//边界

接着递归

return gcd(b%a,a);

撒花

三.代码实现

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

int n,a;

int t;

int ans;

inline int gcd(int a,int b){
	if(a==0)return b;
	if(a==1)return 1;
	return gcd(b%a,a);
}

int main(){
	freopen("sports.in","r",stdin);
	freopen("sports.out","w",stdout);
	scanf("%d",&t);
	while(t--){
		scanf("%d",&n);
		ans=0;
		for(int i=1;i<=n;i++){
			scanf("%d",&a);
			if(ans<a)ans=gcd(ans,a);
			else ans=gcd(a,ans);
		}
		printf("%d\n",ans);
	}
	return 0;	
}

第二题赋值运算

一.题目大意

只有理解了数学建模才能精准模拟

就是说当a=num时，a拥有的是num的属性（也就是num的大小）

? ? ? ? ? 当a=b是，a拥有的是b的属性（也就是b是什么状态a就是什么状态）

二.算法思路

那需要解决的问题，就是如何记录或传递属性（其实就是数值，我们可以把“没有初值”量化为无穷大0x3f3f3f3f）

那么我们发现可以使用标记数组来映射t[char-'a']=...

其实也就是桶

那么分类以上两种

1.t[char-'a']=num-'0'

2.t[char-'a']=t[charb-'a'];

注意没有初值也是可以传递的

三.代码实现

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

int t[26];
int n=0;

char a,c;

int main(){
	freopen("let.in","r",stdin);
	freopen("let.out","w",stdout);
	scanf("%d",&n);
	memset(t,0x3f,sizeof t);
	for(int i=1;i<=n;i++){
		cin>>a>>c>>c;
		if(c>='a' && c<='z'){
			/*说明变量赋值*/
			t[a-'a']=t[c-'a'];
		}else {
			t[a-'a']=c-'0';
		}
	}
	bool flag=0;
	for(int i=0;i<26;i++){
		if(t[i]!=0x3f3f3f3f){
			flag=1;
			cout<<(char)(i+'a')<<':'<<t[i]<<endl;
		}
	}
	if(flag==0)cout<<"none"<<endl;
	return 0;
}

第三题银行排队

一.题目大意

给定一个数列，要求进行排序使得其中“不满足”的最少

什么是不满足，由于每个人有一定的办事时间，那么第i个人就必须等待Σa[i-1]个人，那么就有可能不耐烦，也就是量化为等的时间比办事时间都长，得不偿失 当然前面i-1个人中也有可能被气走的，所以就需要好好安排一下

二.算法思路

这题不显然的贪心吗？

理由1

由于排在前面的人如果办事时间越短，那么后面等待的时间就越短，那么留下的就尽可能多

理由2

由于时间越短的人越有可能被气走，所以放在前面供着

那么这题及时对于t[i]排序，接着从头到位扫一遍

注意一个点，只有心平气和的人才会加上办事时间，

三.代码实现

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

const int N=100005;

int a[N],n;

inline int read(){
	int a=0;char c=getchar();
	while(!isdigit(c))c=getchar();
	while(isdigit(c))a=a*10+c-'0',c=getchar();
	return a;
}

int	work(){
	int ans=0;
	n=read();
	for(int i=1;i<=n;i++)a[i]=read();
	sort(a+1,a+n+1);
	int wait=0;
	for(int i=1;i<=n;i++){
		if(wait<=a[i]){
			ans++;
		wait+=a[i];
		}
	}
	cout<<ans<<endl;
	return 0;
}

int main(){
	freopen("bank.in","r",stdin);
	freopen("bank.out","w",stdout); 
	int t=read();
	while(t--){
		work();
	}
	return 0;
}

第四题同构字符串

这道题首先是四十分的写法，就是暴力枚举所有的子串比较

但是拿40PTS

正解：

一.题目大意

就是判断字符串中b的子串有多少个是和字符串a同构的

所谓同构，也就是各个字母的数量一致的两个字符串，当然不包含顺序

也就是说，我们最笨的能够strlen(a)的算法

但是只有40PTS!!

二.算法思路

所以怎么打正解呢

1.至少一正常初中的思路，无法想到如何不遍历整个b串就解决问题的方法

2.但是由于我们必须遍历，那就不重不漏

怎么不重不漏

尺取法，由于从i开始的子串和从i+1开始的子串知识多了一个b[i+n]少了一个b[i]于是o(strlen(b)*26）完美撒花

三.代码实现

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

char a[1005],b[5000005];

int ta[26],t2[26];

int la,lb;

int main(){
	freopen("same.in","r",stdin);
	freopen("same.out","w",stdout);
	scanf("%s%s",a,b);
	int ans=0;
	la=strlen(a),lb=strlen(b);
	for(int i=0;i<strlen(a);i++)ta[a[i]-'a']++;
	for(int i=0;i<la;i++)t2[b[i]-'a']++;
	for(int i=1;i+la-1<lb;i++){
		bool flag=1;
		for(int j=0;j<26;j++){
			if(ta[j]!=t2[j]){
				flag=0;
				break;
			}
		}
		if(flag==1)ans++;
		t2[b[i-1]-'a']--;
		t2[b[i+la-1]-'a']++;
	}
	int flag=1;
		for(int j=0;j<26;j++){
			if(ta[j]!=t2[j]){
				flag=0;
				break;
			}
		}
		if(flag==1)ans++;
	cout<<ans<<endl;		
	return 0;
}