2013ブルーブリッジカップC.A組02題(暴力)

14378 ワード

引用する
これは2013年の第4回ブルーブリッジカップソフトウェア大会予選A組(C/C++組)の第2題で、空欄の問題で、方法は暴力の列挙である.
タイトルの説明
タイトル:その平方数を並べて明ちゃんは203879という数字を見てぼんやりしています.なるほど、203879*203879=41566646641これは何が不思議ですか?よく見ると、203879は6桁であり、その各桁の数字は異なり、平方後のすべての桁にはそれ自体を構成する数字は現れない.このような特徴を持つ6桁の数字はもう一つあります.それを見つけてください.フィルタリングの要件をまとめます:1.6ビットの正の整数2.数桁ごとに数字が異なる.その平方数の各数桁に元の数字を含まない任意の構成数桁の答えは6桁の正の整数である.ブラウザで答えを提出してください.注意:もう一つの6桁しか提出しません.問題の中ですでに与えられたこれは提出しないでください.注意:他の内容(例えば、説明的な文字)は書かないでください.
考え方:
この問題の主な試験点は暴力で、問題を見てまず時間の複雑度O(n)を推定して、メモリは32 Mより小さくて、運行時間も1 s以内で、ACMの中で効率は普通で、基本的に過ぎることができます;しかし、一定の剪定によって多くの不要な操作を省くことができます.
コード:(暴力)(コードスタイル参考北航伝奇人物---董適、現在マイクロソフトと契約)
#include <iostream> #include <cstdio> #include <cstdlib> #include <cstring> #include <ctype.h> #include <map> #include <set> #include <queue> #include <stack> #define MAXN 10 #define RST(N)memset(N, 0, sizeof(N)) using namespace std; typedef unsigned long long ULL; /**************************************/ int visit[MAXN]; void MES(ULL M) //   i          ,    ; { RST(visit); //     i  RESET    ; while(M) { visit[M%10]++; M = M/10; } } bool Measure(ULL Mc) //  i*i   i    ,   ,  false,     true; { while(Mc) { int flag = Mc % 10; if(visit[flag] != 0) visit[flag]++; //    i         ; Mc = Mc / 10; } for(int i=0; i<10; i++) { if(visit[i] >= 2) return false; } return true; } int main() { freopen("data.in", "r", stdin); //       ; freopen("data.out", "w", stdout); for(ULL i=123456; i<=987654; i++) { MES(i); ULL Mc = i*i; if(Measure(Mc)) printf("%lld %lld
"
, i, Mc); } fclose(stdin); fclose(stdout); return 0; }
最後の答えは:
639172