526互联

Codeforces Round 895 (Div. 3)

发布时间 2023-09-12 20:31:32作者: value0

Codeforces Round 895 (Div. 3)

A. Two Vessels

解题思路:

\(d = \lceil {\frac {abs(a - b)} 2}\rceil\)

\(ans = \lceil {\frac d c}\rceil\)

代码:

#include <bits/stdc++.h>
using namespace std;
const int N = 2e6 + 10;
int n, m;

void solve()
{
    int a, b, c;
    scanf("%d %d %d", &a, &b, &c);
    int d = abs(a - b);
    int ans = (d + 1) / 2;
    ans = (ans + c - 1) / c;
    printf("%d\n", ans);
}

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

B. The Corridor or There and Back Again

解题思路:

我们要在夹子开夹之前回到安全路径内。

对于每一个陷阱，我们起码能走到\(d_i\)。我们要在接下来\(s_i - 1\)秒内回到\(d_i\).

\(ans = min(d_i + \lfloor {\frac {s_i - 1} 2}\rfloor)\)

代码:

#include <bits/stdc++.h>
using namespace std;
const int N = 2e6 + 10;
int n, m;

void solve()
{
    scanf("%d", &n);
    vector<int> s(n + 1), d(n + 1);
    int res = 1e9;
    for (int i = 1; i <= n; i++)
    {
        scanf("%d %d", &d[i], &s[i]);
        res = min(res, d[i] + (s[i] - 1) / 2);
    }
    printf("%d\n", res);
}

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

C. Non-coprime Split

解题思路:

不互质意味着a和b之间存在相同的质因子。

如果\(l\)为偶数，那么\(a == b == [\frac l 2]\)即可。

如果\(l\)为奇数，那么\(l + 1\)必定是偶数。如果\(l + 1 <= r\),与上同理即可。

至于\(1~2~3\)之类的特殊情况特判即可。

代码:

#include <bits/stdc++.h>
using namespace std;
const int N = 2e6 + 10;
int n, m;

void solve()
{
    int l, r;
    scanf("%d %d", &l, &r);
    if (l == 1)
    {
        if (r > l)
        {
            if (r <= 3)
            {
                printf("-1\n");
                return;
            }
            else
            {
                printf("2 2\n");
                return;
            }
        }
        else
        {
            printf("-1\n");
            return;
        }
    }
    if (l == 2)
    {
        if (r > l)
        {
            if (r <= 3)
            {
                printf("-1\n");
                return;
            }
            else
            {
                printf("2 2\n");
                return;
            }
        }
        else
        {
            printf("-1\n");
            return;
        }
    }
    if (l & 1)
    {
        int ans = 0;
        if (r > l)
        {
            ans = (l + 1) / 2;
            printf("%d %d\n", ans, ans);
            return;
        }
        else
        {
            int t = l;
            int a, b;
            bool f = true;
            for (int i = 2; i <= t / i; i++)
            {
                if (t % i == 0)
                {
                    f = false;
                    a = i;
                    b = t / i;
                    break;
                }
            }
            if (f)
            {
                printf("-1\n");
                return;
            }
            b = a * (b - 1);
            printf("%d %d\n", a, b);
            return;
        }
    }
    else
    {
        int res = l / 2;
        printf("%d %d\n", res, res);
    }
}

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

D. Plus Minus Permutation

解题思路:

要结果最大，就要我们让加的数都尽量大，减去的数都尽量小。

能被\(lcm(x,y)\)整除的位置放什么数都无所谓，因为会被加减抵消掉。

对于能被\(x\)整除但不被\(lcm(x,y)\)整除的\(i\),我们对其从大到小赋值。

对于能被\(y\)整除但不被\(lcm(x,y)\)整除的\(i\),我们对其从小到大赋值。

其余位置剩余数随便放即可。

所以，答案根据以上方法得到等差数列，高斯公式求和即可。

代码：

#include <bits/stdc++.h>
using namespace std;
const int N = 2e6 + 10;
using ll = long long;
ll n, m;

ll gcd(ll a, ll b)
{
    return b ? gcd(b, a % b) : a;
}

ll lcm(ll a, ll b)
{
    return a * b / gcd(a, b);
}

void solve()
{
    ll x, y;
    scanf("%lld %lld %lld", &n, &x, &y);
    int l = 1;
    int r = n;
    ll ans = 0;
    ll c1 = n / x;
    ll c2 = n / y;
    ll res = lcm(x, y);
    ll c3 = n / res;
    c1 -= c3;
    c2 -= c3;
    ans += (r - c1 + 1 + r) * c1 / 2;
    ans -= (l + l + c2 - 1) * c2 / 2;
    printf("%lld\n", ans);
}

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

E. Data Structures Fan

解题思路:

  1. 前缀和

    开一个前缀异或和数组\(s\)，同时用一个数记录0和1随便一个数的异或和\(res\)。

    此时，若\(res\)是\(1\)的异或和，那么\(res \oplus s_n\)就是\(0\)的异或和。

    将区间\([l,r]\)翻转，我们可进行\(ans = ans \oplus (s_r\oplus s_{l-1})\)操作：

    相当于该区间的\(1\)异或抵消了，如果本题真的是1和0的异或和那么肯定是不行的。但本题异或的都是a[i],也就是说这次异或是真的相当于将区间中的1异或，同时也将0变成1后的值也异或了。

    这部分将真正的01区间异或和非01区间异或手推一下就能理解了。

前缀和代码:

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
using ll = long long;
int n;
void solve()
{
    scanf("%d", &n);
    vector<int> a(n + 1), b(n + 1);
    for (int i = 1; i <= n; i++)
    {
        scanf("%d", &a[i]);
    }
    string s;
    cin >> s;
    s = ' ' + s;
    int ans = 0;
    for (int i = 1; i <= n; i++)
    {
        if (s[i] == '1')
        {
            ans ^= a[i];
        }
        b[i] = b[i - 1] ^ a[i];
    }
    int m;
    scanf("%d", &m);
    while (m--)
    {
        int t;
        scanf("%d", &t);
        if (t == 1)
        {
            int l, r;
            scanf("%d %d", &l, &r);
            ans ^= b[r] ^ b[l - 1];
        }
        else
        {
            int x;
            scanf("%d", &x);
            if (x == 0)
            {
                printf("%d ", b[n] ^ ans);
            }
            else
            {
                printf("%d ", ans);
            }
        }
    }
    printf("\n");
}

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

  1. 线段树

    真正的传统老方。

    每个结点维护一个\(c[2]\)。

    其中，c[0]表示当前区间0的异或和，c[1]表示当前区间1的异或和。

    修改时找到对应区间，将c[0]和c[1]互换即可。

线段树代码:

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
using ll = long long;
int n;
string s;
struct Node
{
    int l, r;
    int laz;
    int c[2];
} tr[N << 2];
int a[N];

void pushup(int u)
{
    tr[u].c[0] = tr[u << 1].c[0] ^ tr[u << 1 | 1].c[0];
    tr[u].c[1] = tr[u << 1].c[1] ^ tr[u << 1 | 1].c[1];
}

void pushdown(int u)
{
    if (tr[u].laz)
    {
        tr[u << 1].laz ^= 1;
        swap(tr[u << 1].c[0], tr[u << 1].c[1]);
        tr[u << 1 | 1].laz ^= 1;
        swap(tr[u << 1 | 1].c[0], tr[u << 1 | 1].c[1]);
    }
    tr[u].laz = 0;
}

void build(int u, int l, int r)
{
    tr[u] = {l, r, 0};
    if (l == r)
    {
        if (s[l] == '1')
        {
            tr[u].c[1] = a[l];
            tr[u].c[0] = 0;
        }
        else
        {
            // if (l == 4)
            // {
            //     cout << a[l] << endl;
            // }
            tr[u].c[0] = a[l];
            tr[u].c[1] = 0;
        }
        return;
    }
    int mid = l + r >> 1;
    build(u << 1, l, mid);
    build(u << 1 | 1, mid + 1, r);
    pushup(u);
}

void modify(int u, int l, int r)
{
    if (tr[u].l >= l && tr[u].r <= r)
    {
        tr[u].laz ^= 1;
        swap(tr[u].c[0], tr[u].c[1]);
        return;
    }
    pushdown(u);
    int mid = tr[u].l + tr[u].r >> 1;
    if (l <= mid)
    {
        modify(u << 1, l, r);
    }
    if (r > mid)
    {
        modify(u << 1 | 1, l, r);
    }
    pushup(u);
}

int query(int u, int l, int r, int id)
{
    if (tr[u].l >= l && tr[u].r <= r)
    {
        cout << tr[u].c[id] << endl;
        return tr[u].c[id];
    }
    pushdown(u);
    int mid = tr[u].l + tr[u].r >> 1;
    int ans = 0;
    if (l <= mid)
    {
        ans ^= query(u << 1, l, r, id);
    }
    if (r > mid)
    {
        ans ^= query(u << 1 | 1, l, r, id);
    }
    return ans;
}

void solve()
{
    scanf("%d", &n);
    for (int i = 1; i <= n; i++)
    {
        scanf("%d", &a[i]);
    }
    cin >> s;
    s = ' ' + s;
    // cout << s << endl;
    build(1, 1, n);
    int m;
    cin >> m;
    // cout << query(1, 2, 4, 1) << endl;
    // cout << query(1, 4, 4, 0) << endl;
    while (m--)
    {
        int t;
        scanf("%d", &t);
        if (t == 1)
        {
            int l, r;
            scanf("%d %d", &l, &r);
            modify(1, l, r);
        }
        else
        {
            int x;
            scanf("%d", &x);
            if (x == 1)
            {
                printf("%d ", tr[1].c[1]);
            }
            else
            {
                printf("%d ", tr[1].c[0]);
            }
        }
    }
    printf("\n");
}

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

F. Selling a Menagerie

解题思路:

我们建边从\(i\)连向\(a_i\),不难发现图中会出现环。

对于不在环中的结点，我们按拓扑序从前往后排列即为最优。

对于在环中的结点，如果我们去一个结点作为破环成链的尾结点，那么除了尾结点的只有正常收益，其余结点都有两倍收益。

因此，本题的关键就是找出环中收益最小的点作为破环成链后的尾结点。

  1. 我们通过拓扑排序可将不在环上的点先处理出来。
  2. 对于剩余的环，我们可通过dfs遍历找到值最小的点。

代码:

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
using ll = long long;
int n;
int minc;
int id;

void solve()
{
    scanf("%d", &n);
    vector<int> a(n + 1), c(n + 1), deg(n + 1);
    for (int i = 1; i <= n; i++)
    {
        scanf("%d", &a[i]);
        deg[a[i]]++;
    }
    for (int i = 1; i <= n; i++)
    {
        scanf("%d", &c[i]);
    }
    vector<bool> st(n + 1);
    queue<int> q;
    vector<int> ans;
    for (int i = 1; i <= n; i++)
    {
        if (!deg[i])
        {
            q.push(i);
        }
    }
    vector<int> p(n + 1);
    while (q.size())
    {
        auto t = q.front();
        q.pop();
        st[t] = true;
        ans.push_back(t);
        if (--deg[a[t]] == 0)
        {
            q.push(a[t]);
        }
    }
    auto dfs = [&](auto self, int u) -> void
    {
        if (st[u])
        {
            return;
        }
        st[u] = true;
        if (c[u] < minc)
        {
            minc = c[u];
            id = u;
        }
        self(self, a[u]);
    };
    for (int i = 1; i <= n; i++)
    {
        if (!st[i])
        {

            minc = c[i];
            id = i;
            dfs(dfs, i);
            int x = a[id];
            do
            {
                ans.push_back(x);
                x = a[x];
            } while (x != a[id]);
        }
        // cout << i << endl;
    }
    for (auto c : ans)
    {
        cout << c << ' ';
    }
    cout << endl;
}

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

G. Replace With Product

解题思路:

按情况分治。

设

\[res = \prod_{a_i\ne1}a_i \]

  1. 如果\(res\)充分大，那么\(res\)每乘以一个非1数都会是当前最优策略。那么我们去掉前后缀的1，取两个非1数的边界即可。

    时间复杂度为\(O(n)\)。

    如果中途我们发现\(res >= 1e18\),那么接下来我们哪怕乘以最小的非1数2，也一定比将剩下所有数加起来的贡献高。

    因为，\(n <= 2e5\),\(a_i <= 1e9\)。

  2. 如果res不够大，我们可以暴力判断求解。如果我们根据以上的\(1e18\)为边界，此时我们需要暴力的非1数最多为60个左右。时间复杂度为\(O(n^2)\).完全可接受。

代码实现:

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using i128 = __int128;
int n, m;

void solve()
{
    scanf("%d", &n);
    vector<int> a(n + 1);
    i128 res = 1;
    ll s = 0;
    bool g = false;
    for (int i = 1; i <= n; i++)
    {
        scanf("%d", &a[i]);
        s += a[i];
        res *= a[i];
        if (res >= 1e18)
        {
            g = true;
        }
    }
    if (g)
    {
        int l = 1;
        int r = n;
        while (a[l] == 1)
        {
            l++;
        }
        while (a[r] == 1)
        {
            r--;
        }
        printf("%d %d\n", l, r);
    }
    else
    {
        ll ans = 0;
        int l = 1;
        int r = 1;
        for (int i = 1; i <= n; i++)
        {
            ll res = 1;
            ll s = 0;
            if (a[i] != 1)
            {
                for (int j = i; j <= n; j++)
                {
                    res *= a[j];
                    s += a[j];
                    ll t = res - s;
                    if (t > ans)
                    {
                        ans = t;
                        l = i;
                        r = j;
                    }
                }
            }
        }
        printf("%d %d\n", l, r);
    }
}

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