CPTC

CPTC 001

Problem	Coder	Topic
A	Hyperbola	Binary Search
B	Kelly	Greedy, Sort
C	Hyperbola	Enumerate, Prefix Sum
D	Hyperbola	互動題, DP
E	Kelly	數位 DP

今天難得全都 1AC。讀完題後也有迅速抓出水題，兩題都在正常速度開完。pD 被曲線通靈出來，他邊寫我邊聽 LinLee 講題目。我決定把 pE 拿去做，pC 則留給他們想。pE 算是定義好狀態就很好寫的題目，之前常在 AtCoder 看到類似的題目。

pB

 1#include<bits/stdc++.h>
 2using namespace std;
 3typedef long long ll;
 4int main() {
 5    int n, m;
 6    scanf("%d%d", &n ,&m);
 7    vector<int> deg(n);
 8    for (int i = 0; i < m; i++) {
 9        int a, b;
10        scanf("%d%d", &a, &b);
11        deg[a-1]++, deg[b-1]++;
12    }
13    vector<int> h(n);
14    for (int i = 0; i < n; i++)
15        scanf("%d", &h[i]);
16    sort(h.begin(), h.end());
17    sort(deg.begin(), deg.end());
18    ll ans = 0;
19    for (int i = 0; i < n; i++)
20        ans += ll(h[i]) * ll(deg[n - i - 1]);
21    printf("%lld\n", ans);
22    return 0;
23}

pE

一開始會想用 cal(R) - cal(L - 1)，但後來想到 L 會是 0，且減一其實有點小麻煩，所以就用 cal(R) - cal(L - 1)，如果 L 是 rainbow number 就再把答案加一。
另外也有把前綴是 0 的 case 獨立算出來，讓狀態定義的比官解簡潔。

 1#include<bits/stdc++.h>
 2using namespace std;
 3#define maxn 105
 4typedef long long ll;
 5const ll mod = 1000000007;
 6inline int d (char c) {return c - '0';}
 7int check(string s) {
 8    for (int i = 1; s[i]; i++)
 9        if (s[i - 1] == s[i]) return 0;
10    return 1;
11}
12ll cal(string s) {
13    int len = s.length();
14    ll ans = 0, tmp = 1;
15    for (int i = 1; i < len; i++) { //長度小於 len 的數量
16        tmp = tmp * 9 % mod;
17        ans = (ans + tmp) % mod;
18    }
19    s = '0' + s;
20    ll dp[maxn][10][2] = {};
21    dp[0][0][1] = 1;
22    for (int i = 1; i <= len; i++) { //長度等於 len 的數量
23        if (s[i] != s[i - 1]) // dp[i][j][1] 代表前 i 位和 s 一樣
24            dp[i][d(s[i])][1] = dp[i - 1][d(s[i - 1])][1];
25        for (int j = 0; j <= 9; j++) {
26            for (int k = 0; k <= 9; k++)
27                if (k != j) dp[i][j][0] += dp[i - 1][k][0];
28            if (d(s[i - 1]) != j && d(s[i]) > j)
29                dp[i][j][0] += dp[i - 1][d(s[i - 1])][1];
30            d[i][j][0] %= mod;
31        }
32    }
33    for (int i = 0; i <= 9; i++)
34        ans = (ans + dp[len][i][0] + dp[len][i][1]) % mod;
35    return ans;
36}
37int main () {
38    int T; cin >> T;
39    while (T--) {
40        string L, R; cin >> L >> R;
41        cout << (cal(R) - cal(L) + check(L) + mod) % mod << "\n";
42    }
43    return 0;
44}