首页 > 代码库 > 循环序列
循环序列
循环序列
(circulate.cpp/c/pas)
(1s/256M)
题目描述
Alice与Bob在玩游戏：
Alice首先给出两个数X与Y（X<=Y）；
Bob则按顺序将X,X+1,X+2,…,Y-1,Y写成一个大数S。
Alice最后将S首尾相连，让其围成一个圈。
这时，Bob想知道，从S的开头出发，往后的第L位到第R位数字之和是多少。
输入格式(circulate.in)
第一行四个整数X，Y，L，R,代表Alice的两个数字和Bob想要知道的第L位到第R位的数字之和。
输出格式(circulate.out)
仅一行，一个整数M，代表第L位到第R位的数字之和。
样例输入
10 11 4 12
样例输出
7
样例解释
Bob将数字写成一行大数S = 1011；围成一个圈后，从第4位到第12位分别是1,1,0,1,1,1,0,1,1，它们的和是7.
数据范围与限制
对于50%的数据，L=1, X,Y,L,R<=1000；
对于100%的数据，S的长度不大于10000，X,Y,L,R<=100000000.
~\(≧▽≦)/~啦啦啦思路：
首先按题目要求将x到y之间的数拆分存到一个数组中，然后用另一个数组将该数组倒叙存储，（便于计算），运用前缀和，取整环和不完整环，相加
(⊙v⊙)嗯~ 代码：
1 #include<iostream> 2 #include<cstdio> 3 using namespace std; 4 5 const int N = 1e5 + 6; 6 int x,y,r,l,n,m; 7 int a[N],s[N],b[N]; 8 9 void work(int x,int y){10 n=0;11 for(int i=x;i<=y;i++){12 m=0;13 for(int t=i; t ;t/=10) b[++m]=t%10;14 for(int t=m; t ;t--) a[++n]=b[t];15 }16 s[0] = 0;17 for(int i=1;i<=n;i++) s[i]= s[i-1] + a[i];//前缀和 18 }19 20 int cal(int p){21 if(p == 0) return 0;22 int g = (p-1)/n;//整23 int r = (p-1)%n + 1;//余24 return s[n] * g + s[r];25 }26 27 int main() {28 cin>>x>>y;29 cin>>l>>r;30 work(x,y);31 cout<<cal(r)-cal(l-1);32 return 0;33 }
循环序列
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。