AtCoder Regular Contest 150

A. Continuous 1

知识点：简单题
复杂度：\(O(n)\)

当一个区间合法，那么必定区间长度为 k，并且区间内无0，并且1的个数等于所有的1的总和
这个使用个前缀和即可\(O(1)\)维护

#define rep(i,l,r) for(int i=l,_##i=r;i<=_##i;i++)
#define per(i,l,r) for(int i=r,_##i=l;i>=_##i;i--)
#define ll long long
#define fi first
#define se second
#define endl '\n'
#define pll pair<ll,ll>
#define pii pair<int,int>
template<class T> using vc = vector<T>;
template<class T> using vvc = vc<vc<T> >;
const int N = 3e5 + 5;

int n, m, k;
char s[N];

int pre[N][2];

void solve()
{
    cin >> n >> k >> (s + 1);
    int sum = 0;
    rep(i, 1, n) if (s[i] == '1') sum++;
    int cnt = 0;
    rep(i, 1, n)
    {
        rep(j, 0, 1) pre[i][j] = pre[i - 1][j];
        if (s[i] == '0') pre[i][0]++;
        else if (s[i] == '1') pre[i][1]++;
        if (i >= k)
        {
            if (pre[i][0] - pre[i - k][0] == 0 && pre[i][1] - rep[i - k][1] == sum)
                cnt++;
        }
    }
    cout << (cnt == 1 ? "Yes" : "No") << endl;
}

B. Make Divisible

知识点：整除分块
复杂度：\(O(\sqrt{B})\)

没怎么打过Atcoder，但是B题就是整除分块，是不是有点抽象？

数论题一般考虑具体的公式
我们先观察式子

整理得

考虑 K 的上界，为 \(\big \lceil \frac{B}{A} \big \rceil \le 10^9\),显然不能逐一枚举 K，还需要化简，

如果 K 固定，那么观察上式，易得

为了让 X 取到最小值，显然 \(X=max(0,\big \lceil \frac{B}{K} \big \rceil – A)\),
整理得到 \(X=max(0,\big \lfloor \frac{B-1}{K} \big \rfloor +1-A)\)

观察得到 \(\big \lfloor \frac{B-1}{K} \big \rfloor\) 只有 \(\sqrt{B}\) 个取值，所以我们可以直接枚举 X

#define rep(i,l,r) for(int i=l,_##i=r;i<=_##i;i++)
#define per(i,l,r) for(int i=r,_##i=l;i>=_##i;i--)
#define ll long long
#define fi first
#define se second
#define endl '\n'
#define pll pair<ll,ll>
#define pii pair<int,int>
template<class T> using vc = vector<T>;
template<class T> using vvc = vc<vc<T> >;

ll a, b;
void solve()
{
    cin >> a >> b;
    if (a >= b) cout << a - b << endl;
    else if (b % a == 0) cout << 0 << endl;
    else
    {
        ll ans = a - b % a;
        ll lim = b - 1;
        for (ll l = 1, r; l <= lim; l = r + 1)
        {
            r = lim / (lim / l);
            ll x = max(0ll, lim / l + 1 - a);
            ll y = (b + a + x - 1) / (a + x) * (a + x) - b;
            ans = min(ans, x + y);
        }
        cout << ans << endl;
    }
}

原文地址：http://www.cnblogs.com/lunasama/p/16907606.html