首页 > 其他分享 >CF1392I Kevin and Grid 题解

CF1392I Kevin and Grid 题解

时间:2024-02-27 22:01:43浏览次数:24  
标签:连通 const 蓝色 题解 CF1392I 262145 Grid 平面图 cp

题目传送门

\(\large\textbf{Statement.}\)

给定两个序列 \(a,b\),有一个 \(n\times m\) 的网格图,每个 \((i,j)\) 上有个权值 \(a_i+b_j\),每个点和其上、下、左、右方相邻的点有连边。

多次询问,每次给一个阈值 \(x\),将图分为权值 \(< x\) (蓝色)和 \(\ge x\) (红色)的两种连通块。一个连通块如果有点在网格边界则价值为 \(1\),否则为 \(2\)。求红色连通块中的点的价值和减去蓝色连通块中的点的价值和。

\(1\le n,m,q,a_i,b_i\le 10^5\)。


\(\large\textbf{Solution.}\)

几个前置知识:

  • 平面图:可以将所有点画在一个平面上,且所有边不相交的图是平面图。

  • 欧拉定理:\(|V|-|E|+|F|=2\),其中 \(V,E\) 为联通平面图的点集和边集,\(F\) 表示平面图把平面分成的区域集合(注意计算最外层的无穷区域)。

  • 连通块计数公式:\(C=|V|-|E|+|F|-1\)。

考虑这个网格图上每四个点围成的块,发现不可能满足两条对角线上的点颜色分别为红色和蓝色。

对于一个红色连通块,如果其内部还包含一个蓝色连通块,那么蓝色连通块的价值一定为 \(2\),而在红色点组成的平面图上这个蓝色连通块对应的位置是一个完整的区域,所以价值减一下可以视为将红色点组成的平面图上的 \(|F|\) 减去 \(1\)(也就是不统计蓝色连通块对应的那片区域),那个蓝色连通块的价值改为 \(1\)。

所以最后经过不断的抵消之后,所有的连通块价值都变成了 \(1\),两个 \(F\) 集合内只包含面积为一的区域(两种颜色的 \(F\) 都包含最外层的无穷区域,可以抵消),那么答案就是 \((|V_1|-|E_1|+|F_1|)-(|V_2|-|E_2|+|F_2|)\)(下标 \(1\) 和 \(2\) 分别表示两种颜色)。

直接 FFT 计算这些值即可,时间复杂度 \(O(w\log w+q)\),其中 \(w\) 为值域。

参考代码:

#include<bits/stdc++.h>
#define ll long long
#define mxn 100003
#define db double
#define rep(i,a,b) for(int i=a;i<=b;++i)
#define rept(i,a,b) for(int i=a;i<b;++i)
#define drep(i,a,b) for(int i=a;i>=b;--i)
using namespace std;
struct cp{
	db x,y;
	inline cp(const db a=0,const db b=0):x(a),y(b){}
	inline cp operator+(const cp a)const{return cp(x+a.x,y+a.y);}
	inline cp operator-(const cp a)const{return cp(x-a.x,y-a.y);}
	inline cp operator*(const cp a)const{return cp(x*a.x-y*a.y,x*a.y+y*a.x);}
};
const db pi=acos(-1);
int n,m,q,a[mxn],b[mxn],rev[262145];
cp f1[262145],f2[262145],f3[262145],f4[262145],f5[262145],f6[262145];
cp g0[262145],g1[262145],g2[262145],g3[262145],g4[262145],g5[262145],g6[262145];
const int s=262144,k=18;
ll d0[mxn<<1],d1[mxn<<1],d2[mxn<<1],d3[mxn<<1],d4[mxn<<1],d5[mxn<<1];
void fft(cp *a,int n,int flag){
	rept(i,0,n)if(i<rev[i])swap(a[i],a[rev[i]]);
	for(int r=1;r<n;r<<=1){
		cp x,y,s=cp(cos(flag*pi/r),sin(flag*pi/r));
		for(int i=0;i<n;i+=r<<1){
			cp w(1,0);
			for(int k=i;k<i+r;++k){
				x=a[k],y=w*a[k+r];
				a[k]=x+y;
				a[k+r]=x-y;
				w=w*s;
			}
		}
	}
	if(flag==-1)rept(i,0,s)a[i].x/=n,a[i].y/=n;
}
signed main(){
	scanf("%d%d%d",&n,&m,&q);
	rep(i,1,n)scanf("%d",&a[i]),f1[a[i]].x+=1;
	rep(i,1,m)scanf("%d",&b[i]),f2[b[i]].x+=1;
	rept(i,1,n)f3[max(a[i],a[i+1])].x+=1,f4[min(a[i],a[i+1])].x+=1;
	rept(i,1,m)f5[max(b[i],b[i+1])].x+=1,f6[min(b[i],b[i+1])].x+=1;
	rept(i,0,s)rev[i]=(rev[i>>1]>>1)|((i&1)<<(k-1));
	fft(f1,s,1),fft(f2,s,1),fft(f3,s,1),fft(f4,s,1),fft(f5,s,1),fft(f6,s,1);
	rept(i,0,s){
		g0[i]=f1[i]*f2[i];
		g1[i]=f1[i]*f5[i],g2[i]=f3[i]*f2[i];
		g3[i]=f1[i]*f6[i],g4[i]=f4[i]*f2[i];
		g5[i]=f3[i]*f5[i];
		g6[i]=f4[i]*f6[i];
	}
	fft(g0,s,-1),fft(g1,s,-1),fft(g2,s,-1),fft(g3,s,-1),fft(g4,s,-1),fft(g5,s,-1),fft(g6,s,-1);
	rep(i,1,2e5){
		d0[i]=d0[i-1]+round(g0[i].x);
		d1[i]=d1[i-1]+round(g1[i].x)+round(g2[i].x);
		d2[i]=d2[i-1]+round(g5[i].x);
	}
	drep(i,2e5,1){
		d5[i]=d5[i+1]+round(g0[i].x);
		d3[i]=d3[i+1]+round(g3[i].x)+round(g4[i].x);
		d4[i]=d4[i+1]+round(g6[i].x);
	}
	int x;
	while(q--){
		scanf("%d",&x);
		printf("%lld\n",(d5[x]-d3[x]+d4[x])-(d0[x-1]-d1[x-1]+d2[x-1]));
	}
	return 0;
}

标签:连通,const,蓝色,题解,CF1392I,262145,Grid,平面图,cp
From: https://www.cnblogs.com/zifanoi/p/18038504

相关文章

  • P10084 [GDKOI2024 提高组] 计算 题解
    题目传送门前置知识:单位根反演先考虑怎么求\(F(x,a,b)\),易得\(\gcd(x^a-1,x^b-1)=x^{\gcd(a,b)}-1\)。所以\(L=m^{\gcd(a,b)}+1,R=m^{\gcd(c,d)}\),然后发现\([L,R]\)中的数模\(m\)后每种余数出现次数相同,下面记其为\(n=\frac{R-L}{m}\)。考虑用生成函数做,易得答案为......
  • [ABC331G] Collect Them All 题解
    洛谷传送门AT传送门\(\textbf{Statement.}\)有\(M\)种颜色,用\(1\simM\)编号,每次抽奖抽中第\(i\)种颜色的概率为\(\frac{c_i}{N}\),其中\(\sumc_i=N\),求抽中每种颜色至少一次的期望次数。\(1\leM\leN\le2\times10^5\)。\(\textbf{Solution.}\)发现直接求不好......
  • [ARC087F] Squirrel Migration 题解
    洛谷题面AT题面如果两条路径不存在交点,则两条路径各选一个端点交换后两路径相交,答案不会变劣。考虑所有路径两两相交的情况,因为图是一棵树,所以这些路径会交于一点。以这个点为根,那么最大的子树大小一定不超过\(\fracn2\),所以这个点是树的重心,每条路径的端点一定在两个不......
  • 个人题解:2024 年湖北省省队选拔集训暨能力测试 第一试
    时与风对每条边进行BFS。二维偏序部分用vector存一下就行了。花神诞日引理:对于\(a<b<c\),\(\min(a\text{XOR}b,b\text{XOR}c)\leqa\text{XOR}c\)。证明:考虑比较\(a,c\)二进制下第一位不同,也就是\(a=(X0\dots)_{(2)},c=(X1\dots)_{2}\)。因为\(b\in(a,c)\)所以......
  • CSP-S 2023 题解
    T1一开始所有密码都没被标记。对于每个输入的状态枚举一遍所有没标记的密码,判断是否可能是正确密码,如果不行就标记一下。最后输出没被标记的密码个数。总共只有\(10^5\)个密码,可以轻松通过。难度:橙。T2见CF1223FStackExterminableArrays题解。难度:蓝。T3大模拟,直......
  • 2024牛客寒假算法基础集训营5 题解 ( A,C,G,H,I,L,M )
    2024牛客寒假算法基础集训营5题解(A,C,G,H,I,L,M)A mutsumi的质数合数题意有一个由\(n\)个正整数组成的数组,她想知道数组中质数和合数共有几个。思路由质数和合数的定义可知,正整数范围内除\(1\)外,要么是质数要么是合数,本题直接统计不是\(1\)的正整数的个数即可代码......
  • 题解 CF963E Circles of Waiting
    令\(f_{i,j}\)表示\((i,j)\)走出以\((0,0)\)为圆心,半径为\(R\)的期望步数,显然所有在圆外的点\((i,j)\)满足\(f_{i,j}=0\)。有\(f_{i,j}=p_1f_{i-1,j}+p_2f_{i,j-1}+p_3f_{i+1,j}+p_4f_{i,j+1}\)。这东西很套路,高斯消元就行,但状态数是\(O(R^2)\)的,复杂度\(O(R^......
  • 题解 CF725G Messages on a Tree
    updateon2023.8.9修正了一些错误。\(\texttt{link}\)第\(i\)条信息的传输可以表示成\(x_i\)走到\(x_i\)的某一祖先再走回\(x_i\)的路径。所以答案只和\(x_i\)的这一祖先有关,记为\(f_i\),则\(ans_i=t_i+2\timesdep_{x_i}-2\timesdep_{f_i}\)。若\(x_i\)在\(f......
  • 题解 CF1781G Diverse Coloring
    \(\texttt{link}\)题意给定一棵\(n\)个点的二叉树,现对其每个点染成黑色或白色。一种合法的染色方案满足:对于所有黑色的点,都存在白色的点与之相邻。对于所有白色的点,都存在黑色的点与之相邻。一种染色方案的权值是染成黑色的点数与染成白色的点数之差的绝对值。\(\foral......
  • 题解 CF1523H Hopping Around the Array
    \(\texttt{link}\)题意数轴上有\(n\)个点,每个点有属性\(a_i\),在第\(i\)个点可以花费\(1\)的步数移动至\([i,i+a_i]\)中任意一个点。定义一次操作为选出一个\(i\),使\(a_i\getsa_i+1\)。\(q\)组询问,每次给出\(l,r,k\),求有\(k\)次操作机会时,从第\(l\)个点走到......