首页 > Paint Box
开通博客写题解
头像 zzugzx
发表于 2020-06-11 22:13:02
题目链接 题意：题解： AC代码 /* Author:zzugzx Lang:C++ Blog:blog.csdn.net/qq_43756519 */ #include<bits/stdc++.h> using namespace std; #define f 展开全文
去ta的博客 赞 (9) 回复(0) 收起
头像 hnust_zhouzisheng
发表于 2020-06-16 15:22:26
数论——容斥原理。 从m种颜色中选出k种颜色给n个盒子上色，要求k种颜色都要用到且相邻盒子不能同色，求方法数。 首先，计算C(m,k)为选出k种颜色的方法数。 其次，k种颜色都要用到，换一句话说就是恰好用到k种颜色，显而易见应该转化为至少或者至多再考虑用容斥原理去重。记f(i)表示至多用i种颜色上色 展开全文
去ta的博客 赞 (4) 回复(0) 收起
头像 p3ng
发表于 2020-04-08 23:06:35
定义用不超过 种颜色涂完 个盒子的方案数为。 意为：第一个盒子有 种选法，第二个之后的每一个盒子都需要和前一个不一样即为 种选法，共选了次。 于是，根据容斥原理，用正好 种颜色涂完 个盒子的方案数为： 题中给了 种颜色，从 种颜色选 k 种的方案数为。 题目中要求的 n 个盒子，用 展开全文
去ta的博客 赞 (2) 回复(1) 收起
头像 JQK2020
发表于 2020-06-12 17:09:50
题目描述We have n empty boxes, so let’s recolor those boxes with m colors.The boxes are put in a line. It is not allowed to color any adjacent boxes with 展开全文
去ta的博客 赞 (2) 回复(0) 收起
头像 dilingtian
发表于 2022-11-02 12:47:22
快速幂 排列组合 容斥原理及二项式反演 题解 快速幂 对于一个数的次幂，如:2102^{10}210。最常规的计算方法是将2乘以10次，时间复杂度为：O(NNN)。 如果我们将它写成二进制:2101022^{{1010}_2}210102​，很自然的可以分解成2100022^{{1000}_2}2 展开全文
去ta的博客 赞 (2) 回复(0) 收起
头像 shyyhs
发表于 2021-01-21 20:01:10
一直不是很懂容斥原理的原因,学二分图的时候再看看!我们很容易知道,求给n个位子上色,可以最多使用k种颜色的方案数是.由容斥原理想到可以把最多->等于.那么就是最多使用k种颜色-最多使用k-1种颜色+最多使用k-2种颜***r>那么直接这样做就好了.(值得注意的是:因为取模了,所以会存在负 展开全文
去ta的博客 赞 (1) 回复(0) 收起
头像 NCHU19201329
发表于 2021-04-05 22:39:50
题目描述我们有n个空盒子，所以让我们用m种颜色重新着色那些盒子。盒子排成一行。不允许用相同的颜色给任何相邻的盒子上色。框i和框i + 1表示每隔i，1≤i≤n相邻。我们还希望n个框的不同颜色的总数恰好是k。当且仅当至少一个盒子用不同颜色上色时，两种方法才被认为是不同的。 对于恰好这个词,在开始还是不 展开全文
去ta的博客 赞 (1) 回复(0) 收起
查看本题
查看本题讨论

相关比赛

等你来战

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

扫描二维码，进入QQ群

扫码关注“比赛自动姬”