Google Drive
Gist
Clipboard
APCSpeienwu
thanksone
Sun, Nov 7, 2021 8:06 PM
如果在兩端就直接取旁邊的高度，否則取跟左右邊高度的最小值。
\(O(n)\)
#include <bits/stdc++.h>
#define int long long
#define N 105
#define IOS ios::sync_with_stdio(0),cin.tie(0)
using namespace std;
int n,A[N];
signed main(){
IOS;
cin>>n;
for(int i=0;i<n;i++)cin>>A[i];
int ans = 0;
if(A[0] == 0)ans += A[1];
if(A[n-1] == 0)ans += A[n-2];
for(int i=1;i<n-1;i++){
if(A[i] == 0)ans += min(A[i-1],A[i+1]);
}
cout<<ans<<endl;
}
peienwu
把線分成橫的跟直的就可以好好處理交叉了!
\(O(h(n + m))\)
#include <bits/stdc++.h>
using namespace std;
int n, m, cnt = 0, ans = 0;
array<array<int, 104>, 104> R, C, I;
void add(int r, int c){
bool ok;
I[r][c] = 1;
cnt++;
if(C[r][c] || R[r][c]) cnt--;
C[r][c] = R[r][c] = 0;
ok = 0; //直下情況
for(int i = r + 1; i < n; i++){
if(I[i][c]) ok = 1;
}
if(ok){
for(int i = r + 1; i < n; i++){
if(I[i][c] || R[i][c]) break;
R[i][c]++;
cnt += C[i][c] == 0;
}
}
ok = 0; //直上情況
for(int i = r - 1; i >= 0; i--){
if(I[i][c]) ok = 1;
}
if(ok){
for(int i = r - 1; i >= 0; i--){
if(I[i][c] || R[i][c]) break;
R[i][c]++;
cnt += C[i][c] == 0;
}
}
ok = 0; //橫右情況
for(int i = c + 1; i < m; i++){
if(I[r][i]) ok = 1;
}
if(ok){
for(int i = c + 1; i < m; i++){
if(I[r][i] || C[r][i]) break;
C[r][i]++;
cnt += R[r][i] == 0;
}
}
ok = 0; //橫左情況
for(int i = c - 1; i >= 0; i--){
if(I[r][i]) ok = 1;
}
if(ok){
for(int i = c - 1; i >= 0; i--){
if(I[r][i] || C[r][i]) break;
C[r][i]++;
cnt += R[r][i] == 0;
}
}
}
void pull(int r, int c){
I[r][c] = 0;
cnt--;
for(int i = r + 1; i < n; i++){ //直下情況
if(!R[i][c]) break;
R[i][c]--;
cnt -= C[i][c] == 0;
}
for(int i = r - 1; i >= 0; i--){ //直上情況
if(!R[i][c]) break;
R[i][c]--;
cnt -= C[i][c] == 0;
}
for(int i = c + 1; i < m; i++){ //橫右情況
if(!C[r][i]) break;
C[r][i]--;
cnt -= R[r][i] == 0;
}
for(int i = c - 1; i >= 0; i--){ //橫左情況
if(!C[r][i]) break;
C[r][i]--;
cnt -= R[r][i] == 0;
}
}
signed main(){
int h, r, c, t;
cin >> n >> m >> h;
while(h--){
cin >> r >> c >> t;
if(t){
pull(r, c);
}else{
add(r, c);
}
ans = max(ans, cnt);
}
cout << ans << "\n" << cnt;
return 0;
}
thanksone
用差分的想法加值，再用前綴還原，最後再排序。最後利用Greedy的想法，將每一項最小的工作量乘上最大的時間，總和即為答案。
差分
差分是前綴和的逆運算，也就是說，把兩項的差算出來就是差分。定義如下：
\[b_i = \begin{cases}a_i-a_{i-1}, &\text{if }i\gt 1 \\a_1, & \text{if } i = 1\end{cases}\]
差分的使用時機是區間加值，一個區間內的數字都加上一個定值，這時候就可以使用到差分的技巧。使用方式如下，當我要在區間 \([l,r]\) 的每一個數字都加上一個值\(v\)，以下步驟：
第二步驟可以重複好幾次做，這樣複雜度從原本的\(O(n)\)就變成了\(O(1)\)了！
差分：\(O(m)\) 、排序 \(O(n\log n)\)
總時間複雜度：\(O(n\log n + m)\)
#include <bits/stdc++.h>
#define int long long
#define N 200005
#define IOS ios::sync_with_stdio(0),cin.tie(0)
using namespace std;
int n,m,A[N],B[N];
signed main(){
IOS;
memset(A,0,sizeof(A));
cin>>n>>m;
while(m--){
int x,y,w;cin>>x>>y>>w;
A[x] += w;
A[y+1] -= w;
}
for(int i=1;i<=n;i++)cin>>B[i];
for(int i=1;i<=n;i++)A[i] = A[i] + A[i-1];
sort(A+1,A+n+1);
sort(B+1,B+n+1);
int ans = 0;
for(int i=1;i<=n;i++){
ans += A[i] * B[n-i+1];
}
cout<<ans<<endl;
}
peienwu
很奇怪，最近兩次的APCS第三題都有人想要砸資結，特別是線段樹，可能有些人特別偏愛線段樹吧！
線段樹最原本的應該是區間詢問、單點修改，如果要區間修改的話就會用到懶標，所以實作上相對上比較複雜一點。這一題用線段樹的目的是區間加值，加值完過後的排序以及Greedy跟差分的作法是一樣的，用線段樹真的是多此兩舉（實作較複雜、較耗時）！
當然，這一題比較特別只有最後一起做單點查詢，因此不用懶標，最侯直接計算一路去經過的答案也行！下面的程式碼就是把完全包含區間的節點加值，不用使用到懶標，最後一次查詢。
區間加值 \(O(m\log n)\)，n個點的詢問 \(O(n\log n)\)，排序 \(O(n\log n)\)
總時間複雜度：\(O((n+m)\log n)\)
#include <bits/stdc++.h>
#define int long long
#define N 200005
#define IOS ios::sync_with_stdio(0),cin.tie(0)
using namespace std;
int n,m,t,A[N],B[N],ans = 0;
struct node{
int val = 0,sz;
}seg[4*N];
void build(int id,int l,int r){
seg[id].sz = r - l;
if(r - l <= 1)return;
int mid = (l + r) / 2;
build(id*2,l,mid);
build(id*2+1,mid,r);
}
void modify(int id,int l,int r,int ql,int qr,int val){
if(r <= l || r <= ql || l >= qr)return;
if(ql <= l && qr >= r){
seg[id].val += val;
return;
}
int mid = (l + r) / 2;
modify(id*2,l,mid,ql,qr,val);
modify(id*2+1,mid,r,ql,qr,val);
}
void query(int id,int l,int r,int val){
if(r <= l)return;
ans += seg[id].val;
if(r - l == 1)return;
int mid = (l + r) / 2;
if(val < mid)return query(id*2,l,mid,val);
else return query(id*2+1,mid,r,val);
}
signed main(){
IOS;
cin>>n>>m;
build(1,1,n+1);
while(m--){
int x,y,w;cin>>x>>y>>w;
y++;
modify(1,1,n+1,x,y,w);
}
for(int i=1;i<=n;i++){
ans = 0;query(1,1,n+1,i);
A[i] = ans;
}
for(int i=1;i<=n;i++)cin>>B[i];
sort(A+1,A + n + 1);
sort(B+1,B + n + 1);
int ans = 0;
for(int i=1;i<=n;i++)ans += A[i] * B[n-i+1];
cout<<ans<<endl;
}
一開始看到這題，應該很難通靈出二分搜這個作法（我覺得光把題目看懂就有點難度了）。這題有一個條件要特別注意：
保證若調查員的 k 個 pair 的結果和組長存留的 m 個 pair 不會產生矛盾, 則保證調查員的資料一定和原本 A, B 分組吻合
這一題每一個觀察員並可看成不是獨立的（假如一個觀察員不產生矛盾，則他回傳的那一些邊都會被沿用），所以題目 \(p\) 筆詢問可以聯集一起處理。
將情報員當成點，合作關係當成邊，那麼合法的圖就會有兩個點集，點集中的點互不相鄰，也就是二分圖。
二分搜第一個使得圖變得不二分的人，把它消失，最多重複3次就做完了。
為什麼可以二分搜？
二分搜是用來找一串01字串的分界點，並且必須具有單調性才能二分搜。這一題之所以會有單調性是因為，當我查詢觀察員 \(P_i\) 的回傳資料是否正確時，會將前面 \(P_1\) 到 \(P_{i-1}\) 觀察員回傳的所有邊納入考慮。
假設有一個觀察員 \(P_j (1\le j < i)\) 回傳的資料是錯誤的，這些邊會導致整張圖變成非二分圖，對於 \(j\) 後面的所有點來說，都是非二分圖。這樣就有了以 \(j\) 為分界點的單調性，即可二分搜。
二分圖判斷可以用 \(dfs\) 做，\(dfs\) 的時候把每個點塗上顏色，如果相鄰的點跟自己顏色一樣就表示這不是一張二分圖。
\(O((n + m + pk)\log p)\)
#include <bits/stdc++.h>
#define pb push_back
#define mid (l + r) / 2
using namespace std;
struct e{
int u, v;
};
int n;
array<bool, 10004> WA; //不可行的觀察員編號
array<int, 20004> vis; //DFS是否走訪、二分圖顏色
array<vector<e>, 10004> E; //每一個觀察員的回傳邊
array<vector<int>, 20004> G; //存進行DFS的圖
bool dfs(int u, int t){ //用DFS塗色、判斷二分圖
if(vis[u]) return 1;
bool ans = 1;
vis[u] = t;
for(int v : G[u]){
if(vis[v] == t) return 0;
ans &= dfs(v, 3 - t);
}
return ans;
}
bool check(int p){ //檢查第p個觀察員回傳是否正確
bool ans = 1;
for(int i = 0; i < n; i++){
G[i].clear();
vis[i] = 0;
}
for(int i = 0; i <= p; i++){
for(auto [u, v] : E[i]){ //將觀察員的邊推入G
G[u].pb(v);
G[v].pb(u);
}
}
for(int i = 0; i < n; i++){
ans &= dfs(i, 1); //將每一個連通塊
}
return ans;
}
void BS(int l, int r){ //二分搜觀察員
if(check(r)) return; //當邊的連集不會讓圖有問題，則回傳
while(l != r){
if(check(mid)) l = mid + 1;
else r = mid;
}
WA[l] = 1;
E[l].clear(); //剔除一錯誤觀察員
}
signed main(){
int m, p, k, a, b;
cin >> n >> m;
while(m--){
cin >> a >> b;
E[0].pb({a, b});
}
cin >> p >> k;
for(int i = 1; i <= p; i++){
for(int j = 0; j < k; j++){
cin >> a >> b;
E[i].pb({a, b});
}
}
for(int i = 0; i < 3; i++){ //至多三個觀察員
BS(0, p);
}
for(int i = 1; i <= p; i++){
if(WA[i]) cout << i << "\n";
}
return 0;
}
thanksone
Idea From Kennyfs
這一題的題目限制有說最多3個錯誤的情報員，因此我們可以用上面二分搜的方式做三次找到答案。如果題目不限制錯誤調查員的數量，也就是用二分搜時間會超時，但是用DSU可以在線性時間內完成！
DSU的目的在處理集合問題，根據下面這個關鍵條件：
保證若調查員的 k 個 pair 的結果和組長存留的 m 個 pair 不會產生矛盾, 則保證調查員的資料一定和原本 A, B 分組吻合
我們只要對每一筆詢問看會不會與組長手中的pair矛盾即可。如果每一次都做DFS，會發現時間複雜度是 \(O(pn)\)，必然超時。
DSU的想法是，我們將組長手中的圖中上每一個連通塊都分別塗上兩種顏色（必為二分圖，因此將兩邊各塗上不同顏色）。接著，把每個顏色當作初始的並查集中的集合，將每一筆觀察員回傳的邊的兩端指向的集合合併起來，過程中如果發生邊的兩端同屬一個集合，表示這是一個錯誤的觀察員。做完每一個觀察員之後，把所有變更過的還原成初始狀態（組長手中的圖）即可。
舉例
8 5
0 2 1 3 1 2 4 6 5 6
1 2
1 4 0 6
整個過程就是下面這張GIF：
步驟：
\(O(n + pk\alpha)\)
#include <bits/stdc++.h>
#define IOS ios::sync_with_stdio(0),cin.tie(0)
#define int long long
#define N 20005
#define M 10005
using namespace std;
int n,m,p,k;
int color[N],boss[N],num[N];
bool WA[M],f;
int other(int s){return (s%2)?s+1:s-1;} //other為同一連通塊另外一種顏色
vector<int> edge[N],change;
void init(){ //初始化
memset(color,0,sizeof(color));
memset(WA,0,sizeof(WA));
}
void dfs(int id,int col){ //對所有點上色
color[id] = col;
for(auto i:edge[id]){
if(!color[i])dfs(i,other(col));
}
}
int find_boss(int id){ //尋找祖先、及路徑壓縮
if(boss[id] == id)return id;
change.push_back(id);
return boss[id] = find_boss(boss[id]);
}
signed main(){
IOS;
init();
cin>>n>>m;
while(m--){
int x,y;cin>>x>>y;
edge[x].push_back(y);
edge[y].push_back(x);
}
int now = 1;
for(int i=0;i<n;i++){ //對所有點上色
if(!color[i]){
dfs(i,now);now += 2;
}
}
for(int i=1;i<=now;i++){boss[i] = i;num[i] = 1;}
cin>>p>>k;
for(int i=1;i<=p;i++){
change.clear(); //儲存待更改的點集
f = 0;
for(int j=0;j<k;j++){
int x,y;cin>>x>>y;
if(f)continue;
x = color[x],y = color[y]; //尋找邊兩端點的顏色所處的集合
int bx = find_boss(x),by = find_boss(y);
int ox = find_boss(other(y)),oy = find_boss(other(x));
if(bx == by){WA[i] = 1;f = 1;continue;} //位於同一集合，此觀察員是錯的
//以下是啟發式合併（小的集合並到大的集合）
if(num[bx] < num[ox]){
boss[bx] = ox;num[ox] += num[bx];
change.push_back(bx);
}
else{
boss[ox] = bx;num[bx] += num[ox];
change.push_back(ox);
}
if(num[by] < num[oy]){
boss[by] = oy;num[oy] += num[by];
change.push_back(by);
}
else{
boss[oy] = by;num[by] += num[oy];
change.push_back(oy);
}
}
for(auto i : change){boss[i] = i;num[i] = 1;} //觀察員的邊結束，看完後復原
}
for(int i=1;i<=p;i++)if(WA[i])cout<<i<<endl; //輸出最後錯誤觀察員答案
}
peienwu
-
Any changes
Be notified of any changes
-
Mention me
Be notified of mention me
-
Unsubscribe
Subscribe