Educational Codeforces Round 159 (Rated for Div. 2)

A - Binary Imbalance

解题思路:

有一对$(0,1)$，那么$0$就能无限增长。

代码:

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 2e5 + 10;
typedef pair<ll, ll> pii;
const ll mod = 998244353;
ll n, m;
ll a[N];

void solve()
{
    int n;
    cin >> n;
    string s;
    cin >> s;
    int a = 0;
    int b = 0;
    for (int i = 0; i < n - 1; i++)
    {
        if (s[i] != s[i + 1])
        {
            puts("YES");
            return;
        }
    }
    for (auto c : s)
    {
        if (c == '1')
        {
            a++;
        }
        else
        {
            b++;
        }
    }
    if (a >= b)
    {
        puts("NO");
    }
    else
    {
        puts("YES");
    }
}

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

    return 0;
}

B - Getting Points

解题思路:

全部留到最后几天做。

代码:

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 2e5 + 10;
typedef pair<ll, ll> pii;
const ll mod = 998244353;
ll n, m;
ll a[N];

void solve()
{
    ll n, p, l, t;
    cin >> n >> p >> l >> t;
    ll a = 1 + (n - 1) / 7;
    ll ans = 0;
    ll b = a / 2;
    ll base = (l + 2 * t);
    ll res = 0;
    ll cnt = 0;
    if (a & 1)
    {
        res = b * (base) + t + l;
        cnt = b + 1;
    }
    else
    {
        res = b * base;
        cnt = b;
    }
    // cout << res << endl;
    if (res >= p)
    {
        ans = ((p + base - 1) / base);
    }
    else
    {
        ans = cnt + ((p - res) + l - 1) / l;
    }
    cout << n - ans << endl;
}

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

    return 0;
}

C - Insert and Equalize

解题思路:

对$a$排个序，设$b[i] = a[i + 1] - a[i]$，我们得到数组$b[1\sim (n - 1)]$。

$x = gcd(b)$，此时根据此$x$计算数组$a$中的最小运算次数一定数最少的。

如果我们可以加入$a[n + 1] = a[n] - x$,那么最小运算次数$+ 1$；同理，若$a[n + 1] = a[n] - 2 * x$，那么$ + 2$。

如果直到$a[n + 1] = a[n] - (n - 1) * x$都已经存在，那么$a[n + 1] = a[n] + x$。

因为$a[n + 1] = a[n] + x$,最小运算次数$ + n$，且一定合法。

代码:

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e6 + 10;
typedef pair<ll, ll> pii;

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

void solve()
{
    int n;
    cin >> n;
    vector<int> a(n + 1);
    set<int> s;
    for (int i = 1; i <= n; i++)
    {
        cin >> a[i];
        s.insert(a[i]);
    }
    sort(a.begin() + 1, a.end());
    int g = 0;
    for (int i = 2; i <= n; i++)
    {
        g = gcd(g, a[i] - a[i - 1]);
    }
    // cout << g << endl;
    if (g == 0)
    {
        puts("1");
        return;
    }
    ll t = 0;
    bool f = false;
    for (int i = 1; i < n; i++)
    {
        if (!s.count(a[n] - i * g))
        {
            f = true;
            t = a[n] - i * g;
            break;
        }
    }
    ll ans = 0;
    for (int i = 1; i <= n; i++)
    {
        ans += (a[n] - a[i]) / g;
    }
    if (f)
    {
        ans += (a[n] - t) / g;
    }
    else
    {
        ans += n;
    }
    cout << ans << endl;
}

int main()
{
    int t = 1;
    cin >> t;
    while (t--)
    {

        solve();
    }

    return 0;
}

D - Robot Queries

解题思路:

对于每一次查询，我们分三段判断$(1,l -1),(l ,r),(r+1,n)$。

我们记录每个出现过的坐标是在第几步出现的$pos[{x,y}] = i$。

对于$(1,l-1)和(r + 1,n)$我们可直接二分判断是否存在$(x,y)$。

对于$(l,r)$，由于题目要求，我们要进行一些变换。

设$(l-1)步到达的坐标为(a_1,b_1)，第r步到达的坐标为(a_2,b_2)$。

一个区间段中无论正序倒序走，$x$轴和$y$轴最后的偏移量都是不变的。

目标位置到第$(l - 1)$步位置的偏移量为$(x - a_1,y - b_1)$。

第$r$步道减去这些偏移量为$(a_2 - (x - a_1),b_2 - (y - b_1))$

$x_1 = a_2 - (x - a_1),y_1 = b_2 - (y - b_1)$。

$(x_1,y_1)$，就是转换后我们正序走该走到的位置。

我们二分判断该位置是否存在即可。

代码:

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

void solve()
{
    int n, m;
    cin >> n >> m;
    string s;
    cin >> s;
    map<pii, vector<int>> v;
    s = ' ' + s;
    v[{0, 0}].push_back(0);
    map<int, pii> pos;
    int x = 0;
    int y = 0;
    for (int i = 1; i <= n; i++)
    {

        if (s[i] == 'U')
        {
            y++;
        }
        else if (s[i] == 'D')
        {
            y--;
        }
        else if (s[i] == 'L')
        {
            x--;
        }
        else
        {
            x++;
        }
        v[{x, y}].push_back(i);
        pos[i] = {x, y};
        // cout << i << ' ' << x << ' ' << y << endl;
    }
    for (int i = 1; i <= m; i++)
    {
        int x, y, l, r;
        cin >> x >> y >> l >> r;
        if (v[{x, y}].size())
        {
            auto idx = *(v[{x, y}].begin());
            if (idx < l)
            {
                puts("YES");
                continue;
            }
            idx = *v[{x, y}].rbegin();
            if (idx >= r)
            {
                puts("YES");
                continue;
            }
        }
        int a1 = pos[l - 1].fi;
        int b1 = pos[l - 1].se;
        int a2 = pos[r].fi;
        int b2 = pos[r].se;
        int x1 = a2 + a1 - x;
        int y1 = b2 + b1 - y;
        // cout << a1 << b1 << endl;
        // cout << a2 << ' ' << b2 << endl;
        // cout << x1 << ' ' << y1 << endl;
        if (v[{x1, y1}].size())
        {
            auto it = lower_bound(v[{x1, y1}].begin(), v[{x1, y1}].end(), l);
            if (it != v[{x1, y1}].end())
            {
                int idx = *it;
                if (idx >= l && idx <= r)
                {
                    puts("YES");
                    continue;
                }
            }
        }
        puts("NO");
    }
}

int main()
{
    int t = 1;
    // cin >> t;
    while (t--)
    {

        solve();
    }

    return 0;
}

E - Collapsing Strings

解题思路:

$s1 = aabba,s2 = abbcc$,我们发现剩下$aacc$。

观察得到规律:$C(a,b) = len(s1) + len(s2) - 2 *len(a_{pre} == b_{suf})$。就是减去二者前后缀公共部分。

先将所有字符长度累加起来。

$trie$树插入所有字符串，记录每个前缀出现的次数。

将每个字符逆序后一一查询，减去对应前后缀相同长度的代价。

代码:

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e6 + 10;
typedef pair<ll, ll> pii;
#define fi first
#define se second
int tr[N][26];
ll cnt[N];
int idx;

void insert(string s)
{
    int p = 0;
    for (auto c : s)
    {
        int u = c - 'a';
        if (!tr[p][u])
        {
            tr[p][u] = ++idx;
        }
        p = tr[p][u];
        cnt[p]++;
    }
}

ll query(string s)
{
    ll res = 0;
    int p = 0;
    for (auto c : s)
    {
        int u = c - 'a';
        if (!tr[p][u])
        {
            return res;
        }
        p = tr[p][u];
        res += cnt[p] * 2;
    }
    return res;
}

void solve()
{
    int n;
    cin >> n;
    vector<string> v;
    ll ans = 0;
    for (int i = 1; i <= n; i++)
    {
        string s;
        cin >> s;
        v.push_back(s);
        ans += 2 * (ll)s.size() * n;
        insert(s);
    }
    for (auto &s : v)
    {
        reverse(s.begin(), s.end());
        ans -= query(s);
    }
    cout << ans << endl;
}

int main()
{
    int t = 1;
    // cin >> t;
    while (t--)
    {

        solve();
    }

    return 0;
}