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; }