2014 G. Milky Days

实际上是一道模拟题， 我们定义关键天为牛奶数目可能会非因为喝掉而改变的那天。 利用一个deque去处理关键天时能否供给牛奶即可 则关键天为 \(\min(最近牛奶过期天，下一个获得牛奶的天)\) 我们一边求解答案一边算下一个关键天是哪个 假设关键天序列为\(a_0,a_1,a_2,a_3...\) 初始化\(a_0 = 1\) 由于一个关键天到下一个关键天前,牛奶只会被喝掉而不会过期、增加，那么我们就可以\(O(1)\)处理掉这一段了。 于是我们的算法是： 1. 算出下一个关键天\(a_{i+1}\) 2. 处理区间\([a_i,a_{i+1}-1]\) 3. 把关键天对milk数目的影响加入进去

显然，我们如上初始化之后，只需要一个简单的技巧：补一个足够大的关键天并让它对牛奶的影响为0，最后即可得到答案。

我们对每一段的处理是\(O(1)\)的，而总的关键天数不会超过\(2n\)(每一批的牛奶都过期了)，那么总的时间复杂度为\(O(n)\)

Code: 
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
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
void solve()
{
    int n, m, k;
    cin >> n >> m >> k;
    deque<pair<int,int>>dq;
    vector<int>a(n);
    vector<int>d(n);
    for (int i = 0; i < n; i++) {
        cin >> d[i] >> a[i];
    }
    a.push_back(0);
    d.push_back(1145141919);
    int ans = 0;
    int t = 1;
    ll mks = 0;
    int p = 0;
    while (p != n + 1) {
        int nxt;
        if (dq.empty())
            nxt = d[p];
        else
            nxt = min(dq.front().second + k, d[p]);

        ll need = (nxt - t) * (ll)m;
        if (mks >= need) {
            mks -= need;
            ans += nxt - t;
            while (need > 0) {
                if (need >= dq.back().first) {
                    need -= dq.back().first;
                    dq.pop_back();
                }
                else {
                    dq.back().first -= need;
                    need = 0;
                }
            }
        }
        else {
            ans += mks / m;
            mks = 0;
            dq.clear();
        }

        if (nxt == d[p]) {
            dq.push_back({ a[p],d[p] });
            mks += a[p];
            p++;
            t = nxt;
        }
        else{
            if (!dq.empty()) {
                mks -= dq.front().first;
                dq.pop_front();
            }
            t = nxt;
        }
    }
    cout << ans << endl;
    return;
}

2014 H. Robin Hood Archery

通过简单的观察，只有这个区间的所有数都出现偶数次才可能平手，所以我们自然联想到用异或hash来处理： 由异或的性质，每个数的偶数次异或和结果为0。 于是一个区间的数都出现偶数次的必要条件于这个区间的随机异或和为0(充要前提是不发生hash碰撞)。 于是我们给每个数随机一个mt19937_64作为值，然后处理一下异或前缀和方便\(O(1)\)查询每个区间 (每个数异或逆元是它本身，即很好找到异或逆元，这是我们从前缀和得到区间和的必要条件，而像\(\gcd\)等运算根本没有逆元导致没办法处理前缀和之后就\(O(1)\)求解区间和) 之后就很简单了，如果异或和为0即为合法区间。

Code: 
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
void solve()
{
    mt19937_64 rnd(chrono::steady_clock::now().time_since_epoch().count());
    map<int, ll>mp, status;
    int n, q;
    cin >> n >> q;
    vector<int>a(n + 1);
    vector<int>hs(n + 1);
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        if (mp[a[i]] == 0) {
            mp[a[i]] = rnd();
        }
        hs[i] = mp[a[i]];
    }
    for (int i = 1; i <= n; i++) {
        hs[i] ^= hs[i - 1];
    }

    for (int i = 0; i < q; i++) {
        int l, r;
        cin >> l >> r;
        if ((hs[r] ^ hs[l - 1]) == 0) {
            cout << "Yes" << endl;
        }
        else {
            cout << "No" << endl;
        }
       
    }
    return;
}

这题好像也有莫队的做法，想想也可行(如果实现比较好不被卡常)

165 E. Compatible Numbers

从某道最近的题来的S 一道sos dp典题，但是写的时候过于犯病

题意大概是给定一个非空多重集合，\(a_i \ge 1\)。定义compatible(相容)\(a\)相容\(b\)为 \(a \& b = 0\),对集合中每个元素，求集合中与它相容的元素(不能是它本身或者相等的元素)

因为知道是sosdp，所以很快有思路： 每个元素\(a_i\)按位取反\(\sim a_i\)的子掩码都与\(a_i\)相容，我们直接用\(a_i\)的下标\(i\)初始化\(dp[\sim a_i]\)，其他初始值为0,然后跑一遍sosdp即可。设置a[0] = -1即可让\(ans[i] = a[dp[a[i]]]\);

sosdp的dp方法： 对每个位来一轮(假设为第\(i\)位)，遍历整个状态空间，如果该位置\(p\)这一位为1(\((p>>i) \& 1 == 1\))，则更新 \[dp[p \oplus 1<<i] = \max(dp[p],dp[p \oplus 1<<i])\] 取max是为了防止被-1覆盖。

Code: 
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
void solve()
{
    int n;
    cin >> n;
    const int m = 22;
    const int p = 1 << m;
    const int inf = (1 << m) - 1;
    vector<int>a(n + 1);
    vector<int>msk(p);
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        msk[(~a[i]) & inf] = i;
    }

    for (int i = 0; i < m; i++) {
        for (int j = 0; j < p; j++) {
            if ((j >> i) & 1) {
                msk[j ^ (1 << i)] = max(msk[j], msk[j ^ (1 << i)]);
            }
        }
    }

    for (int i = 1; i <= n; i++) {
        if (msk[a[i]])
            cout << a[msk[a[i]]] << " ";
        else
            cout << -1 << " ";
    }
    cout << endl;
    return;
}

<>