526互联

CodeTON Round 7 (Div. 1 + Div. 2, Rated, Prizes!)

发布时间 2023-11-26 16:05:45作者: value0

CodeTON Round 7 (Div. 1 + Div. 2, Rated, Prizes!)

A - Jagged Swaps

解题思路:

若\(a[1] = 1\)，则可以。

代码:

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
typedef pair<int, int> pii;
#define fi first
#define se second
void solve()
{
    ll n;
    cin >> n;
    vector<int> a(n + 1);
    for (int i = 1; i <= n; i++)
    {
        cin >> a[i];
    }
    if (a[1] == 1)
    {
        puts("YES");
    }
    else
    {
        puts("NO");
    }
}

int main()
{
    int t = 1;
    cin >> t;
    while (t--)
    {
        solve();
    }
    return 0;
}

B - AB Flipping

解题思路:

从后往前遍历，累计\(B\)的数目\(cnt\)，遇到\(A\)了就累加到答案上。同时，\(B\)的累计数目重置为\(min(cnt,1)\)。继续遍历。

代码:

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
typedef pair<int, int> pii;
#define fi first
#define se second
void solve()
{
    int n;
    cin >> n;
    string s;
    cin >> s;
    int cnt = 0;
    int ans = 0;
    for (int i = n - 1; i >= 0; i--)
    {
        if (s[i] == 'B')
        {
            cnt++;
        }
        else
        {
            ans += cnt;
            cnt = min(cnt, 1);
        }
    }
    cout << ans << endl;
}

int main()
{
    int t = 1;
    cin >> t;
    while (t--)
    {
        solve();
    }
    return 0;
}

C - Matching Arrays

解题思路:

贪心，尽量让大对大。

首先，将两数列排序。

然后，将\(b[x \sim 1] 和 a[n - (1 \sim x) + 1])\)按照顺序一一比较，若过程中\(b[i] \geq a[n - (x - i)]\),说明无解。否则，二者位置对应放置即可。

最后，将\(b[n \sim (x + 1)] 和 a[(n - x) \sim 1]\)，按照顺序一一比较，若过程中\(b[i] < a[n - (x - i)]\),说明无解。否则，二者位置对应放置即可。

代码:

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
typedef pair<int, int> pii;
#define fi first
#define se second
void solve()
{
    int n, x;
    cin >> n >> x;
    vector<pii> a(n + 1), b(n + 1);
    for (int i = 1; i <= n; i++)
    {
        cin >> a[i].fi;
        a[i].se = i;
    }
    for (int i = 1; i <= n; i++)
    {
        cin >> b[i].fi;
        b[i].se = i;
    }
    sort(a.begin() + 1, a.end());
    sort(b.begin() + 1, b.end());
    vector<int> ans(n + 1);
    for (int i = 1; i <= x; i++)
    {
        if (a[n - i + 1].fi <= b[x - i + 1].fi)
        {
            puts("NO");
            return;
        }
        else
        {
            ans[a[n - i + 1].se] = b[x - i + 1].fi;
        }
    }
    int idx = n;
    for (int i = x + 1; i <= n; i++)
    {
        if (a[n - i + 1].fi > b[idx].fi)
        {
            puts("NO");
            return;
        }
        else
        {
            ans[a[n - i + 1].se] = b[idx].fi;
            idx--;
        }
    }
    puts("YES");
    for (int i = 1; i <= n; i++)
    {
        cout << ans[i] << ' ';
    }
    cout << endl;
}

int main()
{
    int t = 1;
    cin >> t;
    while (t--)
    {
        solve();
    }
    return 0;
}

D - Ones and Twos

解题思路:

首先，对于以\(1\)为端点，\(2\)为中间段的数值段，设其总和为\(s\)，那么这个数值段的子段和一定能表示\(1 \sim s\)的所有数。

举例：

\([1,2,2,2,2]\)总和为\(9\)。\([1,3,5,7,9]\)，分别对应左端点向右扩展，\([2,4,6,8]\)用\(2\)段截取即可。中间有\(1\)同理。

所以，我们可以记录\(1\)的位置，同时更新整段的数值和。

\([2,2,1,2,2,2,1,2]\)。

我们将其划分为端点为\(1\)的子段后会发现，多出一个纯\(2\)段。我们考虑加上纯\(2\)段的情况。

首先，加上纯\(2\)段后，数值和的奇偶性不变。我们设纯\(2\)段的数值和为\(num\)

所以，设目标和\(v\),如果\(v \leq s - num\),说明我们用\(1\)为端点的段就可以得到\(v\)。

否则，说明我们可以尝试加上\(2\)段来进行构造，那么\(v,(s -num)\)的奇偶性要相同，然后就是\(v - (s - num) <= num\)。

实现注意细节：我们在提取纯\(2\)段的时候，纯\(2\)段尽量小。（方便将纯\(2\)段为空的情况进行合并)。

举例：

\([2,2,1,2,2,2,1,2]\)中的纯\(2\)段是\([2]\)而不是\([2,2]\)。

\([1,2]\)中的纯二段为\([]\)而不是\([2]\)。

如果纯二段为\([2]\),这里我们的\(num = 2,res = s - num = 1\)。我们按照上面条件的判断就会发现\(2\)这个数无法构造出来。因为奇偶性不同，而\(2\)本身其实就是答案。

代码:

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
typedef pair<int, int> pii;
#define fi first
#define se second

void solve()
{
    int n, q;
    cin >> n >> q;
    vector<int> a(n + 1);
    ll s = 0;
    set<int> se;
    for (int i = 1; i <= n; i++)
    {
        cin >> a[i];
        s += a[i];
        if (a[i] == 1)
        {
            se.insert(i);
        }
    }
    while (q--)
    {
        int op;
        cin >> op;
        if (op == 1)
        {

            int v;
            cin >> v;
            if (se.empty())
            {
                if (v % 2 == 0)
                {
                    puts("YES");
                }
                else
                {
                    puts("NO");
                }
                continue;
            }
            ll cnt = min(*se.begin() - 1, n - *se.rbegin());
            ll res = s - 2 * cnt;
            if (v <= res || ((v % 2 == res % 2) && (((v - res) / 2) <= cnt)))
            {
                puts("YES");
            }
            else
            {
                puts("NO");
            }
        }
        else
        {
            int idx, val;
            cin >> idx >> val;
            if (a[idx] == 1)
            {
                se.erase(idx);
            }
            if (val == 1)
            {
                se.insert(idx);
            }
            s += val - a[idx];
            a[idx] = val;
        }
    }
}

int main()
{
    int t = 1;
    cin >> t;
    while (t--)
    {
        solve();
    }
    return 0;
}