bzoj 1026 [SCOI2009]windy數 題解

1026: [SCOI2009]windy數

Time Limit: 1 Sec Memory Limit: 162 MB
Submit: 1875 Solved: 810
[Submit][Status]

Description

windy定義了一種windy數。不含前導零且相鄰兩個數字之差至少為2的正整數被稱為windy數。 windy想知道，在A和B之間，包括A和B，總共有多少個windy數？

Input

包含兩個整數，A B。

Output

一個整數。

Sample Input

【輸入樣例一】
1 10

【輸入樣例二】
25 50

Sample Output

【輸出樣例一】
9

【輸出樣例二】
20

【數據規模和約定】
20%的數據，滿足 1 <= A <= B <= 1000000 。
100%的數據，滿足 1 <= A <= B <= 2000000000 。

【分析】暴力顯而易見時20分。對於這種題目，應該是數論或是DP。

基礎的優化：A--B中的數就是1--B中的數減去1--A-1中的數。（前綴和）

【初次做】開始，我用f[i][j]表示滿足條件的、長度為i且尾字母是j的數的個數。轉移的時候方程很簡單：f[i][j]+=f[i-1][k]（|j-k|>=2)但是我不由地想到：這樣怎麼求1--X中的數呢？

【仔細思考】那麼換一種角度考慮：f[i][j]表示滿足條件的、長度為i且首字母是j的數的個數。這樣有什麼好處呢？假設我們要求1--X中符合要求的數。首先設X=abcd。那麼我們先加上f[4][0]、f[4][1]、f[4][2]一直到f[4][a-1]，然後再加上f[3][0]、f[3][1]一直到f[3][b-1]……當然，最後是加上f[1][0]、f[1][1]一直到f[1][d]。

【注意點】

①我們要開兩個數組，f數組如上描述。但是因為有前導0的問題，我們還要開一個ff數組，表示ff[i][0]的狀態（在f數組推導時，為了不影響後面的情況，f[i][0]的處理會少一點）。比如f[2][0]中，01、02這幾種狀態也是可以的。因為我們還算了0這種狀態，最後函數裡要減1。

②細節自己注意。

【代碼】

#include
#include
using namespace std;
int f[20][10],ff[20][10],a,b,i,j,k;
int p(int k)
{
  if (k<10) return(k);
  int t,ans=0,a[20],cnt=0,i,temp;
  while (k>0){a[++cnt]=k%10;k/=10;}
  for (i=1;i<=cnt/2;i++) 
  {
    t=a[i];a[i]=a[cnt-i+1];a[cnt-i+1]=t;
  }
  for (i=0;icnt)
    {
      now--;
      temp=a[now]-a[now-1];
      if (temp<0) temp=-temp;
      if (temp>=2) ans+=f[1][a[now]];
      break;
    }
  }
  return ans-1;
}
int main()
{
  scanf("%ld%ld",&a,&b);
  for (i=0;i<=9;i++)
  {
    f[1][i]=1;ff[1][i]=1;
  }
  for (i=2;i<=10;i++)
    for (j=0;j<=9;j++)
      for (k=0;k<=9;k++)
        if (abs(k-j)>=2) 
        {
          f[i][j]+=f[i-1][k];
          ff[i][j]+=ff[i-1][k];
        }
  for (i=2;i<=10;i++)
  {
    ff[i][0]=0;
    for (j=0;j<=9;j++)
      ff[i][0]+=ff[i-1][j];
  }
  printf("%ld",p(b)-p(a-1));
  return 0;
}