# CF - Round #764 (Div. 3) 個人題解 (2022.1.10)
###### tags: `CF題解` `div3` `CF`
https://codeforces.com/contest/1624
這次用小帳打，結果戳完最後一題就沒時間了

## [pF Interacdive Problem](https://codeforces.com/contest/1624/problem/F)
根本水題
有夠水
奇怪這題怎麼反而少那麼多人
補題大概花了$15$分鐘就一次 <font color=greennn>$AC$</font>
### 想法
發現每次加法，可以區別一半的候選人和另一半候選人。然後用讀進來的結果二分（每次砍一半的候選人）就好了。

:::spoiler Code

int n;
int ask(int x){
    cout<<"+ "<<x<<endl;
    cout.flush();
    int res;cin>>res; return res;
}
signed main(){
    cin>>n;
    int left=1,right=n-1,mid=(left+right)/2;
    int now = 0;
    while(left<right){
        mid = (left+right)/2;
        int q = (1+mid/n)*n - mid - 1;
        int res = ask(q);
        left+=q; right+=q;
        
        if (res==now){
            right=mid+q;
        }else{
            left=mid+q+1;
            now++;
        }
    }
    cout<<"! "<<left<<endl;
    cout.flush();
}
:::

#### Complexity:  --
#### Difficulty:
<font color=pink>根本水題</font> 
#### Status:  --

---

## [pG MinOr Tree](https://codeforces.com/contest/1624/problem/G)

這題我覺得很不錯，但不知道為什麼那麼多人寫出來...
在得出這個簡潔的想法之前，我也繞了很久
### 題意：
> 給你一張圖，找到他的最小bitwise or生成樹。輸出or完的結果就好。
> $n,m \le 2\times 10^5$，$w_i \le 10^9$。
### 觀察
一開始沒什麼想法，那麼我們先試試二進位題目的常用手法---分bit！
要怎麼分呢？
我們先把所有邊權寫成二進位試試。

<img src="https://i.imgur.com/X5B3La7.png" width = "300" height = "350">

<font size="2">這是範側2，2號和4號點中間有重邊111和010</font>


由於or的特性（選了越大的bit，or出來的結果就越大），所以先從大的bit開始看！

1. 假設我們把「有8這個bit的邊」拿掉(2和5間的1000)，那圖就不聯通了，無法形成生成樹。所以這條邊一定要留著。這也代表***答案一定有8這個bit***！！！
2. 假設我們把「有4這個bit的邊」拿掉(4和2間的111)，那圖還是聯通的。所以這條邊不選在生成樹也沒差。
3. 同理，假設我們把「有2這個bit的邊」拿掉，圖就整個支離破碎，所以（不管最後生成樹怎麼選）答案一定有2這個bit。
4. 同理，答案沒有1這個bit。

這時候發現題目等價於：你可以花$2^i$元把一些點聯通，求把整張圖聯通的最小花費！！

### 解法
這時候的想法：假設整個圖原本每條邊都存在，那我每次要拔掉「所有有這個bit的邊」，醬答案就一定沒有那個bit。如果圖還是聯通的，那就很棒，我就把邊全部拔完，答案也可以變小！如果圖不聯通，那答案就一定有這個bit。

可是dsu沒辦法做拔掉啊？？？

不用啦，跑dfs就好了，然後暴力（？）檢查是否每個點都有走到。這件事做30次，同時也要紀錄＋更新目前的答案。

:::spoiler My Code

#define pii pair<int,int>
#define mp make_pair
vector<pii> adj[200005];
int n,m;

int vis[200005];
void dfs(int node,int rev){
vis[node]=true;
for (pii p:adj[node]){
int u=p.first, w=p.second;
if (vis[u]) continue;
if (w & rev) continue;
dfs(u,rev);
}
}

signed main(){
int t;cin>>t;while(t--){
cin>>n>>m;

for (int i=1;i<=n;i++) adj[i].clear();
for (int i=0;i<m;i++){
int a,b,c;cin>>a>>b>>c;
adj[a].push_back(mp(b,c));
adj[b].push_back(mp(a,c));
}

int ans = 2147483647, rev = 0;
for (int k=30;k>=0;k--){
int tmp = rev + (1<<k);
for (int i=1;i<=n;i++) vis[i]=false;
dfs(1,tmp);

int flag=true;
for (int i=1;i<=n;i++) if (!vis[i]) {flag=false; break;}

if (flag){
ans -= (1<<k);
rev += (1<<k);
}
}
cout<<ans<<endl;
}
}
:::
#### Complexity:
$O(nlog(w))$
#### Difficulty:
<font color=#C0C102>偏難</font>
#### Status:
<font color=greennn>AC</font> 102 min<font color=red>(3)</font>