首页 > ACM题库 > HDU-杭电 > HDU 3412-An Odd Award Rule-枚举-[解题报告]HOJ
2014
03-23

HDU 3412-An Odd Award Rule-枚举-[解题报告]HOJ

An Odd Award Rule

问题描述 :

The education of primary school in China is a big problem now. A teacher must be very careful not only when he/she is criticizing the students, but also when he/she is giving awards to good students. Teacher Liu always gave the top ten students on his examination some little awards before, but some parents are a little bit angry about this now. They say that their little kids may get hurt because they will never get the awards. Teacher Liu has to change his award rule. He wants all students have a chance to win the awards, no matter their scores are good or poor. But he still wants good students to get more chance. So the new rule seems a little bit odd: anyone whose score equals to the sum of the scores of OTHER 3 or 2 students, will win the award. Now figuring out who is qualified for the awards seems a little bit hard for Teacher Liu. As the monitor of his class and a little programmer, you should help him to do this.

输入:

For each test case, first print an integer in a line, indicating how many students win the awards. Then print the names of those who win the awards in alphabetic order, each name in a line.

输出:

For each test case, first print an integer in a line, indicating how many students win the awards. Then print the names of those who win the awards in alphabetic order, each name in a line.

样例输入:

1
5
SIKE 12
WORRY 20
LUCENT 8
KILI 3
TOM 1

样例输出:

2
SIKE
WORRY

题目链接:http://poj.org/problem?id=3778     http://acm.hdu.edu.cn/showproblem.php?pid=3412

An Odd Award Rule 这个题目包括上面的两个题目都是昨天做的一套题目中的几个水题,现在整理了一下解题报告。

这个题目一看数据量20左右就基本可以确定用暴力就可以,所以我就直接用暴力暴了一遍,直到现在还没有想到更好的方法。

主要思路就是暴力所以包含第i个学生成绩并且人数为2或人数为3的所有成绩,然后暴力所有同学中2个或3个学生的成绩。然后只要比较一下有或无第i个学生的成绩时成绩为stu[i].sco的组合数大于有第i个学生的成绩时的组合数就可以说明存在一种组合能使其成绩和等于第i个学生的成绩。

这里也考虑到了成绩为0的情况。

#include <iostream>
#include <cstdio>
#include <cstring>
#include <string>
#include <algorithm>

using namespace std;

const int maxx=25;

struct Stu{
	string name;
	int sco;
};

Stu stu[maxx];
string name[maxx];
int yi[maxx][305],yihwi[305];
int st;

void init(){
	st=0;
	memset(yi,0,sizeof(yi));
	memset(yihwi,0,sizeof(yihwi));
}

int main(){
	int T,n,i,j,k;
    scanf("%d",&T);
	while(T--){
		init();
		scanf("%d",&n);
		for(i=0;i<n;i++){
			cin>>stu[i].name>>stu[i].sco;
		}
		for(i=0;i<n;i++){
			for(j=0;j<n;j++){
				if(i==j)continue;
				yi[i][stu[i].sco+stu[j].sco]++;
				for(k=0;k<n;k++){
					if(i==k || j==k)continue;
					yi[i][stu[i].sco+stu[j].sco+stu[k].sco]++;
				}
			}
		}
		for(i=0;i<n;i++){
			for(j=i+1;j<n;j++){
				yihwi[stu[i].sco+stu[j].sco]++;
				for(k=j+1;k<n;k++){
					yihwi[stu[i].sco+stu[j].sco+stu[k].sco]++;
				}
			}
		}
		for(i=0;i<n;i++){
			if(yihwi[stu[i].sco] && yihwi[stu[i].sco]>yi[i][stu[i].sco]){
				name[st++]=stu[i].name;
			}
		}
		sort(name,name+st);
		printf("%d\n",st);
		for(i=0;i<st;i++){
			cout<<name[i]<<endl;
		}
	}
	return 0;
}

今天又试了一下全暴力,过了,查了一下昨天的代码发现少了一个if判断导致没有考虑到0的情况,现在把全暴力的代码写一下。

#include <iostream>
#include <cstdio>
#include <cstring>
#include <string>
#include <algorithm>

using namespace std;

const int maxx=25;

struct Stu{
	string name;
	int sco;
};

Stu stu[maxx];
string name[maxx];
int st;

void init(){
	st=0;
}

int main(){
	int T,n,i,j,k,l;
    scanf("%d",&T);
	while(T--){
		init();
		scanf("%d",&n);
		for(i=0;i<n;i++){
			cin>>stu[i].name>>stu[i].sco;
		}
		for(i=0;i<n;i++){
			for(j=0;j<n;j++){
				if(i==j)continue;
				for(k=0;k<n;k++){
					if(i==k || j==k)continue;
					if(stu[i].sco==stu[j].sco+stu[k].sco){
						name[st++]=stu[i].name;
						goto first;
					}
					for(l=0;l<n;l++){
						if(i==l || j==l || k==l)continue;
						if(stu[i].sco==stu[j].sco+stu[k].sco+stu[l].sco){
							name[st++]=stu[i].name;
							goto first;
						}
					}
				}
			}
            first:;
		}
		sort(name,name+st);
		printf("%d\n",st);
		for(i=0;i<st;i++){
			cout<<name[i]<<endl;
		}
	}
	return 0;
}

参考:http://blog.csdn.net/iaccepted/article/details/6713760


  1. 第一句可以忽略不计了吧。从第二句开始分析,说明这个花色下的所有牌都会在其它里面出现,那么还剩下♠️和♦️。第三句,可以排除2和7,因为在两种花色里有。现在是第四句,因为♠️还剩下多个,只有是♦️B才能知道答案。

  2. if(j){
    int ans=a ;
    for(int x=j-1;x>=0;x–){
    if(!a ) break;
    ans=min(ans,a );
    sum+=ans;
    }
    }
    求解释,,dp的思路是什么呢?

  3. 可以根据二叉排序树的定义进行严格的排序树创建和后序遍历操作。如果形成的排序树相同,其树的前、中、后序遍历是相同的,但在此处不能使用中序遍历,因为,中序遍历的结果就是排序的结果。经在九度测试,运行时间90ms,比楼主的要快。

  4. 第二个方法挺不错。NewHead代表新的头节点,通过递归找到最后一个节点之后,就把这个节点赋给NewHead,然后一直返回返回,中途这个值是没有变化的,一边返回一边把相应的指针方向颠倒,最后结束时返回新的头节点到主函数。