題目描述

奶牛Bessie最近買了一臺手機，它的手機號碼是：13300303003，手機號碼由11個數字組成。Bessie最近在上電腦課學了【復制】和【粘貼】，于是它打開word軟件，把它的手機號碼復制，然后粘貼了N次。例如N=1時，是這樣：13300303003 。又例如N=2時，是這樣：1330030300313300303003。 再例如N=3時，是這樣：133003030031330030300313300303003。 如果N=4，會是這樣：13300303003133003030031330030300313300303003。 現在給出了三個正整數：N，S，T。表示奶牛Bessie把它的手機號碼復制粘貼了N次，然后奶牛要計算：第S個數字到第T個數字之間，有多少個數字3（包含第S個數字和第T個數字）？由于奶牛Bessie復制粘貼N次手機號碼后已經眼花了，所以它希望你能寫個程序來幫它計算，你能做到嗎？

輸入

一行，三個正整數： N，S，T

輸出

一個整數，表示Bessie把手機號碼復制粘貼N次后，第S個數字到第T個數字之間包含了多少個數字3（包含第S個數字和第T個數字）。

樣例輸入

1 2 11

樣例輸出

5

提示

由于N=1，所以復制粘貼后是13300303003，那么第2個數字至第11個數字就是：3300303003，可以算出有5個數字3。
對于50%的數據，? 1<=N<=1000，? 1 <= S < T <= 11×N
對于100%的數據， 1<=N<=100000000，? 1 <= S < T <= 11×N

---

題目大意：給出一組n,l,r，詢問初始字符串“13300303003”復制n次后，第l位到r位中有多少個3

題目分析：簡單的分塊問題，但在著手做這個題目的時候，思路混亂，分類討論的略顯麻煩，導致最后漏情況，其實這個題目可以將模型抽象出來，然后就特別好處理了

因為l和r是基于連續(xù)序號之上的，而且是11位一組，我們不妨將其視為一個矩陣：

? 1? ?2? ?3? ?4? ?5? ?6? ?7? ?8? ?9?10 11

12 13 14 15 16 17 18 19 20 21 22

23 24 25 26 27 28 29 30 31 32 33

類似于這樣的一個矩陣

為了方便處理，我們每一位都減一，變?yōu)橄旅孢@樣：

? 0? 1? ?2? ?3? ?4? ?5? ?6? ?7? ?8? ?9?10?

11 12 13 14 15 16 17 18 19 20 21

22 23 24 25 26 27 28 29 30 31 32

這樣，我們假設每個編號為k，則其對應的坐標就是x=k/11,y=k%11

有了這樣的一個轉換，接下來的操作就方便多了，我們將l的坐標表示為(x,y)，r的坐標表示為(xx,yy)

那么我們只需要分類討論一下：

若x==xx：l和r在同一行，只需要從y遍歷到y(tǒng)y即可

若x!=xx：l和r不在同一行，我們只需要加上中間差的行數中的3的個數即可（每行5個），然后再從y遍歷到尾，從頭遍歷到y(tǒng)y記錄一下個數

這樣答案很容易的就計算出來了

代碼：

#include<iostream> #include<cstdlib> #include<string> #include<cstring> #include<cstdio> #include<algorithm> #include<climits> #include<cmath> #include<cctype> #include<stack> #include<queue> #include<list> #include<vector> #include<set> #include<map> #include<sstream> using namespace std;typedef long long LL;const int inf=0x3f3f3f3f;const int N=1e5+100;string s="13300303003";int main() { // freopen("input.txt","r",stdin); // ios::sync_with_stdio(false);int n,l,r;cin>>n>>l>>r;int x=(l-1)/11;int xx=(r-1)/11;int ans=0;int y=(l-1)%11;int yy=(r-1)%11;if(x!=xx)//不在一行 {ans+=(xx-x-1)*5;for(int i=0;i<=yy;i++)if(s[i]=='3')ans++;for(int i=y;i<s.size();i++)if(s[i]=='3')ans++;}else//在同一行 {for(int i=y;i<=yy;i++)if(s[i]=='3')ans++;}cout<<ans<<endl;return 0; }

?

總結

以上是生活随笔為你收集整理的中石油训练赛 - 手机号码(简单分块+思维)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。