T1

一道非常簡單的題，結果我因為一句話沒寫掛了 80pts……

題目中沒寫 $a$ 數組要按照 $b$ 數組的順序，所以對于最大方案，我們需要從最小的開始，這樣后面的才有可能填上。

所以一開始我們要先對 $b$ 數組從小到大排序（我就是少寫了這一行……），然后我們就可以開始算方案數了，怎么算呢？

很簡單，首先對于 $a_1$，它前面沒有任何數，所以它能取的方案書就是 $b_1$，然后思考 $a_2$，它前面已經有一個數被選了（因為從小到大排序后后面的數一定包含了前面的數），所以對于 $a_2$ 來講它有 $b_2?1$ 種選擇，然后是 $a_3,a_4\dots$，一直到 $a_n$，這時我們很容易發現：對于 $a_i$ 來講，它有 $b_i?i+1$ 種選擇，再根據乘法原理可知答案是：

$$ans=\prod _{i=1}^n{b}_i?i+1$$

然后直接輸出答案即可。

（老規矩。）

T2

這道題很簡單，這里我提供三種做法。

在此之前，我們首先要確定一件事：如果牛郎與織女之間的距離是一個奇數，那么他們會在橋上，否則會在星球上。接下來就是怎么求距離的問題了。

法一：倍增求 LCA

我們可以通過倍增求 LCA 并記錄下距離，代碼很簡單，時間復雜度：$O(Q{\log }_2(N))$。

代碼：

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,q,l,depth[100006],st[100006][26];
vector<int>v[100006];
void LCA(int x,int y)
{if(depth[x]<depth[y]){swap(x,y);}for(int i=20;i>=0;i--){if(depth[st[x][i]]>=depth[y]){x=st[x][i];l+=(1<<i);}}//這里為了節省時間，我直接把后面求 LCA 的過程省略了。//因為后面的跳動都是兩邊同時跳，那么每次加的距離都是偶數，而加偶數并不會改變它的奇偶性。
}
void dfs(int x,int deep,int fa)
{st[x][0]=fa;depth[x]=deep;for(auto i:v[x]){if(i==fa){continue;}dfs(i,deep+1,x);}
}
signed main()
{// freopen("bridge.in","r",stdin);// freopen("bridge.out","w",stdout);cin>>n>>q;for(int x,y,i=1;i<n;i++){cin>>x>>y;v[x].emplace_back(y);v[y].emplace_back(x);}dfs(1,1,0);for(int i=1;i<=20;i++){for(int j=1;j<=n;j++){st[j][i]=st[st[j][i-1]][i-1];}}while(q--){int x,y;l=0;cin>>x>>y;LCA(x,y);if(l&1){cout<<"Y"<<endl;}else{cout<<"N"<<endl;}}return 0;
}

法二：Dijkstra 求最短路

我們可以把它看作一張圖，然后直接跑最短路。

（我沒有代碼，讀者自己寫吧……）

法三：dfs 求深度

我們可以把兩點間距離，看作是兩點間的深度之和，然后判斷奇偶。

代碼（題解的）：

#include <bits/stdc++.h>
#include <stdio.h>
using namespace std;
int n, q, a, b;
vector<vector<int>> s(1e5 + 1);
vector<int> d(1e5 + 1, 1e5);
void dfs(int x, int y) {d[x] = y;for (auto p : s[x]) {if (d[p] > y + 1) {dfs(p, y + 1);}}
}
int main() {cin >> n >> q;for (int i = 0; i < n - 1; i++) {cin >> a >> b;s[a].push_back(b);s[b].push_back(a);}dfs(1, 0);for (int i = 0; i < q; i++) {cin >> a >> b;cout << (((d[a] + d[b]) % 2 == 0) ? "N" : "Y") << endl;}
}

三種方法，任你選擇。

T3

一道不是很簡單的題……

我的基礎想法是用 tarjan 縮點然后再做，但是圖不連通，那么跑 tarjan 的時間復雜度就到了 $O(n^2)$，所以明顯不行。

然后我又思考過跑 dfs 來找連通塊，結果時間復雜度還是 $O(n^2)$。

于是就只有一種方法了：并查集！

然后我們就可以標記連通塊了。

當然，我們肯定要用個 vector 保存下來每個連通塊內的點，接下來又該怎么做呢？

我們要代價最小，說白了就是找離 $i$ 最近的點 $j$，然后我就有了一個想法：二分！（從時間復雜度上也看得出來是 $O(T\times N{\log }_2(N))$）

我們可以用 lower_bound 找出第一個大于等于 $i$ 的點，那么它的上一個就是最后一個小于 $i$ 的點，這兩個點就必然是離 $i$ 最近的兩個點，然后記錄下來就行了。

我們要讓 $1$ 能到 $n$ 連通，那么我們就只需要稍微改一下上面的過程：在包含的 $1$ 這個連通塊里面二分找第 $i$ 個點的 lower_bound。

因為二分需要單調性，所以我們可以在這之前對每個連通塊里面的點排序一下，但這明顯會 $TLE$，又該怎么優化呢？

很簡單，我們只需要請出排序的“老大哥”——set。我們把 vector 換成 set 就行了。

然后就水靈靈的 $AC$ 了！

代碼：

#include<bits/stdc++.h>
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
using namespace std;
int t,n,m,num,ans=INF,fa[100006],col[100006],b[100006],cost[2][100006];
set<int>s[100006];
int find(int x)
{if(fa[x]==x){return x;}return fa[x]=find(fa[x]);
}
signed main()
{cin>>t;while(t--){ans=INF;//初始化！！！for(int i=1;i<=num;i++){s[i].clear();}num=0;memset(b,0,sizeof(b));memset(col,0,sizeof(col));cin>>n>>m;for(int i=1;i<=n;i++){fa[i]=i;}for(int i=1,x,y;i<=m;i++){cin>>x>>y;int xb=find(x);int yb=find(y);if(xb!=yb){fa[yb]=xb;}}if(find(1)==find(n)){cout<<0<<endl;continue;}for(int i=1;i<=n;i++){if(!b[find(i)]){b[find(i)]=col[find(i)]=++num;s[num].insert(i);}else{col[find(i)]=b[find(i)];s[col[find(i)]].insert(i);}}memset(cost,INF,sizeof(cost));for(int i=1;i<=n;i++){if(find(i)==find(1)){continue;}auto it=s[col[find(1)]].lower_bound(i);auto it1=it;if(it1==s[col[find(1)]].end()){it1--,it--;}else if(it1==s[col[find(1)]].begin());else{it--;}cost[0][col[find(i)]]=min({cost[0][col[find(i)]],((*it)-i)*((*it)-i),((*it1)-i)*((*it1)-i)});}for(int i=1;i<=n;i++){if(find(i)==find(n)){continue;}auto it=s[col[find(n)]].lower_bound(i);auto it1=it;if(it1==s[col[find(n)]].end()){it1--,it--;}else if(it1==s[col[find(n)]].begin());else{it--;}cost[1][col[find(i)]]=min({cost[1][col[find(i)]],((*it)-i)*((*it)-i),((*it1)-i)*((*it1)-i)});}for(int i=1;i<=n;i++){if(find(i)==find(1)){continue;}else if(find(i)==find(n)){ans=min(ans,cost[0][col[find(n)]]);}else{ans=min(ans,cost[0][col[find(i)]]+cost[1][col[find(i)]]);}}cout<<ans<<endl;}return 0;
}

當然，這份代碼稍微復雜了點，看看題解代碼：

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define N 100010
int n, m, i, j, k;
set<int>s[N];
set<int>::iterator it, jt, kt;
int f[N], p[N], u, v, a, b, ans, t;
int fa(int x) {return f[x]==x ? x : f[x]=fa(f[x]);
}
int pingfang(int x) {return x*x;
}
int len(int x, int y) {int ans=1e18;for(it=s[x].begin(); it!=s[x].end(); ++it) {jt=s[y].lower_bound(*it);if(jt!=s[y].end()) ans=min(ans, pingfang((*jt)-*it));if(jt!=s[y].begin()) ans=min(ans, pingfang((*(--jt))-*it));}return ans;
}
signed main() {scanf("%lld", &t);while(t--) {scanf("%lld%lld", &n, &m);for(i=1; i<=n; ++i) f[i]=i;for(i=1; i<=n; ++i) s[i].clear();for(i=1; i<=m; ++i) scanf("%lld%lld", &u, &v), f[fa(u)]=fa(v);for(i=1; i<=n; ++i) s[fa(i)].insert(i);a=f[1];b=f[n];ans=len(a, b);for(i=1; i<=n; ++i) {if(f[i]==a||f[i]==b||f[i]!=i) continue;ans=min(ans, len(i, a)+len(i, b));}printf("%lld\n", ans);}return 0;
}

真簡略……

T4

我的評價：特別簡單但是很迷惑人……

這題看上去很復雜，實則一點也不復雜。

對于 50pts，我們可以這么思考：如果兩個點之間可以互相運送垃圾，則連上一條邊，那么同一個連通分量中，所有的垃圾都可以匯集到一個點上，所以問題等價于詢問圖中有多少個連通分量。

但是這樣做最壞情況下時間復雜度為 $O(n^2)$，所以我們肯定要換種方法。

（由于作者實在不是很會描述（懶），于是貼上了一份題解。）

我們對所有點按照 $x$ 坐標排序，如果前面的點中 $y$ 的最小值小于當前點，我們則對這兩個點連邊。
同時我們倒序遍歷，如果后面點的 $y$ 的最大值大于當前點，我們則對這兩個點連邊。
這樣邊的數量就降為了 $O(n)$。

（說實話，我也沒太看懂……只是大致有感覺。）

代碼：

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,x[100006],y[100006],mny[100006],mxy[100006],a[100006];
bool cmp(int xx,int yy)
{return x[xx]<x[yy]||x[xx]==x[yy]&&y[xx]<y[yy];
}
signed main()
{cin>>n;for(int i=1;i<=n;i++){cin>>x[i]>>y[i];a[i]=i;}sort(a+1,a+n+1,cmp);mny[1]=y[a[1]];for(int i=2;i<=n;i++){mny[i]=min(mny[i-1],y[a[i]]);}mxy[n]=y[a[n]];for(int i=n-1;i>=1;i--){mxy[i]=max(mxy[i+1],y[a[i]]);}int ans=1;for(int i=1;i<n;i++){if(mny[i]>mxy[i+1]){ans++;}}cout<<ans;return 0;
}

總結

1. T1： 本來應該 $AC$ 的，結果掛了 80pts……
2. T2： 完美 $AC$！
3. T3： 理論上來講可以拿到 50pts，但因為一些奇奇怪怪的計算機底層問題而 $WA$ 了……（還有 $TLE$。）
4. T4： 根本不會，直接輸出了樣例，騙到 8pts。

總分：129pts，滿分 400pts，反正我不滿意。