2 条题解
-
1养猪场场长zms (njnu19210436) LV 9 MOD @ 2022-03-30 20:21:38
本来是想用暴力开掉,然后有5个点爆了……
这道题还是典型并查集,附上并查集核心代码int find(int x) //查找结点 x的爸比 { if(pre[x] == x) return x; //递归出口:x的爸比为 x本身,即 x为孤儿 return pre[x] = find(pre[x]); //此代码相当于先找到爸比 rootx,然后pre[x]=爸比 }
这个是爆掉的能过15个点的暴力开,不过没试过卡常能多对几个点……
哈哈就这样吧#include "bits/stdc++.h" using namespace std; #define N 100010 struct Arr{ bool vis; Arr() : vis(true) { } void Tip() { this->vis = true; } void Del() { this->vis = false; } }; int n, m; Arr ans[N]; int main() { int a = 0, b = 0; cin >> n >> m; while (m--) { char op; cin >> op; switch (op) { case 'D': cin >> a >> b; for (int i = a; i <= b; i++) { ans[i].Del(); } break; case 'Q': cin >> a; for (int i = a; i <= n; i++) { if (ans[i].vis == true) { cout << i << endl; break; } } break; default: break; } } return 0; }
-
02022-04-04 10:54:08@
#include<iostream> using namespace std; const int Max = 100010; int n,m; int cnt=0; int a[Max]; int b[Max]; //路径压缩 int P[Max]; int f(int p){ if(b[p]==p)return p; return f(b[p]); } int main() { cin >> n>>m; for(int i=1;i<=n;i++){ a[i]=i; b[i]=i; } for(int i=1;i<=m;i++){ char s;cin>>s; if(s=='D'){ int c,d;cin>>c>>d; for(int j=c;j<=d;j++)b[j]=d+1; } if(s=='Q'){ int c;cin>>c; P[cnt++]=f(b[c]); } } for(int i=0;i<cnt;i++)cout<<P[i]<<endl; return 0; }
- 1