昨天编程题第二题

//我是这样的 int main() { int arr[484] = {1, 20, 21, 122, 123, 202, 203, 222, 223, 230, 231, 302, 303, 410, 411, 502, 503, 1130, 1131, 1150, 1151, 1202, 1203, 1212, 1213, 1230, 1231, 1300, 1301, 1402, 1403, 1502, 1503, 1510, 1511, 2006, 2007, 2032, 2033, 2102, 2103, 2200, 2201, 3006, 3007, 3012, 3013, 3050, 3051, 3070, 3071, 3102, 3103, 3110, 3111, 3300, 3301, 4014, 4015, 5000, 5001, 5010, 5011, 5020, 5021, 6002, 6003, 6012, 6013, 6102, 6103, 7000, 7001, 7102, 7103, 8110, 8111, 10006, 10007, 10032, 10033, 10050, 10051, 10060, 10061, 10070, 10071, 10112, 10113, 10132, 10133, 10170, 10171, 10234, 10235, 10310, 10311, 10410, 10411, 10430, 10431, 11012, 11013, 11050, 11051, 11070, 11071, 11114, 11115, 11134, 11135, 11150, 11151, 11214, 11215, 11240, 11241, 11250, 11251, 11260, 11261, 11300, 11301, 11502, 11503, 11710, 11711, 12006, 12007, 12024, 12025, 12112, 12113, 12142, 12143, 12204, 12205, 12214, 12215, 12250 , 12251, 13012, 13013, 13050, 13051, 13200, 13201, 13230, 13231, 14014, 14015, 14020, 14021, 14102, 14103, 14330, 14331, 15002, 15003, 15010, 15011, 15020, 15021, 15030, 15031, 15210, 15211, 15230, 15231, 15310, 15311, 16010, 16011, 16030, 16031, 16102, 16103, 16120, 16121, 16300, 16301, 16310, 16311, 20004, 20005, 20040, 20041, 20050, 20051, 20060, 20061, 20112, 20113, 20142, 20143, 20206, 20207, 20230, 20231, 20312, 20313, 20320, 20321, 20340, 20341, 20414, 20415, 20420, 20421, 21002, 21003, 21022, 21023, 21030, 21031, 21112, 21113, 21202, 21203, 21212 , 21213, 21220, 21221, 21302, 21303, 21400, 21401, 22006, 22007, 22030, 22031, 22120, 22121, 22130, 22131, 22140, 22141, 22210, 22211, 22220, 22221, 22230, 22231, 22302, 22303, 22310, 22311, 22500, 22501, 23004, 23005, 23012, 23013, 23110, 23111, 23210, 23211, 23230, 23231, 24002, 24003, 24012, 24013, 24022, 24023, 24100, 24101, 24302, 24303, 24510, 24511, 26100, 26101, 30006, 30007, 30042, 30043, 30050, 30051, 30060, 30061, 30070, 30071, 30104, 30105, 30112, 30113, 30132, 30133, 30150, 30151, 30210, 30211, 30220, 30221, 30230, 30231, 30320, 30321, 30400 , 30401, 30420, 30421, 30500, 30501, 30702, 30703, 31004, 31005, 31012, 31013, 31120, 31121, 31150, 31151, 31214, 31215, 31300, 31301, 31400, 31401, 31410, 31411, 31420, 31421, 31610, 31611, 31710, 31711, 32002, 32003, 32012, 32013, 32022, 32023, 32112, 32113, 32212, 32213, 32250, 32251, 32302, 32303, 32410, 32411, 32502, 32503, 32700, 32701, 40002, 40003, 40012, 40013, 40022, 40023, 40122, 40123, 40200, 40201, 40210, 40211, 40220, 40221, 40400, 40401, 40430, 40431, 40510, 40511, 40700, 40701, 41210, 41211, 42100, 42101, 43004, 43005, 44000, 44001, 44020 , 44021, 45000, 45001, 45010, 45011, 45020, 45021, 47100, 47101, 50002, 50003, 50012, 50013, 50020, 50021, 50300, 50301, 51010, 51011, 51020, 51021, 51030, 51031, 51130, 51131, 52010, 52011, 52030, 52031, 52110, 52111, 52200, 52201, 52210, 52211, 52220, 52221, 53102, 53103, 53210, 53211, 54010, 54011, 60002, 60003, 60012, 60013, 60022, 60023, 60102, 60103, 60120, 60121, 60200, 60201, 60210, 60211, 60220, 60221, 60300, 60301, 60310, 60311, 60400, 60401, 61002, 61003, 61022, 61023, 61030, 61031, 61210, 61211, 61302, 61303, 61400, 61401, 62010, 62011, 62110 , 62111, 62200, 62201, 63102, 63103, 65000, 65001, 65010, 65011, 65020, 65021, 70010, 70011, 70110, 70111, 71100, 71101, 80110, 80111, 90000, 90001, 90030, 90031 }; int k = 0; for (int i = 1; i <= 100000; i++) { if (i == arr[k])k++; saved.insert(make_pair(i, k)); } int n, m; (cin >> m); { for (int k = 0; k < m; k++) { cin >> n; //int ans, *it = lower_bound(arr, arr + 483, n) ; //ans = it - arr; //if (*it == n)ans++; // cout << saved[n] << endl; } } return 0; }

这题打表吧，反正就10000，先算出每个数的的幸运数个数，然后到时候直接取就行（计算个数不用遍历，只用计算当前的数n是否满足，若满足则n-1的个数+1就行）

昨天的本地编译器打不开，好伤心，直接在OJ上写的，不知道能不能AC这题，求大神指点，或者说下你们的思路，共同讨论学习。

多半会提示超时，我也这么写的，本地能通过，提交后超时ac 0%

实在不懂哪里为什么就是AC不过

这样肯定超时，思密达

相同解法，同问，如何不超时

二进制中1的个数有更优的解法，但是还是显示AC 0% #include <iostream> using namespace std; int DecSum(int i) { int sum = 0; while (i) { sum = sum + i % 10; i /= 10; } return sum; } int BinSum(int i) { int count = 0; while (i) { if (i & 1) count++; i = i >> 1; } return count; } int getRt(int i) { int num = 0; for (int index = 1; index <= i; index++) { if (BinSum(index) == DecSum(index)) { num++; } } return num; } int main() { int input = 0; while (cin>>input) { int rt = getRt(input); cout << rt << endl; } return 0; }

我看到的不超时的解法是先把10000（100000？）个数中全部的幸运数用数组记录下来

import java.util.*; public class Main{ public static boolean isLuckyNumber(int n){ int sum = 0 ; int temp = n ; while(temp!=0){ sum+= temp%10 ; temp = temp/10; } int sum2 = 0 ; int tt = n ; while(tt!=0){ sum2+= tt & 1 ; tt = tt >> 1; } if(sum==sum2) return true; else return false; } public static void main(String[] args){ Scanner cin = new Scanner(System.in); while (cin.hasNextInt()) { int t = cin.nextInt(); while (t--!=0) { int n = cin.nextInt(); if(n<=0) { System.out.println(0); continue; } int count = 0 ; //100000以内所有的幸运数，可根据上边的isLuckyNumber方法事先求出来，存入数组 int[] arr =new int[483]; int k = 0; for (int i = 1; i <=100000; i++) { if (isLuckyNumber(i)) { arr[k++] = i; } } if (n>=90031) { //大于边界值 System.out.println(483); //483是数组的大小 continue; } for (int i = 0; i <arr.length; i++) { if(arr[i]>n){ count = i ; break; } } System.out.println(count); } } } }