Codeforces Round 895 (Div. 3)-蒲公英云

Codeforces Round 895 (Div. 3)

https://codeforces.com/contest/1872

B. The Corridor or There and Back Again

如果还有s秒出发开关，那么就会最多走(s - 1) / 2个房间，在所有可以到的房间个数中选择最小的那个则为最大。首先我们可以发现，陷阱之间是独立的，只有我们到达陷阱之后，陷阱才会启动，而且每个陷阱的触发时间决定了我们应该什么时候回到这个位置，所以我们可以算出来每个陷阱最远可以到达哪里，然后再选择最近的那个点，因为不能跑更远。

#include<bits/stdc++.h>
using namespace std;
int t, n, d, s, ans;
int main()
{
    cin >> t;
    while(t --)
    {
        ans = 2e5 + 10; 
        cin >> n;
        for(int i = 1; i <= n; i ++)
        {
            cin >> d >> s;
            ans = min(ans, d + (s - 1) / 2);
        }
        cout << ans << '\n';
    }
    return 0;
}

C. Non-coprime Split

可以分为奇数和偶数两种情况讨论，应为如果是偶数就一定可以被2整数，如果是奇数就观察是否是素数，如果不是素数则可以使用辗转相减法求gcd(a,b)=gcd(b,a−b)

eg.gcd(12, 3) = gcd(3, 12 - 3)

#include<bits/stdc++.h>
using namespace std;
int t;
void solve()
{
    int l, r;
    cin >> l >> r;
    for(int i = r; i >= l; i --)
    {
        if(i % 2 == 0 && i > 2)
        {
            cout << i - 2 << ' ' << 2 << '\n';
            return;
        }
        else if(i % 2 != 0 && i > 3)
        {
            for(int j = 3; j <= i / j; j ++)
            {
                if(i % j == 0)
                {
                    cout << j << ' ' << i - j << '\n';
                    return;
                }
            }
        }
    }
    cout << -1 << '\n';
    return;
}
int main()
{
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    cin >> t;
    while(t --)
    {
        solve();
    }
    return 0;
}

D. Plus Minus Permutation

要求得最大值需要减数最大，被减数最小，对于下方结论3而言，同是x, y的倍数会使两个数相抵消，加之后会被减去。

利用等差数列公式算出每部分的和再相减即可

#include<bits/stdc++.h>
using namespace std;
long long gcd(long long a, long long b)
{
    return b == 0 ? a : gcd(b, a % b);
}
long long lcm(long long a, long long b)
{
    return a * b / gcd(a, b);
}
long long f(long long a, long long b, long long cnt)
{
    return (a + b) * cnt / 2;
}
void solve()
{
    long long n, x, y;
    cin >> n >> x >> y;
    long long cnt1 = n / x;
    long long cnt2 = n / y;
    long long cnt3 = n / lcm(x, y);
    cnt1 -= cnt3;
    cnt2 -= cnt3;
    cout << f(n,n - cnt1 + 1, cnt1) - f(1, cnt2, cnt2) << '\n';
}
int main()
{
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    long long t;
    cin >> t;
    while(t --)
    {
        solve();
    }
    return 0;
}

E. Data Structures Fan

使用异或和进行优化

#include<bits/stdc++.h>
using namespace std;
int main()
{
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int t;
    cin >> t;
    while(t --)
    {
        int n, q, a[100000], su[100000];
        char s[100000];
        cin >> n;
        for(int i = 1; i <= n; i ++)cin >> a[i]; 
        cin >> s + 1;
        for(int i = 1; i <= n; i ++)
        {
            su[i] = su[i - 1] ^ a[i];
        }
        int sum1 = 0, sum0 = 0;
        for(int i = 1; i <= n; i ++)
        {
            if(s[i] == '1')sum1 ^= a[i];
            if(s[i] == '0')sum0 ^= a[i];
        }
        cin >> q;
        while(q --)
        {
            int tp;
            cin >> tp;
            if(tp == 1)
            {
                int l, r;
                cin >> l >> r;
                sum1 ^= (su[r] ^ su[l - 1]);
                sum0 ^= (su[r] ^ su[l - 1]);
            }
            else if(tp == 2)
            {
                int x;
                cin >> x;
                if(x == 0)cout << sum0 << ' ';
                else cout << sum1 << ' ';
            }
        }
        cout << '\n';
    }
    return 0;
}