首页 > 数据结构 > Hash表 > hdu 1957 A number game-Hash&搜索[解题报告]C++
2013
12-26

hdu 1957 A number game-Hash&搜索[解题报告]C++

A number game

问题描述 :

The wide dissemination of calculators and computers is not without disadvantages. Teachers all over the world find out that even students in technical disciplines tend to have a surprising lack of calculating ability. Accustomed as they are to the use of calculators and computers, many of them are unable to make calculations like 7*8 mentally, or to factor 91 by heart.

We all know, but who cares?

Professor Bartjens cares. Professor Bartjens is a bit old-fashioned. He decided to give his students some training in calculating without electronic equipment – even without a slide rule. He invented a two-person game involving mental calculations.

Professor Bartjens would write a positive number on the blackboard. During the game more positive numbers may appear on the blackboard. The two players will then make moves in turn. A player on move is obliged to make a move, unless the blackboard is empty, in which case the game
is over. A move is one of the following:
--If you see the number 1 on the blackboard, you may take it. That means: you gain one point,and the number disappears from the blackboard.
--If you see a prime number p on the blackboard, you may subtract one. That is: you gain one point, and the p on the blackboard is replaced by p -1.
--If you see a composite number c on the blackboard, you may replace it by two smaller (positive) numbers, a and b, such that a * b = c. You do not gain any points.

The goal is of course to obtain as many points as you can.

Professor Bartjens was hoping that his students would find the game so interesting that they would spend all day playing, thereby improving their skills in calculation. Indeed his students did find the game interesting, and spent many hours, not so much playing the game as discussing optimal strategies.
The students came to two conclusions. First, the sum of the two players’ points after any given game are the same regardless of the actual scheme played. Thus," a player maximising his own points also minimises his opponent’s! Second, it is always best to take a point when you have the
chance. Thus, whenever prime numbers or ones are written on the blackboard, the player on move takes one of them.

Here is your problem: given a starting number, and assuming both players play to maximise their own points, what will be the outcome?

输入:

On the first line of the input is a single positive integer n, telling the number of test scenarios to follow. Each scenario consists of a single line containing the positive integer m<1000000, the number initially written on the blackboard.

输出:

On the first line of the input is a single positive integer n, telling the number of test scenarios to follow. Each scenario consists of a single line containing the positive integer m<1000000, the number initially written on the blackboard.

样例输入:

6
1
2
3
4
5
6

样例输出:

1 0
1 1
2 1
2 2
3 2
2 3


不知道哪天手贱开的题目。。。断断续续搞了有半个月吧。。。
题面:两人轮流游戏,游戏状态为若干不大于100万的数字,每次必须从中选取一个,选了素数或1,将这个数减1后放回,得一分;否则将该合数分解为两个大于1的因子。给定初始的一个数,求结束时两人得分。
题目同时给出两个结论:给定局面的总得分总是固定的;能得分的时候总应该得分。
想了好多DP方程,无解。后来听王牛说是HASH记忆化+爆搜,就写搜了。结果很脑残的无视结论2,认为选素数的顺序也是有关的。。。
后来去掉这个BUG,继续WA和T。最后发现是某年题目,找到标程,对拍发现有错才终于AC。
后记:
1.HASH函数一定不能选纯异或,会在0的位置出现很长的链,怎么T的都不知道。。。
2.信心很重要,慌张迷茫了很久,拿到标程发现做法没错之后信心大增,很快就找到BUG了
3.搜索是个功底,问题透视,搜索方向选择,逻辑判定,细节优化,都需要积累的,不是一天两天能练成的。
4.有时候需要的空间不一定那么多,估算要做好:我的状态表示开始用了50大小的数组,后来自己测了下,最多不过需要10而已;HASH表的大小我开的50万,标程才6万多。

#include <iostream>
#include <cstdio>
#include <cstring>
#include <string>
#include <algorithm>
#include <cmath>
#include <vector>
#include <map>
#include <bitset>
#include <ctime>
#include <queue>
#include <complex>
using namespace std;
#define clr(a) memset(a,0,sizeof(a));
const int maxsize=1000007,inf=0x7fffffff;
template<class T>
void show(T a[],int n){
    for(int i=0;i<n;i++){
        cout<<a[i]<<" ";
    }
    cout<<endl;
}
template<class T>
void show(const vector<T>& t){
    for(int i=0;i<t.size();i++){
        cout<<t[i]<<" ";
    }
    cout<<endl;
}
 
inline int randin(const int& l,const int& r)
{   return rand()%(r-l+1)+l;    }
 
struct node{
    int a,b;
    node(){
        a=b=0;
    }
};
 
char isprime[maxsize];
char  tocombine[maxsize];
void init(){
int i;
for(i=0;i<maxsize;i++)
isprime[i]=1;
isprime[0]=0;
for(i=2;i<maxsize;i++){
tocombine[i]=0;
if(isprime[i]){
int k=i;
while(isprime[k]){tocombine[i]++; k--;}
for(int j=i*2;j<maxsize;j+=i){
isprime[j]=0;
}
}
}
}
 
 
struct state{
int s[11];
int cnt;
state(){cnt=0;}//clr(s);}
void sortme(){sort(s,s+cnt);}
};
 
bool operator < (const state& a,const state& b){
if(a.cnt!=b.cnt) return a.cnt <b.cnt;
for(int i=0;i<a.cnt;i++){
if(a.s[i]!=b.s[i]){
return a.s[i]<b.s[i];
}
}
return false;
}
bool operator == (state a,state b){
if(a.cnt!=b.cnt) return false;
//sort(b.s,b.s+b.cnt);
//sort(a.s,a.s+a.cnt);
for(int i=0;i<a.cnt;i++){
if(a.s[i]!=b.s[i]){
return false;
}
}
return true;
}
 
const int hashsize =maxsize/3;
template<class Tk,class Tv>
class hashmap{
struct hashnode{
Tk key;
Tv value;
hashnode *next;
};
hashnode mem[hashsize];
int mem_end;
hashnode *entry[hashsize];
hashnode* getmem(){mem_end++; return mem+mem_end-1;}
int culhash(const state& a){
int h =0;
for(int i=0;i<a.cnt;i++){
h=h*1007+a.s[i];
}
return (h%hashsize+hashsize)%hashsize;
}
public:
hashmap(){
clr(entry);mem_end=0;
}
bool get(const Tk& k,Tv& v){
int h=culhash(k);
hashnode *p=entry[h];
for(;p;p=p->next){
if(p->key==k){
v=p->value;
return true;
}
}
return false;
}
bool insert(const Tk& key,const Tv& v){
if(mem_end>=hashsize)return false;
int h=culhash(key);
hashnode *p=getmem();
p->key=key;p->value=v;p->next=entry[h];
entry[h]=p;
return true;
}
};
 
hashmap<state,node> hhh;
int maxstate;
 
 
node get(state s){
//if(s.cnt>maxstate) maxstate =s.cnt;
sort(s.s,s.s+s.cnt);
state os =s;
node ret ;
if(!hhh.get(s,ret)){
if(s.cnt==1&&isprime[s.s[0]]){
s.s[0]--;
ret =get(s);
swap(ret.a,ret.b);
ret.a++;
}else{
int i,j,k=0,l;
for(i=0;i<s.cnt;i++){
if(isprime[s.s[i]]){
l=tocombine[s.s[i]];
k+=l;
s.s[i]-=l;
}
if(s.s[i]==0){
s.cnt--;
swap(s.s[i],s.s[s.cnt]);
i--;
}
}
if(s.cnt){
{
for(i=0;i<s.cnt;i++){
int t=s.s[i];
if(i&&t==s.s[i-1]) continue;
int st=sqrt(s.s[i])+2;
for(j=2;j<st;j++){
if(t%j==0){
state ns =s;
ns.cnt++;//while(ns.cnt>=50) ;
ns.s[i]=j;
ns.s[s.cnt]=t/j;
node tmp =get(ns);
swap(tmp.a,tmp.b);
if(tmp.a>ret.a){
ret=tmp;
}
}
}
}
}
if(k%2) swap(ret.a,ret.b);
}
ret.a+=k/2+k%2;
ret.b+=k/2;
}
hhh.insert(os,ret);
}
return ret;
}
 
void test(int n){
clock_t t0=clock();
for(int i=2;i<n;i++){
state s;s.s[0]=i;s.cnt=1;
node ans=get(s);
//printf("%d : (%d,%d)\n",i,ans.a,ans.b);
}
cout<<clock()-t0<<endl;
}
 
 
 
 
 
int main()
{
    init();
state s; s.s[0]=1;s.cnt=1; 
node ans; ans.a=1;
hhh.insert(s,ans);
 
//test(20000);
 
 
 
int n;
for(cin>>n;n;--n){
scanf("%d",s.s);
//maxstate =0;
s.cnt=1;
ans =get(s);
printf("%d %d\n",ans.a,ans.b);
//printf("max =%d\n",maxstate);
}
    
    //system("pause");
    return 0;
}

 


  1. #include <cstdio>
    #include <cstring>

    const int MAXSIZE=256;
    //char store[MAXSIZE];
    char str1[MAXSIZE];
    /*
    void init(char *store) {
    int i;
    store['A']=’V', store['B']=’W',store['C']=’X',store['D']=’Y',store['E']=’Z';
    for(i=’F';i<=’Z';++i) store =i-5;
    }
    */
    int main() {
    //freopen("input.txt","r",stdin);
    //init(store);
    char *p;
    while(fgets(str1,MAXSIZE,stdin) && strcmp(str1,"STARTn")==0) {
    if(p=fgets(str1,MAXSIZE,stdin)) {
    for(;*p;++p) {
    //*p=store[*p]
    if(*p<’A’ || *p>’Z') continue;
    if(*p>’E') *p=*p-5;
    else *p=*p+21;
    }
    printf("%s",str1);
    }
    fgets(str1,MAXSIZE,stdin);
    }
    return 0;
    }

  2. 学算法中的数据结构学到一定程度会乐此不疲的,比如其中的2-3树,类似的红黑树,我甚至可以自己写个逻辑文件系统结构来。

  3. 有限自动机在ACM中是必须掌握的算法,实际上在面试当中几乎不可能让你单独的去实现这个算法,如果有题目要用到有限自动机来降低时间复杂度,那么这种面试题应该属于很难的级别了。

  4. 我还有个问题想请教一下,就是感觉对于新手来说,递归理解起来有些困难,不知有没有什么好的方法或者什么好的建议?

  5. 有两个重复的话结果是正确的,但解法不够严谨,后面重复的覆盖掉前面的,由于题目数据限制也比较严,所以能提交通过。已更新算法

  6. 在方法1里面:

    //遍历所有的边,计算入度
    for(int i=0; i<V; i++)
    {
    degree = 0;
    for (j = adj .begin(); j != adj .end(); ++j)
    {
    degree[*j]++;
    }
    }

    为什么每遍历一条链表,要首先将每个链表头的顶点的入度置为0呢?
    比如顶点5,若在顶点1、2、3、4的链表中出现过顶点5,那么要增加顶点5的入度,但是在遍历顶点5的链表时,又将顶点5的入度置为0了,那之前的从顶点1234到顶点5的边不是都没了吗?