当前位置：首页 > article >正文

Codeforces Round 971 (Div. 4) A~G2

article 2024/9/22 5:33:48

背景

怎么还有人会迟20分钟才开始的啊

开学了，可能没有那么详细

G2包T的，已被斩于马下（已修改，ac）

A题：Minimize!

思路

无论怎么样，答案都是b-a

代码

inline void solve() {
	int a, b; cin >> a >> b;
    cout << b - a << endl;
	return;
}

B题：osu!mania

思路

模拟

代码

inline void solve() {
	int n; cin >> n;
	vector<string> a(n + 1);
	for (int i = 1; i <= n; i ++ ) cin >> a[i];
	for (int i = n; i >= 1; i -- ) {
		for (int j = 0; j < 4; j ++ ) {
			if (a[i][j] == '#') cout << j + 1 << " \n"[i == 1];
		}
	}
	
	return;
}

C题：The Legend of Freya the Frog

思路

先按最大的跳，如果一边跳到了，那么这边之后就跳0等待

特别地，如果y方向先跳到，那么只需由x方向跳最后一下即可

代码

inline void solve() {
	LL x, y, k; cin >> x >> y >> k;
    LL l = (y + k - 1) / k, r = (x + k - 1) / k;
    LL ans = max(l, r) * 2 - (l < r);
    cout << ans << endl;
	return;
}

D题：Satyam and Counting

思路

模拟

代码

inline void solve() {
	int n; cin >> n;
    int cnt[2] = {};
    map<PII, int> e;
    for (int i = 1; i <= n; i ++ ) {
        int x, y; cin >> x >> y;
        cnt[y] += 1;
        e[{x, y}] = 1;
    }
    LL ans = 0;
    for (auto [x, y] : e) {
        if (e.count({x.first, x.second ^ 1}) ans += cnt[x.second ^ 1] - 1;
        if (e.count({x.first + 1, x.second ^ 1}) && e.count({x.first - 1, x.second ^ 1})) ans += 1;
    }
    cout << ans << endl;
	return;
}

E题：Klee's SUPER DUPER LARGE Array!!!

思路

显然地，二分

代码

inline void solve() {
    LL n, k; cin >> n >> k;
    // k ~ n + k - 1
	LL l = k - 1, r = n + k;
    LL tot = (n + k + k - 1) * n / 2;
    while (l + 1 != r) {
        LL mid = l + r >> 1;
        LL val = (mid - k + 1) * (mid + k) / 2;
        if (tot - val >= val) l = mid;
        else r = mid;
    }
    LL v = (l - k + 1) * (l + k) / 2;
    LL ans = (tot - v - v);
    if (l + 1 <= n + k - 1) ans = min(ans, abs(tot - v - r - v - r));
    cout << ans << endl;
	return;
}

F题：Firefly's Queries

思路

有点类似于容斥原理？先算[1~r]和[1~l-1]的，相减就是[l,r]的了

如何计算？

先计算之前有多少个a[1]+a[2]+a[3]~a[n]

再看我们移位了几次，还剩余几个数即可

代码

inline void solve() {
	LL n, q; cin >> n >> q;
    vector<LL> a(2 * n + 1);
    for (int i = 1; i <= n; i ++ ) cin >> a[i], a[i + n] = a[i];
    for (int i = 1; i <= 2 * n; i ++ ) a[i] += a[i - 1];
    function<LL(LL)> cal = [&](LL x) {
        LL ans = 0;
        LL rep = x / n;
        LL last = x - rep * n;
        ans += rep * a[n];
        if (last == 0) return ans;
        LL pos = (x - 1) / n + 1, chong = (x - 1) / n;
        LL head = 1 + chong;
        ans += a[head + last - 1] - a[head - 1];
        return ans;
    };
    while (q -- ) {
        LL l, r; cin >> l >> r;
        cout << cal(r) - cal(l - 1) << endl;
    }
	return;
}

G1: Yunli's Subarray Queries (easy version)

思路

如何有效地判断a[i+1]==a[i]+1?输入a[i]的时候减去i

1 2 3 2 1 2 3

->0 0 0 -2 -4 -4 -4

那么我们只要维护区间内出现最多的元素次数即可

因为区间长度一定，可以用滑动窗口完成

代码

inline void solve() {
	int n, k, q; cin >> n >> k >> q;
    vector<LL> a(n + 1), ans(n + 1);
    //0 0 0 -2 -4 -4 -4
    for (int i = 1; i <= n; i ++ ) cin >> a[i], a[i] -= i;
    map<LL, int> window, cnt;
    for (int i = 1; i <= n; i ++ ) {
        if (cnt.count(window[a[i]])) {
            cnt[window[a[i]]] -= 1;
            if (!cnt[window[a[i]]]) cnt.erase(window[a[i]]);
        }
        window[a[i]] += 1;
        cnt[window[a[i]]] += 1;
        if (i < k) continue;
        ans[i - k + 1] = cnt.rbegin()->first;
        cnt[window[a[i - k + 1]]] -= 1;
        if (!cnt[window[a[i - k + 1]]]) cnt.erase(window[a[i - k + 1]]);
        window[a[i - k + 1]] -= 1;
        if (window[a[i - k + 1]]) cnt[window[a[i - k + 1]]] += 1;
    }
    while (q -- ) {
        LL l, r; cin >> l >> r;
        cout << k - ans[l] << endl;
    }
	return;
}

G2:Yunli's Subarray Queries (hard version)

思路

先仔细看题

然后就可以发现，这个过程可以用单调栈完成，比如说一开始我们发现k长度下要修改2个数才能有k个连续，之后又发现可以只修改1个数就可以了。

修改2个数到1个数这段时间内，都是要修改2个数的，而之后可以变成修改1个数

代码

inline void solve() {
	LL n, k, q; cin >> n >> k >> q;
    vector<LL> a(n + 1), ans(n + 1);
    for (int i = 1; i <= n; i ++ ) cin >> a[i], a[i] -= i;
    map<LL, int> window, cnt;
    for (int i = 1; i <= n; i ++ ) {
        if (cnt.count(window[a[i]])) {
            cnt[window[a[i]]] -= 1;
            if (!cnt[window[a[i]]]) cnt.erase(window[a[i]]);
        }
        window[a[i]] += 1;
        cnt[window[a[i]]] += 1;
        if (i < k) continue;
        ans[i] = cnt.rbegin()->first;
        cnt[window[a[i - k + 1]]] -= 1;
        if (!cnt[window[a[i - k + 1]]]) cnt.erase(window[a[i - k + 1]]);
        window[a[i - k + 1]] -= 1;
        if (window[a[i - k + 1]]) cnt[window[a[i - k + 1]]] += 1;
    }
    vector<LL> nxt(n + 1), st;
    for (int i = n; i; i -- ) {
        while (st.size() && ans[i] >= ans[st.back()]) st.pop_back();
        nxt[i] = st.size() ? st.back() : n + 1;
        st.push_back(i);
    }
    while (q -- ) {
        LL l, r; cin >> l >> r;
        LL id = l + k - 1;
        LL res = 0;
        while (id <= r) {
            res += 1ll * max(0ll, k - ans[id]) * (min(r + 1, nxt[id]) - id);
            id = nxt[id];
        }
        cout << res << endl;
    }
	return;
}

修改后的正解：线段树

const int N = 2e5 + 9;
struct node{
    int l, r;
    LL v, lazy;
}tr[N << 2];
void build(int u, int l, int r) {
    tr[u] = {l, r, 0ll, 0ll};
    if (l == r) return;
    int mid = l + r >> 1;
    build(u << 1, l, mid), build(u << 1 | 1, mid + 1, r);
}
void pushdown(int u) {
    int mid = tr[u].l + tr[u].r >> 1;
    tr[u << 1].v = tr[u].lazy * (mid + 1 - tr[u].l), tr[u << 1 | 1].v = tr[u].lazy * (tr[u].r - mid);
    tr[u << 1].lazy = tr[u << 1 | 1].lazy = tr[u].lazy;
    tr[u].lazy = 0;
}
void update(int u, int l, int r, int v) {
    if (tr[u].l >= l && tr[u].r <= r) {
        tr[u].v = (tr[u].r - tr[u].l + 1) * v;
        tr[u].lazy = v;
        return;
    }
    if (tr[u].lazy) pushdown(u);
    int mid = tr[u].l + tr[u].r >> 1;
    if (l <= mid) update(u << 1, l, r, v);
    if (r > mid) update(u << 1 | 1, l, r, v);
    tr[u].v = tr[u << 1].v + tr[u << 1 | 1].v;
}
LL query(int u, int l, int r) {
    if (tr[u].l >= l && tr[u].r <= r) return tr[u].v;
    if (tr[u].lazy) pushdown(u);
    int mid = tr[u].l + tr[u].r >> 1;
    LL ans = 0;
    if (l <= mid) ans += query(u << 1, l, r);
    if (r > mid) ans += query(u << 1 | 1, l, r);
    return ans;
}
inline void solve() {
	LL n, k, q; cin >> n >> k >> q;
    vector<LL> a(n + 1), ans(n + 1);
    for (int i = 1; i <= n; i ++ ) cin >> a[i], a[i] -= i;
    map<LL, int> window, cnt;
    for (int i = 1; i <= n; i ++ ) {
        if (cnt.count(window[a[i]])) {
            cnt[window[a[i]]] -= 1;
            if (!cnt[window[a[i]]]) cnt.erase(window[a[i]]);
        }
        window[a[i]] += 1;
        cnt[window[a[i]]] += 1;
        if (i < k) continue;
        ans[i - k + 1] = cnt.rbegin()->first;
        cnt[window[a[i - k + 1]]] -= 1;
        if (!cnt[window[a[i - k + 1]]]) cnt.erase(window[a[i - k + 1]]);
        window[a[i - k + 1]] -= 1;
        if (window[a[i - k + 1]]) cnt[window[a[i - k + 1]]] += 1;
    }
    build(1, 1, n - k + 1);
	vector<vector<array<int, 2>>> st(n - k + 2);
    for (int i = 1; i <= q; i ++ ) {
        int l, r; cin >> l >> r;
        st[l].push_back({r, i});
    }
    vector<LL> stk, res(q + 1);
    for (int i = n - k + 1; i; i -- ) {
        while (stk.size() && ans[stk.back()] <= ans[i]) stk.pop_back();
        int ed = stk.size() ? stk.back() - 1 : n + k - 1;
        update(1, i, ed, ans[i]);
        stk.push_back(i);
        for (auto [r, id] : st[i]) {
            LL len = r - i - k + 2;
            res[id] = k * len - query(1, i, i + len - 1);
        }
    }
    for (int i = 1; i <= q; i ++ ) cout << res[i] << endl;
	return;
}

查看全文

http://www.kler.cn/news/294222.html