[2020-2-28]BNUZ套题比赛div3解题报告

[2020-2-28]BNUZ套题比赛div3解题报告

2020/3/8
上周因为偷懒，没有写上周训练赛的解题报告，不过该写还是要写的。然后非常荣幸能拿到本次训练赛的第一名*（排名如下图）*

第一题 Far Relative’s Birthday Cake
Door’s family is going celebrate Famil Doors’s birthday party. They love Famil Door so they are planning to make his birthday cake weird!

The cake is a n × n square consisting of equal squares with side length 1. Each square is either empty or consists of a single chocolate. They bought the cake and randomly started to put the chocolates on the cake. The value of Famil Door’s happiness will be equal to the number of pairs of cells with chocolates that are in the same row or in the same column of the cake. Famil Doors’s family is wondering what is the amount of happiness of Famil going to be?

Please, note that any pair can be counted no more than once, as two different cells can’t share both the same row and the same column.

Input
In the first line of the input, you are given a single integer n (1 ≤ n ≤ 100) — the length of the side of the cake.

Then follow n lines, each containing n characters. Empty cells are denoted with ‘.’, while cells that contain chocolates are denoted by ‘C’.

Output
Print the value of Famil Door’s happiness, i.e. the number of pairs of chocolate pieces that share the same row or the same column.

Examples

Note
If we number rows from top to bottom and columns from left to right, then, pieces that share the same row in the first sample are:

以下是我的程序

#include<stdio.h>
int main()
{
	int n,num;
	char st[102][102];
	while(~scanf("%d",&n))
	{
		getchar();
		num=0;
		for (int i=0;i<n;i++) gets(st[i]);
		for (int i=0;i<n;i++)
			for (int j=0;j<n;j++)
			  for (int k=j+1;k<n;k++) if (st[i][j]=='C' && st[i][k]=='C') num++;
		for (int i=0;i<n;i++)
			for (int j=0;j<n;j++)
			  for (int k=j+1;k<n;k++) if (st[j][i]=='C' && st[k][i]=='C') num++;
		printf("%dn",num);
	}
	return 0;
}

这一题相当于签到题，比较简单，就是横排数列去找有多少对C，然后把结果输出出来。

第二题 Far Relative’s Problem
Famil Door wants to celebrate his birthday with his friends from Far Far Away. He has n friends and each of them can come to the party in a specific range of days of the year from ai to bi. Of course, Famil Door wants to have as many friends celebrating together with him as possible.

Far cars are as weird as Far Far Away citizens, so they can only carry two people of opposite gender, that is exactly one male and one female. However, Far is so far from here that no other transportation may be used to get to the party.

Famil Door should select some day of the year and invite some of his friends, such that they all are available at this moment and the number of male friends invited is equal to the number of female friends invited. Find the maximum number of friends that may present at the party.

Input
The first line of the input contains a single integer n (1 ≤ n ≤ 5000) — then number of Famil Door’s friends.

Then follow n lines, that describe the friends. Each line starts with a capital letter ‘F’ for female friends and with a capital letter ‘M’ for male friends. Then follow two integers ai and bi (1 ≤ ai ≤ bi ≤ 366), providing that the i-th friend can come to the party from day ai to day bi inclusive.

Output
Print the maximum number of people that may come to Famil Door’s party.

Examples

Note
In the first sample, friends 3 and 4 can come on any day in range [117, 128].
In the second sample, friends with indices 3, 4, 5 and 6 can come on day 140.

以下是我的程序

#include<stdio.h>
#include<string.h>
struct member
{
	char sex;
	int first;
	int last;
} a[5002];
int main()
{
	int n,max,num,f,m,flag,number,day[367],b[367];
	while(~scanf("%d",&n))
	{
		getchar();
		memset(day,0,sizeof(day));
		for (int i=1;i<=n;i++) 
		{
			scanf("%c %d %d",&a[i].sex,&a[i].first,&a[i].last);
			for (int j=a[i].first;j<=a[i].last;j++) day[j]++;
			getchar();
		}
		flag=1;number=0;
		while (flag)
		{
			max=0;num=0;
			for (int i=1;i<=366;i++) 
				if (max<day[i]) 
				{
					max=day[i];
					num=i;
				}
			if (max==0) break;
			f=0;m=0;
			for (int i=1;i<=n;i++) if (a[i].first<=num && a[i].last>=num) if (a[i].sex=='F') f++; else m++;
			if (f>m)
			{
				number++;b[number]=m*2;
			}
			else
			{
				number++;b[number]=f*2;
			}
			day[num]=0;
		}
		max=0;
		for (int i=1;i<=number;i++) if (max<b[i]) max=b[i];
		printf("%dn",max);
	}
	return 0;
}

这题大概意思是有若干个男人和女人，他们要去一个party，主人只有一辆车，这辆车只能男人和女人同时上车，不能男男或女女，然后每个人每年里面都会有一个空闲的时间可以来，要求最多可以多少个人在同一天到场。一开始我想得比较单纯，直接把男人或女人的数量相同的才去算，不同的就不管，最后找最大值，这样想只能WA。后来想到另外一种情况，就是男人或女人都有可能多出来，所以就用了一个数组存所有情况，最后找最大。现在想想，好像在处理每个人有空的时间里面，min(男，女)，这样子好像就可以更方便求出当天的最大人数。

第三题 这题是dp，直接跳过（以后自学一下再回头看看吧）

第四题 Joysticks
Friends are going to play console. They have two joysticks and only one charger for them. Initially first joystick is charged at a1 percent and second one is charged at a2 percent. You can connect charger to a joystick only at the beginning of each minute. In one minute joystick either discharges by 2 percent (if not connected to a charger) or charges by 1 percent (if connected to a charger).

Game continues while both joysticks have a positive charge. Hence, if at the beginning of minute some joystick is charged by 1 percent, it has to be connected to a charger, otherwise the game stops. If some joystick completely discharges (its charge turns to 0), the game also stops.

Determine the maximum number of minutes that game can last. It is prohibited to pause the game, i. e. at each moment both joysticks should be enabled. It is allowed for joystick to be charged by more than 100 percent.

Input
The first line of the input contains two positive integers a1 and a2 (1 ≤ a1, a2 ≤ 100), the initial charge level of first and second joystick respectively.

Output
Output the only integer, the maximum number of minutes that the game can last. Game continues until some joystick is discharged.

Examples

Note
In the first sample game lasts for 6 minute by using the following algorithm:
at the beginning of the first minute connect first joystick to the charger, by the end of this minute first joystick is at 4%, second is at 3%;
continue the game without changing charger, by the end of the second minute the first joystick is at 5%, second is at 1%;
at the beginning of the third minute connect second joystick to the charger, after this minute the first joystick is at 3%, the second one is at 2%;
continue the game without changing charger, by the end of the fourth minute first joystick is at 1%, second one is at 3%;
at the beginning of the fifth minute connect first joystick to the charger, after this minute the first joystick is at 2%, the second one is at 1%;
at the beginning of the sixth minute connect second joystick to the charger, after this minute the first joystick is at 0%, the second one is at 2%.
After that the first joystick is completely discharged and the game is stopped.

以下是我的程序

#include<stdio.h>
int main()
{
	int n,m,num,t;
	while(~scanf("%d %d",&n,&m))
	{
		if (n>m)
		{
			t=n;n=m;m=t;
		}	
		num=0;
		while (m>1 && n>0)
		{
			n++;
			m=m-2;
			num++;
			if (m<=2)
			{
				t=n;n=m;m=t;
			}
		}
		printf("%dn",num);
	}
	return 0;
}

这题也比较简单，就是两个手柄一个充电一个放电，最多能用多久，用while模拟一下就好了，要注意一下timeout的条件。

第五题 Beautiful Paintings
There are n pictures delivered for the new exhibition. The i-th painting has beauty ai. We know that a visitor becomes happy every time he passes from a painting to a more beautiful one.

We are allowed to arranged pictures in any order. What is the maximum possible number of times the visitor may become happy while passing all pictures from first to last? In other words, we are allowed to rearrange elements of a in any order. What is the maximum possible number of indices i (1 ≤ i ≤ n - 1), such that ai + 1 > ai.

Input
The first line of the input contains integer n (1 ≤ n ≤ 1000) — the number of painting.

The second line contains the sequence a1, a2, …, an (1 ≤ ai ≤ 1000), where ai means the beauty of the i-th painting.

Output
Print one integer — the maximum possible number of neighbouring pairs, such that ai + 1 > ai, after the optimal rearrangement.

Examples

Note
In the first sample, the optimal order is: 10, 20, 30, 40, 50.
In the second sample, the optimal order is: 100, 200, 100, 200.

这道题有点可惜，时间不够没做出来，然后过后也没来补题，我的。
那我就把我的想法说一下吧，我感觉还是能实现的，先进行从小到大排序，然后从第1个开始往后找找不同的比上一个确定的数要大的然后交换，循环到最后就把最后确定那个往后从小到大排序，继续做上一步的事情，知道找到最后一个。然后找的途中已经可以计算美丽值了。最后再把美丽值输出来。（有空去实现一下）差不多就这个意思，有递归内味儿但不是。

这就是第一周的训练赛，作为竞赛部的成员却老是偷懒，我的。

最后

以上就是开放乌龟为你收集整理的[2020-2-28]BNUZ套题比赛div3解题报告的全部内容，希望文章能够帮你解决[2020-2-28]BNUZ套题比赛div3解题报告所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。