2020笔试编程题两则浅析

2020笔试编程题两则浅析

A.骰子分类

问题描述:

Alice有一堆骰子,每枚骰子都是尺寸一样的正六面体,六个面上分别刻有1到6不同的数字。Alice发现有些骰子和其它的不一样,定义如果两枚骰子的六个面的全部对应相等则认为是同一种。给出N枚骰子的上下左右前后面上的数字,请统计这N枚骰子中共有几种不同的骰子,并且每种分别有几颗(从大到小输出)。

输入有多行,第一行是骰子的数量N,接下来有N行,每行是六个1到6不同数字用一个空格隔开,分别表示一枚骰子的上下左右前后的数字。
输出有多行,第一行是这些骰子中的种类数T,接下来T行,由大到小地输出各类骰子分别有多少枚。

简析

化学上有一种有机物的构形,叫作“手性”,即如果一个碳原子连接四个不同的基团,它有两种排列形式,呈现镜像关系,就像人的两只手,两只手的组成形式完全一样,又不能通过平移将两手重合。

手性分子示例

由于基团的连接完全一样,若要描述手性的这种特征,还指定旋转方向描述。化学上对于手性分子的描述暂且不表。此题我们根据骰子的“手性”,规定一种骰子的命名方式:总是使1在上顶面,1周围的四个面中最小号旋转到前面,那么剩余的四个面也就被确定了下来。若分别记上下,左右,前后为记号ud,lr,fb,可以将骰子编号ufldbr(这样骰子编号最大值是136542,最小值123456,当然只要u和f分别是最高和次高位即可,剩余4位任意排列)。根据骰子编号,当且仅当骰子编号完全一致时才认为两个骰子是同一类。

对骰子的操作只有水平方向旋转(u和d不动,将左面旋转到前面)和垂直方向旋转(l和r不动,将下面旋转到前面)。通过输入数据每得到一个骰子,就先通过旋转的方式将骰子变成1为顶面,周围四面最小号为前面。这样将它用一个hashTable(比如一个int数组)保存各个种类的骰子,为hashTable排序并输出即可。

参考代码

#include <cstdio>
#include <cstring>
#include <algorithm>
using std::sort;
using std::min;
struct theDice
{
	int u,d,l,r,f,b;
	// up,	down
	// left,right
	// front,back
	theDice() {};
	theDice(int uu,int dd,
		int ll,int rr,
		int ff,int bb)
	{
		u=uu;
		d=dd;
		l=ll;
		r=rr;
		f=ff;
		b=bb;
	}
	int hash()
	{
		return ((((10*u + f)*10 + l)*10 + d)*10+ b)*10 + r;
	}
};
theDice vRotate(theDice a)
{
	return theDice(a.f,a.b,a.l,a.r,a.d,a.u);
}
theDice hRotate(theDice a)
{
	return theDice(a.u,a.d,a.b,a.f,a.l,a.r);
}
theDice normlize(theDice a)
{
	theDice ret;
	// move `1` to upward
	if(a.u==1)
	{
		ret =a ;
	}
	else if (a.d==1)
	{
		ret = vRotate(vRotate(a));
	}
	else if(a.f==1)
	{
		ret = vRotate(a);
	}
	else if(a.b==1)
	{
		ret = vRotate(hRotate(hRotate(a)));
	}
	else if (a.l ==1)
	{
		ret = vRotate(hRotate(a));
	}
	else if(a.r==1)
	{
		ret = vRotate(hRotate(hRotate(hRotate(a))));
	}
	//here, ret is always upward == 1
	//next, move the min to front
	int frontVal = min(ret.l,min(ret.r,min(ret.f,ret.b)));
	if(ret.l==frontVal)
	{
		ret = hRotate(ret);
	}
	else if(ret.b==frontVal)
	{
		ret = hRotate(hRotate(ret));
	}
	else if(ret.r==frontVal)
	{
		ret = hRotate(hRotate(hRotate(ret)));
	}
	// else a.f == frontVal, do nothing
	return ret;
}
#define MAXN 16000
// in fact, MAXN only need 136542 - 123456 = 13086
int main(void)
{
	int i,N;
	int u,d,l,r,f,b;
	theDice *dice;
	scanf("%d",&N);
	dice = new theDice[N];
	int typeCounter=0;
	int bucket[MAXN];
	memset(bucket,0,sizeof(bucket));
	for(i=0;i<N;i++)
	{
		scanf("%d%d%d%d%d%d",&u,&d,&l,&r,&f,&b);
		dice[i] = normlize(theDice(u,d,l,r,f,b));
		int t=dice[i].hash() - 123456;
		if(bucket[t]==0)
		{
			typeCounter +=1;
		}
		bucket[t]+=1;
	}
	sort(bucket,bucket+MAXN);
	printf("%d\n",typeCounter);
	for(i=MAXN-1;i>=0;i--)
	{
		if(bucket[i]==0)
		{
			break;
		}
		printf("%d\n",bucket[i]);
	}
	delete [] dice;
	return 0;
}

B.美食家

问题描述

Alice的公司提供早、午、晚餐,但是996的Alice加班太晚而早晨难以按时起床,就形成了不吃早餐的习惯。这样Alice要在公司的午餐和晚餐中选择。公司里的午餐有N份,晚餐有M份,每份含有\(x\)的热量和\(y\)的美味值,Alice希望在吃到美味值不低于\(T\)的情况下,摄入的热量最低。Alice需要在午餐和晚餐当中至多各选一份。如果只吃一餐就满足了美味值的要求,Alice也可以只吃这一餐。
编写程序计算Alice摄入的最低的热量值,如果根据菜谱无论如何Alice也吃不到美味值不低于T的两餐,则输出”-1″;

输入数据有多行,第一行有三个用空格分隔的正整数N,M,T分别表示午餐份数、晚餐份数、美味值下限,接下来有N+M行,前N行表示午餐,后M行表示晚餐,每行都是两个用空格分隔的正整数,分别表示热量和美味值。
输出只有1行,一个整数,表示美味值不小于T的情况下可能摄入热量的最小值。

简析

抽象成数学模型:有两组二维平面的点(包含原点,表示不吃这一餐),从每组向量中各选出一个点,使这两点在 \(x_i+x_j \geq T\) 的条件下使 \( y_i+y_j \) 最小。

将这两个点如果视为两个向量,就是两个向量之和 \((x,y) \),在横坐标\(x\)大于T的时候使\(y\)尽量小,所以应当先选择那些斜率比较低的,即向量的\( y/x \)尽量小。

建立两个列表分别保存午餐和晚餐,输入后根据\( \frac{热量}{美味值} \)排序,为了防止除0,只吃1餐的情况单独使用1重循环做判断,然后是二重循环计算午餐+晚餐的情况。
虽然是二重循环,但是平均时间是排序的\( O(N \cdot \log{N}) \),平凡情况下这个二重循环大概是\( O(\min\{N,M\}) \)的,因为我们只需要找到首个\( y/x \)最小并且 \(x_i+x_j \geq T\)的向量就能够退出循环。

不过,从数学上严格来讲,这种方法仍存在缺陷。如果题目的数据比较弱,这种方法是能得分的。

参考代码

#include <cstdio>
#include <algorithm>
#define INF 0x7FFFFFF
using std::sort;
int N,M,T;
struct foodNode{
    int heat,taste;
    bool operator<(const foodNode &o)
    {
        return heat*1.0/taste < o.heat*1.0/o.heat; // assume tast never 0
    }
};
int main(void)
{
    int i,j;
    scanf("%d%d%d",&N,&M,&T);
    foodNode *lunch,*dinner;
    lunch = new foodNode[N];
    dinner = new foodNode[M];
    for(i=0;i<N;i++)
    {
        scanf("%d%d", &(lunch[i].heat),&(lunch[i].taste));
    }
    sort(lunch,lunch+N);
    for(i=0;i<M;i++)
    {
        scanf("%d%d", &(dinner[i].heat),&(dinner[i].taste));
    }
    sort(dinner,dinner+M);
    // only eat one meal
    int minHeat=INF;
    for(i=0;i<N;i++)
    {
        if(lunch[i].taste>=T)
        {
            minHeat = std::min(minHeat,lunch[i].heat);
            break;
        }
    }
    for(i=0;i<M;i++)
    {
        if(dinner[i].taste>=T)
        {
            minHeat = std::min(minHeat,dinner[i].heat);
            break;
        }
    }
    int target;
    char winFlag = 0;
    // lunch + dinner
    for(i=0;i<N && winFlag ==0 ;i++)
    {
        target = T-lunch[N].taste;
        for(j=0;j<M && winFlag ==0;j++)
        {
            if(dinner[j].taste>=target)
            {
                minHeat = std::min(minHeat,target+dinner[j].heat);
                winFlag = 1;
                break;
            }
        }
    }
	delete [] lunch;
    delete [] dinner;
    if(minHeat == INF)
    {
     	printf("-1\n");
    }
  	else
  	{
    	printf("%d\n",minHeat);
	}
    return 0;
}

发表回复

您的电子邮箱地址不会被公开。 必填项已用*标注