没事儿也来做做题

發表於 2022-06-26 分類於开发笔记

http://sdoi.programming-rabbit.com/

第一题

题目描述

张三和李四在玩一种游戏。

首先，张三从 A 与 B 之间（包括A和B）选择一个整数，告诉李四。

其次，李四从 C 与 D 之间（包括C和D）选择一个整数。

两个整数之和，如果是素数，张三赢，否则李四赢。

当两个人都是最佳发挥时，谁会赢？

输入格式：
一行四个正整数 A B C D 以空格隔开。

输入格式：
如果张三赢了，输出 X，否则输出 Y。

代码实现

#include <iostream>
#include <sys/time.h>

using namespace std;

bool IsPrimeNumber(int n)
{
	if (n < 2)
	{
		return false;
	}

	int SquareRoot = 1;

	while (SquareRoot * SquareRoot < n)
	{
		SquareRoot++;
	}

	for (int i = 2; i <= SquareRoot; i++)
	{
		if (n % i == 0)
		{
			return false;
		}
	}

	return true;
}

int main(int argc, char **argv)
{
	int a = 0;
	int b = 0;
	int c = 0;
	int d = 0;
	int i = 0;
	int j = 0;
	int sum = 0;
	int x_win = 0;
	int y_win = 0;
	bool PrimeExist = false;

	int usec_bgn;
	int usec_end;
	int usec_sub;
	struct timeval tv;

	/* 等待输入 */
	cin>>a>>b>>c>>d;
	// a = 1; b = 100; c = 2; d = 3;

	/* 参数判断 */
	if (a <= 0 || a > 100 || b <= 0 || b > 100 || c <= 0 || c > 100 || d <= 0 || d > 100)
	{
		printf("error input! a, b, c, d should be greater than zero and less than or equal to 100! \r\n");
		return 0;
	}

	/* 参数判断 */
	if (a > b || c > d)
	{
		printf("error input! b is bigger than a!\r\n");
		return 0;
	}

	/* 参数判断 */
	if (c > d)
	{
		printf("error input! d is bigger than c!\r\n");
		return 0;
	}

	// printf("%d,%d,%d,%d\r\n", a, b, c, d);

	/* 起始时间 */
	gettimeofday(&tv, NULL);
	usec_bgn = (int)tv.tv_usec;
	printf("\r\n");
	printf("bgn time (second, micro-second): %ds, %dus\r\n", (int)tv.tv_sec, (int)tv.tv_usec);
	printf("\r\n");

	/* 胜负推演 */
	for (i = a; i <= b; ++i)
	{
		PrimeExist = false;

		for (j = c; j <= d; ++j)
		{
			sum = i + j;

			if (IsPrimeNumber(sum))
			{
				PrimeExist = true;
				break;
			}

		}

		if (PrimeExist)
		{
			y_win++;

			#if 1 /* 如果不想显示中间过程，可以屏蔽下行（将 #if 1 改为 #if 0） */
			printf("X = %d\tY = %d\tSUM  = %d \tY WIN !\r\n", i, j, sum);
			#endif
		}
		else
		{
			x_win++;

			#if 1 /* 如果不想显示中间过程，可以屏蔽下行（将 #if 1 改为 #if 0） */
			printf("X = %d\tY =  \tSUM != Prime \tX WIN !\r\n", i);
			#endif
		}
	}

	printf("\r\n");

	/* 比较小X和小Y总的胜负次数 */
	if (x_win > y_win)
	{
		printf("X WIN TIMES = %d, Y WIN TIMES = %d, SO X WINS FINALLY !\r\n", x_win, y_win);
	}
	else
	if (x_win < y_win)
	{
		printf("X WIN TIMES = %d, Y WIN TIMES = %d, SO Y WINS FINALLY !\r\n", x_win, y_win);
	}
	else
	{
		printf("X WIN TIMES = %d, Y WIN TIMES = %d, DRAWN GAME !\r\n", x_win, y_win);
	}

	/* 结束时间 */
	gettimeofday(&tv, NULL);
	usec_end = (int)tv.tv_usec;
	printf("\r\n");
	printf("end time (second, micro-second): %ds, %dus\r\n", (int)tv.tv_sec, (int)tv.tv_usec);
	printf("\r\n");

	/* 计算耗时 */
	if (usec_end >= usec_bgn)
	{
		usec_sub = usec_end - usec_bgn;
	}
	else
	{
		usec_sub = 1000000 - (usec_bgn - usec_end);
	}
	printf("time cost :%d us\r\n", usec_sub);
	printf("\r\n");

	return 0;
}

测试记录

编译环境 windows subsystem for linux (wsl) & gcc/g++ v9.3.0

user@localhost:/mnt/e/gcc$ g++ main.cpp -o main.cppout
user@localhost:/mnt/e/gcc$ ./main.cppout
1 100 2 3

bgn time (second, micro-second): 1656168565s, 669332us

X = 1   Y = 2   SUM  = 3        Y WIN !
X = 2   Y = 3   SUM  = 5        Y WIN !
X = 3   Y = 2   SUM  = 5        Y WIN !
X = 4   Y = 3   SUM  = 7        Y WIN !
X = 5   Y = 2   SUM  = 7        Y WIN !
X = 6   Y =     SUM != Prime    X WIN !
X = 7   Y =     SUM != Prime    X WIN !
X = 8   Y = 3   SUM  = 11       Y WIN !
X = 9   Y = 2   SUM  = 11       Y WIN !
X = 10  Y = 3   SUM  = 13       Y WIN !
X = 11  Y = 2   SUM  = 13       Y WIN !
X = 12  Y =     SUM != Prime    X WIN !
X = 13  Y =     SUM != Prime    X WIN !
X = 14  Y = 3   SUM  = 17       Y WIN !
X = 15  Y = 2   SUM  = 17       Y WIN !
X = 16  Y = 3   SUM  = 19       Y WIN !
X = 17  Y = 2   SUM  = 19       Y WIN !
X = 18  Y =     SUM != Prime    X WIN !
X = 19  Y =     SUM != Prime    X WIN !
X = 20  Y = 3   SUM  = 23       Y WIN !
X = 21  Y = 2   SUM  = 23       Y WIN !
X = 22  Y =     SUM != Prime    X WIN !
X = 23  Y =     SUM != Prime    X WIN !
X = 24  Y =     SUM != Prime    X WIN !
X = 25  Y =     SUM != Prime    X WIN !
X = 26  Y = 3   SUM  = 29       Y WIN !
X = 27  Y = 2   SUM  = 29       Y WIN !
X = 28  Y = 3   SUM  = 31       Y WIN !
X = 29  Y = 2   SUM  = 31       Y WIN !
X = 30  Y =     SUM != Prime    X WIN !
X = 31  Y =     SUM != Prime    X WIN !
X = 32  Y =     SUM != Prime    X WIN !
X = 33  Y =     SUM != Prime    X WIN !
X = 34  Y = 3   SUM  = 37       Y WIN !
X = 35  Y = 2   SUM  = 37       Y WIN !
X = 36  Y =     SUM != Prime    X WIN !
X = 37  Y =     SUM != Prime    X WIN !
X = 38  Y = 3   SUM  = 41       Y WIN !
X = 39  Y = 2   SUM  = 41       Y WIN !
X = 40  Y = 3   SUM  = 43       Y WIN !
X = 41  Y = 2   SUM  = 43       Y WIN !
X = 42  Y =     SUM != Prime    X WIN !
X = 43  Y =     SUM != Prime    X WIN !
X = 44  Y = 3   SUM  = 47       Y WIN !
X = 45  Y = 2   SUM  = 47       Y WIN !
X = 46  Y =     SUM != Prime    X WIN !
X = 47  Y =     SUM != Prime    X WIN !
X = 48  Y =     SUM != Prime    X WIN !
X = 49  Y =     SUM != Prime    X WIN !
X = 50  Y = 3   SUM  = 53       Y WIN !
X = 51  Y = 2   SUM  = 53       Y WIN !
X = 52  Y =     SUM != Prime    X WIN !
X = 53  Y =     SUM != Prime    X WIN !
X = 54  Y =     SUM != Prime    X WIN !
X = 55  Y =     SUM != Prime    X WIN !
X = 56  Y = 3   SUM  = 59       Y WIN !
X = 57  Y = 2   SUM  = 59       Y WIN !
X = 58  Y = 3   SUM  = 61       Y WIN !
X = 59  Y = 2   SUM  = 61       Y WIN !
X = 60  Y =     SUM != Prime    X WIN !
X = 61  Y =     SUM != Prime    X WIN !
X = 62  Y =     SUM != Prime    X WIN !
X = 63  Y =     SUM != Prime    X WIN !
X = 64  Y = 3   SUM  = 67       Y WIN !
X = 65  Y = 2   SUM  = 67       Y WIN !
X = 66  Y =     SUM != Prime    X WIN !
X = 67  Y =     SUM != Prime    X WIN !
X = 68  Y = 3   SUM  = 71       Y WIN !
X = 69  Y = 2   SUM  = 71       Y WIN !
X = 70  Y = 3   SUM  = 73       Y WIN !
X = 71  Y = 2   SUM  = 73       Y WIN !
X = 72  Y =     SUM != Prime    X WIN !
X = 73  Y =     SUM != Prime    X WIN !
X = 74  Y =     SUM != Prime    X WIN !
X = 75  Y =     SUM != Prime    X WIN !
X = 76  Y = 3   SUM  = 79       Y WIN !
X = 77  Y = 2   SUM  = 79       Y WIN !
X = 78  Y =     SUM != Prime    X WIN !
X = 79  Y =     SUM != Prime    X WIN !
X = 80  Y = 3   SUM  = 83       Y WIN !
X = 81  Y = 2   SUM  = 83       Y WIN !
X = 82  Y =     SUM != Prime    X WIN !
X = 83  Y =     SUM != Prime    X WIN !
X = 84  Y =     SUM != Prime    X WIN !
X = 85  Y =     SUM != Prime    X WIN !
X = 86  Y = 3   SUM  = 89       Y WIN !
X = 87  Y = 2   SUM  = 89       Y WIN !
X = 88  Y =     SUM != Prime    X WIN !
X = 89  Y =     SUM != Prime    X WIN !
X = 90  Y =     SUM != Prime    X WIN !
X = 91  Y =     SUM != Prime    X WIN !
X = 92  Y =     SUM != Prime    X WIN !
X = 93  Y =     SUM != Prime    X WIN !
X = 94  Y = 3   SUM  = 97       Y WIN !
X = 95  Y = 2   SUM  = 97       Y WIN !
X = 96  Y =     SUM != Prime    X WIN !
X = 97  Y =     SUM != Prime    X WIN !
X = 98  Y = 3   SUM  = 101      Y WIN !
X = 99  Y = 2   SUM  = 101      Y WIN !
X = 100 Y = 3   SUM  = 103      Y WIN !

X WIN TIMES = 50, Y WIN TIMES = 50, DRAWN GAME !

end time (second, micro-second): 1656168565s, 670078us

time cost :746 us

user@localhost:/mnt/e/gcc$

第二题

题目描述

张三成为了一家餐厅的采购员。作为一个采购员要有良好的职业素养。必须保证每次采购的物资不超过自己车辆的容量，然后在此条件下使得餐厅赚取的收益最大。

商场中共有 n 种物资，编号为 1 到 n 。每种物资都有两个参数 v 和 w，分别表示这种物资的体积和采购这种物资可以给餐厅带来的收益。注意每种物资每天至多只能采购一件。

张三有一辆容量为 V 的采购车，每天张三只去采购一次，采购的物资体积之和不能超过车辆的容量。

对于每天采购的物资，餐厅老板还有特殊的要求，第 i 天老板要求张三不能采购编号大于等于 Li 并且小于等于 Ri 的物资（即不能采购编号在 [Li,Ri] 之间的物资）。特别的，当 Li>Ri 时表示这天没有不可采购的物资。

对于接下来的 m 天，你需要告诉张三他每天分别最多可以给餐厅赚取多少的收益。

输入格式：
输入第一行两个个整数 n, V 表示共有 n 种物资，张三的车子容量是 V。
接下来 n 行，每行两个整数。
第 i+1 行输入vi, wi 表示第 i 种物资的体积和收益。
接下来一行输入一个整数 m ，表示需要采购的天数。
接下来 m 行，每行输入两个整数 Li, Ri 表示第 i 天不能采购编号位于 Li 到 Ri 之间的物资。

输出格式：
输出共 m 行，每行一个整数表示张三第 i 天可以给餐厅带来的收益。

输入样例：

6   290     物资种类，容量
85  97      1号体积，收益
80  81      2号体积，收益
83  1       3号体积，收益
79  81      4号体积，收益
89  1       5号体积，收益
92  97      6号体积，收益
5           天数
3   5       Li-Ri
1   1
1   3
5   2
3   1

输出样例：

补充说明：
前 20% 的数据满足: 1<=n<=10,1<=m<=1000.
前 50% 的数据满足: 1<=n, m, V<=300.
对于 100% 的数据满足: 1<=n, m, V<=3000; 1<=vi<=3000; 1<=Li, Ri<=n; 1<=wi<=10^6.

时间限制：1s

空间限制：512M

代码实现

#include <iostream>
#include <sys/time.h>

using namespace std;

int main(int argc, char **argv)
{
	int daytotal;                       // 天数
	int category;                       // 种类
	int capacity;                       // 容量
	int capacity_left;                  // 容量（剩余）
	int edge[3001][2];                  // 边界条件
	int menu[3001][2];                  // 货单
	int menu_sort[3001][3];             // 货单（根据每件货物的收益率排序）
	int idx = 0;
	int sum = 0;                        // 收益
	double rate_max = 0;                // 收益率
	double rate_tmp = 0;                // 收益率

	int usec_bgn;
	int usec_end;
	int usec_sub;
	struct timeval tv;

	#if 0
	cin>>category>>capacity;

	for (int i = 0; i < category; ++i)
	{
		cin>>menu[i][0]>>menu[i][1];
	}

	cin>>daytotal;

	for (int i = 0; i < daytotal; ++i)
	{
		cin>>edge[i][0]>>edge[i][1];
	}
	#else
	category = 10;
	capacity = 300;
	menu[0][0] = 85; menu[0][1] = 97;
	menu[1][0] = 80; menu[1][1] = 81;
	menu[2][0] = 83; menu[2][1] = 1;
	menu[3][0] = 79; menu[3][1] = 81;
	menu[4][0] = 89; menu[4][1] = 1;
	menu[5][0] = 92; menu[5][1] = 97;
	daytotal = 10;
	edge[0][0] = 3; edge[0][1] = 5;
	edge[1][0] = 1; edge[1][1] = 1;
	edge[2][0] = 1; edge[2][1] = 3;
	edge[3][0] = 5; edge[3][1] = 2;
	edge[4][0] = 3; edge[4][1] = 1;
	#endif

	/* 起始时间 */
	gettimeofday(&tv, NULL);
	usec_bgn = (int)tv.tv_usec;
	printf("\r\n");
	printf("bgn time (second, micro-second): %ds, %dus\r\n", (int)tv.tv_sec, (int)tv.tv_usec);
	printf("\r\n");

	for (int j = 0; j < category; ++j)
	{
		idx = 0;
		rate_max = 0;

		for (int i = 0; i < category; ++i)
		{
			if (menu[i][0] == 0)
			{
				continue;
			}

			rate_tmp = (double)menu[i][1] / (double)menu[i][0];

			if (rate_tmp > rate_max)
			{
				rate_max = rate_tmp;
				idx = i;
			}
		}

		menu_sort[j][0] = menu[idx][0];
		menu_sort[j][1] = menu[idx][1];
		menu_sort[j][2] = idx;
		menu[idx][0] = 0;
		menu[idx][1] = 0;
	}

	for (int day_idx = 0; day_idx < daytotal; ++day_idx) /* 第n天 */
	{
		sum = 0;
		capacity_left = capacity;

		for (int i = 0; i < category; ++i)
		{
			if ((menu_sort[i][2]+1) >= edge[day_idx][0] && (menu_sort[i][2]+1) <= edge[day_idx][1])
			{
				continue;
			}

			if (capacity_left >= menu_sort[i][0])
			{
				capacity_left -= menu_sort[i][0];
				sum += menu_sort[i][1];
			}
		}

		printf("%d\r\n", sum);
	}

	/* 结束时间 */
	gettimeofday(&tv, NULL);
	usec_end = (int)tv.tv_usec;
	printf("\r\n");
	printf("end time (second, micro-second): %ds, %dus\r\n", (int)tv.tv_sec, (int)tv.tv_usec);
	printf("\r\n");

	/* 计算耗时 */
	if (usec_end >= usec_bgn)
	{
		usec_sub = usec_end - usec_bgn;
	}
	else
	{
		usec_sub = 1000000 - (usec_bgn - usec_end);
	}
	printf("time cost :%d us\r\n", usec_sub);
	printf("\r\n");

	return 0;
}

测试记录

user@localhost:/mnt/e/gcc$ g++ main.cpp -o main.cppout
user@localhost:/mnt/e/gcc$ ./main.cppout

bgn time (second, micro-second): 1656593986s, 560594us

275
259
179
275
275
275
275
275
275
275

end time (second, micro-second): 1656593986s, 560641us

time cost :47 us

user@localhost:/mnt/e/gcc$