2020-2021:teams:wangzai_milk:20200803比赛记录
差别
这里会显示出您选择的修订版和当前版本之间的差别。
| 两侧同时换到之前的修订记录 前一修订版 | |||
|
2020-2021:teams:wangzai_milk:20200803比赛记录 [2020/08/05 20:10] zars19 [E - Enigmatic Partition] |
2020-2021:teams:wangzai_milk:20200803比赛记录 [2020/08/05 23:24] (当前版本) zars19 |
||
|---|---|---|---|
| 行 4: | 行 4: | ||
| ^题号 ^A ^B ^C ^D ^E ^F ^G ^H ^I ^J ^K | | ^题号 ^A ^B ^C ^D ^E ^F ^G ^H ^I ^J ^K | | ||
| - | ^状态 |- |- |- |- |Ø |- |O |- |O |- |O | | + | ^状态 |Ø |- |- |- |Ø |- |O |- |O |- |O | |
| //O 在比赛中通过 Ø 赛后通过 ! 尝试了但是失败了 - 没有尝试// | //O 在比赛中通过 Ø 赛后通过 ! 尝试了但是失败了 - 没有尝试// | ||
| 行 13: | 行 13: | ||
| ===== 题解 ===== | ===== 题解 ===== | ||
| + | |||
| + | ==== A - All-Star Game ==== | ||
| + | |||
| + | 每个球员有一些粉丝，一个粉丝会去看某个球员比赛的条件是他喜欢这个球员或和他喜欢同一个球员的人喜欢这个球员。球员与粉丝的关系可以动态改变，问每一次改变之后，最少请多少球员来比赛才可以使得所有粉丝来看比赛。 | ||
| + | |||
| + | 2019牛客暑期多校第八场的E也是这个科技，不会线段树分治时间并查集（不知道这个叫什么我乱叫的）一周年纪念。其实就是把每一条边在线段树上加到它存在的时间里 | ||
| + | |||
| + | 记录一下没有粉丝的球员数，和不喜欢任何球员的粉丝数，并查集可以搞出连通块数，即可（如果没有不喜欢任何球员的粉丝，答案是 $连通块数-没有粉丝的球员$ ）。 | ||
| + | |||
| + | <hidden><code cpp> | ||
| + | #include<bits/stdc++.h> | ||
| + | #define ll long long | ||
| + | #define pii pair<int,int> | ||
| + | #define mp make_pair | ||
| + | #define fi first | ||
| + | #define se second | ||
| + | #define pb push_back | ||
| + | using namespace std; | ||
| + | const int N=5e5+10; | ||
| + | map<pii,int>vis; | ||
| + | int n,m,q,cnt,res[N],pa[N],h[N],st[N],top,bloc,d[N],num1,num2; | ||
| + | struct Node{int u,v,l,r;}e[N*10]; | ||
| + | vector<int>a[N*4]; | ||
| + | void Insert(int idx,int l,int r,int L,int R,int p) | ||
| + | { | ||
| + | if(l>=L&&r<=R){a[idx].push_back(p);return;} | ||
| + | int mid=(l+r)>>1; | ||
| + | if(L>mid)Insert(idx<<1|1,mid+1,r,L,R,p); | ||
| + | else if(R<=mid)Insert(idx<<1,l,mid,L,R,p); | ||
| + | else Insert(idx<<1,l,mid,L,R,p),Insert(idx<<1|1,mid+1,r,L,R,p); | ||
| + | } | ||
| + | int find(int x){return pa[x]==x?x:find(pa[x]);} | ||
| + | void Union(int u,int v) | ||
| + | { | ||
| + | d[u]++,d[v]++,num1-=(d[u]==1),num2-=(d[v]==1); | ||
| + | int fu=find(u),fv=find(v); | ||
| + | if(fu==fv)return; | ||
| + | if(h[fu]>h[fv])pa[fv]=fu,h[fu]+=h[fv],st[++top]=fv; | ||
| + | else pa[fu]=fv,h[fv]+=h[fu],st[++top]=fu; | ||
| + | bloc--; | ||
| + | } | ||
| + | void dfs(int idx,int l,int r) | ||
| + | { | ||
| + | int rec=top; | ||
| + | for(int i:a[idx])Union(e[i].u,e[i].v); | ||
| + | if(l==r)res[l]=num2?-1:bloc-num1; | ||
| + | else | ||
| + | { | ||
| + | int mid=(l+r)>>1; | ||
| + | dfs(idx<<1,l,mid),dfs(idx<<1|1,mid+1,r); | ||
| + | } | ||
| + | while(top!=rec)h[pa[st[top]]]-=h[st[top]],pa[st[top]]=st[top],top--,bloc++; | ||
| + | for(int i:a[idx]) | ||
| + | d[e[i].u]--,d[e[i].v]--,num1+=(d[e[i].u]==0),num2+=(d[e[i].v]==0); | ||
| + | } | ||
| + | int main() | ||
| + | { | ||
| + | scanf("%d%d%d",&n,&m,&q); | ||
| + | bloc=n+m,num1=n,num2=m; | ||
| + | for(int i=1;i<=n+m;i++)pa[i]=i,h[i]=1; | ||
| + | for(int i=1;i<=n;i++) | ||
| + | { | ||
| + | int k,x; | ||
| + | scanf("%d",&k); | ||
| + | for(int j=1;j<=k;j++) | ||
| + | scanf("%d",&x),vis[mp(i,n+x)]=1; | ||
| + | } | ||
| + | for(int i=2;i<=q+1;i++) | ||
| + | { | ||
| + | int x,y; | ||
| + | scanf("%d%d",&x,&y); | ||
| + | int t=vis[mp(y,n+x)]; | ||
| + | if(t)e[++cnt]=Node{y,n+x,t,i},vis[mp(y,n+x)]=0; | ||
| + | else vis[mp(y,n+x)]=i; | ||
| + | } | ||
| + | for(auto p:vis)if(p.se)e[++cnt]=Node{p.fi.fi,p.fi.se,p.se,q+2}; | ||
| + | for(int i=1;i<=cnt;i++)Insert(1,1,q+2,e[i].l,e[i].r-1,i); | ||
| + | dfs(1,1,q+2); | ||
| + | for(int i=2;i<=q+1;i++)printf("%d\n",res[i]); | ||
| + | return 0; | ||
| + | } | ||
| + | </code></hidden> | ||
| + | \\ | ||
| ==== E - Enigmatic Partition ==== | ==== E - Enigmatic Partition ==== | ||
2020-2021/teams/wangzai_milk/20200803比赛记录.1596629405.txt.gz · 最后更改: 2020/08/05 20:10 由 zars19
