Abstract

第一次打 CF 的比赛~~~~

A. Legs

Idea

签到题，没什么好说的。

Code

#include <bits/stdc++.h>
using namespace std;

int main()
{
    int t;
    scanf("%d", &t);
    while (t--)
    {
        int n;
        scanf("%d", &n);
        int cnt = n / 4;
        n %= 4;
        cnt += n / 2;
        printf("%d\n", cnt);
    }
    return 0;
}

B. Scale

Idea

还是签到题，模拟一遍就行了，也没什么好说的。

Code

#include <bits/stdc++.h>
using namespace std;

int main()
{
    int t;
    scanf("%d", &t);
    while (t--)
    {
        int n, m;
        scanf("%d%d", &n, &m);
        string text;
        string ans[2000];
        for (int i = 1; i <= n; i++)
        {
            cin >> text;
            if (m == 1)
            {
                ans[i - 1] = text;
                continue;
            }
            if (i % m != 1)
            {
                continue;
            }

            for (int j = 0; j < text.length(); j += m)
            {
                ans[(i - 1) / m] += text[j];
            }
        }

        for (int i = 0; i <= (n - 1) / m; i++)
        {
            cout << ans[i] << endl;
        }
    }
    return 0;
}

C. Sort

Idea

和排序没什么关系，实际上就是问你对于区间 [l,r] , a 变换几个字符后，它的组成就可以和 b 一样，那么我们只需要给每一个字母都做前缀和，就能知道区间 [l,r] 种 a 和 b 的字符组成情况，然后考虑变换的最小次数就可以了，这个需要模拟得出，具体模拟方法见代码。

Code

#include <bits/stdc++.h>
using namespace std;

int t;
int a[30][300000];
int b[30][300000];
void solve()
{
    int n, m;
    cin >> n >> m;
    string text;
    cin >> text;

    int len = text.length();
    for (int i = 0; i < len; i++)
    {
        for (int j = 0; j < 26; j++)
        {
            a[j][i + 1] = a[j][i];
        }
        a[text[i] - 'a'][i + 1]++;
    }

    cin >> text;

    for (int i = 0; i < len; i++)
    {
        for (int j = 0; j < 26; j++)
        {
            b[j][i + 1] = b[j][i];
        }
        b[text[i] - 'a'][i + 1]++;
    }

    for (int i = 0; i < m; i++)
    {
        int ans = 0;
        int l, r;
        cin >> l >> r;
        int sum = 0;
        for (int i = 0; i < 26; i++)
        {
            int new_sum = sum + (a[i][r] - a[i][l - 1]) - (b[i][r] - b[i][l - 1]);
            // 如此计算变换的最小次数
            if (new_sum > 0 && sum <= 0)
            {
                ans += new_sum;
            }
            else if (new_sum < 0 && sum >= 0)
            {
                ans -= new_sum;
            }
            else if (sum <= 0 && new_sum < sum)
            {
                ans += sum - new_sum;
            }
            else if (sum >= 0 && new_sum > sum)
            {
                ans += -sum + new_sum;
            }

            sum = new_sum;
        }
        cout << ans << endl;
    }

    return;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> t;
    while (t--)
    {
        solve();
    }
    return 0;
}

D. Fun

Idea

直接枚举 a,b,c 当然会超时了，实际上，我们可以只枚举 b、c ，然后根据 b、c 的取值判断 a 的范围，这里需要做一些公式推导。为了枚举出的保证情况不重复，我们可以规定 a > b > c,然后再考虑 a、b、c 中有数字相等的情况即可。

Code

#include <bits/stdc++.h>
using namespace std;
#define int long long
signed main()
{
    int t;
    scanf("%lld", &t);
    while (t--)
    {
        int n, x;
        scanf("%lld%lld", &n, &x);
        bool ok = 1;
        int cnt = 0;
        for (int b = 1; 3 * b + 3 <= x; b++)
        {
            for (int c = b + 1; ok; c++)
            {
                int a = x - b - c;
                a = min(a, (n - b * c) / (b + c));
                if (a <= c)
                {
                    break;
                }
                int sum = a - c;
                cnt += 6 * sum;
            }
        }
        int num = pow(n / 3, 0.5);
        cnt += min(x / 3, num);
        for (int b = 1;; b++)
        {
            int a = min((n - b * b) / 2 / b, x - 2 * b);
            if (a <= 0)
            {
                break;
            }
            if (a < b)
            {
                cnt += 3 * (a);
            }
            else
            {
                cnt += 3 * (a - 1);
            }
        }
        cout << cnt << endl;
    }
    return 0;
}