e140: 不要 XY
Tags : DP dfs digitDP dp
Accepted rate : 1人/1人 ( 100% ) [非即時]
評分方式:
Tolerant

最近更新 : 2026-06-01 15:56

Content

題目名稱:排除不吉利數 (Lucky Numbers Only)

【題目描述】

給定一個整數區間 L 到 R,請計算出在該區間內,共有多少個「吉利數字」。

不吉利數字的定義:

只要數字中含有特定的單一數字 X,或者出現特定的相鄰數字組合(連號) Y,該數字即被視為不吉利。

  1. 單一數字檢查:數字的任何一個位數等於 X。

  2. 相鄰組合檢查:數字中包含連續的子字串 Y。

舉例說明:

假設 X = 4 且 Y = 67。

67674:不吉利(同時包含連號 67 與數字 4)。

267:不吉利(包含連號 67)。

4123:不吉利(包含數字 4)。

2589:吉利(既沒有 4 也沒有 67)。

【測資範圍】

1 <= L <= R <= 10^18 (提示:需使用 64-bit 整數型別如 long long)

0 <= X <= 9 (X 必為單一位數)

10 <= Y <= 10^9 (Y 為至少兩位數以上的正整數)

【注意事項與邊界條件】

  1. 前導零不計入判斷:數字在表示時不包含前導零。例如:當 X = 0 時,數字 5 視為吉利數字(不可將其視為 005 而誤判為包含 0)。

  2. 重疊涵蓋:有時 Y 本身就包含了 X(例如 X = 4, Y = 47),判斷邏輯需能兼容此情況,兩者只要觸發其一即為不吉利。

  3. 區間大小:測資範圍高達 10^18,請勿使用窮舉法遍歷區間,否則將導致 Time Limit Exceeded (TLE)。

Input

輸入四個數字

L,R,X,Y

用意如題幹所述

Output

輸出最終有多少個數字符合題述

Sample Input
1 100 4 67
Sample Output
80
測資資訊:
記憶體限制: 64 MB
公開 測資點#0 (5%): 1.0s , <1K
公開 測資點#1 (5%): 1.0s , <1K
公開 測資點#2 (5%): 1.0s , <1K
公開 測資點#3 (5%): 1.0s , <1K
公開 測資點#4 (5%): 1.0s , <1K
公開 測資點#5 (5%): 1.0s , <1K
公開 測資點#6 (5%): 1.0s , <1K
公開 測資點#7 (5%): 1.0s , <1K
公開 測資點#8 (5%): 1.0s , <1K
公開 測資點#9 (5%): 1.0s , <1K
公開 測資點#10 (5%): 1.0s , <1K
公開 測資點#11 (5%): 1.0s , <1K
公開 測資點#12 (5%): 1.0s , <1K
公開 測資點#13 (5%): 1.0s , <1K
公開 測資點#14 (5%): 1.0s , <1K
公開 測資點#15 (5%): 1.0s , <1K
公開 測資點#16 (5%): 1.0s , <1K
公開 測資點#17 (5%): 1.0s , <1K
公開 測資點#18 (5%): 1.0s , <1K
公開 測資點#19 (5%): 1.0s , <1K
Hint :
Tags:
DP dfs digitDP dp
出處:
[管理者:
benjaminshih (11104)
]


ID User Problem Subject Hit Post Date
沒有發現任何「解題報告」