求助：杭电ACM 2089
题目：http://acm.hdu.edu.cn/showproblem.php?pid=2089
这是我写的程序：
#include <iostream>
using namespace std;
bool Have(int n);
int main()
{
int n, m, i, result;
while(cin >> n >> m)
{
if(0==n && 0== m)
break;
result = 0;
for(i=n;i<=m;i++)
if(Have(i))
result++;
cout << result << endl;
}
return 0;
}
bool Have(int n)
{
while(n > 0)
{
if(0==(n-62)%100 || 0==(n-4)%10)
return false;
n /= 10;
}
return true;
}
但交上去却显示：“Time Limit Exceeded”，请问大家有什么好的思路吗？
小弟是ACM的新手，请不要见笑，谢谢。
[解决办法]
根据数据量，可以先把0到1000000，不吉利的数字全部算出来放一张表里，只要算这张表不超时，之后的解直接读这种表中的数据，就不会超时了。
[解决办法]
再计算 ak ak-1 ... a2里a3a2这样的组合含62的个数 q , p+q*a1为0到n中含62的个数
注意到其中 a2a1组合后就是100进制的数， 就跟上面计算4的方法一样， 对高位不够的采取补零的方法
感觉还是要根据ak ak-1 ... a1 用组合数学的方法来计算， 考虑每位的取值的可能性
[解决办法]
我上面已经说了大致思路了，再补充一点，在算0到1000000之间不吉利的数，可以用染色法。整个效率就o(1000000)一秒内绝对可以算出来了.
之后对算出来的不吉利数做累加就能算出0到n的不吉利数d(n)。结果f(a,b)=d(b)-d(a)
有简单的算法，何必弄的那么复杂。
如果要用统计的方法算，可以尝试用容斥原理来解。
[解决办法]
【程序】
#include <stdio.h>#include <string.h>int fun(int x,int *c){ int i,len,f,n; char a[10]; sprintf(a,"%d",x); len=strlen(a); f=0;*c=1; for(i=0;i<len;i++){ if(a[i]=='6'){ if(i+1<len&&a[i+1]=='2'){ f=2;break; } }else if(a[i]=='4'){ f=1;break; } } if(f==2){ a[++i]='1';*c=0; for(i=i+1;i<len;i++) a[i]='9'; }else if(f==1){ a[i]='3';*c=0; for(i=i+1;i<len;i++) a[i]='9'; } for(i=0;i<len;i++){ if(a[i]>='5') a[i]=a[i]-1; } n=a[0]-'0'; for(i=1;i<len;i++){ n=n*9+a[i]-'0'; } return n;}int data[531442]={0};int have(int n){ while(n>0){ if(0==(n-47)%81) return 0; n/=9; } return 1;}int main(){ int i,k; int m,n; int a,b,c; k=0; for(i=0;i<531442;i++){ k+=have(i); data[i]=k; } while(scanf("%d %d",&m,&n)!=EOF){ if(m==0&&n==0) break; b=fun(n,&c); a=fun(m,&c); printf("%d\n",data[b]-data[a]+c); } return 0;}
[解决办法]
public static int lucky(int start, int end) { int value = 0; if (start <= end) { if (start <= 0) start = 1; if (end >= 1000000) end = 999999; int[] c2 = { 1, 0, 0, 0, 0 }, c4 = { 1, 0, 0, 0, 0 }, c = { 8, 0, 0, 0, 0 }; for (int j, sum = 100, i = 1; i < 5; sum *= 10, i++) c[i] = sum - (c2[i] = c2[j = i - 1] + c[j]) - (c4[i] = (c2[j] << 1) + 10 * c4[j] + c[j]); value = lucky(end, c2, c) - (start == 1 ? 0 : lucky(start - 1, c2, c)) - 1; } return value; } private static int lucky(int end, int[] count2, int[] count) { int value = 0; List<int> mod = new List<int>(); while (end > 9) { mod.Add(end % 10); end /= 10; } mod.Add(end); int m, lm = 0; bool not62 = true; for (int c, ci, i = mod.Count - 1; not62 && i > 0; not62 = m != 4 && (m != 2 || lm != 6), lm = m, i--) { if ((m = mod[i]) != 0) { value += m * (c = count2[ci = i - 1] + count[ci]); if (lm == 6 && m > 2) value -= c; if (m > 4) { value -= c; if (m > 6) value -= count2[ci]; } } } if (not62) { value += (m = mod[0]); if (m < 4) { if (lm != 6 || m < 2) value++; } else if (lm == 6) value--; } return value; }
[解决办法]
上面的有点错误
public static int lucky(int start, int end) { int value = 0; if (start <= end) { if (start <= 0) start = 1; if (end >= 1000000) end = 999999; int[] c2 = { 1, 0, 0, 0, 0 }, c4 = { 1, 0, 0, 0, 0 }, c = { 8, 0, 0, 0, 0 }; for (int j, sum = 100, i = 1; i < 5; sum *= 10, i++) c[i] = sum - (c2[i] = c2[j = i - 1] + c[j]) - (c4[i] = (c2[j] << 1) + 10 * c4[j] + c[j]); value = lucky(end, c2, c) - (start == 1 ? 0 : lucky(start - 1, c2, c)); } return value; } private static int lucky(int end, int[] count2, int[] count) { int value = 0; List<int> mod = new List<int>(); while (end > 9) { mod.Add(end % 10); end /= 10; } mod.Add(end); int m, lm = 0; bool not62 = true; for (int c, ci, i = mod.Count - 1; not62 && i > 0; not62 = m != 4 && (m != 2 || lm != 6), lm = m, i--) { if ((m = mod[i]) != 0) { value += m * (c = count2[ci = i - 1] + count[ci]); if (lm == 6 && m > 2) value -= c; if (m > 4) { value -= c; if (m > 6) value -= count2[ci]; } } } if (not62) { value += (m = mod[0]); if (m < 4) { if (lm != 6 || m < 2) value++; } else if (lm == 6) value--; } return value - 1; }
[解决办法]
#include <string.h>#include <stdio.h>int b[7] = {1, 9, 80, 711, 6319, 56160, 499121};int g(char *a);int f(char *a){ int len; len = strlen(a); if (len == 0) return 0; else if (len == 1) { if (a[0] >= '4') return a[0] - '0'; else return a[0] - '0' + 1; } else { switch(a[0]-'0') { case 0: case 1: case 2: case 3: return f(a+1) + (a[0] - '0')*b[len-1]; case 4: return 4*b[len-1]; case 5: return 4*b[len-1] + f(a+1); case 6: return 5*b[len-1] + f(a+1) - g(a+1); default: return (a[0] - '0' - 1)*b[len-1] + f(a+1) - b[len - 2]; } }}int g(char *a){ if (a[0] == '\0') return 0; switch(a[0] - '0') { case 0: case 1: return 0; case 2: return (a[1] == '\0')?1:f(a+1); default: return b[strlen(a) - 1]; }}int main(){ int m, n; int k, t; char a[10]; while (scanf("%d %d", &m, &n) != EOF) { if (m == 0 && n == 0) break; if (0 == m) a[0] = '\0'; else sprintf(a, "%d", m-1); k = f(a); sprintf(a, "%d", n); t = f(a); printf("%d\n", t - k); }}
[解决办法]
f(m,n) 表示求区间 [m,n] 之间的不含有不吉利数字的统计个数，有
f(m,n) = f(0,n) - f(0,m-1)
用 fx(n) 表示 f(0,n)，针对特殊的 n 为 {9,99,999,9999,...} 序列有 a[k+1] = 9a[k] - a[k-1]（21楼），这个序列结果为
a[] = {1,9,80,711,6319,56160} //a[0]=1 不对应具体数字，方便计算。
用 fy(d[]) 来计算 fx(n)，d[] 为数字 n 的各位十进制数字，比如 n=36574 则 d={4,7,5,6,3,0,0}
这样可以将区间 [0,36574] 拆成多个区间进行统计
//★ d[4] = 3+ a(4)*3 //[00000, 29999] //★ d[3] = 6+ a(3)*5 //[30000,33999]∪[35000,35999] //★ d[2] = 5+ a(2)*4 //[36000,36399]- a(2) //排除 [36200,36299] //★ d[1] = 7+ a(1)*6 //[36500,36539]∪[36550,36569]- a(0) //排除 [36562,36562] //★ d[0] = 4+ a(0)*4 //[36570,36573]---------= 22809
[解决办法]
长久不用 C 了，大致意思补完整一下，O(1) 的算法
#include <iostream> using namespace std; int a[] = {1,9,80,711,6319,56160};int f(int m, int n){ return (fx(n)-f(m-1));}int fx(int n){ byte d[7]; for (int i=0;i<=5;i++){ d[i] = (n % 10); n /= 10; } return fy(d);}int fy(byte d[]){ ...}int main() { int n, m, result; while(cin >> n >> m) { if(0==n && 0== m) break; result = f(m,n); cout < < result < < endl; } return 0; }
[解决办法]
这样不知道在效率上能不能达到要求:
m=10033
n=630001
Num=0
while m <=n
'response.write "xxxxx"&cStr(m)&"xxxxx<br>"
strM=cStr(m)
if instr(strM,"4")=0 then
if inStr(strM,"62")=0 then
Num=Num+1
strM=Replace(strM,"4","XXXXXXXXXX4XXXXXXXXXX")
strM=Replace(strM,"62","XXXXXXXXXX62XXXXXXXXXX")
'response.write strM&"<br>"
m=m+1
else
m=m+10^(len(strM)-InStrRev(strM,"62")-1)
'response.write "000000000000000000000000000000000000000000<br>"
end if
else
m=m+10^(len(strM)-InStrRev(strM,"4"))
'response.write "000000000000000000000000000000000000000000<br>"
end if
wend
精简了在极端情况下如最上位3进位5时多余计算,我想应该是足够了,反正我这里10000个号码不需要1秒就可以算出来了
另外还有一种时间换空间的算法的延续:
记录1 2 3 4 5 6 7 8 9 中排除数的个数
记录10 20 30 40 50 60 70 80 90 中排除数的个数
记录100 200 300 400 500 600 700 800 900 中排除数的个数
记录1000 2000 3000 4000 5000 6000 7000 8000 9000中排除数的个数
............
一直记录到符合要求的位数
然后根据给出的数字每一位上对应的数字对应得到
如计算633567时,结果为
600000对应数+30000上对应数+3000上对应数+500上对应数+60上对应数+7上对应个数
因为无须考虑给出的车牌本身就有问题如要求计算6234567上62和4带来的问题,所以我认为这种算法也是可行的
如果考虑到给出的车牌本身就有问题,只需要在开始计算的时候就做个判断取下限后最小合理数和上限前最大合理数就可以了