A. Do Not Be Distracted!

https://codeforces.com/contest/1520/problem/A

    #include <iostream>
    #include <algorithm>
    #include <cstring>

    using namespace std;

    const int N = 1000000;

    int t, n;
    string s;
    int visit[N];

    int main() {
        cin >> t;
        while(t--){
            cin >> n;
            cin >> s;
            memset(visit, 0, sizeof(visit));
            bool flag;
            for(int i = 0; i < n; i++){
                flag = true;
                if(visit[s[i]] == 0){
                    visit[s[i]] = 1;
                }else{
                    if(s[i] != s[i-1]){
                        flag = false;
                        break;
                    }
                }
            }
            if(flag) {
                printf("YES\n");
            }else{
                printf("NO\n");
            }
        } 

        return 0;
    }

B. Ordinary Numbers

https://codeforces.com/contest/1520/problem/B
不能用dp,原因见const int行。
而且cur需要用longlong,否则会溢出,导致结果出错。

#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;

//const int N = 1e9;  //这样不行,开到1e9会爆内存,如果改成1e8就可以,而题目最大到1e9,说明o(n)的复杂度不行,不能用dp。改成使用搜索,构造字符串,每次加一位同样的数就行。 

int t;
long long n;
//int dp[N];

bool isOrdinary(int n){
    if(n < 10) return true;
    int last, cur;
    bool flag;
    last = n % 10;
    while(n > 0){
        n /= 10;
        cur = n % 10;
        if(last != cur){
            flag = false;
            break;
        }
    }
    return flag;
}

int main(){
    cin >> t;
    while(t--){
        cin >> n;
//        dp[1] = 1;
//        for(int i = 2; i <= n; i++){
//            if(isOrdinary(i)){
//                dp[i] = dp[i-1] + 1;
//            }else{
//                dp[i] = dp[i-1];
//            }
//        }
        int ans = 0;
        for(int i = 1; i < 10; i++){
            long long cur = i;
            while(cur <= n){
                ans++;
                cur = cur * 10 + i;
            }
        }    
        printf("%d\n", ans);
    }
    return 0;
}