首页 > 其他分享 >2023.8.3测试

2023.8.3测试

时间：2023-08-07 20:12:45浏览次数：41  
标签：最简 颜色 int sum 测试 序列 rm 2023.8

一场 \(\rm NOIP\) 模拟赛搬了四道 Atcoder 的题

T1 跑路

一个 \(n\times m\) 的 \(01\) 矩阵 \(A\)，从左上角出发，每次向下走或向右走，终点为右下角。若路径途中只经过 \(0\)，则称 \(A\) 为“好矩阵”。给定矩阵 \(A\)，每次可以选择它的一个子矩阵取反，求将 \(A\) 变成“好矩阵”的最小操作数。

\(1\leq n,m\leq 1000\)

签到题，设 \(f[x][y]\) 表示从 \((x,y)\) 出发到终点的最小操作数是多少。显然操作数与路径上 \(1\) 的连续段个数一一对应，记忆化搜索即可

T2 Cleaning

一开始只会打特殊性质，最后 \(20\rm min\) 才打出正解

数据太水放我过了，但实际上在 At 过不了（细节出大锅）

对于节点 \(x\)，设从儿子节点传上来的石头数量总和为 \(s=\sum\limits_{y\in son(x)}v_y\)，显然这些石头可以在此处合并，也可以往上走。设它们的数量分别为 \(a,b\)，则有方程

\[\begin{cases}2a+b=s\\a+b=v_x\end{cases} \]

解得

\[\begin{cases}a=s-v_x\\b=2v_x-s\end{cases} \]

显然有范围限制 \(0\leq a,b\leq v_x\)

对于在此处合并的，考虑存在方案使得可以凑出 \(a\) 次合并的条件。一顿模拟后，发现只要 \(s-\max\limits_{y\in son(x)}v_y\leq a\) 即可

特别地，当 \(x=rt\) 时，要有 \(a=v_x,b=0\)

注意特判 \(n=2\)！！！！！！

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

const int N=100010,M=400010,INF=1e9;

int T,n,rt,a[N],deg[N];
vector <int> g[N];
bool flag1,flag2;

bool dfs(int x,int fa)
{
	if(deg[x]==1)
		return 1;			
	
	LL sum=0,mx=0;
	for(int i=0; i<g[x].size(); i++)
	{
		int y=g[x][i];
		if(y==fa)
			continue;
		bool ansy=dfs(y,x);
		if(!ansy)
			return 0;
		sum+=(LL)a[y];
		mx=max(mx,(LL)a[y]);
	}
	
	if(sum<(LL)a[x])
		return 0;
	LL aa=sum-(LL)a[x],bb=1LL*2*a[x]-sum;
	if(aa<0 || bb<0 || bb>a[x] || aa>a[x] || sum-mx<aa)
		return 0;
	if(x==rt && aa!=a[x])
		return 0;
	a[x]-=aa;
	return 1;
}

int main()
{
	scanf("%d",&n);
	for(int i=1; i<=n; i++)
		scanf("%d",&a[i]);
	for(int i=1; i<n; i++)
	{
		int x,y;
		scanf("%d%d",&x,&y);
		deg[x]++;  deg[y]++;
		g[x].push_back(y);  g[y].push_back(x);
	}
		
	if(n==2)	
	{
		if(a[1]==a[2])
			printf("YES");
		else
			printf("NO");
		return 0;
	}		
		
	for(int i=1; i<=n; i++)
	{
		if(deg[i]!=1)
		{
			rt=i;
			break;
		}
	}
		
	bool pd=dfs(rt,0);
	if(pd)
		printf("YES");
	else
		printf("NO");

	return 0;
}

T3 Two Faced Edges

很牛逼的题，只会暴力 \(\rm Tarjan\)，喜提 \(40\) 分

先求一次 \(\rm SCC\)。对于边 \((x,y)\)，分情况讨论：

  • \(x\) 和 \(y\) 在同一个 \(\rm SCC\) 里

    此时 \(\rm SCC\) 数量若不改变，则需满足还存在一条 \(x\rightarrow y\) 的路径不经过边 \((x,y)\)

  • \(x\) 和 \(y\) 不在同一个 \(\rm SCC\) 里

    此时 \(\rm SCC\) 数量若改变，则同样需满足还存在一条 \(x\rightarrow y\) 的路径，不经过边 \((x,y)\)

设 \(g[x][y]\) 表示是否存在 \(x\rightarrow y\) 的路径且不含边 \((x,y)\)，如何计算？

从 \(x\) 出发对整张图进行一次深搜，再将边表反过来重新搜一次。若 \(x\) 在 \(\rm dfs\) 树中的深度为 \(1\)，则 \(g[x][y]=0\) 的充分条件为两次搜索中 \(y\) 的深度都为 \(2\)

时间复杂度 \(O(nm)\)

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

const int N=1010,M=200010;

int n,m;
int cnt,dfn[N],low[N],num,ins[N],c[N],sta[N],top;
int f[N][N],dep[N],cmp[N];
struct node{int x,y;}e[M];
vector <int> g[N];

void Tarjan(int x)
{
	dfn[x]=low[x]=++num;
	sta[++top]=x;  ins[x]=1;
	int len=g[x].size();
	for(int i=0; i<len; i++)
	{
		int y=g[x][i];
		if(!dfn[y])
		{
			Tarjan(y);
			low[x]=min(low[x],low[y]);
		}
		else if(ins[y])
			low[x]=min(low[x],dfn[y]);
	}
	
	if(dfn[x]==low[x])
	{
		int y;  cnt++;
		do
		{
			y=sta[top--];
			ins[y]=0;
			c[y]=cnt;
		}while(x!=y);
	}
}

void dfs1(int x,int d)
{
	dep[x]=d;
	int len=g[x].size();
	for(int i=0; i<len; i++)
	{
		int y=g[x][i];
		if(dep[y])
			continue;
		dfs1(y,d+1);
	}
}

void dfs2(int x,int d)
{
	dep[x]=d;
	int len=g[x].size();
	for(int i=len-1; i>=0; i--)
	{
		int y=g[x][i];
		if(dep[y])
			continue;
		dfs2(y,d+1);
	}
}

int main()
{
	scanf("%d%d",&n,&m);
	for(int i=1; i<=m; i++)
	{
		scanf("%d%d",&e[i].x,&e[i].y);
		g[e[i].x].push_back(e[i].y);
	}
	
	for(int i=1; i<=n; i++)
		if(!dfn[i])
			Tarjan(i);
	
	for(int i=1; i<=n; i++)
	{
		for(int j=1; j<=n; j++)
			dep[j]=0;
		dfs1(i,1);
		for(int j=1; j<=n; j++)
			cmp[j]=dep[j],dep[j]=0; 
		dfs2(i,1);
		for(int j=1; j<=n; j++)
		{
			if(cmp[j]==2 && dep[j]==2)
				f[i][j]=0;
			else
				f[i][j]=1;
			
		}
	}
	
	for(int i=1; i<=m; i++)
	{
		int x=e[i].x,y=e[i].y;
		if(c[x]==c[y])
		{
			if(f[x][y])
				printf("same\n");
			else
				printf("diff\n");
		}
		else
		{
			if(f[x][y])
				printf("diff\n");
			else
				printf("same\n");
		}
	}
	
	return 0;
}

T4 ColoringBalls

神仙题，不在能力范围之内

Step 1：考虑某种颜色序列能否被生成

注意到如果一些颜色段之间有黑色，那么这些颜色段之间就是相互独立的。于是我们先考虑这些独立的颜色段

一些叠加的等效的操作（如操作 rbr 染成一个纯红色段）其实都可以变成一个最简的操作（只操作 r，略过 rb），因此我们我们定义一个颜色序列 \(C\) 的最简操作序列 \(P\) 为： \(P\) 能染出 \(C\) 而 \(P\) 的任意子序列都无法染出 \(C\)。可以定义纯红段为只有红色的独立颜色段，杂色段为红蓝混合的独立颜色段

  • 考虑杂色段的最简操作序列

    不难发现，如果一个杂色段段有 \(k\) 个蓝色段，那么至少要染 \(k+1\) 次，红色和蓝色的染色次数在 \([1,k]\) 之间，都至少染一次。特殊的，若没有蓝色，则只需染一次红色

    在此基础上，还有染色顺序的限制。若我们决定染 \(a\) 次蓝色，最好的方案是：先染 \(1\) 次红色，再染 \(a-1\) 次蓝色，然后染一大段蓝色，最后这段大蓝色染完剩下的红色

    因此对杂色段最简操作序列的要求：满足个数 \(=k+1\)，最前面是 r，第二个是 b；

  • 而纯红段的最简操作序列即是一个 r

接着考虑由黑球分隔的各个颜色段

  • 设有 \(c\) 个杂色段，现在要在整个操作序列中选出若干个子序列，分别作为每个杂色段的操作序列。

    我们先要选出 \(c\) 个子序列 {r,b} 作为 \(c\) 个最简操作序列的开头，之后要为每个最简操作序列添加指定数目的字符，且满足字符在开头 {r,b} 的右侧。

    记 \(t_i\) 表示表示第 \(i\) 个 {r,b} 右侧剩余的未选择的字符数目，对应的最简操作序列还需要 \(s_i\) 个字符。那贪心一下，显然我们要将 \(t_i\) 从大到小排序，依次考虑，每次要尽量靠左选择字符

    形式化的，有解的充要条件是

    \[\forall i,t_i\geq\sum_{j=i}^c{s_i} \]

    用人话说就是剩余的字符数目要够自己和后面的所有 {r,b} 选择

    进一步考虑如何排列 \(s\) 的顺序。不难发现，将 \(s_i\) 降序排列，每个 \(\sum\limits_{j=i}^cs_j\) 都取到最小值，此时最可能满足条件

  • 再考虑 \(a\) 个纯红色段的情况，根据贪心，显然选取前面 \(a\) 个 r 最优

Step 2：\(\rm DP\) 计数

枚举纯红段和杂色段的数量 \(a,c\)，可确定 \(t_{1\sim c}\)

先考虑在确定 \(s\) 的情况下如何确定颜色序列的方案数

  • 先考虑颜色段之间的排列顺序。首先是杂色段和纯红段混合的方案数，为 \(\dbinom{a+c}{a}\)。由于纯红段最简操作序列的长度都是 \(1\)，因此我们只需考虑杂色段内部的顺序数，即 \(s\) 的不同排列数。这是典型的多重排列，记 \(x_i=[s_j=i]\)，排列数即为 \(\dfrac{(\sum{s_i})!}{\prod{c_i}!}\)

  • 接下来考虑确定颜色段顺序后的方案数

    各个颜色段长度不定，可以看作装球的盒子

    • 对于一个杂色段对应的 \(s_i\)，（注意总字符数为 \(s_i+2\)，蓝色段个数为 \(s_i+1\)），会产生 \(2s_i+1\) 个至少有一个球的颜色段，以及 \(2\) 个可以为空的颜色段（两端的红球段）

    • 对于一个纯红段，会产生 \(1\) 个至少有一个球的颜色段

    • 对于黑色的部分，会产生 \(a+c-1\) 个至少有一个球的颜色段，以及 \(2\) 个可以为空的颜色段（两端的黑球段）

    综上，非空盒的个数为 \(2(\sum{s_i}+c+a)-1\)，可空盒的个数为 \(2c+2\)，总球数为 \(n\)，插板法可求，答案为

    \[\binom{n+2c+2-1}{(\sum{s_i}+c+a)-1+2c+2-1} \]

接下来对不同的 \(s\) 序列进行统计。

设 \(f[i][j][k]\) 表示填写了 \(s_{i\sim c}\)，目前 \(\sum s=j\)，且 \(s_i=k\) 的方案数，则有转移：

\[f[i][j][k]=\sum_{p\geq 1}{\binom{c-i+1}{k}\sum_{g<k}{f[i+p][j-pk][g]}} \]

式子 \(\binom{c-i+1}{k}\) 用于处理多重排列，是将 \(p\) 个 \(k\) 归并到目前的 \(s\) 的方案数

前文的 \(\forall i,t_i\geq\sum\limits_{j=i}^c{s_i}\) 在这里体现为要求 \(j\leq t_i\) 且 \(j-pk\leq t_{i+p}\)

最终的答案为 \(\binom{a+c}{a}\times \sum{(f[1][\_][\_]\times cnt)}\)，\(cnt\) 为 \(s\) 序列的不同排列数，根据第二维的 \(\sum s\) 求出

使用前缀和优化 \(\rm dp\) 转移，再加上枚举 \(a,c\) 的复杂度，时间复杂度 \(O(n^5\log n)\)，可以通过

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

const int N=80,MOD=1e9+7;

int n,m;
int C[6*N][6*N],t[N],posr[N],posb[N];
LL ans,f[N][N][N];;
char str[N];
bool v[N];

void prework()
{
	for(int i=0; i<=320; i++)
		C[i][0]=1;
	for(int i=1; i<=320; i++)
		for(int j=1; j<=i; j++)
			C[i][j]=(C[i-1][j-1]+C[i-1][j])%MOD;
}

LL calc(int a,int c)
{
	memset(v,0,sizeof(v));
	memset(f,0,sizeof(f));
	
	int cnt=0;  LL res=0;
	for(int i=1; i<=m; i++) //计算杂色段的{r,b}
	{
		if(cnt==c)
			break;
		if(str[i]=='r')
		{
			v[i]=1;
			posr[++cnt]=i;  posb[cnt]=0;
			for(int j=i+1; j<=m; j++)
			{
				if(str[j]=='b' && !v[j])
				{
					v[j]=1;
					posb[cnt]=j;
					break;
				}
			}
			if(!posb[cnt])
				return 0;
		}
	}
	if(cnt<c)
		return 0;
	
	cnt=0;
	for(int i=1; i<=m; i++) //计算纯红段的一个r
	{
		if(cnt==a)
			break;
		if(v[i])
			continue;
		if(str[i]=='r')
			v[i]=1,cnt++;
	}
	if(cnt<a)	
		return 0;
	
	cnt=0;  int id=c;
	for(int i=m; i>=1; i--)  //计算t_1~t_c
	{
		if(!v[i])
			cnt++;
		if(i==posb[id])
			t[id]=cnt,id--;
	}
	
	for(int i=0; i<=m; i++)	
		f[c+1][0][i]=1;
	for(int i=c; i>=1; i--)
	{
		for(int j=0; j<=t[i] && 2*(j+a+c)-1<=n; j++)
		{
			for(int k=1; k<=m; k++)
			{
				int kk=k-1; //注意这里有一个下标的偏移
				for(int p=1; p<=c-i+1 && j-p*kk>=0 && j-p*kk<=t[i+p]; p++)
					(f[i][j][k]+=1LL*f[i+p][j-p*kk][k-1]*C[c-i+1][p]%MOD)%=MOD;
			}
			
			for(int k=1; k<=m; k++)  //前缀和优化
				(f[i][j][k]+=f[i][j][k-1])%=MOD;
		}
	}
	
	for(int j=0; j<=m; j++)
	{
		int x=2*(j+a+c)-1,y=2*c+2;
		(res+=1LL*f[1][j][m]*C[n+y-1][x+y-1]%MOD)%=MOD;  //s序列的不同排列数
	}
	res=1LL*res*C[a+c][a]%MOD;  //别忘了这个
	
	return res;	
}

int main()
{
	prework();
	
	scanf("%d%d%s",&n,&m,str+1);
	
	for(int a=0; a<=m; a++)  //枚举a,c
		for(int c=0; a+2*c<=m; c++)
			(ans+=calc(a,c))%=MOD;
			
	printf("%lld",ans);

	return 0;
}

\(100+100+40+0=240\)，\(\rm rk6\)

总结

  • T1 切的有点慢，以后得加快速度

  • T2 最后时间才想出正解，需要加强思维。部分分要大胆写，这次正解就是在部分分里想出来的。写代码要注意细节与范围限制，不能写的太随便

  • T3 其实可以进一步思考，不能满足暴力

  • T4 随缘

标签：最简,颜色,int,sum,测试,序列,rm,2023.8
From： https://www.cnblogs.com/xishanmeigao/p/17612604.html

相关文章

  • Apipost接口自动化测试入门
    今天我们来聊一聊接口自动化测试。以往我们都是以以代码的形式编写自动化测试脚本做自动化测试，网上也有非常多的攻略，那么在不会代码的情况下该怎么做接口自动化呢，今天给大家介绍Apipost自动化测试模块，不用写代码也能做接口自动化！点击左侧菜单栏「自动化测试」按钮进入自动化测试页......
  • Markdown测试页
    AwesomeEditor!Ithasbeenreleasedasopensourcein2018andhascontinuallyevolvedtoreceive10kGitHub⭐️Stars.CreateInstanceYoucancreateaninstancewiththefollowingcodeandusegetHtml()andgetMarkdown()oftheEditor.consteditor=new......
  • 性能测试-基础篇
    前言：性能是什么 每个人眼里对性能理解不一样，但是我们如果从一个App的维度来看： 用户眼中的性能：1、App使用崩溃，卡顿，延迟2、App反应慢，使用页面无反应 那开发眼中的性能：1、数据库设计是否合理2、代码逻辑、算法是否可以优化 运维眼中的性能：1、服务器资源使用是否合理......
  • 软件测试|web自动化测试神器playwright教程（二十七）
    前言使用selenium进行web自动化测试，如果我们打开了多个网页，进行网页切换时，我们需要先获取各个页面的句柄，通过句柄来区分各个页面，然后使用switch_to.window()实现切换，这样的操作比较麻烦，playwright的网页切换比selenium更为简单快捷。本文就给大家介绍一下playwright多个网页的切......
  • 软件测试|JMeter 参数化的方式有哪些
    JMeter中常见的参数化方式包括：CSV数据文件：从CSV文件中读取数据，并将其用于请求参数。数据库访问：从数据库中读取数据，并将其用于请求参数。用户定义的变量：手动定义变量值，并将其用于请求参数。随机变量：随机生成变量值，并将其用于请求参数。Counter：生成一个递增的计数器，并将其......
  • 软件测试|web自动化测试神器playwright教程（二十八）
    前言在我们使用部分网站的时候，我们会遇到进行日期选择的问题，比如我们预定火车票或者预定酒店，需要选择发车日期或者酒店的入住与退房时间。我们执行自动化测试遇到日期控件时，如果可以输入，可以使用selenium的send_keys()方法进行输入，playwright同样也可以实现对日期控件的操作，本文......
  • 2023.8 模拟赛日志
    2023暑假集训ab班day1127round。预期：\(0+25+0=25\)实际：\(80+20+0=100\)题目：23ab-day1划（待写）不会做，搞了很久最后逐一假掉。竟然有分。题解是一些恶心的区间分类，比较简单，可惜了。好像有很多做法23ab-day1Heinrich树论科技，跳过。写了暴力换根。23ab-day1朝花夕拾......
  • 2023.8.7
    CodeforcesRound890(Div.2)A.TalesofaSort题意给定一段数字序列，每次操作将每个大于\(0\)的数\(-1\)，求最少几次操作后整个序列单调上升。我们可以转化成将序列中的每个数都减去某个数\(x\)，使得序列大于等于\(0\)的部分单调上升，这个\(x\)就是操作的次数。也就......
  • ku安装及测试
    1）修改内核参数和模块cat<<EOF>/etc/sysctl.d/k8s.confnet.bridge.bridge-nf-call-ip6tables=1net.bridge.bridge-nf-call-iptables=1EOF#使内核参数配置生效sysctl--system&&modprobebr_netfilter&&lsmod|grepbr_netfilter2）关闭交换内存swapoff-a&......
  • 【软件测试学习】—软件测试的基本认识（一）
    【软件测试学习】—软件测试的基本认识（一）文章目录【软件测试学习】—软件测试的基本认识（一）一、什么是软件测试二、软件测试的目的三、测试的原则四、测试的标准五、测试的基本要求六、bug的由来七、测试的流程八、开发模式九、测试与开发的关系一、什么是软件测试总结起来就是：使......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99