ACM题目与答案 - J - 图文

油漆金字塔

★问题描述

法老 Smith打算盖一座金字塔。为了避免金字塔受风吹日晒,他打算给金字塔刷上油漆。但是在当时,油漆还是比较稀有的东西,价格比较贵。 Smith希望在保证金字塔质量(即体积)的情况下,用尽量少的油漆。

身为建造官的你,需要帮法老解决这个问题。你请来了王国最好的数学家

身为建造官的你,需要帮法老解决这个问题。你请来了王国最好的数学家,设计了金字塔的结构图:

金字塔由N个长方体组成。每个长方体,高度为h,长度和宽度均为d。它们以顶部正方形的中心为轴心，层层叠加。为了保持金字塔稳定性,从下至上,每层长方体的高度和边长必需逐级递减,且为了计算方便,h和d均为正整数。

金字塔总体积为V,总面积为S(除金字塔最底部外的其他暴露在空气中的面积之和) 法老需要知道,在保证体积为M的基础上,最小的油漆面积S是多少。 ★实验任务

现请你写一个程庐,输出最小油漆面积。 ★数据输入

输入数据包括一行,为两个整数N(I≤n≤25)和V(≤m=5000),分别表示金字塔层数和总体积。输入保证该体积的金字塔是可以建造的 ★结果输出

輪出一行一个整整数,为最小油面积S 输入示例 3 36 #include #include

#Define INF 100000000 #Define Min(a, b)(a

int minv[25], mins[25]; void init() {

minv[0]=0; mins[0]=0;

for(int i=1; i<=M; i++)

输出示例 65 {

minv[i]= minv[i-1]+i*i*i; mins[i]=mins[i-1]+4*i*i; } }

void dfs(int m, int v, int s, int d, int h) {

if(m==0) {

if(ans>s&&v==N) ans=s; }

if(s+mins[m-1] > ans || v + minv[m-1]> N || 4*(N-v)/d+s >=ans) return; for(int i=d-1; i>=m; i--) {

int maxh= Min((N-v-minv[m-1])/(i*1),h-1); for(int j=max; j>=m; j--) {

if(m==M) S=i*i;

dfs(m-1,v+i*i*j,S+4*i*j,i,j); } } }

int main() {

scanf(\ ans=INF; init();

dfs(M,0,0,N+1,N+1); printf(\ return 0; }

冰桶挑战

Z大也兴起了一股冰桶挑战之风,参加过的人将会请自己的好友一起参加,并如此继线下去. 实验任务

已知一个N*M的关系图,每人相邻的四个方向上的人表示他的好友。希望价你能找到最后参加冰桶挑战的人 输入数据就一行

有4个正数N,M和X，Y(1<=N,M,X,Y<=100),表示关系图是N行M列的,并且第一个参加冰桶挑战的人位上(X，Y)

输出

轴出最后参加冰桶战的人位于关系图的位置,若有多个则先按X从小到大,X相同则按Y从小到大 输入示例 3 3 2 2 输出示例 1 1 1 3 3 1 3 3 3 3 3 3 1 1 #include

double fun(int a, int b, int x, int y) {

double c;

c=(x-a)*(x-a)+(y-b)*(y-b); return c; }

int main() {

int N, M,X, Y;

cin >>N>>M>>X>>Y; double d1, d2, d3, d4; d1=fun(1,1,X,Y); d2=fun(1, M, X, Y); d3=fun(N, 1, X, Y); d4=fun(N, M, X, Y); i(N==1) {

if(d1>d2)

cout<

cout<

cout<

if(M==1&&N!=1) {

if(d1>d3)

cout<

cout<

else {

cout<

double max =0; if(max

cout<<1<<\ if(max==d2)

cout<<1<<\ if(max==d3)

cout<

cout<

N皇后问题

★问题描述

八皇后问题,是一个古老而著名的问照,是回算法的典型素例该问问黑是际西洋棋棋手马克斯·贝器尔于1848年提出,在8X8格的国际象上摆放八个皇后,使其不能互相攻击,即任竄两个皇后都不能处于同一行、间一列取同一斜线上,问有多少种摆法。高斯认为有76种方案。1854年在柏林的象棋染上不同的作者发表了40种不同的解,后来有人用图论的方法解出92种结果

现在问是,给一个NN的棋盘,在上面放N个皇后,使其不能互相攻击,并且,给定某些位置是不能放皇后的,同总共有多少种提法。 ★编程任务

給一个N*N的林盘,在上面放N个皇后,使其不能互相攻击。并且,给定某些位置是不能放皇后的,问总共有多少种法 ★数据输入

输入数据第一行为两个整数N,M(3<=N<=8,0<=M<=N*N),表示棋盘大小为N*N,有M个位置不能放皇后,接下来轴入M行,每行两个整数x、y(1<=x,y<=N),表示第x行第y列不能放皇后 ★数据输出

1个整数,表示有多少种摆法