整體概述

• 難度：1000 $\to$ 1500 $\to$ 2000

---

1567B. MEXor Mixup

• 標簽：前綴和

• 前置知識：無

• 難度：Div.2.B 1000

題目描述：

輸入格式：

輸出格式：

樣例輸入：

5
1 1
2 1
2 0
1 10000
2 10000

樣例輸出：

3
2
3
2
3

解題思路：

• 首先我們知道，想要讓 $MEX=a$ 則 $[0,a?1]$ 范圍內的數都得選，發現 $1\le a\le 3?10^5$ 那么我們可以預處理出所有 $[0,x]$ 的異或和。

• 接著要讓 $xor=b$，我們設 $xo{r}_{i=0}^a?1=c$，那么還差 $b^c$ 就可以湊出該數字。

• 需要注意的是如果 $c=a$，那么我們需要拿兩個數字湊出 $c$，否則只需要直接再增加一個 $c$ 即可。

  如果 $c=0$ 表示直接湊出 $b$ 了，那么不需要再加數字了。

• 預處理出前綴異或和，查詢復雜度 $O(1)$，總復雜度 $O(3?10^5)$。

完整代碼

#include<bits/stdc++.h>
#define Size(x) ((int)(x).size())
#define int long long
using namespace std;
const int N = 3e5+5;
int pre[N];
inline void solve(){int a,b; cin >> a >> b;int c = pre[a-1]^b;if(!c) cout << a << '\n';else if(c == a) cout << a+2 << '\n';else cout << a+1 << '\n';
}
signed main(){ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);int T; cin >> T;for(int i=1;i<N;i++) pre[i] = pre[i-1]^i; while(T--) solve();return 0;
}

---

501C. Misha and Forest

• 標簽：拓撲排序

• 前置知識：無

• 難度：Div.2.C 1500

題目描述：

輸入格式：

輸出格式：

樣例輸入：

3
2 3
1 0
1 0

2
1 1
1 0

樣例輸出：

2
1 0
2 0

1
0 1

解題思路：

• 由于是一片森林，不存在環，那么一定有某些節點的度為 $1$，而我們又知道這些節點的相鄰節點編號的異或和，就是相鄰節點的編號，那么這些邊就都可以確定了。

• 接著在未確定的邊中刪去這些邊，就會又有某些節點度為 $1$，這個過程其實就是拓撲排序的過程，我們跑一遍拓撲排序，每次連邊即可。

  需要注意的是，如果出隊列的點度為 $0$ 表明已經連過了，此時跳過即可。

• 總復雜度 $O(n)$。

完整代碼

#include<bits/stdc++.h>
#define Size(x) ((int)(x).size())
#define int long long
using namespace std;
const int N = (1<<16)+5;
int n,d[N],eor[N];
vector<pair<int,int>> res;
inline void solve(){cin >> n;for(int i=0;i<n;i++) cin >> d[i] >> eor[i];queue<int> qu;for(int i=0;i<n;i++) if(d[i] == 1) qu.push(i);while(!qu.empty()){int u = qu.front(); qu.pop();int v = eor[u];if(!d[u]) continue;res.push_back({u,v});eor[v] ^= u;if(--d[v] == 1) qu.push(v);}cout << res.size() << '\n';for(auto [u,v]:res) cout << u << ' ' << v << '\n';
}
signed main(){ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);int T; T = 1;while(T--) solve();return 0;
}

---

755D. PolandBall and Polygon

• 標簽：樹狀數組

• 前置知識：無

• 難度：8VC Venture Cup 2017.D 2000

題目描述：

輸入格式：

輸出格式：

樣例輸入：

5 2

10 3

樣例輸出：

2 3 5 8 11 

2 3 4 6 9 12 16 21 26 31 

解題思路：

• 通過畫圖我們發現，$畫一條線增加的區域數$ 等同于 $與原有線段的交點個數+1$，所以問題就轉化為每次給出線段的兩個端點，求有多少個交點。

• 我們發現所有相交線段的兩個端點分別位于線段兩側，即有且僅有一個端點在新線段的 $(l,r)$ 間。由于每條線段兩個端點間的距離是固定的，因此我們僅需統計在 $(l,r)$ 內的節點的總度數，即為交點個數。

  需要注意的是，我們用的 $[l,r]$ 區間需要是劣弧的那一段。

• 那么我們用樹狀數組進行單點修改，區間查詢，總復雜度 $O(n?lo{g}_{2}n)$。

完整代碼

#include<bits/stdc++.h>
using namespace std;
const int N = 1e6+5;
int n,k,tr[N];
inline void add(int x,int v){for(int i=x;i<=n;i+=i&-i) tr[i] += v;
}
inline long long sum(int l,int r){if(l > r) return 0;long long ans = 0;for(int i=r;i;i&=i-1) ans += tr[i];for(int i=l-1;i;i&=i-1) ans -= tr[i];return ans;
}
inline void solve(){cin >> n >> k;long long ans = 1;for(int i=1,p=1,l,r,cur;i<=n;i++){l = p,r = p = l+k > n ? l+k-n : l+k;if(l > r) swap(l,r);cur = (r-l-1) <= (n-r+l-1) ? sum(l+1,r-1) : sum(r+1,n) + sum(1,l-1); ans += cur+1;cout << ans << ' ';add(l,1), add(r,1);}
}
signed main(){ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);int T; T = 1;while(T--) solve();return 0;
}

---