首页 > 代码库 > sicily 2010 H number
sicily 2010 H number
解释:根据规则构造数字,而不是从头遍历一遍判断,这样可以避免很多不必要的计算。
运行效率:0秒,312KB。
代码如下,类似广度优先搜索:
#include<stdio.h> #include<string.h> #include <iostream> #include<queue> using namespace std; //int toInt(char c){ return c-'0'; } //char toChar(int i){ return i+'0'; } struct Node{ Node* pre; int pos; char self; Node():pos(-1),pre(NULL) { } }; int getNcount(int n) { char strNum[10]; int ret = 0; sprintf(strNum,"%d",n); int len = strlen(strNum); queue<Node*> Q; queue<Node*> Mem; for(char i = '1'; i <= strNum[0]; i++) { Node* n = new Node; n->self = i; n->pos = 0; Q.push(n); Mem.push(n); } while(!Q.empty()) { Node* front = Q.front(); Q.pop(); if(front->pos == len-1) { ret++; // char res[10]; // Node* tmp = front; // int ide = 0; // while(tmp != NULL) // { // res[ide++]=tmp->self; // tmp = tmp->pre; // } // for(int i = ide-1; i >=0; i--) // cout << res[i]; // cout << ' '; } else { if(front->pre == NULL) { char bound = '9'; if(front->self == strNum[0]) { bound = strNum[1]; } for(char s = '0'; s <= bound; s++) { Node* n = new Node; n->self = s; n->pos = front->pos+1; n->pre = front; Q.push(n); Mem.push(n); } } else { int sign[3][2] = {{1,1},{1,-1},{-1,1}}; bool duplicateTest[10]={false}; for (int k = 0; k < 3; k++) { int selfInt = sign[k][0]*(front->pre->self-'0')+sign[k][1]*(front->self-'0'); if(selfInt < 0 || selfInt > 9) { continue; } if(duplicateTest[selfInt] == true) continue; else duplicateTest[selfInt] = true; Node* n = new Node; n->pre = front; n->pos = front->pos+1; n->self = selfInt+'0'; Node* tmp = n->pre; bool canPush = false; if(n->self <= strNum[n->pos]) canPush = true; else { while(tmp != NULL) { if(tmp->self < strNum[tmp->pos]) { canPush = true; break; } tmp = tmp->pre; } } if(canPush) { Q.push(n); Mem.push(n); } else { delete n; } } } } } while (!Mem.empty()) { Node* front = Mem.front(); Mem.pop(); delete front; } return ret; } int main() { int N; while(cin >> N) { if(N < 100) { cout << N << endl; continue; } int count = 0; count = getNcount(N); char str[10]; sprintf(str,"%d",N); int len = strlen(str); len--; while(len > 2) { char tmp[10]; int i; for(i = 0; i < len; i++) tmp[i] = '9'; tmp[i]='\0'; int n; sscanf(tmp,"%d",&n); count += getNcount(n); len--; } if(len == 2) count += 99; cout << count << endl; } }
sicily 2010 H number
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。