首页 > 最后的晚餐(dinner)
开通博客写题解
头像 shyyhs
发表于 2020-09-22 17:54:45
首先因为是个环,我们得先随机分配一个确定起点,然后剩下的方案总数是(2*n-1)!.然后就是我们的容斥原理了,0个相邻的-1个相邻的+2个相邻的-3+4... 0个相邻的答案就是(2*n-1)! 1个相邻的答案是2*C(n,1)*(2*n-2)!.对于这个的解释就是你n对中选取1对,然后前后顺序考虑 展开全文
去ta的博客 赞 (9) 回复(0) 收起
头像 又在摸鱼的大熊猫很勤奋努力
发表于 2020-09-22 17:00:45
#最后的晚餐 题目大意 有一个有2∗n2*n2∗n个座位的圆桌，还有nnn对情侣 求任意一对情侣不相邻的座位安排方案数（按顺/逆时针旋转重合视为一种方案） 分析 感觉主流做法都是组合数+简单容斥 这里来一个非主流做法，希望能给到大家一些新的思路 Step One 首先假设，这nnn对情侣中每队都有一 展开全文
去ta的博客 赞 (9) 回复(3) 收起
头像 DeNeRATe
发表于 2020-09-22 16:16:46
分析 看到这道题断定就是一个简单的圆排列问题但由于我们不知道有几对情侣会在一起那么我们求一个补问题枚举坐在一起的情侣的对数再进行简单容斥即可容易推出公式: 由于本题需要的是的时间复杂度所以我们需要对于每个组合数求得Fac[]表示前缀积Inv[]表示前缀积的逆元那么 即可解决这个问题 代码 //New 展开全文
去ta的博客 赞 (4) 回复(0) 收起
头像 __故人__
发表于 2020-09-22 16:21:38
分析 一眼的数学题。因为原问题并不好做，按照正难则反，我们先考虑容斥。定义 表示至少有 对情侣坐在了一起。那么 。 为容斥系数。考虑单独的 如何求解。那么我们发现这是在求一个圆排列，根据 元素构成的圆排列方式为 。所以 。 表示 个有标号的元素的圆排列方式。最后 。注意一下空间 展开全文
去ta的博客 赞 (4) 回复(0) 收起
头像 林思艺
发表于 2020-09-23 11:20:59
一眼看上去就是一个经典题啊 直接考虑不是很容易那就容斥 全部方案为：一对相邻：,此情况有种两对相邻：,此情况有种……所以： 最后预处理一下就可以了。 #include<bits/stdc++.h> #define ll long long const ll N=30000010,INF 展开全文
去ta的博客 赞 (3) 回复(0) 收起
头像 issue是云哥的小迷×呀
发表于 2020-10-01 21:03:00
不得不说是个垃圾题目,这样可以卡空间真的没必要..... 圆排列个数是,因为可以以任意一个点开头 那么考虑至少有一对情侣相邻,也就是,选一对情侣出来 现在把这对情侣看成一个整体,就只剩下个人排列了 情侣内部可以正反,再乘以 接下来就上容斥把 #include <bits/stdc++.h> 展开全文
去ta的博客 赞 (2) 回复(0) 收起
头像 sunrise__sunrise
发表于 2020-09-28 12:00:18
题目大意 存在n对情侣，一共2 * n个人，现在要求每对情侣都不能相邻而坐，有多少种排序的方案。 Solution 首先这是一个环，所以1234与2341是同样的方案，那么从n对情侣中先把男生挑出来共n个人先去坐位子，共(n-1)!个方案。 接下来就是把剩下n个人插入进去了。定义dp[i]代表安排完 展开全文
去ta的博客 赞 (0) 回复(0) 收起
头像 andif
发表于 2023-09-10 15:37:00
NC19857 - 最后的晚餐 题意 给你一个圆桌，这个圆桌有个位置，现在有对情侣要入座，问你有多少种方案使得所有情侣都不相邻 数据范围 思路 我们定义性质表示第对情侣相邻， 那么这个题的答案就是 那么根据容斥原理可得: 因为每对情侣的情况是一样的，假设有对情侣相邻，那么方案数就是 那么最终的答 展开全文
去ta的博客 赞 (0) 回复(0) 收起
查看本题
查看本题讨论

相关比赛

等你来战

查看全部
牛客竞赛，专业的竞技算法训练平台

扫描二维码，进入QQ群

扫码关注“比赛自动姬”