首页 > 其他分享 >A Simple Task 题解

A Simple Task 题解

时间:2023-12-19 11:57:39浏览次数:37  
标签:Task Simple 题解 走过 计算 编号

这道题比较简单,简述一下思路。

考虑状压 \(DP\)。

设 \(dp_{i,j}\) 表示走到第 \(i\) 个点,之前走过的点的状态为 \(j\) 的环的数量。这里有一个细节,就是我们都钦定每个走过的第一点是整个状态中编号最小的点,这样不会重复计算。

考虑如何进行转移。如果当前点的编号比走过的最小编号还小就直接跳过这种情况。如果当前点没有走过,就走;如果走过且形成了环的话,就把答案加上。

for(int i = 0;i < (1 << n);i++)
		for(int j = 0;j < n;j++)
		{
			for(int k = head[j]; ~ k;k = e[k].nxt)
			{
				int now = e[k].v;
				if((1 << now) < (i & -i)) continue;
				if((1 << now) & i) 
				{
					if((i & -i) == 1 << now) ans += dp[i][j];
				}
				else dp[(1 << now) | i][now] += dp[i][j];
			}
		}

因为是无向边,所以每个环会被计算两次,还会计算二元环。最后将这些减掉就可以了。

标签:Task,Simple,题解,走过,计算,编号
From: https://www.cnblogs.com/Creeperl/p/17913373.html

相关文章

  • CF1900D Small GCD 题解
    原题链接:CF1900D,题意不多赘述。首先可以将\(a\)数组排序,并且枚举中间的那个数\(a_i\)。那么答案就是\(\sum_{j=1}^{i-1}\gcd(a_j,a_i)\times(n-i)\)。重点在于求前面的\(\gcd\)。可以用欧拉反演,但是也可以不用,因为我不会。假设我们当前已经枚举到了\(a_i\),设\(f_k\)表......
  • CF1902D Robot Queries 题解
    题意:有一个二维平面直角坐标系,给定一串向某个方向移动\(1\)个单位的操作。有\(q\)个询问,对于每个询问给定\(x,y,l,r\),问如果倒着做\(l\)到\(r\)这段区间中的操作,是否会经过\((x,y)\)。ds题。先预处理出\(sx_i,sy_i\)表示执行完操作\(i\)后的位置,如果在\([l,r]\)......
  • 华中师范大学2023新生赛 H 龙 题解
    Link华中师范大学2023新生赛H龙Question有\(m\)个宝石孔,有\(n\)个宝石,每个宝石可以提升\(a_i\)点战斗力每次镶嵌一个宝石,被选中的宝石会随机选择一个宝石孔进去,如果这个孔原来有宝石,则原来的宝石会被损坏你可以任意决定镶嵌宝石的顺序,她想知道,如果把着\(n\)颗宝......
  • 华中师范大学2023新生赛 D 身无彩凤双飞翼 题解
    Link华中师范大学2023新生赛D身无彩凤双飞翼Question给出一个\(n\timesm\)的网格,网格上有一些障碍,问最少添加多少障碍才能使\((1,1)\)和\((n,m)\)不连通Solution我好像用了一种和标答不一样的写法我们先对图bfs一次,如果\((1,1)\)不能到达\((n,m)\),则图本来就......
  • CF1905 B Begginer's Zelda 题解
    LinkCF1905BBegginer'sZeldaQuestion给出一棵树,每次能把一条路径压缩成一个点,求最少几次把树压缩成一个点Solution贪心的想,路径肯定越长越好,所以肯定是以一个儿子节点为起点,以一个儿子节点为终点,儿子节点合并了儿子到根的父节点也合并了,每次合并两个儿子节点,假设儿子节点......
  • 【题解】CodeForces-1913
    CodeForces-1913ARatingIncrease依题意模拟。提交记录:Submission-CodeForcesCodeForces-1913BSwapandDelete交换免费就是能任意重排,从头开始尽量填相反的,剩下只能删去了。提交记录:Submission-CodeForcesCodeForces-1913CGamewithMultiset从大到小能减则减一定......
  • 【题解】CodeForces-1905
    CodeForces-1905AConstructiveProblems发现沿着对角线放就行了,答案是\(\max(n+m)\)。提交记录:Submission-CodeForcesCodeForces-1905BBegginer'sZelda最优操作每次删两个叶子(除了最后一次只剩两个节点),所以答案是叶子个数除以二上取整。提交记录:Submission-CodeForc......
  • LightGCL Simple Yet Effective Graph Contrastive Learning For Recommendation论文
    Abstract目前的图对比学习方法都存在一些问题,它们要么对用户-项目交互图执行随机增强,要么依赖于基于启发式的增强技术(例如用户聚类)来生成对比视图。这些方法都不能很好的保留内在的语义结构,而且很容易受到噪声扰动的影响。所以我们提出了一个图对比学习范式LightGCL来减轻基于CL......
  • Java面向对象程序设计(上海交通大学出版社)12章及以后的课后问题解析
    1)Map集合和Collection集合的区别是什么? Map集合和Collection集合都是Java集合框架中的接口,它们之间有一些关键的区别:元素存储方式:Collection:用于存储单一元素的集合接口。它继承自Iterable接口,包含常见的子接口如List、Set。Map:用于存储键值对(key-value......
  • Cesium开发遇到的问题解决
    问题1:后台缓存收回进程无法释放上下文[/BUSINESS的缓存的[10]%-请考虑增加缓存的最大大小。原因:出现该问题是Tomcat启动时,占用的缓存较大,Tomcat默认的缓存是10000KB.解决:需要调整Tomcat目录下\conf\context.xml文件中的缓存的最大值,需要添加在<Context></Context>标签内,添加项如......