DDJ Regular Contest Round#9 Tutorial

---

a648：A. 完美曲線

tag: math、sort

這題給定的是 x 對 y 的函數，
因此第一步先把點依照 x 座標排序，
之後由小到大遍歷全部的點，
一次比較三個點的大小，
如果中間的比較小，
則完美度

$+1$，
如果中間的比較大，
則完美度

$-1$，
最後就輸出就好了。

code by revcoding

#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

code by tree~

#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，不過離時限似乎很近。

code by tree~

#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|\le 200$，DFS 剪枝將拿到 NA 80%，未剪枝但有判斷是否為重複字串則是NA 60%。

若未考慮到「重複字串輸出的問題」(如測資 "good" 中，可能輸出兩次 "od")，則會拿到 NA 40%。

正解為 BFS 搭配剪枝。(先 sort 字串再用一個變數 pre 存下重複字元)

code by RexWu

#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

這題基本上就是按照題目上的規則進行 DP。

• 第一個數字符號可以任意的往阿拉伯的任何一位數字對照
• 剩餘的數字遵循以下規則
  • 當數字符號比上一個大時，所對照的阿拉伯數字也要比上一個大
  • 當數字符號比上一個小時，所對照的阿拉伯數字也要比上一個小
  • 當數字符號一樣大時，所對照的阿拉伯數字也要一樣大
• 無法符合以上規則時，則此數字符號可以對照成任意阿拉伯數字

而 DP 的方法就是窮舉所有可能，
至於第三大點就直接轉移，
不須做任何的運算，
只須找出最小的就好。
按照以上四個規則所推得的轉移式如下

$$dp[j][i]=\{\begin{array}{lll}min(dp[j][i],dp[l][i-1]+1),ifS[i]==S[i-1]& \wedge & j\ne i\\ min(dp[j][i],dp[l][i-1]+1),ifS[i]>S[i-1]& \wedge & j\le i\\ min(dp[j][i],dp[l][i-1]+1),ifS[i]<S[i-1]& \wedge & j\ge i\\ min(dp[j][i],dp[l][i-1]),else\end{array}$$
這個轉移式DP的是 DP[對照成第幾個阿拉伯數字][現在是第幾個符號]

code by revcoding

#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_{n}B=A_{n+1}$」

設

$I$ 為單位矩陣，

$A^{\prime }$ 為

$A$ 之反矩陣，則：

${\mathrm{\Sigma }}_{n=l}^R{A}_n\times I=A_l+A_{l}B+A_l{B}^2+...+A_l{B}^{r-l}$

${\mathrm{\Sigma }}_{n=l}^R{A}_n\times B=$

$A_{l}B+A_l{B}^2+...+A_l{B}^{r-l}+A_l{B}^{r-l+1}$

${\mathrm{\Sigma }}_{n=l}^R{A}_n\times (B-I)=A_l{B}^{r-l+1}-A_l$

${\mathrm{\Sigma }}_{n=l}^R{A}_n=(A_l{B}^{r-l+1}-A_l)\times (B-I{)}^{\prime }=A_l\times (B^{r-l+1}-I)\times (B-I{)}^{\prime }$

本題中，

$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^{\prime }=\frac{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{)}^{\prime }=\frac{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 即可，

只有

$\frac{1}{a+b+c-1}$ 需要利用模逆元，也就是

$(a+b+c-1{)}^{{10}^9+5}$

$mod$

${10}^9+7$

把這些算式用程式實作出來即可 AC。

code by tree~

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