Problem A Together

题目描述：

Problem Statement

Constraints

Input

Output

Sample Input 1

Sample Output 1

翻译成人话：

给一组数，对每一个数有三种操作：在原本基础上加一、在原本基础上减一、不变。然后对这三种情况进行统计，看看哪个数字出现次数最多，将最大次数输出。

思路：

题目给的a[i]最大可能是1e5，所以就开一个cnt[100010]的数组统计数字出现的次数。

代码：

#include <iostream>
#include <cstring>
using namespace std;

int main()
{
	int N;
	cin >> N;
	int cnt[100010];
	memset( cnt , 0 , 100010 * 4);
	for ( int i = 0 ; i < N ; i ++)
	{
		int t;
		scanf("%d",&t);
		cnt[t] ++;
		cnt[t + 1] ++;
		cnt[t - 1] ++;
	}
	int res = 0;
	for ( int i = 0 ; i < 100010 ; i ++)
	{
		if ( cnt[i] > res ) res = cnt[i];
	}
	printf("%d",res);
	
	return 0;
}

Problem B - Fractions Again?!

题目描述：

翻译成人话：

输入一个数k，需要满足1/k = 1/x + 1/y，然后把满足的条件的数量和式子输出。

思路：

题目给的k值最大是10000，那么x的取值大概在1e8左右，用两个for循环分别枚举x和y肯定会超时。

将式子1/k = 1/x + 1/y转换为y关于x的式子

所以先枚举一个x，然后结合k，验证所得的y是否满足要求（即是否能整除）

注意：根据数学推导可得，x的取值范围为[k+1,2k]，在这一部分讨论即可，多了可能超时，而且没有意义

代码：

这里我用a[]和b[]存储得到x和y的值

注意输出结果要按照题目的排序来

#include <stdio.h>

int main()
{
	int k;
	while ( scanf("%d",&k) != EOF)
	{
		int cnt = 0 , a[10000] , b[10000];
		for ( int x = k + 1 ; x <= 2 * k ; x ++)
		{
			if ( ( k * x ) % ( x - k ) == 0 )
			{
				a[cnt] = x;
				b[cnt] = ( k * x) / ( x - k);
				cnt ++;
			}
		}
		printf("%d\n",cnt);
		for ( int i = 0 ; i < cnt ; i ++)
		{
			printf("1/%d = 1/%d + 1/%d\n", k , b[i] , a[i]);
		}
	 } 
	return 0;
}

Problem C - Maximum Product

题目描述：

翻译成人话：

给定一组数，求出连续子序列乘积最大的值

思路：

题目要求的是连续子序列，遍历连续子序列只需要枚举起始坐标和终止坐标即可

代码：

这题恶心就恶心在输出上，需要有两个\n

因为题目中有这句话：

After each test case you must print a blank line.

#include <stdio.h>

int main()
{
	int N ,num = 0;
	while ( scanf("%d",&N) != EOF)
	{
		num ++;
		int a[N+10] ;
		for ( int i = 0 ; i < N ; i ++)
		{
			scanf("%d",&a[i]);
		}
		long long res = 0;
		for ( int i = 0 ; i < N ; i ++)
		{
			long long ans = 1;
			for ( int j = i ; j < N ; j ++)
			{
				ans *= a[j];
				if ( ans > res ) res = ans;
			}
		}
		printf("Case #%d: The maximum product is %lld.\n\n", num, res);
	}
	return 0;
}

Problem D - Division

题目描述：

翻译成人话：

给定一个数N，满足abcde / fghij = N，并且a b c d e f g h i j这十个数不能重复

如果有解，按顺序输出结果，没有的话输出There are no solutions for N.

思路：

和Problem B一样，想要枚举两个，肯定会超时，所以只能枚举一个，然后验证。

这里的验证需要验证两个地方：

• 验证是否满足abcde / fghij = N
• 验证a b c d e f g h i j这十个数是否重复

代码：

换行问题：

这题和Problem C一样，输出上面有点恶心，但是又不完全一样，第一行输出的时候不需要换行，后面的都需要换行。

所以用了bool is_first变量判断是否是第一行，如果是就不加\n，如果不是，那就加上

is_appear_once函数：

这是一个自定义函数，给定的x，y各个位数是否只出现一次

注意：这里的判断不能用下方这种代码进行判断

while ( x )
{
    cnt[ x % 10] ++;
    x /= 10;
}

因为如果传入的x为1，那么就只对1这个数加了一次，但是四个前导0都没有加进去，然而这也是不符合条件的。所以要用for循环。

#include <iostream>
#include <cstring>
using namespace std;

bool is_appear_once( int x , int y)
{
	if ( x > 99999 || y > 99999) return false;
	int cnt[10];
	memset( cnt , 0 , 10 * 4);
	for ( int i = 0 ; i < 5 ; i ++)
	{
		cnt[x % 10] ++;
		x /= 10;
	}
	for ( int i = 0 ; i < 5 ; i ++)
	{
		cnt[y % 10] ++;
		y /= 10;
	}
	for ( int i = 0 ; i < 10 ; i ++)
	{
		if ( cnt[i] != 1) return false;
	}
	return true;
}

int main()
{
	int n;
	bool is_first = true;
	while ( scanf("%d",&n) != EOF && n )
	{
		if( !is_first ) printf("\n");
		is_first = false;
		bool is_find = false;
		for ( int i = 1234 ; i < 100000 ; i ++)
		{
			if ( is_appear_once( i , i * n))
			{
				printf("%05d / %05d = %d\n", i * n , i , n);
				is_find = true;
			}
		}
		if ( !is_find) printf("There are no solutions for %d.\n", n );
		 
	}
	
	return 0;
}

Problem E - Ants

题目描述：

Sample Input

Sample Output

翻译成人话：

给定N只蚂蚁，并且给定他们的坐标以及活动范围，蚂蚁只会朝着一个方向走，如果遇到另一只蚂蚁就换个方向走，由于蚂蚁走的方向不确定，因此蚂蚁全部离开活动范围所需的时间也不一样，需要我们输出可能所需时间的最大值以及最小值。

思路：

对于所需时间的最小值：

只要让所有蚂蚁往距离自己最近的端点走即可，然后找出最后一只蚂蚁离开的时间，输出即可。

对于所需时间的最大值：

其实两只蚂蚁遇见之后，换个方向走，对结果没有影响，因为每只蚂蚁都是一样的，原本一只向左，一只向右，遇见之后是一只向右，一只向左，对整体来说没有影响。因此只需要要所有蚂蚁往距离自己最远的端点走即可，然后找出最后一只蚂蚁离开的时间，输出即可。

代码：

其实就是一个在所有最小值里找最大和在所有最大值里找最大的题目。

#include <iostream>

using namespace std;

int main()
{
	int N;
	cin >> N;
	while ( N --)
	{
		int len , num;
		cin >> len >> num;
		int a[1000010];
		for ( int i = 0 ; i < num ; i ++)
			cin >> a[i];
		int mins = 0 , maxs = 0;
		for ( int i = 0 ; i < num ; i ++)
		{
			mins = max( min(a[i] , len - a[i] ), mins);
		}
		for ( int i = 0 ; i < num ; i ++)
		{
			maxs = max( max(a[i] , len - a[i] ), maxs);
		}
		cout << mins << " " << maxs << endl;
	}
	
	return 0;
}