2023.5.19测试

xishanmeigao / 2023-08-07 / 原文

T1 数

\(T\) 组测试数据，已知 \(\gcd(a,b)=g,\operatorname{lcm}(a,b)=l\)，，求 \(\min\{a+b\}\)。无解输出 \(-1\)

\(1\leq T\leq 5\)，\(1\leq g,l \leq 10^{12}\)

唯一会的题

设 \(a=gi,b=gj\)，显然 \(\gcd(i,j)=1\)，问题转化成求 \(\min\{g(i+j)\}=\min\{i+j\}\times g\)

我们又知道 \(l=\dfrac{ab}{g}=gij\)，所以 \(ij=\dfrac{l}{g}\)。同时我们也可以知道当 \(g\nmid l\) 时无解

直接根号枚举 \(\dfrac{l}{g}\) 的约数即可。时间复杂度 \(O(T\sqrt{\dfrac{l}{g}})\)

#include<bits/stdc++.h>
#define LL long long
using namespace std;

int T;
LL g,l;

LL gcd(LL a,LL b)
{
	if(b==0)
		return a;
	return gcd(b,a%b);
}

int main()
{
	scanf("%d",&T);
	while(T--)
	{
		scanf("%lld%lld",&g,&l);
		if(l%g!=0)
		{
			printf("-1\n");
			continue;
		}
		
		LL k=l/g,ans=1e15;
		for(LL i=1; i<=sqrt(k); i++)
		{
			if(k%i!=0)
				continue;
			LL a=i,b=k/i;
			if(gcd(a,b)==1)
				ans=min(ans,a+b);
		}
		
		printf("%lld\n",ans*g);
	}
	
	return 0;
}

T2 兼容

有 \(n\) 个物品，每个物品两种属性 \(x_i,y_i\)。若 \(x_ix_j+y_jy_j=0\) 则称 \(i\) 和 \(j\) “不兼容” 。现在要从中选若干个物品（不能一个不选），且选择的物品两两都要“兼容”，求有多少种方案。答案模 \(10^9+7\)

\(1\leq n\leq 2\times 10^5,-10^{18}\leq x,y\leq 10^{18}\)

考场没有考虑 \(0\) 的情况喜提 \(47\) 分

变换一下式子，不兼容的情况为 \(\dfrac{x_i}{y_i}=-\dfrac{x_j}{y_j}\)

所以两种物品不兼容的前提是 \(\dfrac{x_i}{y_i}\) 和 \(\dfrac{x_j}{y_j}\) 异号。开两个 \(\mathrm{map}\)，分别存放 \(x,y\) 同号和异号，记为 \(fa,fb\)。由于 \(\mathrm{double}\) 精度问题用 \(\mathrm{pair}\) 存储，注意 \(x,y\) 要同时除以 \(gcd\) 才能化为既约分数

那么问题就很简单了，对于最简的 \(x_i,y_i\)，记它的数量为 \(cnta\)。在另一个 \(\mathrm{map}\) 里找 \(pair(y_i,x_i)\) 的数量，记为 \(cntb\)。如果 \(cntb=0\)，则 \(ans\) 乘上 \(2^{cnta}\)，否则乘上 \(2^{cnta}+2^{cntb}-1\)。注意因为 \(2^{cnta}\) 和 \(2^{cntb}\) 都包括了不选的情况，所以要 \(-1\)

最后 \(ans\) 再 \(-1\)，因为不能一个都不选

考场上以为这样能 \(AC\)，后面发现成小丑了。因为 \(x,y\) 可能为 \(0\)，要特判一下

我们将所有物品分为四类：

\(x,y\) 均为 \(0\)，数量记为 \(A\)
\(x\) 为 \(0\)，但 \(y\) 不为 \(0\)，数量记为 \(B\)
\(x\) 不为 \(0\)，但 \(y\) 为 \(0\)，数量记为 \(C\)
\(x,y\) 均不为 \(0\)，数量记为 \(D\)

对于第四种我们像上述那样计算。第二和第三种即让 \(ans\) 乘上 \(2^B+2^C-1\) 即可。对于第一种，我们要在 \(ans-1\) 后加上 \(A\)。因为选了第一种就不能选其它任何的。

综上，这是一道sb细节计数题：）

#include<bits/stdc++.h>
#define LL long long
#define mp make_pair
using namespace std;

const int N=200010;
const LL MOD=1000000007;

struct node
{
	LL x,y;
}a[N];
int n,v[N];
LL ans=1,A,B,C,D;
map <pair<LL,LL>,int> fa,fb,ida,idb;

LL gcd(LL a,LL b)
{
	if(b==0)
		return a;
	return gcd(b,a%b);
}

LL ksm(int a,int b)
{
	if(b==0)
		return 1;
	if(b==1)
		return (LL)a;
	
	LL tmp=ksm(a,b/2);
	if(b%2==0)
		return tmp*tmp%MOD;
	return tmp*tmp%MOD*1LL*a%MOD;
}

int main()
{
	scanf("%d",&n);
	for(int i=1; i<=n; i++)
	{
		scanf("%lld%lld",&a[i].x,&a[i].y);
		
		if(a[i].x==0 && a[i].y==0)
			A++;
		else if(a[i].x==0 && a[i].y!=0)
			B++;
		else if(a[i].x!=0 && a[i].y==0)
			C++;
		else
		{
			D++;
			if((a[i].x>0 && a[i].y>0) || (a[i].x<0 && a[i].y<0))
			{
				v[i]=1;
				a[i].x=abs(a[i].x);  a[i].y=abs(a[i].y);
				LL d=gcd(a[i].x,a[i].y);
				a[i].x/=d;  a[i].y/=d;
				
				pair<LL,LL> tmp=mp(a[i].x,a[i].y);
				if(fa[tmp])
					v[i]=0;
				else
					ida[tmp]=i;
				fa[tmp]++;
			}
			else
			{
				v[i]=-1;
				a[i].x=abs(a[i].x);  a[i].y=abs(a[i].y);
				LL d=gcd(a[i].x,a[i].y);
				a[i].x/=d;  a[i].y/=d;
				
				pair<LL,LL> tmp=mp(a[i].x,a[i].y);
				if(fb[tmp])
					v[i]=0;
				else
					idb[tmp]=i; 
				fb[tmp]++;
			}
		}
	}
	
	for(int i=1; i<=n; i++)
	{
		if(!v[i])
			continue;
		
		pair<LL,LL> cur=mp(a[i].x,a[i].y);
		if(v[i]>0)
		{
			pair<LL,LL> tur=mp(a[i].y,a[i].x);
			int cnta=fa[cur],cntb=fb[tur];
			if(cntb==0)
				(ans*=ksm(2,cnta))%=MOD;
			else
				(ans*=(ksm(2,cnta)+ksm(2,cntb)-1)%MOD)%=MOD;
			
			v[i]=v[idb[tur]]=0;
		}
		else
		{
			pair<LL,LL> tur=mp(a[i].y,a[i].x);
			int cnta=fb[cur],cntb=fa[tur];
			if(cntb==0)
				(ans*=ksm(2,cnta))%=MOD;
			else
				(ans*=(ksm(2,cnta)+ksm(2,cntb)-1)%MOD)%=MOD;
			
			v[i]=v[ida[tur]]=0;
		}
	}
	
	if(!B && C)
		(ans*=ksm(2,C))%=MOD;
	else if(B && !C)
		(ans*=ksm(2,B))%=MOD;
	else if(B && C)
		(ans*=(ksm(2,B)+ksm(2,C)-1)%MOD)%=MOD;
	
	(ans-=1-MOD)%=MOD; //警钟敲响
	(ans+=A)%=MOD;
	
	printf("%lld",ans);
	
	return 0;
}

T3 面积

一个平面直角坐标系，\(y\) 向右，\(x\) 向下。有 \(n\) 条水平的线段和 \(m\) 条竖直的线段。一奶牛从 \((0,0)\) 出发，求它能到达的面积是多少。若无穷输出 INF

\(1\leq n,m\leq 1000\)，坐标绝对值 \(\leq 10^9\)

不会，只会输出 \(\mathrm{INF}\) 拿到 \(27\) 分。但lgj说是大水题

好吧我是小丑

将坐标离散化后就会出现很多被线段分割出来的矩形，用一个差分把所有线段的坐标转移到新的坐标上，然后直接搜索即可

因为求的是面积，我们不在点上面走，而在格子上面走，用格子右上角的坐标表示这个格子，这样可以方便计算

#include<bits/stdc++.h>
#define LL long long
using namespace std;

const int N=3010;

struct node
{
	int a,b,c;
}s1[N],s2[N];
int n,m,bx[N],by[N],tx,ty,nx,ny;
int r[N][N],c[N][N];
LL ans;
bool v[N][N];

void dfs(int x,int y)
{
	if(v[x][y])
		return;
	if(x<=1 || y<=1 || x>nx || y>ny)
	{
		printf("INF");
		exit(0);
	}
	
	v[x][y]=1;
	ans+=1LL*(bx[x]-bx[x-1])*(by[y]-by[y-1]);
	if(!r[x][y])
		dfs(x+1,y);
	if(!r[x-1][y])
		dfs(x-1,y);
	if(!c[y][x])
		dfs(x,y+1);
	if(!c[y-1][x])
		dfs(x,y-1);
}

int main()
{
	scanf("%d%d",&n,&m);
	for(int i=1; i<=n; i++)
	{
		scanf("%d%d%d",&s1[i].a,&s1[i].b,&s1[i].c);
		bx[++tx]=s1[i].a;  bx[++tx]=s1[i].b;
		by[++ty]=s1[i].c;
	}
	for(int i=1; i<=m; i++)
	{
		scanf("%d%d%d",&s2[i].a,&s2[i].b,&s2[i].c);
		by[++ty]=s2[i].b;  by[++ty]=s2[i].c;
		bx[++tx]=s2[i].a;
	}
	
	bx[++tx]=0;  by[++ty]=0;
	sort(bx+1,bx+1+tx);
	sort(by+1,by+1+ty);
	nx=unique(bx+1,bx+1+tx)-(bx+1);
	ny=unique(by+1,by+1+ty)-(by+1);
	
	for(int i=1; i<=n; i++)
	{
		s1[i].a=lower_bound(bx+1,bx+1+nx,s1[i].a)-bx;
		s1[i].b=lower_bound(bx+1,bx+1+nx,s1[i].b)-bx;
		s1[i].c=lower_bound(by+1,by+1+ny,s1[i].c)-by;
		c[s1[i].c][s1[i].a+1]++; //注意差分的下标
		c[s1[i].c][s1[i].b+1]--;
	}
	for(int i=1; i<=m; i++)
	{
		s2[i].a=lower_bound(bx+1,bx+1+nx,s2[i].a)-bx;
		s2[i].b=lower_bound(by+1,by+1+ny,s2[i].b)-by;
		s2[i].c=lower_bound(by+1,by+1+ny,s2[i].c)-by;
		r[s2[i].a][s2[i].b+1]++;
		r[s2[i].a][s2[i].c+1]--;
	}
	
	for(int i=1; i<=nx; i++)
		for(int j=1; j<=ny+1; j++)
			r[i][j]+=r[i][j-1];
	for(int i=1; i<=ny; i++)
		for(int j=1; j<=nx+1; j++)
			c[i][j]+=c[i][j-1];
	
	int sx=lower_bound(bx+1,bx+1+nx,0)-bx;
	int sy=lower_bound(by+1,by+1+ny,0)-by;
	
	dfs(sx,sy);
	
	printf("%lld",ans);
	
	return 0;
}

T4 中位数

已知 \(a_i\leq s_i\leq b_i\)，求 \(s\) 的中位数有多少种可能

\(2\leq n\leq 200000\)，\(1\leq a_i,b_i\leq 10^9\)

又是一道不会的题，暴力搜索 \(36\) 分

没想到居然是道数学题

直接给出结论：
将 \(a,b\) 从小到大排序

当 \(n\) 是奇数时，设 \(mid=\left\lfloor\dfrac{n}{2}\right\rfloor+1\)，\(ans=b_{mid}-a_{mid}+1\)
当 \(n\) 是偶数时，设 \(mid=\dfrac{n}{2}\)，\(ans=b_{mid}+b_{mid+1}-a_{mid}-a_{mid+1}\)

下面证明一下当 \(n\) 是奇数时的正确性，偶数的类似

首先显然 \(s\) 的中位数一定大于等于 \(a_{mid}\)，并且小于等于 \(b_{mid}\)。那为什么 \([a_{mid},b_{mid}]\) 中的每个数都能取到呢？

设 \(x\in [a_{mid},b_{mid}]\)，将所有的区间 \( [a_i,b_i]\) 分成 \(3\) 类：

\(b_i<x\)，数量记为 \(A\)
\(a_i>x\)，数量记为 \(B\)
\(a_i\leq x\leq b_i\)

若能取到 \(x\)，就必须满足 \(A,B\leq \left\lfloor\dfrac{n}{2}\right\rfloor\)。而 \(b_i<b_{mid},a_i>a_{mid}\) 的数量已经小于等于 \(\left\lfloor\dfrac{n}{2}\right\rfloor\) 了，所以这个条件显然满足。故奇数时答案为 \(b_{mid}-a_{mid}+1\)

sort(a+1,a+1+n);
sort(b+1,b+1+n);
	
if(n&1)
	printf("%d",b[n/2+1]-a[n/2+1]+1);
else
	printf("%d",b[n/2+1]+b[n/2]-a[n/2+1]-a[n/2]+1);

T5 网格

一个 \(n\) 行 \(m\) 列的表格，除了左上角的格子是 \(0\)，其它每个格子填上 \([0,s]\) 的整数。从左上角格子出发，每步规则如下：

若处在第 \(m\) 列或第 \(n\) 行，则向下/向右走一步
否则，往下和右数字大的地方走，相同则往右走

问从左上角走到右下角，途中经过的格子数字和为 \(s\) 的填表格方案数？答案模 \(10007\)

非常困难的 \(\rm dp\)！

首先有个朴素的 \(\rm dp\)，设 \(f[i][j][k]\) 表示走到第 \(i\) 行第 \(j\) 列经过的数字和为 \(k\) 的方案数，那么有转移：

\[f[i][j][k]=\begin{cases}\sum\limits_{t=0}^jf[i-1][j][k-t]\times t\times(s+1)^{m-j-1}\\\sum\limits_{t=0}^jf[i][j-1][k-t]\times t\times (s+1)^{n-i-1}\end{cases} \]

时间复杂度 \(O(nms^2)\)，可以通过优化搞到 \(O(ms^2)\)，看这个

不过我们主要讲另一种方法，就是将路径和填数分开考虑

设 \(f[i][j]\) 表示到第 \(i\) 行第 \(j\) 列的有多少种走法，简单递推可得。当然，我们可以顺便把那个 \((s+1)\) 的幂计算进去

容易发现，当到达第 \(n\) 行或第 \(m\) 列的某个格子后，后面只能单向移动，而之前向下或向右移动的次数必为 \(n-1\) 或 \(m-1\)。

因此，我们设 \(e[i][j]\) 表示走了 \(n-1\) 次向下，\(i\) 次向右，经过的数字和为 \(j\) 的方案数，\(h[i][j]\) 表示走了 \(m-1\) 次向右，\(i\) 次向下，经过的数字和为 \(j\) 的方案数，可以先算 \(n-1\) 次向下或 \(m-1\) 次向右的方案数，再简单递推一下即可

对于最后单向移动的那部分，我们设 \(g[i][j]\) 表示走 \(i\) 个格子和为 \(j\) 的方案数，直接递推

那么最后我们枚举到达的点 \((n,i)\) 或 \((m,j)\)，这里以 \((n,i)\) 为例，它的贡献为

\[\sum_{j=0}^s{f[n][i]\times e[i-1][j]\times g[m-i][s-j]} \]

时间复杂度 \(O(ns^2)\)

总的来说，要想到将填数和路径分离，并且以最后的行和列作为突破口，将前后两段分开，是这道题制胜的关键。果然还是太菜了，考场上甚至没去写朴素的 \(\rm dp\)，\(\rm dp\) 还得多练

#include<bits/stdc++.h>
using namespace std;

const int N=2510,M=110;
const int MOD=10007;

int n,m,s,pw[N],ans;
int f[N][N],g[N][M];
int e[N][M],h[N][M],ee[N][M],hh[N][M];

void prework()
{
	pw[0]=1;
	for(int i=1; i<=max(n,m); i++)
		pw[i]=1LL*pw[i-1]*(s+1)%MOD;
		
	ee[0][0]=1;
	for(int i=1; i<n; i++)
		for(int j=0; j<=s; j++)
			for(int k=0; k<=j; k++)
				(ee[i][j]+=ee[i-1][j-k]*k%MOD)%=MOD;
	
	hh[0][0]=1;
	for(int i=1; i<m; i++)
		for(int j=0; j<=s; j++)
			for(int k=0; k<=j; k++)
				(hh[i][j]+=hh[i-1][j-k]*(k+1)%MOD)%=MOD;	
}

signed main()
{
	scanf("%d%d%d",&n,&m,&s);
	
	if(n==1 && m==1 && s==0)
	{
		printf("1");
		return 0;
	}
	
	prework();
	
	for(int i=0; i<=s; i++)
		e[0][i]=ee[n-1][i];
	for(int i=1; i<m; i++)
		for(int j=0; j<=s; j++)
			for(int k=0; k<=j; k++)
				(e[i][j]+=e[i-1][j-k]*(k+1)%MOD)%=MOD;
				
	for(int i=0; i<=s; i++)
		h[0][i]=hh[m-1][i];
	for(int i=1; i<n; i++)
		for(int j=0; j<=s; j++)
			for(int k=0; k<=j; k++)
				(h[i][j]+=h[i-1][j-k]*k%MOD)%=MOD;
	
	g[0][0]=1;
	for(int i=1; i<=max(n,m); i++)
		for(int j=0; j<=s; j++)
			for(int k=0; k<=j; k++)
				(g[i][j]+=g[i-1][j-k])%=MOD;
				
	f[1][1]=1;
	for(int i=1; i<n; i++)
	{
		for(int j=1; j<m; j++)
			f[i][j]+=(1LL*f[i-1][j]*pw[m-j-1]%MOD+1LL*f[i][j-1]*pw[n-i-1]%MOD)%MOD;
			
		f[i][m]+=1LL*f[i][m-1]*pw[n-i-1]%MOD;
		for(int j=0; j<=s; j++)
			(ans+=1LL*f[i][m]*h[i-1][j]%MOD*g[n-i][s-j]%MOD)%=MOD;
	}
	
	for(int i=1; i<m; i++)
		f[n][i]+=1LL*f[n-1][i]*pw[m-i-1]%MOD;
	for(int i=1; i<m; i++)
		for(int j=0; j<=s; j++)
			(ans+=1LL*f[n][i]*e[i-1][j]%MOD*g[m-i][s-j]%MOD)%=MOD;
	
	printf("%d",ans);
	
	return 0;
}

\(100+47+27+36+0=210\)，\(\rm rk12\)