Practice.

A. Extremely Round

题意

给定一个整数 \(n\)，输出 \([1,n]\) 内只有一位非 \(0\) 的数的个数。

思路

显然，对于 \(t\) 位，有 \(9\) 个满足要求的数，我们只需考虑到何时停下枚举即可。

时间复杂度：\(O(\log_{10} n)\)

对应AC代码

#include <bits/stdc++.h>

using namespace std;

#define int long long

signed main() {
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int t;
    cin >> t;
    while(t --){
        int n;
        cin >> n;
        int a = n, tot = 0;
        while(a >= 10) a /= 10, tot ++;
        cout << tot * 9 + a << '\n';
    }
    return 0;
}

简单打卡题

B. Notepad#

题意

给定一个长为 \(n\) 且由小写字母构成的字符串，输出是否存在两段及以上长度大于等于 \(2\) 的相同连续子序列。

思路

我们不妨只寻找长为 \(2\) 的重复子串，也就是说我们只需记录 \(n - 1\) 对子序列的情况。我们可以边记录边向后遍历，并判断当前字母以及前一个字母是否在之前被记录过，若记录过则输出存在即可。

此处我们需要排除如下情况：\(hhh\)，此处不满足题意但会被误判为 \(YES\)，因而我们可以记录该子串在当前状态之前最近被统计的位置，然后判断位置是否和当前位置出现了交集即可。

时间复杂度：\(O(n)\)

对应AC代码

#include <bits/stdc++.h>

using namespace std;

#define int long long

const int N = 30;

int a[N][N];

signed main() {
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int t;
    cin >> t;
    while(t --){
        int n;
        cin >> n;
        string cur;
        cin >> cur;
        cur = ' ' + cur;
        memset(a, 0, sizeof a);
        bool ok = false;
        for(int i=1;i<n;i++){
            int o1 = cur[i] - 'a', o2 = cur[i + 1] - 'a';
            if(a[o1][o2] != 0 && a[o1][o2] != i - 1) {
                ok = true;
                break;
            }
            if(a[o1][o2] == 0) a[o1][o2] = i;
        }
        cout << (ok ? "YES" : "NO") << '\n';
    }
    return 0;
}

WA了好几遍捏

C. Hamiltonian Wall

题意

给定一个长为 \(n\)，宽为 \(2\) 的矩阵，矩阵元素为 \(B\) 或 \(W\)，输出是否可以从最左边列的某个元素 \(B\) 开始一笔画，在不重复经过同一个元素以及不经过元素 \(W\) 的前提下连接所有元素 \(B\)。不可以沿对角线连接。

思路

我们可以直接模拟，判断前者的入口在何处，若出现冲突就直接输出 \(NO\)。

具体按照下面的方法模拟：

找出第一个不是 \(BB\) 的列；
将入口更新为 \(B\) 出现的位置；
若相邻出现 \(WB,BW\) 或 \(BW,WB\)，输出 \(NO\);
若出现多个 \(BB\)，根据奇偶性判断之后的入口；
遇到 \(WW\) 直接输出 \(NO\)。
无冲突输出 \(YES\)。

时间复杂度：\(O(n)\)

对应AC代码

#include <bits/stdc++.h>

using namespace std;

#define int long long

const int N = 2e5 + 10;

bool a[N];

signed main() {
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int t, n;
    char c;
    cin >> t;
    while(t --){
        cin >> n;
        for(int i=0;i<n;i++){
            cin >> c;
            a[i] = c == 'B';
        }
        bool f = false, ans = true;
        int pre;
        cin >> c;
        if(a[0] && c == 'B') pre = 2, f = true;
        else if(a[0]) pre = 0;
        else if(c == 'B') pre = 1;
        else pre = -1;
        for(int i=1;i<n;i++){
            cin >> c;
            if(!ans) continue;
            int now;
            if(a[i] && c == 'B') now = 2;
            else if(a[i]) now = 0;
            else if(c == 'B') now = 1;
            else now = -1;
            if(f && now == 2) continue;
            f = false;
            if((pre == -1 && now != -1) || (pre == 0 && now == 1) || (pre == 1 && now == 0)){
                ans = false;
                continue;
            }
            if(now == 2) now = 1 - pre;
            pre = now;
        }
        cout << (ans ? "YES" : "NO") << '\n';
    }
    return 0;
}

太模拟了，不过貌似一笔画不止可以暴力模拟（