比赛回顾

题目清晰简单，难得最有希望上 1500 分的比赛可惜没有把握住机会（近期划水导致注定滑铁卢，又懈怠了）。A 题读错题意，B 题考虑不全面 WA 两次罚时起飞，C 题手速太慢，D 题画蛇添足 WA 了两次，E 题 30 分钟写的时间竟然被一个小点卡住（经典赛后 1 分钟改对）

赛后个人总结：

  • 手速太慢，码力不足，前三题还不如学弟稳健
  • 经常想着想着就发呆了，D 和 E 题一直问队友

A.Dislike of Threes—签到

题意：满足不能被 3 整除而且个位上的数不是 3 的正整数是满足条件的数，输出第 k 个满足条件的数

比赛前看了把 PUBG 的 PCL，精神还有点恍惚竟然把题目读错为每个位置上都不能有 3。。。

1
2
3
4
5
6
7
8
9
10
11
12
vector<int> vec;
void table() {
    for (int i = 1; i <= 100000; ++i) {
        if (i % 3 == 0 || (i % 10) == 3) continue;
        vec.push_back(i);
    }
}
void test_case() {
    int k;
    cin >> k;
    cout << vec[k - 1] << endl;
}

B.Who’s Opposite?—判断语句

题意：有偶数个人站成相隔距离相等的圆圈，现在已知 a 和 b 面对面，请问 c 面对的人序号是多少，如果情况不成立输出 -1

思路：a 和 b 序号相减就是半个圆圈上的人数，那么进而可以得到整个圆圈的人数 n。考虑全面一些先判断 a、b 和 c 是否序号在 [1,n][1,n]，进而从 c−n2c-\frac{n}{2} 和 c+n2c+\frac{n}{2} 中确定正确的答案

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
void test_case() {
    ll a, b, c;
    cin >> a >> b >> c;
    ll len = abs(b - a);
    ll tot = len * 2;
    if (a > tot || b > tot || c > tot) {
        cout << -1 << endl;
        return;
    }
    ll tmp = c - len;
    if (tmp > 0 && tmp <= tot) {
        cout << tmp << endl;
        return;
    }
    tmp = c + len;
    if (tmp > 0 && tmp <= tot) {
        cout << tmp << endl;
        return;
    }
    cout << -1 << endl;
}

C.Infinity Table—找规律

题意：某个人按照上图规律放置数字，请确定第 k 个数字所在的行和列

思路：首先第 i 行第 i 列的数字就是 i2−(i−1)i^2-(i-1)，我们可以先找到这样最的靠近数字 k 且大于等于 k 数，假设这样的数字处于 j 行 j 列，这样 k 肯定与当前数字同列，或者与处于 j-1 行 j-1 列的数字同行或者同列

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
ll ans[maxn];
ll len;
 
void table() {
    for (ll i = 1; i <= 100000; ++i) {
        ans[i] = i * i - (i - 1);
        if (ans[i] > (int)1e9) {
            len = i;
            break;
        }
    }
}
 
void test_case() {
    ll k;
    cin >> k;
    ll row, col;
    row = col = lower_bound(ans + 1, ans + len, k) - ans;
    ll now = ans[row];
    if (k < now && now - (row - 1) > k) --col, --row, now = ans[row];
    if (k > now)
        cout << col << ' ' << row - abs(k - now) << endl;
    else
        cout << col - abs(k - now) << ' ' << row << endl;
}

D.Make a Power of Two—暴力枚举+打表

题意：有两种操作：删除数字某位上的数（前导零也需要自己删），在数字末尾放上一个 0~9 的数，求将数字转变为 2 的次幂需要的最少操作次数

思路：肯定是先删除一些然后在末尾再插上一些数，所以我们打个边界足够大的 2 的次幂的表（因为可能最终答案是往大了凑所以表打到 1e18），然后将数尝试转变为表中的数取操作最小值就可，中途发现等于某个表中的数可以直接输出 0

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
vector<ll> vec;
 
void table() {
    ll now = 1;
    do {
        vec.pb(now);
        now *= 2;
    } while (now <= (ll)1e18);
}
 
ll check(ll now, ll x) {
    string s1 = to_string(now), s2 = to_string(x);
    ll len1 = s1.size(), len2 = s2.size();
    ll p = 0, ans = 0;
    for (ll i = 0; i < len2; ++i) {	//s2哪些数字能用来凑s1
        if (s2[i] == s1[p])
            ++p;
        else
            ++ans;
        if (p == len1)	//凑完s1了说明s2剩余的数全部删掉
            return ans + len2 - 1 - i;
    }
    ans += len1 - p;	//s2都用完了还需要插入一些数凑s1
    return ans;
}
 
void test_case() {
    ll n;
    cin >> n;
    ll ans = LLONG_MAX;
    for (auto e : vec) {
        if (n == e) {
            cout << 0 << endl;
            return;
        }
        ans = min(ans, check(e, n));
    }
    cout << ans << endl;
}

E.Polycarp and String Transformation—模拟+思维

题意：用原串 s 操作生成目标串 t（开始为空串）：将 s 串拼接到 t 串末尾，然后从 s 串中选一个字母从 s 串中全部删掉。执行上述操作直至 s 串为空，现在给出最终生成的目标串 t，请判断能够用某个 s 串生成，不能输出 -1，否则输出 s 串以及删除字符的顺序

1
2
3
4
5
6
Input: abacabaaacaac
Output: abacaba bac
//consider s="abacaba" so the actions may be performed as follows:
//t="abacaba", the letter 'b' is selected, then s="aacaa";
//t="abacabaaacaa", the letter 'a' is selected, then s="c";
//t="abacabaaacaac", the letter 'c' is selected, then s="" (the empty string).

思路：倒着看一连串相同的字母一定是最后删除的，依次类推第二个一连串相同且没出现过的字母一定是倒数第二个删除的，那么我们就可以这样计算出每个字母拼接所贡献的次数，再统计一下每个字母在整个 t 串中的数量。两者相除就是字母在 s 串中的个数，所有字母的个数相加进而求出 s 串长度 len。又因为 t 串包含 s 串所以我们直接取 t 串中前 len 个字符作为 s 串，再按照规则模拟一遍看 s 串能够生成 t 串，不能说明矛盾输出 -1，否则输出答案

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
bool check(string s1, string s2, string tmp) {
    int p = 0;
    string str = s1;
    while (s1 != "") {
        while (s1.find(tmp[p]) != -1)
            s1.erase(s1.find(tmp[p]), 1);
        str += s1;
        ++p;
    }
    if (str != s2) return false;
    return true;
}
 
void test_case() {
    string s;
    cin >> s;
    int len = s.size();
    int cnt[35] = {};
    bool vis[35] = {};
    int j = 0;
    string tmp = "";
    for (int i = len - 1; i >= 0; --i) {
        ++cnt[s[i] - 'a'];
        if (!vis[s[i] - 'a']) vis[s[i] - 'a'] = 1, tmp = tmp + s[i];
    }
    ll tot = 0;
    reverse(all(tmp));
    for (int i = 0; i < tmp.size(); ++i)
        tot += cnt[tmp[i] - 'a'] / (i + 1);
    string ss = s.substr(0, tot);
    if (check(ss, s, tmp)) {
        cout << ss << ' ';
        cout << tmp << endl;
    } else
        cout << -1 << endl;
}

F.Nearest Beautiful Number—贪心+模拟

题意：此题有简易两个版本，区别在于 k 的范围。定义 k-beautiful 的数为不含前导零的包含不同 0~9 数字种类不超过 k 的正整数。现在给出一个正整数 n，求第一个大于等于 n 的 k-beautiful 数

思路：出题人并不是希望我们去分类讨论，而是冷静的分析找出整体的策略。可以想到以下几个规律：记修改 n 使得满足 k-beautiful 的最高位为 pos

  • pos 后面的数可以随意修改，但是要保证后面出现的数字种类和前面出现的数字种类不超过 k

  • pos 的位置越靠后越好，pos 位置修改的数越小越好，修改范围是 [num[pos+1]+1,9][num[pos+1]+1,9]，不考虑进一的情况因为这相当于是更高位进行修改

  • 记 pos 位置及之前出现的数字种类为 cnt，如果 cnt<k 或者出现过 0，那么后面的数填充 0 肯定是最优的，否则后面的数不能产生新的数字种类，那么就用前面出现的最小的数数字填充后面的数

因为我们尝试从最低位作为 pos 位置逐渐增大当前位置的数字，先检查是否能凑成 k-beautiful，能的话拼出这个这个数字并返还结果，否则继续尝试更高位

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
int n, k;
 
inline bool check(int x) {	//检查
    vector<bool> vec(10);
    while (x) {  //修改位置到前面出现的不同数字
        vec[x % 10] = true;
        x /= 10;
    }
    int cnt = 0;
    for (auto e : vec) cnt += e;
    return cnt <= k;
}
 
inline int getans(int x, int pos) {	//凑数
    int ans = x;
    vector<bool> vec(10);
    while (x) {
        vec[x % 10] = true;
        x /= 10;
    }
    int cnt = 0;
    for (auto e : vec) cnt += e;
    //修改位置后面的数可以随便填
    if (vec[0] || cnt < k) {  //如果前面有0或者还可以有不同的数后面的数直接用0填充
        while (pos--) ans = ans * 10;
        return ans;
    }
    //否则后面的数只能用前面最小的数填充
    int minn = 0;
    for (int i = 9; i >= 0; --i)
        if (vec[i]) minn = i;
    while (pos--) ans = ans * 10 + minn;
    return ans;
}
 
void test_case() {
    cin >> n >> k;
    int tmp = n;
    for (int i = 0; i < 10; ++i, tmp /= 10) {  //枚举当前位置作为最靠前的修改位置
        int now = tmp % 10;
        if (i != 0) ++now;                //确定当前位置修改的最小范围
        for (int j = now; j < 10; ++j) {  //枚举尝试修改的值
            if (check(tmp / 10 * 10 + j)) {
                cout << getans(tmp / 10 * 10 + j, i) << endl;
                return;
            }
        }
    }
}