寒假训练营第二场补题+题解

A.小沙的炉石

思路：

code：

B.小沙的魔法

思路：

code：

C.小沙的杀球

思路：

按题意贪心处理即可

code：

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pll;
const double eps = 1e-9;
int main()
{
    std::ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

#ifdef ak
    freopen("in.txt", "r", stdin);
    freopen("out.txt", "w", stdout);
#endif
    ll x, a, b, ans = 0;
    string s;
    cin >> x >> a >> b >> s;
    for (int i = 0; i < s.length(); i++)
    {
        int t = s[i] - '0';
        if (t && x > a)
            x -= a, ans++;
        else
            x += b;
    }
    cout << ans << endl;
    return 0;
}

D.小沙的涂色

思路：

code：

E.小沙的长路

思路：

code：

F.小沙的算数

思路：

code：

G.小沙的身法

思路：

code：

H.小沙的数数

思路：

计算出m二进制下1的个数 $i d x$ ，计算 $n^{idx}$ 即可

code：

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pll;
const double eps = 1e-9;
const int mod = 1e9 + 7;
ll fastpow(ll a, ll b, ll mod)
{
    a %= mod;
    ll base = a, ans = 1;
    while (b)
    {
        if (b & 1)
            ans *= base;
        base *= base;
        base %= mod;
        ans %= mod;
        b >>= 1;
    }
    return ans % mod;
}
int main()
{
    std::ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

#ifdef ak
    freopen("in.txt", "r", stdin);
    freopen("out.txt", "w", stdout);
#endif
    ll n, m;
    cin >> n >> m;

    ll x = 0;
    while (m)
    {
        if (m & 1)
            x++;
        m >>= 1;
    }
    ll ans = fastpow(n, x, mod);
    cout << ans << endl;
    return 0;
}

I.小沙的构造

思路：

双指针模拟，最后奇偶条件特判。

code：

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pll;
const double eps = 1e-9;
pair<char, char> s[10];
const int N = 1e4 + 10;
char ans[N], cs[25] = {'V', '"', '!', '\'', '*', '+', '-', '.', '0', '8', ':', '=', '^', '_', 'W', 'T', 'Y', 'U', 'I', 'O', 'A', 'H', 'X', 'M', '|'};
int n, m;
bool failed = 0;
void op()
{
    int idx1 = 1, idx2 = 0;
    int l = 1, r = n, res = n;
    while (m)
    {
        if (m >= 2 && idx1 <= 5)
        {
            m -= 2;
            if (l >= r)
            {
                failed = 1;
                return;
            }
            ans[l++] = s[idx1].first;
            ans[r--] = s[idx1++].second;
            res -= 2;
        }
        else
        {
            m -= 1;
            if (l > r || idx2 >= 25)
            {
                failed = 1;
                return;
            }
            else
            {
                ans[l] = ans[r] = cs[idx2++];
                l++, r--;
                res -= 2;
            }
        }
    }
    if (l <= r)
    {
        if (ans[l - 1] != ans[r + 1])
        {
            if (res & 1)
            {
                if (idx2 <= 23)
                {
                    char c1 = cs[idx2];
                    char c2 = cs[++idx2];
                    l--;
                    r++;
                    while (l < r)
                    {
                        ans[l++] = c1;
                        ans[r--] = c1;
                    }
                    ans[l] = c2;
                }
                else
                {
                    failed = 1;
                    return;
                }
            }
            else
            {
                char c1 = ans[l - 1], c2 = ans[r + 1];
                while (l <= r)
                {
                    ans[l++] = c1;
                    ans[r--] = c2;
                }
            }
        }
        else
        {
            char c1 = ans[l - 1];
            while (l <= r)
            {
                ans[l++] = c1;
                ans[r--] = c1;
            }
        }
    }
}
int main()
{
    std::ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

#ifdef ak
    freopen("in.txt", "r", stdin);
    freopen("out.txt", "w", stdout);
#endif
    s[1] = {'<', '>'};
    s[2] = {'[', ']'};
    s[3] = {'{', '}'};
    s[4] = {'(', ')'};
    s[5] = {'\\', '/'};
    cin >> n >> m;
    op();
    if (failed)
        cout << -1 << endl;
    else
        cout << ans + 1 << endl;
    return 0;
}

J.小沙的Dota

思路：

code：

K.小沙的步伐

思路：

按题意模拟步数即可

code：

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pll;
const double eps = 1e-9;
ll a[100];
int main()
{
    std::ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
#ifdef ak
    freopen("in.txt", "r", stdin);
    freopen("out.txt", "w", stdout);
#endif
    string s;
    cin >> s;
    for (int i = 0; i < s.length(); i++)
    {
        int t = s[i] - '0';
        if (t != 5)
        {
            a[5]++;
            a[t]++;
        }
    }
    for (int i = 1; i <= 9; i++)
    {
        cout << a[i] << " ";
    }
    return 0;
}