Visits: 341

Codeforces Round #626 (Div. 1, based on Moscow Open Olympiad in Informatics)

Unusual Competitions

前缀和一下，从前缀和为 $0$ 的位置将序列分成若干段。

对于每一段，如果它是负的，则这一段必须要重排，否则不用。

const int N = 1e6 + 7;
int n, c[2], a[N], ans;
char s[N];

int main() {
    rd(n), rds(s, n);
    for (int i = 1; i <= n; i++)
        if (s[i] == '(') c[0]++;
        else c[1]++;
    if (c[0] != c[1]) return print(-1), 0;
    for (int i = 1, p = 0; i <= n; i++) {
        if (s[i] == '(') a[i] = a[i-1] + 1;
        else a[i] = a[i-1] - 1;
        if (!a[i]) {
            bool ok = 0;
            for (int j = p + 1; j <= i; j++)
                if (a[j] < 0) ok = 1;
            if (ok) ans += i - p;
            p = i;
        }
    }
    print(ans);
    return 0;
}

Present

按位考虑。

对于第 $k$ 位，我们只关心每个数对 $2^{k+1}$ 取模后的值。

对于两个取模后的数，如果要在第 $k$ 位为 $1$，和必须在 $[2^k, 2^{k+1}-1]$ 或 $[2^k + 2^{k+1}, 2^{k+2}-2]$ 中。

排序之后双指针扫一遍即可，时间复杂度 $\mathcal O(n \log n \log w)$。

const int N = 4e5 + 7;
int n, a[N], b[N], ans;

inline bool calc(int L, int R) {
    if (L > R) return 0;
    ll ret = 0;
    for (int i = n, l = 1, r = 1; i; i--) {
        while (l <= n && b[i] + b[l] < L) ++l;
        while (r <= n && b[i] + b[r] <= R) ++r;
        ret += r - l - (l <= i && i < r);
    }
    return (ret >> 1) & 1;
}

inline bool solve(int k) {
    for (int i = 1; i <= n; i++) b[i] = a[i] & ((1 << (k + 1)) - 1);
    sort(b + 1, b + n + 1);
    return calc(1 << k, (1 << (k + 1)) - 1) ^ calc(3 << k, (1 << (k + 2)) - 2);
}

int main() {
    rd(n), rda(a, n);
    for (int i = 0; i < 26; i++) ans |= solve(i) << i;
    print(ans);
    return 0;
}

Instant Noodles

对于右部点 $i$，设 $S(i)$ 表示所有与其相连的左部点的集合。

对于 $i$，若 $|S(i)| = 0$，则可以直接扔掉。

对于 $i,j$，若 $S(i) = S(j)$，则这两个点可以合并为一个，合并后的点的权值为原先两点权值之和。

合并后，所有点的 $S(i)$ 均不为空集且互不相同，此时对所有点的权值求 $\gcd$ 即可。

判断 $S(i) = S(j)$ 时需要 hash 一下。

const int N = 5e5 + 7;
int n, m, B, P;
ll a[N];
vi e[N];

inline int h(vi p) {
    sort(p.begin(), p.end());
    int ret = 0;
    for (int x : p) ret = (1ll * ret * B + x) % P;
    return ret;
}

inline void solve() {
    rd(n), rd(m), rda(a, n);
    for (int i = 1; i <= n; i++) e[i].clear();
    for (int i = 1, x, y; i <= m; i++) rd(x), rd(y), e[y].pb(x);
    map<int, ll> p;
    for (int i = 1; i <= n; i++)
        if (e[i].size()) p[h(e[i])] += a[i];
    ll d = 0;
    for (auto o : p) d = d ? __gcd(d, o.se) : o.se;
    print(d);
}

int main() {
    srand(time(0));
    P = rdm((int)1e8, (int)1e9);
    B = rdm((int)1e7, (int)1e8);
    int T;
    rd(T);
    while (T--) solve();
    return 0;
}

Reality Show

题目太神仙了，先咕咕咕着。

Median Mountain Range

题目太神仙了，先咕咕咕着。

Assigning Fares

题目太神仙了，先咕咕咕着。