- 注册时间
- 2007-12-27
- 最后登录
- 1970-1-1
- 威望
- 星
- 金币
- 枚
- 贡献
- 分
- 经验
- 点
- 鲜花
- 朵
- 魅力
- 点
- 上传
- 次
- 下载
- 次
- 积分
- 40155
- 在线时间
- 小时
|
发表于 2012-4-13 07:49:17
|
显示全部楼层
- // sf.cpp : Defines the entry point for the console application.
- //
-
- #include "stdafx.h"
- #include <map>
- #include <vector>
- #include <list>
- #include <algorithm>
- using namespace std;
-
- #define MOD 10
- unsigned char mullist[3]={3,7,9};
- #define MC (sizeof(mullist)/sizeof(mullist[0]))
- //we must make sure a<=b and c<=d
- #define MAKE_STATE(a,b,c,d) ((((unsigned)(unsigned char)a)<<24)|(((unsigned)(unsigned char)b)<<16)|(((unsigned)(unsigned char)c)<<8)|(((unsigned)(unsigned char)d)))
- #define GET_A(x) ((unsigned char)(((unsigned)(x))>>24))
- #define GET_B(x) ((unsigned char)(((unsigned)(x))>>16))
- #define GET_C(x) ((unsigned char)(((unsigned)(x))>>8))
- #define GET_D(x) ((unsigned char)(((unsigned)(x))))
-
- unsigned int make_state(unsigned char a, unsigned char b, unsigned char c, unsigned char d)
- {
- unsigned char t;
- if(a>b){t=b;b=a;a=t;}
- if(c>d){t=d;d=c;c=t;}
- return MAKE_STATE(a,b,c,d);
- }
- typedef map<unsigned int, int> IdMap;
- IdMap myIdMap;
- vector<unsigned int> idToState;
- vector<unsigned int> result;
- #define UNKNOWN 0
- #define FIRSTWIN 1
- #define FIRSTLOST 2
- struct Edges{
- int e[4];
- };
-
- vector<Edges> prev,next;
- list<int> losers;
- vector<int> winers;
- int lc,wc;
- int getStateId(unsigned int x)
- {
- IdMap::iterator it;
- it=myIdMap.find(x);
- if(it==myIdMap.end())return -1;
- return it->second;
- }
- void init()
- {
- unsigned char a,b,c,d;
- int id=0;
- int i;
- myIdMap.clear();
- for(a=0;a<MOD;a++)for(b=a;b<MOD;b++)for(c=0;c<MOD;c++)for(d=c;d<MOD;d++){
- unsigned int state = make_state(a,b,c,d);
- int i;
- for(i=0;i<MC;i++){
- IdMap::iterator iit=myIdMap.find(make_state((a*mullist[i])%MOD,(b*mullist[i])%MOD,(c*mullist[i])%MOD, (d*mullist[i])%MOD));
- if(iit!=myIdMap.end()){
- myIdMap.insert(make_pair(state,iit->second));
- break;
- }
- }
- if(i==MC){
- myIdMap.insert(make_pair(state,id));
- idToState.push_back(state);
- id++;
- }else{
- continue;
- }
- }
- for(i=0;i<id;i++)result.push_back(UNKNOWN);
- for(id=0;id<idToState.size();++id){
- unsigned int state=idToState[id];
- unsigned char a,b,c,d;
- a=GET_A(state);
- b=GET_B(state);
- c=GET_C(state);
- d=GET_D(state);
- if(c==0&&d==0){
- Edges e;
- e.e[0]=e.e[1]=e.e[2]=e.e[3]=-1;
- next.push_back(e);
- continue;///terminate states, no out edges
- }
- int cc=0;
- int j;
- Edges e;
- if(c!=0){
- if(a!=0)
- e.e[cc++]=myIdMap.find(make_state(c,d,(a+c)%MOD,b))->second;
- if(b!=0)
- e.e[cc++]=myIdMap.find(make_state(c,d,a,(b+c)%MOD))->second;
- }
- if(d!=0){
- if(a!=0)
- e.e[cc++]=myIdMap.find(make_state(c,d,(a+d)%MOD,b))->second;
- if(b!=0)
- e.e[cc++]=myIdMap.find(make_state(c,d,a,(b+d)%MOD))->second;
- }
- sort(&e.e[0],&e.e[cc]);
-
- for(i=1,j=1;i<cc;i++){
- if(e.e[i]==e.e[i-1])continue;
- e.e[j]=e.e[i];
- j++;
- }
- cc=j;
- for(i=cc;i<4;i++){
- e.e[i]=-1;///mark invalid edges
- }
- next.push_back(e);
- }
- for(id=0;id<idToState.size();++id){
- unsigned int state=idToState[id];
- unsigned char a,b,c,d;
- a=GET_A(state);
- b=GET_B(state);
- c=GET_C(state);
- d=GET_D(state);
- if(a==0&&b==0){
- Edges e;
- e.e[0]=e.e[1]=e.e[2]=e.e[3]=-1;
- prev.push_back(e);
- continue;
- }
- int cc=0;
- int j;
- Edges e;
- if(a!=0){
- if((c-a)%MOD!=0)
- e.e[cc++]=myIdMap.find(make_state((c-a+MOD)%MOD,d,a,b))->second;
- if((d-a)%MOD!=0)
- e.e[cc++]=myIdMap.find(make_state(c,(d-a+MOD)%MOD,a,b))->second;
- }
- if(b!=0){
- if((c-b)%MOD!=0)
- e.e[cc++]=myIdMap.find(make_state((c-b+MOD)%MOD,d,a,b))->second;
- if((d-b)%MOD!=0)
- e.e[cc++]=myIdMap.find(make_state(c,(d-b+MOD)%MOD,a,b))->second;
- }
- sort(&e.e[0],&e.e[cc]);
-
- for(i=1,j=1;i<cc;i++){
- if(e.e[i]==e.e[i-1])continue;
- e.e[j]=e.e[i];
- j++;
- }
- cc=j;
- for(i=cc;i<4;i++){
- e.e[i]=-1;///mark invalid edges
- }
- prev.push_back(e);
- }
- for(id=0;id<idToState.size();++id){
- unsigned int state=idToState[id];
- unsigned char a,b,c,d;
- a=GET_A(state);
- b=GET_B(state);
- c=GET_C(state);
- d=GET_D(state);
- if(c==0&&d==0&&(a!=0||b!=0)){
- result[id]=FIRSTLOST;
- losers.push_back(id);
- lc++;
- }
- if(a==0&&b==0&&(c!=0||d!=0)){
- result[id]=FIRSTWIN;
- wc++;
- }
- }
- }
-
- void dumpstate(int i){
- unsigned int state=idToState[i];
- unsigned char a,b,c,d;
- // if(result[i]!=FIRSTLOST)return;
- a=GET_A(state);
- b=GET_B(state);
- c=GET_C(state);
- d=GET_D(state);
- printf("state[%d:%d;%d:%d] is ",a,b,c,d);
- if(result[i]==FIRSTWIN){
- printf("first user win\n");
- }else if(result[i]==FIRSTLOST){
- printf("first user lost\n");
- }else{
- printf("tie \n");
- }
- }
-
- int _tmain(int argc, _TCHAR* argv[])
- {
- int i;
- init();
- start:
- while(losers.size()>0){
- int id = losers.front();
- losers.pop_front();
- for(i=0;i<4;i++){
- int pid=prev[id].e[i];
- if(pid<0)break;
- if(result[pid]==UNKNOWN){
- result[pid]=FIRSTWIN;
- wc++;
- winers.push_back(pid);
- }else if(result[pid]!=FIRSTWIN){
- fprintf(stderr,"Invalid 1\n");
- return -1;
- }
- }
- }
- int c=winers.size();
- for(i=0;i<c;i++){
- int id = winers[i];
- int j;
- for(j=0;j<4;j++){
- int pid=prev[id].e[j];
- if(pid<0)break;
- if(result[pid]==UNKNOWN){
- int k;
- for(k=0;k<4;k++){
- if(next[pid].e[k]<0)break;
- if(result[next[pid].e[k]]!=FIRSTWIN)break;
- }
- if(k==4||next[pid].e[k]<0){//all next are first_win
- result[pid]=FIRSTLOST;
- lc++;
- losers.push_back(pid);
- }
- }
- }
- }
- if(losers.size()>0)goto start;
- c=result.size();
- printf("win count=%d, lost count=%d, undertermined=%d\n",wc,lc,c-wc-lc);
- for(i=0;i<result.size();i++){
- if(result[i]!=UNKNOWN){
- dumpstate(i);
- }
- }
- return 0;
- }
|
|
楼主: 056254628
IP卡
狗仔卡
显身卡
