Harbour.Space Scholarship Contest 2021-2022 (open for everyone, rated, Div. 1 Div. 2)

A Digits Sum

题目大意

S(x)为x各个位上的数的和，问在1~n这n个数中有多少个数满足S(x + 1) < S(x)

主要思路

只有发生进位才会满足S(x + 1) < S(x)，统计9，19，29..等个数即可

AC代码

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define debug(a) cout << #a << " = " << a << endl;
#define x first
#define y second
typedef pair<int, int> P;
const int N = 200010;
int n;
int a[N];
signed main(void)
{
    int T;
    cin >> T;
    while(T--)
    {
        cin >> n;
        int res = 0;
        res = n / 10;
        if(n % 10 == 9) res++;
        cout << res << endl;
    }
    return 0;
}

B Reverse String

题目大意

给一个字符串s，一个字符串t，问能否通过在任意位置先向右遍历s一个长度(可以为0)，再向左遍历一个长度(可以为0)来得到字符串t

主要思路

找到s[i] == t[0]的位置枚举向右遍历的长度，由于t字符串长度固定，那么向左的长度也能确定，将字符串拼接判断是否等于t即可，模拟

AC代码

#include <bits/stdc++.h>
using namespace std;
#define debug(a) cout << #a << " = " << a << endl;
#define x first
#define y second
typedef pair<int, int> P;
const int N = 200010;
int n;
int main(void)
{
    int T;
    cin >> T;
    while(T--)
    {
        string s1, s2;
        cin >> s1 >> s2;
        int x = s1.find(s2);
        if(x != -1) puts("YES");
        else
        {
            bool flag = false;
            for(int i = 0; i < s1.size(); i++)
            {
                if(s1[i] == s2[0])
                {
                    string s = "";
                    for(int len = 0; len < s2.size(); len++)//枚举长度
                    {
                        s.clear();
                        int pos;
                        for(int j = i; j <= i + len && j < s1.size(); j++)//先向右
                        {
                            s += s1[j];
                            pos = j;
                        }
                        pos--;
                        while(pos >= 0 && s.size() != s2.size())//再向左
                        {
                            s += s1[pos];
                            pos--;
                        }
                        if(s == s2)
                        {
                            flag = true;
                            break;
                        }
                    }
                }
            }
            if(flag) puts("YES");
            else puts("NO");
        }
    }
    return 0;
}

C Penalty

题目大意

两队一人一球踢点球，1表示进球，0表示没进球，？表示未知，问能否通过修改？为1或0来让点球用最少的局数结束，当1队的进球数+剩余局数 < 另一队进球数时结束

主要思路

一共只有10局比赛，我们统计?个数，枚举每一种情况判断即可

或者考虑由于求局数最小，则让？全为1或者全为0取局数最小值即可

AC代码

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define debug(a) cout << #a << " = " << a << endl;
#define x first
#define y second
typedef pair<int, int> P;
const int N = 200010;
int n;
int ans;
int f(string s, int st, int n)
{
    int cnt = 0;
    for(int i = 0; i < s.size(); i++)
    {
        if(s[i] == '?')
        {
            if((st >> cnt) & 1)
            {
                s[i] = '1';
            }
            else s[i] = '0';
            cnt++;
        }
    }
    int t1 = 0, cnt1 = 5;
    int t2 = 0, cnt2 = 5;
    for(int i = 0; i < 10; i++)
    {
        if(s[i] == '1' && i % 2 == 0) t1++;
        else if(s[i] == '1' && i % 2 == 1) t2++;
        if(i % 2 == 0) cnt1--;
        else cnt2--;
        if(t1 + cnt1 < t2)
        {
            return i + 1;
        }
        else if(t2 + cnt2 < t1)
        {
            return i + 1;
        }
    }
    return (int)10;
}
signed main(void)
{
    int T;
    cin >> T;
    while(T--)
    {
        int ans = 11;
        string s;
        cin >> s;
        int cnt = 0;
        for(int i = 0; i < s.size(); i++)
        {
            if(s[i] == '?') cnt++;
        }
        for(int i = 0; i < 1 << cnt; i++)
        {
            ans = min(ans, f(s, i, cnt));
        }
        cout << ans << endl;
    }
    return 0;
}

D Backspace

题目大意

给一个字符串s和一个字符串t，每次可以写入一个字符或者删除上一个输入的字符（如果上一个没输入字符则不用删除，相当于不输入当前字符），问能否通过s得到字符串t

主要思路

考虑从前往后遍历，如果s[i] == t[j]那么i++, 否则i += 2，这样我们最后还得考虑剩余的字符串是否是偶数个，如果是奇数则不成立。

于是我们考虑从后往前遍历，如果s[i] == t[j]那么i—, 否则i -= 2，这样在匹配成功时不需考虑最后剩余字符数为奇数还是偶数，全部删除即可

AC代码

#include <bits/stdc++.h>
using namespace std;
int main()
{
    int T;
    cin >> T;
    while(T--)
    {
        string s, t;
        cin >> s >> t;
        for(int i = s.size() - 1; i >= 0; i--)
        {
            if(s[i] == t.back()) t.pop_back();
            else i--;
            if(t.size() == 0) break;
        }
        if(t.size() == 0) puts("YES");
        else puts("NO");
    }
    return 0;
}