求助：杭电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，不吉利的数字全部算出来放一张表里，只要算这张表不超时，之后的解直接读这种表中的数据，就不会超时了。
[解决办法]
[解决办法]
可能有办法计算出答案……
考虑不含“4”的情况
例如：
1 100
0-->0
1-->1
2-->2
3-->3
4-->×
5-->4
6-->5
7-->6
8-->7
9-->8
把100按照上面的表进行转换为：100（9进制）
【先求 0 100】
9进制下的100为十进制里的：
1*9^2+0*9^1+0=81
其中含有62的情况只有1种
所以从0~100（十进制）里一共有（81-0+1）-1 = 81个不含“4”和“62”的数……
【再求 0 1】
0 1==》2
【最后1求 1 100】
（1 100）= 81-2+（1符合条件?1:0） = 79+1 = 80
[解决办法]
[解决办法]
[解决办法]
[解决办法]
按此思路， 计算1到n中含4和含62的数是可以的，但是交集如果不遍历还是不太好想象
ak ak-1 ... a1, 是n的k位数, 分别计算 a2a1 这样的位含62的个数为p
再计算 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)
有简单的算法，何必弄的那么复杂。
如果要用统计的方法算，可以尝试用容斥原理来解。
[解决办法]
【程序】
- C/C++ code
#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;}
[解决办法]
[解决办法]
有你们这么麻烦的吗,炫耀技巧啊
整个深圳市一年想新增2500台的士都引起骚动,你们以为杭州1天能新增多少台?
C++我不熟,用VBs表示好了,区间为M到N:
Num=0
while m<=n
strM=cstring(m)
if instr(strM,"4")=0 then
if instr(strM,"62")=0 then
Num=Num+1
end if
end if
next
m=m+1
next
Num即为所求
[解决办法]
性能和复杂度有时候不能兼顾.
这个题目就像是求1-n的和
循环累加简单,但是慢.
用公式n*(n+1)/2快,但是需要知道等差数列的公式.
就这么回事情.
所以要想代码完成快,就循环解决,要想效率高,就应该先推导出数学公式.
[解决办法]
- C# code
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; }
[解决办法]
上面的有点错误
- C# code
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; }
[解决办法]
------解决方案--------------------
其实还是有规律的
按位数考虑
0 ~ 9 满足条件的有 9 个
0 ~ 99 满足条件的有 80 个
0 ~ 999 满足条件的有 712 个
于是得到递归公式 a[k+1] = 9a[k] - a[k-1] 此数列可求出通项表达式的
于是 n 对应为bk, bk-1, ... , b1
用f(bkbk-1...b1) 表示0 ~ n中满足的个数
则对bk考虑
switch(bk){
case 1:
case 2:
case 3:f(bkbk-1...b1) = bk*a[k-1] + f(bk-1bk-1...b1); break;
case 4:f(bkbk-1...b1) = 4*a[k-1]; break;
case 5:f(bkbk-1...b1) = 4*a[k-1] + f(bk-1bk-1...b1); break;
case 6:f(bkbk-1...b1) = 5*a[k-1] + f(bk-1bk-1...b1) - g(bk-1bk-1...b1); break; //同样减去2开头的?
case 7:
case 8:
case 9:f(bkbk-1...b1) = (bk - 1)*a[k-1] + f(bk-1bk-1...b1) - a[k-2]; break;//最后一项表示的是6开头时减去2开头的
}
g(bkbk-1...b1)=
switch(bk){
case 1: return 0;
case 2: return f(bk-1bk-2...b1)
default: return a[k-1];
}
无奈啊， 谁给个O(1)的算法
[解决办法]
- C/C++ code
#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] 拆成多个区间进行统计
- C/C++ code
//★ 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) 的算法
- C/C++ code
#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带来的问题,所以我认为这种算法也是可行的
如果考虑到给出的车牌本身就有问题,只需要在开始计算的时候就做个判断取下限后最小合理数和上限前最大合理数就可以了