首页技术正文

BZOJ3544 [ONTAK2010]Creative Accounting

开发者艺馨技术 2022年11月13日

0 收藏 929 点赞 3,565 浏览 880 个字

看不懂题，就不能写的稍微像人话点吗我去。。。

题目就是要找一段区间使得Σai mod m的值最大。

于是嘛。。。前缀和一下再贪心就好了。

先求出前i个数的前缀和s，然后用s更新解。

还有可能就是前面的某个前缀和s1刚好在mod m意义下大于s且是最小的一个，那么这一段的和就是m + s – s1，再用它来更新解。

 /**************************************************************
     Problem: 3544
     User: rausen
     Language: C++
     Result: Accepted
     Time:2056 ms
     Memory:7012 kb
 ****************************************************************/ #include <cstdio>
 #include <algorithm>
 #include <set> using namespace std;
 typedef long long ll;
 int n;
 ll mod, s, a, ans, p;
 set <ll> S; inline ll read(){
     ll x = , sgn = ;
     char ch = getchar();
     while (ch < '' || ch > ''){
         if (ch == '-') sgn = -;
         ch = getchar();
     }
     while (ch >= '' && ch <= ''){
         x = (ll) x *  + ch - '';
         ch = getchar();
     }
     return sgn * x;
 } int main(){
     scanf("%d", &n); mod = read();
     for (int i = ; i <= n; ++i){
         a = read();
         if (a < ) a += (abs(a / mod) + ) * mod;
         s += a, s %= mod;
         ans = max(ans, s);
         if (S.upper_bound(s) != S.end()){
             p = *(S.upper_bound(s));
             ans = max(ans, (s + mod - p) % mod);
         }
         S.insert(s);
     }
     printf("%lld\n", ans);
     return ;
 }