差别

这里会显示出您选择的修订版和当前版本之间的差别。

--- 2020-2021:teams:wangzai_milk:20200803比赛记录 [2020/08/05 15:01]
zars19 [题解]
+++ 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	|
-^状态 	|- 	|- 	|- 	|- 	|- 	|- 	|O 	|- 	|O	|-	|O	|
+^状态 	|Ø 	|- 	|- 	|- 	|Ø 	|- 	|O 	|- 	|O	|-	|O	|
 //O 在比赛中通过 Ø 赛后通过 ! 尝试了但是失败了 - 没有尝试//
@@ 行 13: / 行 13: @@
 ===== 题解 =====
+==== A - All-Star Game ====
+每个球员有一些粉丝，一个粉丝会去看某个球员比赛的条件是他喜欢这个球员或和他喜欢同一个球员的人喜欢这个球员。球员与粉丝的关系可以动态改变，问每一次改变之后，最少请多少球员来比赛才可以使得所有粉丝来看比赛。
+牛客暑期多校第八场的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 ====
+ $f(x)$ 表示 $x$ 由连续三个数字组成的划分有多少种，给出 $l,r$ 求 $\sum_{k=l}^rf(k)$ 。
+显然只要能求得出来所有 $f(x)$ ，就可以通过前缀和 $O(1)$ 得到 $\sum_{k=l}^rf(k)$ 。
+{{:2020-2021:teams:wangzai_milk:2020牛客8e.jpg?550|}}
+先放一个写题解必画的图…这是当起始数字 $i=1$ ，长度固定为 $j=6$ 时的情况，差分一次我们发现 $+1$ 是从 $ij+3$ 开始往前跳两个数字一次， $-1$ 是从 $(i+1)j+1$ 开始往前跳一个数字一次。于是再差分一次（ $+1$ 是跨度 $2$ 的差分），这样就可以枚举 $i,j$ 后 $O(1)$ 计入贡献，最后做几次前缀和还原原数组即可。
+<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=1e5+10;
+ll add[10*N],del[10*N],f[N];
+int main()
+{
+	for(int i=1;i<N/3;i++)
+	for(int j=3;j*i+3<N;j++)
+	{
+		add[i*j+3]++,add[(i+2)*j-1]--;
+		del[(i+1)*j+1]++,del[(i+2)*j-1]--;
+	}
+	for(int i=2;i<N;i++)
+	add[i]+=add[i-2],del[i]+=del[i-1],f[i]=add[i]-del[i]+f[i-1];
+	for(int i=1;i<N;i++)f[i]+=f[i-1];
+	int t;
+	scanf("%d",&t);
+	for(int ca=1;ca<=t;ca++)
+	{
+		int l,r;
+		scanf("%d%d",&l,&r);
+		printf("Case #%d: %lld\n",ca,f[r]-f[l-1]);
+	}
+	return 0;
+}
+</code></hidden>
+\\
 ==== G - Game SET ====

CVBB ACM Team

用户工具

站点工具

差别

页面工具