---
tags: 2022二篩
---
# 2022二篩題解
## 哈囉
`tag: 哈囉, while`
此題為送分水題，以下講解兩種解此題方式
1. 手刻:poop:
2. 到DDJ首頁 $\to$ 找到"使用手冊"並點進去 $\to$ 滑到底下有程式碼的地方 $\to$ 找到C++的程式碼 $\to$ Ctrl+C $\to$ 回到題目 $\to$ 送出解答 $\to$ Ctrl+V $\to$ <font color="green"><b>AC</b></font>
:::spoiler `code`
```cpp=
#include <iostream>
using namespace std;
int main() {
string s;
while(cin >> s) {
cout << "hello, "<< s << endl;
}
return 0;
}
```
:::
---
## 球球遊戲
`tag : stack`
這題其實就是簡單的實作題
我們可以做得基本上就是
1. 把球從A移動到C
2. 把球從A移動到B
3. 把球從C移動到B
那甚麼時候要執行這些操作呢
當A最前面的球和B最裡面需要的球一樣時，就可以執行2
當C最上面的球和B最裡面需樣的球一樣時，就可以執行3
而上面兩個都不符合時就只剩下1可以做
而當A和C都空了，也就是達成了遊戲要求的排列
如果A空了但C還沒空，且C的最上面也不能移到B了，就是無法達成排列
而實作部分，C區域的只能取最上面的性質就是$stack$，可以用$STL$實現，也可以直接用陣列實作
A區域是照順序的所以只需要一個變數紀錄現在最前面的是甚麼就可以了
B區域是只要用到用到序列的最前方，這也可以用$stack$(要反轉)也可以用$queue$，也可以直接用陣列實作
而剩下的就是用$while$重複進行上面判斷並進行操作
時間複雜度為:$O(n)$
空間複雜度為:$O(n)$
---
## 簡單的小遊戲
`tag:`
這題的想法也很簡單
我們先把問題簡化
如果他們玩的棋盤都是單條1*n
我們可以很簡單的想到n如果是偶數，先手必勝
n如果是奇數，後手必勝
而它們只是玩了兩次這種遊戲
第一次輸的第二次當先手
第二次輸的就輸的這場遊戲
(或是當成同時玩只是分成兩個棋盤)
### 正確性證明
可以發現，他們走到的格子必定是 $奇數\implies 偶數 \implies 奇數 \implies 偶數$，所以對於一個$1\times n$的格子，只要$n$是偶數他們走的方式就必定是奇數次，否則就會是偶數次，所以只要判斷總共次數是奇數還是偶數就可以推斷是誰會獲勝了。
時間複雜度:$O(T)$
空間複雜度:$O(T)$
---
## 防空雷達
`tag:二分搜`
這題我們可以很明顯地看到所有的飛行器物體在經過排序後
會有單調性
而講到單調性我們就會想到二分搜
這題其實就是用二分搜找到雷達上下界的座標是排序後的第幾個
然後就可以知道中間有幾個了
實作時善用lower_bound和upper_bound
時間複雜度:$O(nlogn)$
空間複雜度:$O(n)$
---
## 簡單的費事數列(1)
`tag: DP`
:::success
DP簡單來說就是透過儲存以前的狀態來減少複雜度的方式
:::
就是最基礎的`DP`，基本上只要照著所給的提示打出來就可以了
:::spoiler `虛擬碼`
```cpp=
mxN := 10^6 // 附值
dp[0] := 1
dp[1] := 1
for i in range(2, mxN+1) : // i 從 [2, mxN+1)
dp[i] := dp[i-1] + dp[i-2];
```
:::
時間複雜度: $O(N)$
空間複雜度: $O(N)$
---
## 犯人是誰
`tag: string count array`
既然都說了只要***組成一樣***，所以我們可以只在$a$上維護大小為$b$的連續子字串，如果和$b$組成一樣就可以了
:::spoiler `虛擬碼`
```cpp=
b_char_cnt[ 26 ] := Char_Count( b, 0, b.size); // Char_Count(string, l, r) [l, r)
a_char_cnt[ 26 ] := Char_Count( a, 0, b.size);
cnt := 0
for i in range( b.size, a.size)
if b_char_cnt .all() == a_char_cnt .all()
cnt := cnt+1
a_char_cnt[ a[i-b.size] ]--
a_char_cnt[ a[i+1] ]++
```
:::
---
## A.水題
https://hackmd.io/@fuyajo/drc7-tutorial#a618-A-%E6%B0%B4%E9%A1%8C
---
## A.區間相乘(1)
`tag : Math`
對於一個大小為$N$的陣列，總共會有$\frac{N(N + 1)}{2}$ 個$sum[l, r] (1\leq l \leq r\leq N)$。
所以如果$\frac{N(N +1)}{2} \gt 10^9+7$則必定會有兩個區間和相同。
---
## 千束開車(1)
`tag:前綴和`
這題是要做區間操作
一般我們單純用陣列存每次搜尋時都要把區間加起來，時間複雜度是$O(n)$
這題n和m都是$10^5$每次都要把區間加起來的話，作多會要操作$10^{10}
大幅超過了電腦每秒運算速度的$3*10^8$
所以我們需要區間和
區間和是把現在位置前的所有數都加起來存到現在這一格，也就是
$pre[5] = a[1] + a[2] + a[3] + a[4] + a[5]$
$pre[5] = pre[4] + a[5]$
pre為儲存前綴和的陣列，a是一般的數列
這樣假設我們要取$a[3]$，就可以用$pre[3] - pre[2]$計算
如果要去$a[3] + a[4] + a[5] + ... + a[10]$，就可以用$pre[10] - pre[2]$計算
所以只要先把前綴和處理好
這樣原本$O(n)$的計算區間和就變成了，$O(1)$計算
時間複雜度: $O(N)$
空間複雜度: $O(N)$
---
## Fibonacci Sequence DX
`tag: DP, 費氏數列, 建表, 神奇的double精度`
我們在題目中有定義了$FDX$數列為：
$\large{FDX_n = \frac{F_n}{1.618^n}}$
其中的$F_n$指的是**費氏數列**的第$n$項，其值為：
$\large{F_n = \begin{cases} 1 \qquad \qquad \qquad \quad n=1 \\ 1 \qquad \qquad \qquad \quad n=2 \\ F_{n-1}+F_{n-2} \qquad else \\ \end{cases}}$
相信大家都看過這個一般費氏數列的遞迴式，
那所以$FDX_n$的遞迴式就是：
$\large{FDX_n = \begin{cases} \frac{1}{1.618} \qquad \qquad \qquad \qquad \ n=1 \\ \frac{1}{1.618^2} \qquad \qquad \qquad \qquad n=2 \\ \frac{FDX_{n-1}}{1.618}+\frac{FDX_{n-2}}{1.618^2} \qquad \ else \\ \end{cases}}$
然後因為 $n \leq 6 * 10^5$ 所以我們就可以建一個陣列，再用$O(n)$跑$DP$過去就可以取得所有的值。
:::spoiler `code`
```cpp=
#include<bits/stdc++.h>
#define IO cin.tie(0) -> sync_with_stdio(0)
#define endl "\n"
using namespace std;
using LL = long long;
constexpr double phi = 1.618, phi2 = phi * phi;
constexpr LL maxN = 6e5;
inline void output(double num) {
cout << fixed << setprecision(1) << num << endl;
}
double FDX[maxN];
inline void init() {
FDX[0] = 1 / phi;
FDX[1] = 1 / phi2;
for(LL i = 2; i < maxN; i ++ )
FDX[i] = FDX[i - 1] / phi + FDX[i - 2] / phi2;
}
inline void solve() {
LL n;
cin >> n;
output(FDX[n - 1]);
}
int main() {
// IO;
init();
LL T;
cin >> T;
while(T -- )
solve();
}
```
:::
阿然後因為`C++`的`double`精度很神奇，又加上經過了數十萬次的小數加法，他精度會跑掉超多，所以只要輸出四捨五入到點下$1$位(原本想到$5$位的...)。
---
## XD ecneuqeS iccanobiF
`tag: 二分搜, struct, 運算子重載`
基本上就是上題的進化版，在建出整個陣列後對其做二分搜。
但在二分搜前會先遇到一個問題，$FDX$的前幾位(差不多到$11$位吧)其實是沒有符合單調性的，這樣其實是不能做二分搜的。
但是我們題目說的是找到$max(n)\ when\ FDX_n < num$，所以其實答案這樣沒差(因為前幾項的$n$小$FDX_n$大，然後要找的答案要是$n$大的，所以真正的答案永遠不會是他們)。
那在二分搜的時候，當然可以用內建的`lower_bound`函式，但是這樣好麻煩(又要用到`struct`跟`operator overload`)，所以自己手刻二分搜也是個好方法。
以下提供使用了`lower_bound`的code。
:::spoiler `code`
```cpp=
#include<bits/stdc++.h>
#define IO cin.tie(0) -> sync_with_stdio(0)
#define endl "\n"
using namespace std;
using LL = long long;
struct stc {
LL pos;
double val;
stc(LL _pos = 0, double _val = 0) : pos(_pos), val(_val) {;}
};
inline bool cmp(stc a, double b) {
return a.val < b;
}
constexpr double phi = 1.618, phi2 = phi * phi;
constexpr LL maxN = 6e5;
inline void output(double num) {
cout << fixed << setprecision(4) << num << endl;
}
stc FDX[maxN];
inline void init() {
FDX[0] = stc(1, 1 / phi);
FDX[1] = stc(2, 1 / phi2);
for(LL i = 2; i < maxN; i ++ ) {
double tmp = FDX[i - 1].val / phi + FDX[i - 2].val / phi2;
FDX[i] = stc(i + 1, tmp);
}
for(LL i = 0; i < 6; i ++ )
FDX[i] = FDX[i * 2 + 1];
for(LL i = 6; i + 6 < maxN; i ++ )
FDX[i] = FDX[i + 6];
}
inline void solve() {
double num;
cin >> num;
LL pos = lower_bound(FDX, FDX + maxN - 6, num, cmp) - FDX - 1;
if(pos < 0)
cout << -1 << endl;
else
cout << FDX[pos].pos << endl;
}
int main() {
IO;
init();
LL T;
cin >> T;
while(T -- )
solve();
}
```
:::
---
## FF39沒搶到想要的東西好難過 可以進來安慰我嗎
`tag: priority_queue`
其實這題真的很水，就簡單`priority_queue`實作而已，
作法都在題目裡面了，不會的應該就單純不會`priority_queue`而已。
然後FF39我是有搶到想要的東西啦，但[有人](https://forum.gamer.com.tw/Co.php?bsn=60076&sn=85733166)沒有，幫哭QAQ。
題述純屬虛構，一切都是工讀生的錯，跟我無關。
:::spoiler `code`
```cpp=
#include<bits/stdc++.h>
#define IO cin.tie(0) -> sync_with_stdio(0)
#define endl "\n"
using namespace std;
using LL = long long;
inline void solve() {
LL N;
cin >> N;
priority_queue<LL> pq;
while(N -- ) {
LL num;
cin >> num;
pq.push(num);
}
while(pq.size() != 1) {
LL a = pq.top();
pq.pop();
LL b = pq.top();
pq.pop();
pq.push(a - b);
}
cout << pq.top() << endl;
}
int main() {
IO;
LL T;
cin >> T;
while(T -- )
solve();
}
```
:::
---
## 區間相乘(2)
`tag : Math, Modulo, inverse`
如果要窮舉所有的$sum[l,r]$的話，時間複雜度為$O(N^2)$，顯然會$TLE$，所以嘗試把$sum[l, r]$簡化。
$inv(k) \equiv \frac{1}{k}\quad (mod \quad p)$
$sum[l, r] \equiv (a_l*a_{l+1}*a_{l+2}*.....a_{r-1} * a_r)\quad (mod\quad p)\\\implies sum[l, r] \equiv (sum[0, r] \quad *\quad inv(sum[0,l-1])\quad (mod \quad p)$
看起來是不是簡單一些了呢:poop:
再嘗試往下推。
簡單版:
### $sum[l, r] = k\\\implies\frac{sum[0,r]}{sum[0,l-1]} = k \\\implies \frac{sum[0,r]}{k} = sum[0,l -1]$
完整版:
### $sum[l, r] \equiv k \quad (mod \quad p)\\ \implies sum[0, r] \times inv(sum[0, l-1]) \equiv k\quad (mod \quad p)\\\implies sum[0, r] \times inv(sum[0, l-1]) \times inv(k) \equiv k \times inv(k)\quad (mod \quad p)\\\implies sum[0, r] \times inv(k) \times inv(sum[0, l-1]) \equiv 1\quad (mod \quad p)\\\implies sum[0,r] \times inv(k) \equiv sum[0,l-1] \quad (mod \quad p)$
由此可知，只要每次更新右界再判斷乘$sum[0,r] * inv[k]$是否有等於$sum[0,l-1]$即可。
值可以用`unordered_map<int, vector<int>>`存。
時間複雜度為$O(N)$
:::spoiler `code`
```cpp=
ll ar[mxN];
unordered_map<ll, vector<int>> mp;
inline ll fpow(int K) {
int N = mod - 2;
ll ans = 1, res = K;
while(N) {
if(N & 1) ans = ans * res % mod;
res = res * res % mod;
N >>= 1;
}
return ans;
}
inline void solve() {
int N, K; cin >> N >> K;
bool ans = 1;
ll invK = fpow(K);
ll sum = 1;
mp[1].EB(-1);
for(int i =0, val, fnd;i < N ;i++) {
cin >> val;
sum = sum * val % mod;
fnd = sum * invK % mod;
if(mp.find(fnd) != mp.end()) {
for(auto &j : mp[fnd]) cout << j + 1 << ' ' << i << endl;
ans = 0;
}
mp[sum].EB(i);
}
if(ans) cout << -1 << endl;
mp.clear();
}
```
:::
---
## 神奇的三元樹
`tag: BST `
就照著他的規律做就好了
---
## 斑馬線(1)
`tag: 位元運算, 卡常`
這題如果你要喇分，真的很簡單，用陣列去實作就行了。
但如果你要<font color="green"><b>AC</b></font>的話就需要用到位元運算了，
因為$N \leq 60$，所以用位元去存的話(白 $\to\ 1$, 黑$\to 0$)是可以只用一個$long\ long$的數字去維護的。
在塗斑馬線的時候，可以用`and, or, xor`這些運算子去遮罩有進行修改的區間。
而在回答問題的時候，一樣可以先遮罩出整個區間，再一個一個數。
:::spoiler `code`
```cpp=
#include<bits/stdc++.h>
#define IO cin.tie(0) -> sync_with_stdio(0)
#define endl "\n"
using namespace std;
using LL = long long;
inline LL lowbit(LL x) {
return (x) & (-x);
}
inline LL highbit(LL x) {
return __lg(x);
}
inline void solve() {
LL pwr2[61];
pwr2[0] = 1;
for(LL i = 1; i <= 60; i ++ )
pwr2[i] = pwr2[i - 1] << 1;
LL N, M, Q;
cin >> N >> M >> Q;
LL num = 0;
for(LL i = 0, tmp = 1; i < N; i ++ , tmp <<= 1) {
char chr;
cin >> chr;
num += (chr == 'w') * tmp;
}
while(M -- ) {
LL op, l, r;
cin >> op >> l >> r;
LL tmp = pwr2[r] - pwr2[l];
if(op == 1)
num |= tmp;
if(op == 2) {
tmp = ~tmp;
num &= tmp;
}
if(op == 3)
num ^= tmp;
}
while(Q -- ) {
LL op, l, r;
cin >> op >> l >> r;
LL tmp = pwr2[r] - pwr2[l];
LL num2 = (num & tmp) >> l;
if(op == 4) {
if(num2 == 0)
cout << -1 << endl;
else
cout << __lg(lowbit(num2)) + l << endl;
}
if(op == 5) {
if(num2 == 0)
cout << -1 << endl;
else
cout << highbit(num2) + l << endl;
}
if(op == 6)
cout << __builtin_popcountll(num2) << endl;
}
}
int main() {
IO;
LL T;
cin >> T;
while(T -- )
solve();
}
```
:::
然後code的第59行有一個神奇的函式叫做`__builtin_popcountll(long long n)`，
其實就是可以算出這個數字在二進位中有幾個$1$，就這樣。
喔然後，我在出完這題後發現，其實用陣列跟用位元運算的速度差不多，所以才把時間壓那麼緊，不要罵我QAQ。
---
## C. 二元樹
`tag: BST STL`
簡單來說這題就是考二元樹的父子關係，
其實你可以把二元樹想成一個序列，
然後每個子節點都會有他所在的區間，
像一開始的時候區間範圍是$(-\infty, \infty)$，
如果這時候插入了一個數$k$，
這時候區間就會變成
>$k 的左子節點 \implies (-\infty, k)$
>$k的右子節點\implies [k ,\infty)$
如果這時候再插入一個數$b < k$
區間就會變成。
>$k 的右子節點 \implies [k ,\infty)$
>$b 的左子節點\implies [-\infty ,b)$
>$b 的右子節點\implies [b ,k)$
總共區間的範圍仍然是$(-\infty, \infty)$，
這就是為什麼二元樹可以一直插入的原因，
所以你只要記錄下每一個區間屬於哪一個節點，
之後只要好好的去維護他即可
可以用一個`map<int, node*>`來去維護
`map<pair<int,int>, node*>`也可以:poop:
:::spoiler `虛擬碼`
```cpp=
struct BST {
struct node {
int val;
node *l, *r;
node( int _val ) {
val := _val;
l := NULL;
r := NULL;
}
}*root;
map< pair<int, int>, node* > range;
void insert( int val ) {
auto find := range .include( val);
// find .node* = find .second
// find .l_range = find .first .first
// find .r_range = find .first .second
find .node* = new node( val );
range[ [find .l_range, val) ] = find .node* -> l;
range[ [val, find .r_range) ] = find .node* -> r;
range .erase( find );
}
void sort( node* cur) {
if( cur == NULL ) return;
sort( cur -> l );
print( cur -> val );
sort( cur -> r );
}
void preorder( node* cur ) {
if( cur == NULL) return;
print( cur->val );
preorder( cur->l );
preorder( cur->r );
}
BST(){
root := new node( 0 );
range[ (-inf, 0) ] := root->l; // 左閉右開
range[ [0, inf) ] := root->r;
};
}
```
:::
### 題外話
這邊有一個不是我想出來的令解 :poop:
在測資是隨機的情況下複雜度也是$O(NlogN)$ (可惜我出的不是隨機測資)
就是用類似$quick\; sort$的方式來去維護，
維護好先後順序也同樣可以拿到解答。
---
Sign in with Wallet
Connect another wallet