Educational Codeforces Round 155 (Rated for Div. 2)

A. Rigged!

解题思路:

若存在\(s[i] >= s[1]\)并且\(e[i] >= e[i]\),那么答案为\(-1\).

否则，答案为\(s[1]\).

代码:

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 1e6 + 10;
const int M = 2 * M;
typedef pair<int, int> pii;
#define fi first
#define se second
int n, m, k;

void solve()
{
    scanf("%d", &n);
    vector<int> s(n + 1), e(n + 1);
    bool sus = true;
    bool gs = false;
    bool ge = false;
    for (int i = 1; i <= n; i++)
    {
        scanf("%d %d", &s[i], &e[i]);
        if (i > 1)
        {
            if (s[i] >= s[1] && e[i] >= e[1])
            {
                sus = false;
            }
        }
    }
    if (!sus)
    {
        printf("-1\n");
    }
    else
    {
        printf("%d\n", s[1]);
    }
}

int main()
{
    int t = 1;
    scanf("%d", &t);
    while (t--)
    {
        solve();
    }
    return 0;
}

B .Chips on the Board

解题思路:

要么每行选最小，要么每列选最小。

代码:

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 1e6 + 10;
const int M = 2 * M;
typedef pair<int, int> pii;
#define fi first
#define se second
int n, m, k;

void solve()
{
    scanf("%d", &n);
    vector<int> a(n + 1), b(n + 1);
    int mina = 1e9 + 1;
    int minb = 1e9 + 1;
    for (int i = 1; i <= n; i++)
    {
        scanf("%d", &a[i]);
        mina = min(mina, a[i]);
    }
    for (int i = 1; i <= n; i++)
    {
        scanf("%d", &b[i]);
        minb = min(minb, b[i]);
    }
    ll ans = 0;
    for (int i = 1; i <= n; i++)
    {
        ans += b[i] + mina;
    }
    ll res = 0;
    for (int i = 1; i <= n; i++)
    {
        res += a[i] + minb;
    }
    ans = min(ans, res);
    printf("%lld\n", ans);
}

int main()
{
    int t = 1;
    scanf("%d", &t);
    while (t--)
    {
        solve();
    }
    return 0;
}

C. Make it Alternating

解题思路:

找到有多少个连续段\(res\).

每个段中有\(cnt_1,cnt_2,...,cnt_k\)个数。

我们从每个段中选择一个留下来的数\(cnt_1 * cnt_2* ...*cnt_k\),第\(i\)段有\(cnt_i\)中选法。

我们要删掉\(num = \sum_\limits{i = 1}^k cnt_i - res\)个数，每个段只留一个。

将这\(num\)个数进行排列\(num!\)

\(ans = (\prod\limits_{i = 1}^kcnt_i * num!) \%mod\)。

代码:

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 1e6 + 10;
const int M = 2 * M;
const int mod = 998244353;
typedef pair<int, int> pii;
#define fi first
#define se second
int n, m, k;
ll f[N];

void solve()
{
    string s;
    cin >> s;
    n = s.size();
    s = ' ' + s;
    ll cnt = 0;
    ll ans = 1;
    ll res = 0;
    for (int i = 2; i <= n; i++)
    {
        if (s[i] == s[i - 1])
        {
            cnt++;
        }
        else
        {
            if (cnt)
            {
                ans = (ans * (cnt + 1)) % mod;
            }
            res += cnt;
            cnt = 0;
        }
    }
    if (cnt)
    {
        ans = (ans * (cnt + 1)) % mod;
        res += cnt;
        cnt = 0;
    }
    ans = (ans * f[res]) % mod;
    printf("%lld %lld\n", res, ans);
}

int main()
{
    int t = 1;
    f[0] = 1;
    f[1] = 1;
    for (int i = 1; i <= N - 5; i++)
    {
        f[i] = (f[i - 1] * i) % mod;
    }
    scanf("%d", &t);
    while (t--)
    {
        solve();
    }
    return 0;
}

D .Sum of XOR Functions

解题思路:

\[\begin{align*} s_k &= \bigoplus_{i=1}^ka_i \\ f(l,r) &= \bigoplus_{i=l}^r a_i \\ &= s_r \oplus s_{l-1} \end{align*} \]

\[\begin{align*} ans &= \sum_{l= 1}^n\sum_{r=l}^n f(l,r)\cdot(r - l + 1) \\ &= \sum_{l= 1}^n\sum_{r=l}^n f(l,r)\cdot r- f(l,r)\cdot (l - 1)\\ &= \sum_{l= 0}^n\sum_{r=l}^n (\sum_{i = 1} ^ {32} 2^{i} * ((s_r \& 2^i) \oplus (s_l \&2^i))*(r - l))\\ \end{align*} \]

那么对于每一个\(s_i\)来说，假设第\(j\)位为\(1\),他的左侧有\(k\)个数的第\(j\)位为\(0\)。

那么但对于这个数的这一位的和左边比对的的贡献为

\[\begin{align*} res &=2^i [(r-l_1) + (r - l_2) + ... + (r - l _k)]\\ &=2^i[kr - \sum_\limits{i = 1}^kl_i] \end{align*} \]

所以，我们在遍历的时候，将所有的\(l_i\)累加，并计算\(k\)即可。

代码:

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 1e6 + 10;
const int M = 2 * M;
const int mod = 998244353;
typedef pair<int, int> pii;
#define fi first
#define se second
int n, m, k;

void solve()
{
    scanf("%d", &n);
    vector<ll> a(n + 1);
    for (int i = 1; i <= n; i++)
    {
        scanf("%lld", &a[i]);
        a[i] ^= a[i - 1];
    }
    vector<vector<ll>> f(40, vector<ll>(4));
    vector<vector<ll>> cnt(40, vector<ll>(4));
    ll ans = 0;
    for (int i = 0; i <= n; i++)
    {
        for (int j = 32; j >= 0; j--)
        {
            if (a[i] >> j & 1)
            {
                ans = (ans + (((((cnt[j][0] * (ll)i - f[j][0]) % mod + mod) % mod) * (1ll << j)) % mod)) % mod;
                f[j][1] = (f[j][1] + i) % mod;
                cnt[j][1] = (cnt[j][1] + 1) % mod;
            }
            else
            {
                ans = (ans + (((((cnt[j][1] * (ll)i - f[j][1]) % mod + mod) % mod) * (1ll << j)) % mod)) % mod;
                f[j][0] = (f[j][0] + i) % mod;
                cnt[j][0] = (cnt[j][0] + 1) % mod;
            }
        }
    }
    printf("%lld\n", ans);
}

int main()
{
    int t = 1;
    // scanf("%d", &t);
    while (t--)
    {
        solve();
    }
    return 0;
}