求star

A - 放苹果#

题目#

小蒜想知道把 M 个同样的苹果放在 N 个同样的盘子里，允许有的盘子空着不放，共有多少种不同的分法？（用 K 表示）5，1，1和 1，$，1 是同一种分法。

输入格式#

第一行是测试数据的数目 t(0 < t < 20)。 以下每行均包含两个整数 M 和 N，以空格分开。1 < M, N < 10。

输出格式#

对输入的每组数据 M和 N，用一行输出相应的 K。

Sample Input: 1 7 3

Sample Output 8

思路#

本题主要根据 苹果与盘子数目之间的大小关系 和 是否有盘子空着 这两点分为不同的情况进行处理

代码#

#include <stdio.h>
int fcount(int m,int n){
	if(m==0||n==1)
		return 1; // 苹果数为0或者盘子数为1只有一种放法
	if(m < n)
		return fcount(m,m);
		/*当苹果数小于盘子数目的时候，只需要考虑将m个苹果
		放入m个盘子的情况即可，多余的盘子可以空着*/
	else
		return fcount(m,n-1)+fcount(m-n,n); 
		//对于苹果数大于盘子数的情况，分为 "有盘子空" 和 "所有盘子都有苹果" 这两种情况处理
}
 
int main(void)
{
	int t,n,m,count;
	scanf("%d",&t);
	while(t--)
	{
		scanf("%d %d",&m,&n);
		count=fcount(m,n);
		printf("%d\n",count);
	}
	
}

B - 非常男女#

题目#

近来，蒜头君致力于研究班上同学的配对问题（别想太多，仅是舞伴），通过各种推理和实验，他掌握了大量的实战经验。例如，据他观察，身高相近的人似乎比较合得来。 万圣节来临之际，蒜头君准备在学校策划一次大型的“非常男女”配对活动。对于这次活动的参与者，蒜头君有自己独特的选择方式。他希望能选择男女人数相等且身高都很接近的一些人。这种选择方式实现起来很简单。他让学校的所有人按照身高排成一排，然后从中选出连续的若干个人，使得这些人中男女人数相等。为了使活动更热闹，蒜头君当然希望他能选出的人越多越好。请编写程序告诉他，他最多可以选出多少人来。

输入格式#

第一行有一个正整数 $n\ (1\le n \le 10^5)$，代表学校的人数。 第二行有 $n$ 个用空格隔开的数，这些数只能是 $0$ 或 $1$，其中，$0$ 代表一个女生，$1$代表一个男生。

输出格式#

输出一个非负整数，这个数表示在输入数据中最长的一段男女人数相等的连续子序列长度。

Sample Input#

9 0 1 0 0 0 1 1 0 0

Sample Output#

6

思路#

本题是一道关于前缀和的题目，为方便之后的计算和比较我们先将原数组中代表女生的 0 改为 -1，男生还是1（这样做的好处是：当一个前缀和的值为1时，我们就能直接得出这段子列中男生个数比女生多1个，而在原来的表示方法中，前缀和为1只能说明是有一个男生）

• 所以问题转化为：只要找到两个位置的前缀和相等，他们之间就是男女相等的连续子序列。我们记录每个前缀和第一次出现的位置，下次出现的时候，减去第一次的位置就是长度。
• 然后用双重for循环来遍历每个区间，求出最大的长度

代码1#

#include<stdio.h>
#define MAX 100005
int main(void)
{
	int n,i,j;
	int a[MAX],vis[2*MAX],s[2*MAX]; 
	int ans=0;
	scanf("%d",&n);
	for(i=1;i<=n;i++)
	{
		scanf("%d",&a[i]);
		if(!a[i])
		{
			a[i]=-1;
		}
		s[i]=s[i-1]+a[i];
	}
	
	for(i=1;i<=n;i++)
	{
		for(j=0;j<i;j++)
		{
			if(s[i] == s[j])
			{
				if(i-j> ans)
				{
					ans=i-j;
				}
				break;//注意此步
			}
		}
	}
	
	printf("%d\n",ans);
	
	
	return 0;
}

注意：此方法中的break不可省略，省略过后时间复杂度太高会超时

代码2#

TIP

同时在查阅资料的同时还看到了一种 用空间换取时间的方法 基本思路是一致的，只不过这种方法创建了一个Map[]数组，用来查看当前前缀和有没有出现过（即是不是第一次出现），例如 Map[i]就是查看 i 这个前缀和是不是第一次出现

#include<stdio.h>

int main(void)
{
	int a[100001];
	int Map[200001],sum[200001];
	int n,i,ans;
	scanf("%d",&n);
	for(i=1;i<=n;i++)
	{
		scanf("%d",&a[i]);
		if(a[i]==0) 
			a[i]=-1;
		sum[i]=sum[i-1]+a[i];
	}
	
	for(i=1;i<=n;i++){
		//因为sum表示从1-n的前缀和，所以如果等于0；那么表示从1开始到目前这个数，
		//1和-1的个数是一样的，所以ans取max 
		if(sum[i]==0){
			ans=i;
			continue;
		}
		//  Map[j]  记录j这个前缀和出现的最早位置
		//如果前缀和出现过，更新ans值。 
		if(Map[sum[i]+n]  && ans<i-Map[sum[i]+n])
			ans=i-Map[sum[i]+n];
		//如果这个和没有出现过，就记录当前第一次出现的位置 
		if(Map[sum[i]+n]==0) 
			Map[sum[i]+n]=i;
	}
	
	printf("%d\n",ans);
	return 0;
}