# T26寒訓練習賽題解
## [codeforces](https://codeforces.com/contests/499783)
## 比賽結束後仍然可以submit code
## 賽前預測AC人數
## 實際AC人數
由 moon 出 A, D, H
其他由 tw20000807 出題
## A. 不要懷疑 首殺 : blameazu.
:::danger
**To AC is human; to AK, divine. - Moon**
:::
輸出"Hello worId"
但是他的world拼成worId了
:::spoiler 範例code byKCC
```cpp=
#include<bits/stdc++.h>
using namespace std;
#define KCC ios::sync_with_stdio(0);cin.tie(0);
int main()
{
cout << "Hello worId" << "\n";
}
```
:::
---
## C. 假日時就是要刷題阿不然要幹嘛 首殺 : blameazu.
因為假日固定只有兩天，所以原本的問題可以理解成以下敘述
::: success
給你 $n$ 個數，有兩個序列，把這 $n$ 個數**依序**放進其中一個序列裡
問最小的不爽值是多少
以及怎麼放
:::
我們可以貪心一下
:::success
在放的時候我們希望每個序列最後放入的數字越大越好，因為這樣越有可能不會增加不爽值
:::
我們可以設想一些情況
假設第一個序列最後放入的數字為ff
假設第二個序列最後放入的數字為ss
假設現在要放入的數字為k
我們要讓ff跟ss越大越好
所以接下來會有6種情況
:::info
k > ss > ff
把k放進第一個序列
ff變成k
不爽值 + 1
:::
:::info
k > ff > ss
把k放進第二個序列
ss變成k
不爽值 + 1
:::
:::info
ss > k > ff
把k放進第二個序列
ss變成k
:::
:::info
ss > ff > k
把k放進第一個序列
ff變成k
:::
:::info
ff > ss > k
把k放進第二個序列
ss變成k
:::
:::info
ff > k > ss
把k放進第一個序列
ff變成k
:::
如果ss = k or ff = k 那就直接放到等號成立的那個序列
::: spoiler 範例code byKCC
```cpp=
#include<bits/stdc++.h>
using namespace std;
#define pb push_back
vector<int> f, s;
int ary[1000000];
int main()
{
int n;
cin >> n;
for(int i = 1; i <= n; i++) cin >> ary[i];
long long ff = INT_MAX, ss = INT_MAX - 1;
int k = 0;
for(int i = 1; i <= n; i++){
if(ary[i] == ff) f.pb(i);
else if(ary[i] == ss) s.pb(i);
else if(ary[i] > ss and ss > ff){
k++;
f.pb(i);
ff = ary[i];
}
else if(ary[i] > ff and ff > ss){
k++;
s.pb(i);
ss = ary[i];
}
else if(ss > ary[i] and ary[i] > ff){
s.pb(i);
ss = ary[i];
}
else if(ss > ff and ff > ary[i]){
f.pb(i);
ff = ary[i];
}
else if(ff > ss and ss > ary[i]){
s.pb(i);
ss = ary[i];
}
else if(ff > ary[i] and ary[i] > ss){
f.pb(i);
ff = ary[i];
}
}
cout << k << "\n";
cout << f.size() << "\n";
for(auto w : f) cout << w << ' ';
if(f.size() > 0) cout << "\n";
cout << s.size() << "\n";
for(auto w : s) cout << w << ' ';
}
```
:::
:::spoiler 範例code by tw20000807
```cpp=
#include<bits/stdc++.h>
using namespace std;
int inf = 1e9 + 10;
int v[200010];
int main(){
int n, ans = 0;
vector< int > a = {0}, b = {0};
v[0] = inf;
cin >> n;
for(int i = 1; i <= n; i++)
cin >> v[i];
for(int i = 1; i <= n; i++){
if(v[a.back()] > v[b.back()])swap(a, b);
if(v[a.back()] >= v[i])a.push_back(i);
else if(v[b.back()] >= v[i])b.push_back(i);
else{
ans++;
a.push_back(i);
}
}
cout << ans << "\n" << a.size() - 1 << "\n";
for(int i = 1; i < a.size(); i++)
cout << a[i] << " \n"[i == a.size() - 1];
cout << b.size() - 1 << "\n";
for(int i = 1; i < b.size(); i++)
cout << b[i] << " \n"[i == b.size() - 1];
}
```
stl 的 swap 是 O(1)
c style array 是 O(n)
:::
---
## D. 寫報告 首殺 :
我不會qwq
詳解by moon
這是個貪心的題目
應該很好看出來
第一想法可能會是直接sort結束時間
然後逐步做過去就好
但仔細想想就會發現不太對
因為只限制了要在什麼時間之前做完
而不是開始和結束時間
只要在結束時間之前是可以自由移動的
所以按照限制時間來排序之後
越後面的報告 如果能做的話
那一定能在更早之前做
所以我們會利用priority_queue來維護 之前的報告中花費時間最久的那個
可以試試看這個例子，答案應該是3
:::success
4
1 4
3 4
2 5
5 8
:::
:::spoiler 範例code by tw20000807
```cpp=
#include<bits/stdc++.h>
#define ll long long
#define pii pair< ll, ll >
#define X first
#define Y second
using namespace std;
int main(){
int n;
cin >> n;
vector< pii > v(n);
//Y is need time, X is deadline
for(int i = 0; i < n; ++i){
cin >> v[i].Y >> v[i].X;
}
sort(v.begin(), v.end());
ll ans = 0, cur = 0;
priority_queue< ll > pq;
for(int i = 0; i < n; ++i){
if(cur + v[i].Y <= v[i].X){
cur += v[i].Y;
ans++;
pq.push(v[i].Y);
}
else if(!pq.empty() && v[i].Y < pq.top()){
cur -= pq.top(); pq.pop();
cur += v[i].Y;
pq.push(v[i].Y);
}
}
cout << ans << "\n";
}
```
:::
:::spoiler 範例code by moon
```cpp=
#include<bits/stdc++.h>
using namespace std;
int main()
{
int n;
cin >> n;
vector<pair<int, int>> v(n);
for(int i = 0; i < n; ++i){
cin >> v[i].second >> v[i].first;
}
sort(v.begin(), v.end());
long long ans = 0, cur = 0;
priority_queue<int> pq;
for(int i = 0; i < n; ++i){
if(cur + v[i].second <= v[i].first){
cur += v[i].second;
ans++;
pq.push(v[i].second);
}
else if(pq.size() and v[i].second < pq.top()){
cur = cur - pq.top() + v[i].second;
pq.pop();
pq.push(v[i].second);
}
}
cout << ans << '\n';
}
```
:::
---
## E. 中位數的中位數 首殺 : RedPlus
~~閱讀完題目後直接實作即可~~
因為這題的$n$很小，所以可以直接實作
題目給的數字到2147483674而int只到2147483647，所以要開long long
::: spoiler 範例code byKCC
```cpp=
#include<bits/stdc++.h>
using namespace std;
#define KCC ios::sync_with_stdio(0);cin.tie(0);
#define pb push_back
vector<long long> ans;
int main()
{
KCC
int n;
cin >> n;
for(int i = 0; i < n; i++){
vector<long long> v;
for(int j = 0; j < n; j++){
long long a;
cin >> a;
v.pb(a);
}
sort(v.begin(), v.end());
ans.pb(v[n / 2]);
}
sort(ans.begin(), ans.end());
cout << ans[n / 2] << "\n";
return 0;
}
```
:::
:::spoiler 範例code by tw20000807
```cpp=
#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll arr[1010][1010];
ll ans[1010];
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
int n;
cin >> n;
for(int i = 0; i < n; i++){
for(int j = 0; j < n; j++){
cin >> arr[i][j];
}
sort(arr[i], arr[i] + n);
ans[i] = arr[i][n / 2];
}
sort(ans, ans + n);
cout << ans[n / 2] << "\n";
}
```
:::
---
## F. 迷宮 首殺 : charhao
這裡有一個難一點的類似題可以去試試看[連結在這](https://cses.fi/problemset/task/1193)
這題是一個BFS的裸題，題目就是問$A$走到傳送門及$B$走到傳送門分別最少要走幾步，然後再乘上各自走一步需要的時間
簡單來說就是做兩次BFS
::: spoiler 範例code byKCC
```cpp=
// 變數解釋:
// n, a, b 與題目敘述相同
// xa, xb, xo
// A,B, 傳送門的x座標
// yo, ya, yb
// A,B, 傳送門的y座標
// queue<pair< pair< int , int >, int>> q
// queue<pair< pair< X座標, Y座標>, 走到(X,Y)需要的步數>> q
// 所以
// X座標會是 q.front().first.first
// Y座標會是 q.front().first.second
// 走到(X,Y)需要的步數會是 q.front().second
// ~~這寫法好像有點毒瘤~~
// 也可以用tuple(第二天的課有講到)
// aa為A走到傳送門需要的最短步數(也就是BFS後的結果)
// bb為B走到傳送門需要的最短步數(也就是BFS後的結果)
#include<bits/stdc++.h>
using namespace std;
#define KCC ios::sync_with_stdio(0);cin.tie(0);
long long n, a, b, xa, xb, xo, ya, yb, yo;
char c[1005][1005];
int dx[] = {0, 0, 1, -1};
int dy[] = {1, -1, 0, 0};
queue<pair< pair<int, int>, int >> q;
bool used[1005][1005];
long long bfs(int x, int y)
{
q.push({{x, y}, 0});
while(q.size()){
int nowx = q.front().first.first;
int nowy = q.front().first.second;
int f = q.front().second;
q.pop();
if(nowx == xo and nowy == yo) return f;
for(int i = 0; i < 4; i++){
int next_x = nowx + dx[i];
int next_y = nowy + dy[i];
if(!used[next_x][next_y] and
next_x >= 0 and next_x < n
and next_y >= 0 and next_y < n
and c[next_x][next_y] != '#')
{
q.push({{next_x, next_y}, f + 1});
used[next_x][next_y] = true;
}
}
}
return -1;
}
int main()
{
KCC
cin >> n >> a >> b;
for(int i = 0; i < n; i++){
for(int j = 0; j < n; j++){
cin >> c[i][j];
if(c[i][j] == 'A'){
xa = i;
ya = j;
}
if(c[i][j] == 'B'){
xb = i;
yb = j;
}
if(c[i][j] == 'O'){
xo = i;
yo = j;
}
}
}
long long aa = bfs(xa, ya);
while(!q.empty()) q.pop();
for(int i = 0; i < n; i++){
for(int j = 0; j < n; j++) used[i][j] = false;
}
long long bb = bfs(xb, yb);
if(aa == -1) cout << aa << ' ';
else cout << aa * a << ' ';
if(bb == -1) cout << bb << "\n";
else cout << bb * b << "\n";
}
```
:::
:::spoiler 範例code by tw20000807
```cpp=
#include<bits/stdc++.h>
#define pii pair<int, int>
#define X first
#define Y second
using namespace std;
char mp[1010][1010];
long long disa[1010][1010];
long long disb[1010][1010];
int dx[] = {1, -1, 0, 0};
int dy[] = {0, 0, 1, -1};
int main(){
int n, at, bt;
cin >> n;
cin >> at >> bt;
pii A, B, O;
for(int i = 1; i <= n; i++){
for(int j = 1; j <= n; j++){
disa[i][j] = disb[i][j] = -1;
cin >> mp[i][j];
if(mp[i][j] == 'O'){
O = {i, j};
}
if(mp[i][j] == 'A'){
A = {i, j};
}
if(mp[i][j] == 'B'){
B = {i, j};
}
}
}
for(int i = 0; i <= n + 1; i++){
mp[0][i] = mp[i][0] = mp[n + 1][i] = mp[i][n + 1] = '#';
}
vector< pii > qu;
int idx = 0;
qu.push_back(A);
disa[A.X][A.Y] = 0;
while(qu.size() > idx){
pii cur = qu[idx++];
for(int k = 0; k < 4; k++){
pii nw = {cur.X + dx[k], cur.Y + dy[k]};
if(mp[nw.X][nw.Y] != '#' && disa[nw.X][nw.Y] == -1){
disa[nw.X][nw.Y] = disa[cur.X][cur.Y] + at;
qu.push_back(nw);
}
}
}
qu.clear();
idx = 0;
qu.push_back(B);
disb[B.X][B.Y] = 0;
while(qu.size() > idx){
pii cur = qu[idx++];
for(int k = 0; k < 4; k++){
pii nw = {cur.X + dx[k], cur.Y + dy[k]};
if(mp[nw.X][nw.Y] != '#' && disb[nw.X][nw.Y] == -1){
disb[nw.X][nw.Y] = disb[cur.X][cur.Y] + bt;
qu.push_back(nw);
}
}
}
cout << disa[O.X][O.Y] << " " << disb[O.X][O.Y] << "\n";
}
```
:::
---
## G. 兩個背包問題 首殺 :
這顯然是DP的經典問題對吧?
沒錯!!
當只有一個背包的時候dp的關係式為
\begin{align}
dp[i][j] = max
\begin{cases}
&dp[i - 1][j - w[i]] + val[i]\\
&dp[i - 1][j]\\
\end{cases}
\end{align}
那兩個背包呢?
有幾個想法
* 把它視為一個大背包
* 增維
視為一個大背包顯然是不行的
因為物品不能被拆開成小塊
::: danger
例:一個背包能裝重量1，另一個能裝重量2，不能裝重量3的物品
:::
那增維的dp式怎麼列?
就像一個背包的時候一樣
$dp[i][j][k] = 選到第i個，第一個背包裝了j重量 + 第二個背包裝了k重量 的價值最大值$
$$
dp[i][j][k] = max
\begin{cases}
dp[i - 1] &[j] &[k]\\
dp[i - 1] &[j - w[i]] &[k] &+ val[i]\\
dp[i - 1] &[j] &[k - w[i]] &+ val[i]]\\
\end{cases}
$$
::: success
**dp的精隨在於宣告一個名為dp的陣列**
:::
:::spoiler 範例code byKCC
```cpp=
#include<bits/stdc++.h>
using namespace std;
int w[105];
int val[105];
int dp[200][200][200];
int main()
{
int n, a, b, ans = 0;
cin >> n >> a >> b;
for(int i = 0; i < n; i++) cin >> val[i];
for(int i = 0; i < n; i++) cin >> w[i];
for(int i = 0; i < n; i++){
for(int j = 0; j <= a; j++){
for(int k = 0; k <= b; k++){
if(i - 1 >= 0){
if(j - w[i] >= 0) dp[i][j][k] = max(dp[i][j][k], dp[i - 1] [j - w[i]] [k] + val[i]);
if(k - w[i] >= 0) dp[i][j][k] = max(dp[i][j][k], dp[i - 1] [j] [k - w[i]] + val[i]);
dp[i][j][k] = max(dp[i][j][k], dp[i - 1][j][k]);
}
else{
if(j - w[i] >= 0) dp[i][j][k] = max(dp[i] [j - w[i]] [k], val[i]);
if(k - w[i] >= 0) dp[i][j][k] = max(dp[i] [j] [k - w[i]], val[i]);
}
ans = max(ans, dp[i][j][k]);
}
}
}
cout << ans << "\n";
}
```
:::
::: spoiler 範例code by tw20000807
```cpp=
#include<bits/stdc++.h>
using namespace std;
int w[110], v[110];
int dp[110][120][120];
int main(){
int n;
cin >> n;
int a, b, ans = 0;
cin >> a >> b;
for(int i = 1; i <= n; i++)cin >> v[i];
for(int i = 1; i <= n; i++)cin >> w[i];
for(int i = 1; i <= n; i++){
for(int j = 0; j <= a; j++){
for(int k = 0; k <= b; k++){
dp[i][j][k] = dp[i - 1][j][k];
if(j - w[i] >= 0)
dp[i][j][k] = max(dp[i][j][k], dp[i - 1][j - w[i]][k] + v[i]);
if(k - w[i] >= 0)
dp[i][j][k] = max(dp[i][j][k], dp[i - 1][j][k - w[i]] + v[i]);
ans = max(ans, dp[i][j][k]);
}
}
}
cout << ans << "\n";
}
```
:::
---
## H. different prefix product 首殺 :
這題要用到**模逆元**的概念
以下為$n$的模逆元(公式)
:::info
$inv[i]$ = $(n-n/i)$ $*$ $inv$[ $n$ % $i$ ] % $n$
:::
或者(費馬小定理推廣)
:::info
$i^{p - 2} \mod p$
:::
首先，0 必須要放在最後一位
如果0不放在最後一位，前綴積會重複出現0
例 : 0 1 2 3
其次，1必須放在第一位
如果不是放在第一位的話會出現兩個一樣的前綴積
例 : 2 1 3 0
最後，$n$必須要是質數才行
如果$n$不是質數，那麼從$1$~$n$的某些數乘起來一定會是$n$的倍數
那麼在做前綴積的時候一定會發生取mod後變成0的情況
例 : $n = 6, 2 \times 3 = 6 \times 1$
例 : $n = 9, 3 \times 6 = 9 \times 2$
但是4是例外，可以構造出1 3 2 0
綜合上述，我們可以構造出類似這樣子的東西
:::success
1, $\frac{2}{1}$, $\frac{3}{2}$, $\frac{4}{3}$, $\frac{5}{4}$, $\frac{6}{5}$.....$\frac{n - 1}{n - 2}$, $\frac{n}{n - 1}$($每一項其實就相當於 (i + 1) \times inv[i]$)
:::
::: spoiler 範例code byKCC(公式)
```cpp=
#include<bits/stdc++.h>
using namespace std;
long long inv[1000000];
int main()
{
int n;
cin >> n;
if(n == 1){
cout << "YES" << "\n";
cout << "0" << "\n";
return 0;
}
if(n == 4){
cout << "YES" << "\n";
cout << "1 3 2 0" << "\n";
return 0;
}
for(int i = 2; i * i <= n; i++){
if(n % i == 0){
cout << "NO" << "\n";
return 0;
}
}
cout << "YES" << "\n";
inv[1] = 1;
for(int i = 2; i <= n; i++) inv[i] = ((n - n / i) * inv[n % i]) % n;
cout << 1 << ' ';
for(int i = 1; i < n; i++) cout << ((i + 1) * inv[i]) % n << ' ';
return 0;
}
```
:::
:::spoiler 範例code by tw20000807(費馬小定理)
```cpp=
#include<iostream>
#define ll long long
using namespace std;
ll ans[200010];
ll fpow(ll a, ll b, ll mod){
ll re = 1;
while(b){
if(b & 1)re = re * a % mod;
b >>= 1;
a = a * a % mod;
}return re;
}
ll rev(ll a, ll mod){
return fpow(a, mod - 2, mod);
}
int main(){
int n;
cin >> n;
ans[1] = 1 % n;
if(n == 4){
cout << "YES\n";
cout << "1 3 2 0\n";
return 0;
}
for(ll i = 2; i * i <= n; i ++){
if(n % i == 0){
cout << "NO\n";
return 0;
}
}
for(int i = 2; i <= n; i++){
ans[i] = i * rev(i - 1, n) % n;
}
cout << "YES\n";
for(int i = 1; i <= n; i++)cout << ans[i] << " \n"[i == n];
}
```
:::
[別人的題解](https://blog.csdn.net/tc_to_top/article/details/43614795)
---
## I. 動態工作規劃 首殺 : blameazu.
區間求和，單點修改
可用線段樹 or BIT(樹狀數組)來操作
可是線段樹的常數比較大且實作上較複雜，所以使用BIT就可以了
:::danger
使用線段樹只能拿45分qwq(後來把題目修改成線段樹也可以過了)
:::
因為需要蓋很多棵BIT樹，所以直接多一維變成二維即可
[不知道BIT是什麼的點這裡](https://hackmd.io/@tw20000807/all/https%3A%2F%2Fhackmd.io%2F%40tw20000807%2Fdatastructure)
[或者這裡](https://www.youtube.com/watch?v=ErmFGGw7f-s)
:::spoiler 後計
後來被用前綴和過了?!?!?!
顯然測資不夠強
前綴和複雜度$O(q \times k)$
:::
::: spoiler BIT範例code byKCC
```cpp=
#include<bits/stdc++.h>
using namespace std;
#define KCC ios::sync_with_stdio(0);cin.tie(0);
long long n, k, q, ans = 0;
long long bit[25][10005];
long long ary[25][10005];
long long sum(int w, int a, int b)
{
long long k = 0, q = 0;
a--;
for(; b; b -= b & -b) k += bit[w][b];
for(; a; a -= a & -a) q += bit[w][a];
return k - q;
}
void fix(int w, int t, int x)
{
for(; t <= k; t += t & -t) bit[w][t] += x;
return ;
}
int main()
{
KCC
cin >> n >> k >> q;
for(int i = 1; i <= n; i++){
for(int j = 1; j <= k; j++)
cin >> ary[i][j];
}
for(int i = 1; i <= n; i++){
for(int j = 1; j <= k; j++) fix(i, j, ary[i][j]);
}
while(q--){
int x;
cin >> x;
if(x == 1){
int a, b;
cin >> a >> b;
long long k = 0;
for(int i = 1; i <= n; i++) k = max(k, sum(i, a, b));
ans += k;
}
else{
int w, t, x;
cin >> w >> t >> x;
fix(w, t, x - ary[w][t]);
ary[w][t] = x;
}
}
cout << ans << "\n";
}
```
:::
:::spoiler 線段樹範例code byKCC
```cpp=
#include<bits/stdc++.h>
using namespace std;
#define KCC ios::sync_with_stdio(0);cin.tie(0);
long long tree[25][40010];
long long a[25][10010];
long long n, k, q;
void build(int w, int l, int r, long long id)
{
if(l == r){
tree[w][id] = a[w][l];
return ;
}
long long mid = (l + r) >> 1;
build(w, l, mid, id * 2 + 1);
build(w, mid + 1, r, id * 2 + 2);
tree[w][id] = tree[w][id * 2 + 1] + tree[w][id * 2 + 2];
return ;
}
void fix(int w, int t, int x, int l, int r, long long id)
{
if(l == r and l == t){
tree[w][id] = x;
return;
}
long long mid = (l + r) >> 1;
if(t <= mid) fix(w, t, x, l, mid, id * 2 + 1);
else fix(w, t, x, mid + 1, r, id * 2 + 2);
tree[w][id] = tree[w][id * 2 + 1] + tree[w][id * 2 + 2];
return ;
}
long long sum(int w, int a, int b, int l, int r, long long id)
{
if(l >= a and b >= r) return tree[w][id];
long long ans = 0;
long long mid = (l + r) >> 1;
if(a <= mid) ans += sum(w, a, b, l, mid, id * 2 + 1);
if(b > mid) ans += sum(w, a, b, mid + 1, r, id * 2 + 2);
return ans;
}
int main()
{
KCC
cin >> n >> k >> q;
for(int i = 0; i < n; i++){
for(int j = 0; j < k; j++){
cin >> a[i][j];
}
}
for(int i = 0; i < n; i++) build(i, 0, k - 1, 0);
long long ans = 0;
while(q--){
int f;
cin >> f;
if(f == 1){
int a, b;
cin >> a >> b;
a--;b --;
long long wage = 0;
for(int i = 0; i < n; i++) wage = max(wage, sum(i, a, b, 0, k - 1, 0));
ans += wage;
}
else if(f == 2){
int w, t, y;
cin >> w >> t >> y;
w--;t--;
fix(w, t, y, 0, k - 1, 0);
}
}
cout << ans << "\n";
}
```
:::
:::spoiler BIT範例code by tw20000807
```cpp=
#include<iostream>
using namespace std;
int n, k, q;
int v[25][10010];
long long tree[200010];
int to(int i, int j){
return (i - 1) * k + j;
}
void update(int id, int val){
for(; id <= n * k; id += id &-id)tree[id] += val;
}
long long query(int id){
long long re = 0;
for(; id; id -= id&-id)re += tree[id];
return re;
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
cin >> n >> k >> q;
for(int i = 1; i <= n; i++){
for(int j = 1; j <= k; j++){
cin >> v[i][j];
update(to(i, j), v[i][j]);
}
}
long long ans = 0;
while(q--){
int t; cin >> t;
if(t == 1){
int a, b;
long long mx = 0;
cin >> a >> b;
for(int i = 1; i <= n; i++)
mx = max(mx, query(to(i, b)) - query(to(i, a) - 1));
ans += mx;
}
if(t == 2){
int w, t, x;
cin >> w >> t >> x;
update(to(w, t), x - v[w][t]);
v[w][t] = x;
}
}
cout << ans << "\n";
}
```
:::
---
## J. 糖果傳奇 首殺 : blameazu.
這題主要考stl的操作及使用
可以利用 $map<int, set<int>> xy, yx$來操作
xy代表在x這個鉛直線上有哪些條紋糖果及他們的y座標
yx代表在y這個水平線上有哪些條紋糖果及他們的x座標
用一個queue來記錄哪些條紋糖果爆炸了
然後再分別檢查x座標及y座標的哪些條紋糖果會被炸到
一直重複做，直到所有爆炸了的條紋糖果
:::warning
後來發現其實用pair就可以了
:::
:::spoiler 範例code byKCC
```cpp=
#include<bits/stdc++.h>
using namespace std;
map<int, set<int>> xy, yx;
int main()
{
int k, x0, y0, ans = 1;
cin >> k;
cin >> x0 >> y0;
for(int i = 0; i < k - 1; i++){
int a, b;
cin >> a >> b;
xy[a].insert(b);
yx[b].insert(a);
}
queue<pair<int, int>> q;
q.push({x0, y0});
while(!q.empty()){
pair<int, int> f = q.front();
q.pop();
vector<pair<int, int>> v;
for(int i : xy[f.first]) v.push_back({f.first, i});
for(int i : yx[f.second]) v.push_back({i, f.second});
for(pair<int, int> i : v){
ans++;
q.push(i);
xy[i.first].erase(i.second);
yx[i.second].erase(i.first);
}
}
cout << k - ans << "\n";
}
```
:::
::: spoiler 範例code by tw20000807
```cpp=
#include<bits/stdc++.h>
#define pii pair< int, int >
#define X first
#define Y second
using namespace std;
map< int, set<int> > xy, yx;
int main(){
int k, a, b;
cin >> k;
int x0, y0;
cin >> x0 >> y0;
for(int i = 1; i < k; i++){
cin >> a >> b;
xy[a].insert(b);
yx[b].insert(a);
}
vector< pii > stk;
int ans = 1;
stk.push_back({x0, y0});
while(!stk.empty()){
pii cur = stk.back(); stk.pop_back();
vector< pii > clr;
for(int i : xy[cur.X]){
clr.push_back({cur.X, i});
}
for(int i : yx[cur.Y]){
clr.push_back({i, cur.Y});
}
for(pii i : clr){
ans++;
stk.push_back(i);
xy[i.X].erase(i.Y);
yx[i.Y].erase(i.X);
}
clr.clear();
}
cout << k - ans << "\n";
}
```
:::
::: spoiler 範例code by yuzhe097
```cpp=
#include<bits/stdc++.h>
#define ll long long
#define pf p[i].first
#define ps p[i].second
using namespace std;
ll n , x , y , ans;
pair<ll , ll> p[2000000];
bool pq[2000000];
int f( ll x , ll y ){
for( ll i = 0 ; i < n-1 ; i++ ){
if( pf == x && !pq[i] ){
pq[i] = 1;
ans --;
f( pf , ps );
}
if( ps == y && !pq[i]){
pq[i] = 1;
ans --;
f( pf , ps );
}
}
return 0;
};
int main(){
cin >> n >> x >> y;
ans = n-1;
for( ll i = 0 ; i < n-1 ; i++ ){
cin >> pf >> ps;
}
f(x,y);
cout << ans << '\n';
}
```
:::
---
<!-- ## Multiplication Table
:::success
中位數的意思是前面有一半的數字小於或等於中位數，也就是有$n \times n / 2$個數字小於或等於中位數
:::
我們可以利用二分搜找出答案
每次利用
```cpp
for(int i = 1; i <= n; i++) cnt += min(n, mid / i);
```
找出小於mid的數字數量
其中，$mid / i$ 代表 $i$ 的倍數有幾個比 $mid$ 小
因為最多只會有 $n$ 個數字(題目限制說的)，所以跟 $n$ 取 $min$
這裡$r$不能 $= mid - 1$，因為$mid - 1$不一定能夠滿足前面有$n \times n / 2$個數字小於或等於$mid - 1$
而$l$則一定要是$mid + 1$，因為$mid$已經確定不符合條件了
如果剛好有 $n \times n / 2$個數字 $\leq mid$ 那就輸出$mid + 1$
因為
---
-->
## 我超棒
## 注意
由於測資都是隨機生成且沒有特別去卡假解，因此可能會被一些假解唬爛過去，也可能官解本身就是錯的，有任何問題可以到 https://hackmd.io/@tw20000807/T26_winter/edit 回報
我不會出題
好多題被假解唬爛過去
Sign in with Wallet
Connect another wallet