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;
}