P1956 Sum
题目描述
给出一个数列a1,a2,⋯ ,ana_1,a_2,\cdots,a_na1,a2,⋯,an和k,pk,pk,p；
设Si,j=∑k=ijakS_{i,j}=\sum\limits_{k=i}^ja_kSi,j=k=i∑jak，则：
Answer=min{Si,j mod p ∣ Si,j mod p≥k}\mathit{Answer}=\min\{S_{i,j}\bmod p\ |\ S_{i,j}\bmod p\ge k\}Answer=min{Si,jmodp∣Si,jmodp≥k}
其中，i≤j,{Si,j mod p ∣ Si,j mod p≥k}≠∅i\le j, \{S_{i,j}\bmod p\ |\ S_{i,j}\bmod p\ge k\}\ne\varnothingi≤j,{Si,jmodp∣Si,jmodp≥k}=∅。
输入格式
第一行三个正整数n,k,pn,k,pn,k,p。
第二行nnn个正整数，表示a1,a2,⋯ ,ana_1,a_2,\cdots,a_na1,a2,⋯,an。
输出格式
一行一个正整数，表示Answer\mathit{Answer}Answer。
输入输出样例 #1
输入 #1
7 2 17 12 13 15 11 16 26 11输出 #1
2说明/提示
数据范围
对于100%100\%100%的数据，1≤n≤1051\le n\le10^51≤n≤105，1≤k,p,ai≤10181\le k,p,a_i\le10^{18}1≤k,p,ai≤1018。
C++实现
#include<set>#include<stdio.h>#include<algorithm>#defineintlonglongusingstd::min;std::set<int>q;ints[100005];signedmain(){q.insert(0);intn,k,p,i,x,res=1ll<<60;scanf("%lld %lld %lld",&n,&k,&p);for(i=1;i<=n;++i){scanf("%lld",&x);s[i]=(s[i-1]+x)%p;}for(i=1;i<=n;++i){res=min(res,s[i]+(s[i]<k?p:0)-(*--q.upper_bound((s[i]+p-k)%p)));q.insert(s[i]);}printf("%lld",res);return0;}后续
接下来我会不断用C++来实现信奥比赛中的算法题、GESP考级编程题实现、白名单赛事考题实现，记录日常的编程生活、比赛心得，感兴趣的请关注，我后续将继续分享相关内容