---
tags: DDJRC
---
# DDJ Regular Contest Round#9 Tutorial
---
## a648：A. 完美曲線
`tag`: `math`、`sort`
這題給定的是 x 對 y 的函數，
因此第一步先把點依照 x 座標排序，
之後由小到大遍歷全部的點，
一次比較三個點的大小，
如果中間的比較小，
則完美度 $+1$，
如果中間的比較大，
則完美度 $-1$，
最後就輸出就好了。
:::spoiler `code by revcoding`
```cpp=
#include <bits/stdc++.h>
using namespace std;
int main() {
int N;
cin >> N;
vector<pair<int,int>> pts(N);
for(auto& i : pts)
cin >> i.first >> i.second;
sort(pts.begin(), pts.end());
int ans = 0;
for(int i = 0; i < N; ++i) {
if(i+2 < N) {
int p1 = pts[i].second, p2 = pts[i+1].second, p3 = pts[i+2].second;
if(p1 < p2 && p3 < p2)
--ans;
if(p1 > p2 && p3 > p2)
++ans;
}
}
cout << ans << '\n';
}
```
:::
---
## a641：B. 洗分孤兒是朋友
`tags: 均攤分析, Chtholly Tree, Old Driver Tree`
本題輸入`0 l r v`時，可以模擬成座號`l`之後，所有人分數`+v`，座號 `r + 1`之後，所有人分數`-v`。
利用均攤分析然後比較區間大小及分數，本題就可以 `AC`。
注意尚未賦值但在詢問區間內的地方都是 `0`，需要判斷最長連續區段的值是否為 `0`
:::spoiler `code by tree~`
``` cpp=
#include<bits/stdc++.h>
#define LL long long
#define f first
#define s second
using namespace std;
int main() {
cin.tie(nullptr), ios_base::sync_with_stdio(false);
int q, val, op; LL p, l, r;
map<LL, int> m;
m[0] = 0, m[1e18] = 0;
cin >> p >> q;
while (q--) {
cin >> op >> l >> r;
if (!op) {
cin >> val;
m[l] += val, m[r + 1] -= val;
}
else {
auto it = m.begin();
LL max_v = 0, max_d = -1, tmp = 0; it++;
for (auto i = m.begin(); it != m.end(); i++) {
if (i -> f > r + 1) break;
else if (it -> f >= l) {
if (min(it -> f, r + 1) - max(l, i -> f) > max_d) {
max_d = min(it -> f, r + 1) - max(l, i -> f);
max_v = tmp;
}
else if (min(it -> f, r + 1) - max(l, i -> f) == max_d)
max_v = max(max_v, tmp);
}
tmp += it -> s;
it++;
}
cout << max_d << ' ' << max_v << '\n';
it = m.begin(), it++, tmp = m.begin() -> s;
for (auto i = m.begin(); it != m.end(); i++) {
if (i -> f > r + 1) break;
else if (it -> f >= l) {
if (min(it -> f, r + 1) - max(l, i -> f) == max_d && tmp == max_v)
cout << max(l, i -> f) << ' ' << min(it -> f - 1, r) << '\n';
}
tmp += it -> s;
it++;
}
}
}
return 0;
}
```
:::
\
本題也可以用珂朵莉樹存下所有人的分數並比較區間大小及分數，這樣也可以 `AC`，不過離時限似乎很近。
:::spoiler `code by tree~`
``` cpp=
#include<bits/stdc++.h>
#define LL long long
#define f first
using namespace std;
struct seg {
LL l, r, d; mutable int v;
seg(const LL &l, const LL &r, const int &v) : l(l), r(r), d(r - l + 1), v(v) {}
bool operator< (const seg &s) const {return l < s.l;}
};
bool cmp(const seg &i, const seg &j) {
return i.d > j.d || (i.d == j.d && i.v > j.v) || (i.d == j.d && i.v == j.v && i.l < j.l);
}
set<seg> s;
auto split(const LL &p) {
auto it = s.lower_bound(seg(p, 0, 0));
if (it != s.end() && it -> l == p) return it;
it--;
LL l = it -> l, r = it -> r; int v = it -> v;
s.erase(it), s.insert(seg(l, p - 1, v));
return s.insert(seg(p, r, v)).f;
}
void merge(set<seg>::iterator &it) {
auto tmp = it;
if (it != s.begin()) {
tmp--;
if (tmp -> v == it -> v) {
LL l = tmp -> l, r = it -> r, v = it -> v;
s.erase(tmp), s.erase(it), s.insert(seg(l, r, v));
}
}
}
void add(const LL &l, const LL &r, const int &v) {
auto end = split(r + 1), begin = split(l);
auto it = begin;
for (; it != end; it++) it -> v += v;
merge(begin), merge(end);
}
int main() {
cin.tie(nullptr), ios_base::sync_with_stdio(false);
int q, val, op; LL p, l, r;
cin >> p;
s = {seg(1, p, 0)};
cin >> q;
while (q-- && cin >> op >> l >> r) {
if (!op) cin >> val, add(l, r, val);
else {
auto end = split(r + 1), begin = split(l);
vector<seg> v(begin, end);
merge(begin), merge(end);
sort(v.begin(), v.end(), cmp);
LL max_d = v[0].d; int max_v = v[0].v;
cout << max_d << ' ' << max_v << '\n';
for (size_t i = 0; i < v.size() && max_d == v[i].d && max_v == v[i].v; i++)
cout << v[i].l << ' ' << v[i].r << '\n';
}
}
return 0;
}
```
:::
---
## a639：C. 你學會無詠唱了？
`tag: BFS`
本題 $\left |s\right | \leq 200$，`DFS` 剪枝將拿到 `NA 80%`，未剪枝但有判斷是否為重複字串則是`NA 60%`。
若未考慮到「重複字串輸出的問題」(如測資 "good" 中，可能輸出兩次 "od")，則會拿到 `NA 40%`。
正解為 `BFS` 搭配剪枝。(先 `sort` 字串再用一個變數 `pre` 存下重複字元)
:::spoiler `code by RexWu`
``` cpp=
#include<bits/stdc++.h>
#define endl '\n'
using namespace std;
struct wd {
char c; int idx;
bool operator<(const wd& w) const {
return c < w.c || (c == w.c && idx < w.idx);
}
};
struct ans {
string s; wd w;
};
int main() {
int t;
while (cin >> t) {
vector<wd> str(201);
while (t--) {
string s; cin >> s;
const int len = int(s.length());
for (int i = 0; i < len; i++) str[i].c = s[i], str[i].idx = i;
sort(str.begin(), str.begin() + len);
deque<ans> dq{{"", {0, -1}}};
while (!dq.empty()) {
ans tmp = dq.front(); dq.pop_front();
cout << endl << tmp.s;
char pre = 0;
for (int i = 0; i < len; i++) {
if (pre == str[i].c) continue;
else if (str[i].idx > tmp.w.idx)
dq.push_back({tmp.s + str[i].c, str[i]}), pre = str[i].c;
}
}
if (t) cout << endl;
}
}
return 0;
}
```
:::
---
## a649：D. 未知的數字表示系統
`tag`：`DP`、`Greedy`
> 原題: [Google Kick Start 2020 Round D Alien Piano](https://codingcompetitions.withgoogle.com/kickstart/round/000000000019ff08/0000000000387174)
這題基本上就是按照題目上的規則進行 DP。
* 第一個數字符號可以任意的往阿拉伯的任何一位數字對照
* 剩餘的數字遵循以下規則
* 當數字符號比上一個大時，所對照的阿拉伯數字也要比上一個大
* 當數字符號比上一個小時，所對照的阿拉伯數字也要比上一個小
* 當數字符號一樣大時，所對照的阿拉伯數字也要一樣大
* 無法符合以上規則時，則此數字符號可以對照成任意阿拉伯數字
而 DP 的方法就是窮舉所有可能，
至於第三大點就直接轉移，
不須做任何的運算，
只須找出最小的就好。
按照以上四個規則所推得的轉移式如下
$$
dp[j][i] =
\begin{cases}
min(dp[j][i], dp[l][i-1]+1),\quad if\quad S[i] == S[i-1] &\wedge& j\neq i \\
min(dp[j][i], dp[l][i-1]+1),\quad if\quad S[i] > S[i-1] &\wedge& j\leq i \\
min(dp[j][i], dp[l][i-1]+1),\quad if\quad S[i] < S[i-1] &\wedge& j\geq i \\
min(dp[j][i], dp[l][i-1]),\quad else
\end{cases}
$$
這個轉移式`DP`的是 `DP[對照成第幾個阿拉伯數字][現在是第幾個符號]`
:::spoiler `code by revcoding`
```cpp=
#include <bits/stdc++.h>
using namespace std;
const int mxK = 1e4;
int main() {
int N, K;
cin >> N >> K;
vector<int> S(K);
for(auto& i : S)
cin >> i;
vector<vector<int>> dp(11, vector<int>(mxK, 0));
for(int i = 0; i < 10; ++i)
for(int j = 1; j < K; ++j)
dp[i+1][j] = 1e9;
for(int i = 1; i < K; ++i) {
for(int j = 1; j < 11; ++j) {
for(int l = 1; l < 11; ++l) {
if(S[i] == S[i-1] && j != l)
dp[j][i] = min(dp[j][i], dp[l][i-1]+1);
else if(S[i] > S[i-1] && j <= l)
dp[j][i] = min(dp[j][i], dp[l][i-1]+1);
else if(S[i] < S[i-1] && j >= l)
dp[j][i] = min(dp[j][i], dp[l][i-1]+1);
else
dp[j][i] = min(dp[j][i], dp[l][i-1]);
}
}
}
int ans = 1e9;
for(int i = 0; i < 10; ++i)
ans = min(ans, dp[i+1][K-1]);
cout << ans << '\n';
}
```
:::
\
至於`Greedy`解就參考原題題解吧。
---
## a640：E. 當他拔出第三把劍，所有人都必須倒下
`tags: Matrix, Modular inverse element, Fast pow`
這題精髓在於「設給定數列第 $n$ 項可表示為矩陣 $A_n$，則適當矩陣 $B$ 可以使得 $A_nB = A_{n + 1}$」
設 $I$ 為單位矩陣，$A'$ 為 $A$ 之反矩陣，則：
$\Sigma_{n = l}^RA_n \times I =\quad A_l + A_lB + A_lB^2 + ... + A_lB^{r - l}$
$\Sigma_{n = l}^RA_n\times B =$ $\quad\quad\quad A_lB + A_lB^2 + ... + A_lB^{r - l} + A_lB^{r - l + 1}$
$\Sigma_{n = l}^RA_n\times (B - I) = A_lB^{r - l + 1} - A_l$
$\Sigma_{n = l}^RA_n = (A_lB^{r - l + 1} - A_l)\times (B - I)' = A_l\times (B^{r - l + 1} - I)\times (B - I)'$
本題中，$A_l = \left [ \begin{array}{ccc} v_l & v_{l + 1} & v_{l + 2}\end{array}\right ]$，$B = \left [ \begin{array}{ccc} 0 & 0 & c\\1 & 0 & b\\0 & 1 & a\end{array}\right]$
設 $M = \left [ \begin{array}{ccc} a_1 & a_2 & a_3\\b_1 & b_2 & b_3\\c_1 & c_2 & c_3\end{array}\right]$，
則 $M' = \cfrac{1}{det(M)}\left [ \begin{array}{ccc} +\left |\begin{array}{cc}b_2 & b_3\\c_2 & c_3\end{array}\right | & -\left |\begin{array}{cc}a_2 & a_3\\c_2 & c_3\end{array}\right | & +\left |\begin{array}{cc}a_2 & a_3\\b_2 & b_3\end{array}\right |\\-\left |\begin{array}{cc}b_1 & b_3\\c_1 & c_3\end{array}\right | & +\left |\begin{array}{cc}a_1 & a_3\\c_1 & c_3\end{array}\right | & -\left |\begin{array}{cc}a_1 & a_3\\b_1 & b_3\end{array}\right |\\+\left |\begin{array}{cc}b_1 & b_2\\c_1 & c_2\end{array}\right | & -\left |\begin{array}{cc}a_1 & a_2\\c_1 & c_2\end{array}\right | & +\left |\begin{array}{cc}a_1 & a_2\\b_1 & b_2\end{array}\right |\end{array}\right]$
($det(M)$ 之解法不多贅述)
又 $B - I = \left [ \begin{array}{ccc} -1 & 0 & c\\1 & -1 & b\\0 & 1 & a - 1\end{array}\right]$，
則 $(B - I)' = \cfrac{1}{a + b + c - 1}\left [ \begin{array}{ccc} -a - b + 1 & c & c\\-a + 1 & -a + 1 & b + c\\1 & 1 & 1\end{array}\right]$
所有次方算法請使用快速冪。
到這邊，只剩下 `mod 1e9 + 7` 的問題。
因為大部分都是乘法，因此只要在每個算式中加上一個 `mod 1e9 + 7` 即可，
只有 $\cfrac {1}{a + b + c - 1}$ 需要利用模逆元，也就是 $(a + b + c - 1)^{10^9 + 5}$ $mod$ $10^9 + 7$
把這些算式用程式實作出來即可 `AC`。
:::spoiler `code by tree~`
``` cpp=
#include<bits/stdc++.h>
#define LL long long
using namespace std;
constexpr LL m = 1e9 + 7;
const vector<vector<LL>> I = {{1, 0, 0}, {0, 1, 0}, {0, 0, 1}};
inline LL fpow(LL x, LL y = m - 2) {
LL ret = 1;
for (; y; y >>= 1, x = x * x % m)
if (y & 1) ret = ret * x % m;
return ret;
}
inline vector<vector<LL>> mat(const vector<vector<LL>> &x, const vector<vector<LL>> &y) {
vector<vector<LL>> ret(3, vector<LL> (3, 0));
for (int i = 0; i < 3; i++) {
for (int j = 0; j < 3; j++) {
for (int k = 0; k < 3; k++)
ret[i][j] = (ret[i][j] + x[i][k] * y[k][j]) % m;
}
}
return ret;
}
inline vector<vector<LL>> mpow(vector<vector<LL>> x, LL y) {
vector<vector<LL>> ret = I;
for (; y; y >>= 1, x = mat(x, x)) {
if (y & 1) ret = mat(ret, x);
}
return ret;
}
inline vector<vector<LL>> Minus(const vector<vector<LL>> &x, const vector<vector<LL>> &y) {
vector<vector<LL>> ret = x;
for (int i = 0; i < 3; i++) {
for (int j = 0; j < 3; j++) {
ret[i][j] = (ret[i][j] - y[i][j]) % m;
}
}
return ret;
}
inline vector<vector<LL>> det(const LL a, const LL b, const LL c) {
vector<vector<LL>> ret(3, vector<LL> (3));
LL dt = (a + b + c - 1) % m;
dt = fpow(dt);
ret[0][0] = (-a - b + 1) % m, ret[0][1] = ret[0][2] = c;
ret[1][0] = ret[1][1] = -a + 1, ret[1][1] = (b + c) % m;
ret[2][0] = ret[2][1] = ret[2][2] = 1;
for (int i = 0; i < 3; i++) {
for (int j = 0; j < 3; j++) ret[i][j] = ret[i][j] * dt % m;
}
return ret;
}
int main() {
cin.tie(nullptr), ios_base::sync_with_stdio(false);
LL T, v[3], a, b, c, l, r;
cin >> T >> a >> b >> c;
for (auto & i : v) cin >> i;
vector<vector<LL>> A = {{v[0], v[1], v[2]}, {0, 0, 0}, {0, 0, 0}},\
B = {{0, 0, c}, {1, 0, b}, {0, 1, a}}, detBI, ans;
detBI = det(a, b, c);
while (T--) {
cin >> l >> r;
ans = mat(mat(A, mpow(B, l - 1)), mat(Minus(mpow(B, r - l + 1), I), detBI));
cout << ans[0][0] << '\n';
}
return 0;
}
:::
Sign in with Wallet
Connect another wallet