题解-Codeforces Round 1050 (Div. 4)

赛时5道，第6道纯模拟有点难绷

题目链接

A

b为偶数则为0， 否则为a。

void solve() {
    int a, b; cin >> a >> b;
    if(b % 2 == 0) cout << 0 << "\n";
    else cout << a << "\n";
}

B

结果一定是n + m，与其他的无关.

void solve() {
    int n, m, x, y; 
    cin >> n >> m >> x >> y;
    
    for(int i = 0; i < n; ++ i) {
        int a; cin >> a;
    }
    for(int i = 0; i < m; ++ i) {
        int a; cin >> a;
    }
    cout << n + m << "\n";
}

C

有点久远了，忘了咋写的，看代码吧

void solve() {
    int n, m; cin >> n >> m;
    vii v(n + 5);
    for(int i = 0; i < n; ++ i) {
        cin >> v[i].first >> v[i].second;
    }

    int ans = 0;
    int pre = 0;
    bool y = false;
    for(int i = 0; i < n; ++ i) {
        if(v[i].first % 2 == v[i].second % 2 && y) {
            ans += v[i].first - pre - 1;
            y = !y;
            pre = v[i].first;
            continue;
        }
        if(v[i].first % 2 == v[i].second % 2 && !y) {
            ans += v[i].first - pre;
            pre = v[i].first;
            continue;
        }
        if(v[i].first % 2 != v[i].second % 2 && y) {
            ans += v[i].first - pre;
            pre = v[i].first;
            continue;
        }
        if(v[i].first % 2 != v[i].second % 2 && !y) {
            ans += v[i].first - pre - 1;
            pre = v[i].first;
            y = !y;
            continue;
        }
    }
    ans += m - pre;
    cout << ans << '\n';
}

D

如果没有奇数的，输出0；否则，先把所有偶数相加，加上最大的奇数，再在剩下的奇数中选一半的最大的数。

void solve() {
    int n; cin >> n;
    vi v(n + 5);
    for(int i = 1; i <= n;++ i) {
        cin >> v[i];
    }
    vi ji;
    vi ou;
    int sum = 0;
    for(int i = 1; i <= n; ++ i) {
        if(v[i] % 2 == 0) {
            ou.push_back(v[i]);
            sum += v[i];
        } else {
            ji.push_back(v[i]);
        }
    }
    if(sz(ji) == 0) {
        cout << 0 << "\n";
    } else {
        sort(all(ji), greater<int>());
        sum += ji[0];
        for(int i = 1; i <= (sz(ji) - 1) / 2; ++ i)
            sum += ji[i];
        cout << sum << "\n";
    }
}

E

双指针计数，加一个特判

void solve() {
    int n, k; cin >> n >> k;
    vi v(n + 5);
    map<int, int> mp;
    for(int i = 0; i < n; ++ i) {
        cin >> v[i];
        mp[v[i]] ++;
    }
    for(auto [x, y]: mp) {
        if(y % k != 0) {
            cout << 0 << "\n";
            return;
        }
    }
    map<int, int> mp1;
    int l = 0, r = 0;
    int ans = 0;
    while(l < n && r < n) {
        mp1[v[r]] ++;
        while(mp1[v[r]] > mp[v[r]] / k) {
            mp1[v[l]] --;
            l ++;
        }
        ans += r - l + 1;
        r ++;
    }
    cout << ans << "\n";
}

F

纯模拟我无话可说。

void solve() {
    int n; cin >> n;
    vvi v(n);
    int len = 0;
    for(int i = 0; i < n; ++ i) {
        int k; cin >> k;
        v[i].resize(k);
        for(int j = 0; j < k; ++ j) {
            cin >> v[i][j];
        }
        len = max(len, k);
    }

    vi ans(len);

    int pos = 0;

    while(pos < len) {
        sort(all(v));
        for(int i = 0; i < sz(v[0]); ++ i) {
            ans[pos ++] = v[0][i];
        }
        vvi b;
        int k = sz(v[0]);
        for(int i = 0; i < sz(v); ++ i) {
            vi c;
            for(int j = k; j < sz(v[i]); ++ j) {
                c.pb(v[i][j]);
            }
            if(sz(c)) {
                b.push_back(c);
            }
        }
        v = b;
    }
    for(auto i : ans) {
        cout << i << " ";
    }
    cout << "\n";
}

G

预处理每个数的约数，再维护前缀gcd

const int N = 2e5 + 5;

vvi d;

void solve() {
    int n; cin >> n;
    vi v(n + 5);
    for(int i = 0; i < n; ++ i) cin >> v[i];

    vi cnt(n + 5);
    int ans = 0, g = 0;

    for(int i = 0; i < n; ++ i) {
        for(auto d: d[v[i]]) {
            cnt[d] ++;
            if(cnt[d] != i + 1) {
                ans = max(ans, cnt[d]);
            }
        }
        if(gcd(v[i], g) != g) {
            ans = max(ans, cnt[g]);
        }
        g = gcd(g, v[i]);
        cout << ans << " \n"[i == n - 1];
    }
}

signed main() {
    ios::sync_with_stdio(false); 
    cin.tie(nullptr);
    cout.tie(nullptr);

    d.assign(N + 1, {});

    for(int i = 1; i <= N; ++ i) {
        for(int j = i; j <= N; j += i) {
            d[j].push_back(i);
        }
    }

    int _ = 1;
    cin >> _;
    while(_ --) solve();
    
    return 0;
}