转跳到内容

【红包inside!】萌新的算法挑战#3~


由骚男添加的消息,

即日起(7.12),将对本主题的回复进行更进一步的审查,以减少水红包的情况

一些不违规的回复,也有被视为水回的可能。还请各位适度吐槽,积极交流。

推荐贴

一共520朵花,n : 花的品种的个数,c: 花的颜色的个数。要求:每个花束中的花数量差值不可超过一

 每个花束中的花品种颜色各不相同          你想要将这些花放在尽可能少的花束之中
解:难点为花束要少,即每束花花量最多,假设520朵都放一束里,n=520,c=1。
答:有520朵不同品种的花,每个品种花都只有一种颜色,颜色有520种。(色值问题其实没有完全一样的颜色)
自定义框架下:常用的十二种颜色分别是红,橙,黄,绿,青,蓝,紫,灰,粉,黑,白,棕。 十二色又称十二色环 即0<c<13,0<n<521。品种颜色各不相同即同颜色只能出现在一个品种上,要求每束花里品种不同即一束花最多有12朵颜色的品种不同花。即最少1束花,一束花里 43 43 43 43 43 43 43 43 4 44 44 44 44 差值为1 也满足,总520朵

谷fds 获得了红包 0.23节操

链接到点评
  • 2 周后...

好难啊,不会

能想到的思路1是二分答案+dfs的check,但是好像答案因为有差值1的约束,并不具有单调性

思路2是试图转化为二分图,想不懂,大概是只能处理min(c,n)== 2的情况

最后就是枚举size+dfs回溯了。总感觉问题是npc的,但又不会证明或者规约

 

(我说实话,就算数据量很小,指数级dfs回溯都不一定会写,好讨厌带约束的最值

这题我如果遇到,我就直接模拟退火了,生死由命成败在天

Muriya Tensei 获得了红包 0.32节操

链接到点评

不是太能理解做法,如果是每个种类的花束中以种类划分花的颜色尽可能多而且差值均等那试试看贪心算法?

先选定某个品种的某个颜色,最大值定为temp,然后比对其他颜色的最大值,如果差值小于1则不动,大于1则取这个值赋给temp依次类推直到得到所有种类的temp

不过这样不太像贪心了

mhs117 获得了红包 2.64节操

mhs117在诱导萌新女装时被路过的随便拦下,被批评教育并收取学费-3节操

链接到点评
  • 2 周后...
  • 3 周后...

 

首先将每朵花转换为另一个矩阵:(其实我是想起了消消乐)

如:

引用

1, 2, 3, 1, 1

0, 1, 0, 1, 1

中,红色数字的花朵转为:

引用

1 1 1 2 1

0 0 0 1 0

则可以轻易得出,对于任意一束花:

"其所有花的foo矩阵求和结果中的每一个值都不大于2" 等价于 "该花束满足题目条件";

证明如下:

剧透

正向:如果花束有冲突,则冲突花位置的值肯定不小于 3;

反向:如果花束满足条件,但 某点的值>=3 则:

  1. 该点有花,但因为满足条件,同行或同列没有花,此点的值为 2;

  2. 该点没花,则[所在行]和[所在列]的花朵数量之和>=3,则鸽笼原理,一定有一行/列有两朵花,矛盾。

 

因此我们将题设矩阵转为上文的矩阵,将其结果中最大值除以2,就是[不考虑花束数量均摊]的最小值。

 

(但是均摊算法还没想好,应该得矩阵排序下)

 

(说起来我想起那个红魔馆女仆打扫房间的矩阵题目了...)

drop_table_all 获得了红包 7.71节操

链接到点评

思路:1.把每个种类中的颜色数量最多的花依次排序

2.依次把数量最多的这些花组成花束

3.最后会剩下有空缺种类颜色的,从之前的花束里遍历,如果其中有自己空缺的种类+颜色且花束为满,摘到自己的花束中,直到自己花束花的数量=最多的花束-1

饿掉鱼 获得了红包 18.99节操

链接到点评
  • 2 周后...
  • 1 个月后...
  • 骚男锁定了本主题
游客
此主题已关闭。
×
×
  • 新建...

重要消息

为使您更好地使用该站点,请仔细阅读以下内容: 使用条款