Codeforces Round #762 (Div. 3)（A~C,E）

• 题目链接
• • • • • A Square String?
        • B Squares and Cubes
        • C Wrong Addition
        • E MEX and Increments
        • 有能力再继续补

补题挖坑

判断拆两半是不是一样，奇数直接NO，偶数从中间分开判断一下

#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;
typedef long long ll;
ll t, n;
int main()
{
    cin >> t;
    while (t--)
    {
        string s;
        cin >> s;
        if (s.size() % 2)
            cout << "NOn";
        else
        {
            bool flag = 0;
            for (int i = 0; i < s.size() / 2; i++)
            {
                if (s[i] != s[i + s.size() / 2])
                {
                    flag = 1;
                    break;
                }
            }
            if (flag)
                cout << "NOn";
            else
                cout << "YESn";
        }
    }
    return 0;
}

判断n以内的平方数和立方数有多少
我开始还在傻不拉几平方根立方根统计
后来想起来set操作数据范围不是很大，直接输出set.size()

#include 
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;
typedef long long ll;
ll t, n;
int main()
{
    cin >> t;
    while (t--)
    {
        cin >> n;
        set x;
        for (ll i = 1;; ++i)
        {
            if (i * i * i <= n)
            {
                x.insert(i * i * i);
            }
            else
            {
                break;
            }
        }
        for (ll i = 1;; ++i)
        {
            if (i * i <= n)
            {
                x.insert(i * i);
            }
            else
            {
                break;
            }
        }

        cout << x.size() << endl;
    }
    return 0;
}

看见这道题差点摆大烂
就纯纯的模拟，但是要注意几点

• 必须以s字符串结尾算整体结尾，不然都算异常输出-1，因为a有可能是长的有可能是短的，如果a没了放0代替
• 注意数据范围long long
• 减法只支持个位数减法和10~18为减数得减法，不然的话算异常
• 最后避免麻烦直接加，但是要使用大数据范围

#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;
typedef long long ll;
ll t;
string a, s;
int main()
{
    cin >> t;
    while (t--)
    {
        cin >> a >> s;
        string b = "";
        bool target = 0;
        for (int i = a.size() - 1, j = s.size() - 1;; i--, j--)
        {
            if (j < 0 && i < 0)
                break;
            else if (j < 0 && i >= 0)
            {
                target = 1;
                break;
            }
            int num;
            if (i >= 0)
                num = a[i] - '0';
            else
                num = 0;
            int ans = s[j] - '0';
            if (ans < num && j > 0)
            {
                ans += 10 * (s[j - 1] - '0');

                if (s[j - 1] != '1')
                    target = 1;
                j--;
            }
            else if (ans < num && j == 0)
            {
                target = 1;
            }
            if (target)
                break;
            b += (ans - num) + '0';
        }
        if (target)
            cout << -1 << endl;
        else
        {
            ll ans = 0;
            for (ll i = 0, j = 1; i < b.size(); i++, j *= 10)
                ans += j * (b[i] - '0');

            cout << ans << endl;
        }
    }
    return 0;
}

这个题给出长度为n且元素小于等于n的序列，所以第一步肯定是要统计，桶排序的感觉
之后要补全没有的数字，比如说

3
0 0 1 3

所得到的桶排序就是

大意就是用左边的多的可以通过操作挪过来
因为要消耗操作数所以就要就近，这个我就用的stack存上述例子大于1个的，然后遇到0个的就取出来利用，并在元数据的second位置储存损耗的操作数，但是如果栈空了那就说明到这个位置就不能做了存个-1跳出来就行
最后就输出，每一个位置的MEX情况需要的操作数就是

• 当前位置全挪走a[i].first
• 之前位置补全0的a[i].second

但是如果遇到-1说明不用挪走当前的但是要输出补全之前的0需要的操作数
最终把剩余位置没到n的话补全-1到第n位置就ok

#include 
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;
typedef long long ll;
ll t, n;
int main()
{
    cin >> t;
    while (t--)
    {
        cin >> n;
        vector> a(n + 1);
        for (int i = 0; i < n; ++i)
        {
            ll x;
            cin >> x;
            a[x].first++;
        }
        stack> b;
        // index num
        bool flag = 0;
        for (int i = 0; i < n; ++i)
        {
            if (a[i].first > 1)
            {
                b.push({i, a[i].first - 1});
            }
            else if (a[i].first == 0 && !b.empty())
            {
                pair ans = b.top();
                b.pop();
                a[i].second = i - ans.first;
                ans.second--;
                if (ans.second >= 1)
                    b.push(ans);
            }
            else if (a[i].first == 0 && b.empty())
            {
                a[i].second = -1;
                flag = 1;
                break;
            }
        }
        int index = 0;
        ll sum = 0;
        for (; index <= n; ++index)
        {
            if (index == 0 && a[0].second != -1)
            {
                cout << a[index].first << ' ';
            }
            else if(index == 0 && a[0].second == -1)
            {
                cout << a[index++].first + sum << ' ';
                break;
            }
            else if (a[index].second == -1)
            {
                sum += a[index - 1].second;
                cout << a[index++].first + sum << ' ';
                break;
            }
            else
            {
                sum += a[index - 1].second;
                cout << a[index].first + sum << ' ';
            }
        }
        for (; index <= n; ++index)
            cout << -1 << ' ';
        cout << endl;
    }
    return 0;
}

D是个二分？？但我好像没看出来，，，等以后有机会看看