FJOI倒数21天

[隐藏]

今天江副校长和段长和我们三个谈话了,放我上来杠省选。期末考不用考。会考要考(倒数17天)。

不过说实话21天太少了。

红色题号:没搞很懂的题。

Notifications

  1. 不要忘记开long long int。
  2. 不要忘记取模。
  3. 不要忘记初始化数组。(高精度 / Floyd)
  4. 注意计算函数的位置。
  5. 提交前先查看计算结果。
  6. 提交前多做几组数据,特别是做数据难度不大的时候。
  7. 注意输出格式,特别是没有SPJ的带小数的时候。
  8. 注意查询区间max/min时,暂存变量的变量类型。
  9. abs不是模板函数,double类型使用fabs。

Day 1 [December 27, 2016]

照叶犇说的Register了bzoj开始刷。下午一节课加上一个晚自习。

“这个命有点难续啊。。

疯狂地做bzoj可能可以补救一下。。”

我也这么觉得。

正文中对于名词的超链接均蕴含“这是什么玩意”。

P1000 A+B Problem (Accepted)

深呼吸,一切正常,下一题。

P1001 [BeiJing2006]狼抓兔子 (Accepted)

这是什么玩意… 满脑子都是暴力,懵逼之后点开Google。

平面图的最小割,转对偶图求最短路。

具体操作就是,把(1,1)和(n,m)连一条边,构成一个新面,记为ext。把原来的外面的面记为0。

对于每条边(除了刚才连的那条),把它两侧的面连起来,代价即边权。

然后求[0]到[ext]的最短路,就AC了。

P1002 [FJOI2007]轮状病毒 (Accepted)

打表找规律,f[i] = 3 f[i-1] – f[i-2] + 2,要高精度。

但是据说正解是用基尔霍夫矩阵推的,这是什么玩意……

P1003 [ZJOI2006]物流运输 (Accepted)

嘿嘿嘿这题我之前写过了(趴)

最短路加上DP,没有什么搞不懂的。

P1004 [HNOI2008]Cards (Accepted)

这是什么玩意……

要打标签的话好像是DP,置换,逆元,Burnside引理。有点像求简化剩余系的感觉(虽然完全不是一个东西)。

呃,这里参考VFK的博客,DP方面参考IT大道的这篇文章

|X/G|就是解?求G中所有置换的d值的平均值就可以啦?

“X中经过G[i]的作用后仍旧为没有变化的元素个数为d(i),

置换群G在有限集合X作用下等价类的数目等于d(1),d(2),d(3)…d(n)的平均数。”

好吧,那怎么求d(i)?

“对于某一个置换要使置换后得到的与原来的相同,就应该把置换形成的染成同一种颜色,也就是说属于一个环内的元素颜色一定相同,然后一定要有一定量的红蓝绿色,因此用一个完全背包即可。

f[i][j][k]表示选了i张红色j张蓝色k张绿色的方案数,f[i][j][k]=f[i][j][k]+f[i-sum][j][k]+f[i][j-sum][k]+f[i][j][k-sum](sum表示当前环大小,然后i,j,k一定要判是不是大于sum),最后还有就是任何时候都不要忘了不动也是一个置换,因此有m+1个置换。”

恩……然后……就AC了。

这题调了半天在洛谷上各种WA和TLE,百思不得其解。

然后发现我把本来只要跑一次的计算函数重复跑了n次,放在input函数里了。

Day 2 [December 28, 2016]

恩……早上的政治课和地理课就……算了吧……?

P1005 [HNOI2008]明明的烦恼 (Accepted)

这题据说要用Prüfer序列

“一棵树要得到普吕弗序列,方法是逐次去掉树的顶点,直到剩下两个顶点。考虑树T,其顶点为{1, 2, …, n}。在第i步,去掉标号最小的叶,并把普吕弗序列的第i项设为这叶的邻顶点的标号。

一棵树的序列明显是唯一的,而且长为n − 2。”

另外有个Cayley定理,n顶点的标号树共有nn−2棵。(虽然这题好像没用)。

总之,这个树可以表示为n-2长度的序列,要往里面插入(tot=度数和-1)个序号;插第一个节点的方法x插第二个节点的方法…再x无度数限制的m个排列在剩余(n-2-tot)个空间中。

参考是这篇博文,还有这篇

我感觉我要死了Orz

我艹!A了!

高精度稍微改了一下,这回居然没出错。

我还想着这个数据规模怎么可能会TLE,结果是因为忘了把之前改的地方改回来导致质因数数量变成了负数……

结果两节课就做了两题(还有一题是昨天的)(趴)。

P1006 [HNOI2008]神奇的国度 (Accepted)

刚才打的五百多个字不见了,真是日狗。

算了,这题就是弦图染色。

参考资料是弦图与区间图的PPT

解法似乎有两种:

字典序BFS(这个我并没有看懂)

  • Initialize a sequence Σ of sets, to contain a single set containing all vertices.
  • Initialize the output sequence of vertices to be empty.
  • While Σ is non-empty:
    • Find and remove a vertex v from the first set in Σ
    • If the first set in Σ is now empty, remove it from Σ
    • Add v to the end of the output sequence.
    • For each edge v-w such that w still belongs to a set S in Σ:
      • If the set S containing w has not yet been replaced while processing v, create a new empty replacement set T and place it prior to S in the sequence; otherwise, let T be the set prior to S.
      • Move w from S to T, and if this causes S to become empty remove S from Σ.

最大势算法,但是按照英文名好像应该叫最大匹配搜索?

这个倒是挺好理解的,从n到1标号。每次标号的对象是现在势最大的点,其中势定义为相连的已标号的点数。标号为i的就是完美消除序列的第i个。

“先求出完美消除序列,再依照完美消除序列,从后向前,依次贪心染色,每次尽量染编号小的颜色。
最后输出最大颜色编号即可。”

那,写看看……WA了。

遂发现好像写的不对。

打出queue一看,发现有重复的,什么都明白了……

然后现在回头看jcvb说的就明白啦。

维护每个结点的“势”。并维护n个链表,分别表示势为0~n-1的结点各有哪些。
维护一个best值表示当前最大的势。
再开一个bool数组记录每个点是否已被取出放入序列。

初始时每个点势为0,都放在0号链表里。best=0。
①更新操作:某结点u的势从x变为x+1时,只要把u插到x+1链表的头部,无需将其从x链表中删除(所以不用写双向链表)。然后更新best值。
②取最大操作:取最大势结点时从best链表的头开始取,如果取到的是已被放入序列的结点就删除并继续往后取,仍取不到则–best,直到取到一个未被放入序列的点。
操作①每次O(1),总共执行O(m)次。best++也被执行O(m)次,那么操作②中–best也只有O(m)次。操作①每次插一个结点,则总共有O(n+m)个结点,而操作②中每往后取一个就删一个,所以也是O(n+m)。

哎,我还是把以前的那个blockquote的css搬过来吧。

恩,AC了。

第二次的WA死于贪心逆序,应该从后往前涂色,而不是从前往后涂色。不过到底怎么找“最小的可用的颜色”效率比较高呢?我直接扫了一遍周围的所有点,然后拿bool数组标记,再找最小的可用值。

P1007 [HNOI2008]水平可见直线 (Accepted)

看起来是道几何题,随便搜了一下……半凸包是什么玩意儿?

这题说不定可以直接写(?)

虽然我不知道半凸包是什么玩意儿但是我写了个二分(大概吧)就AC了。

具体来说,按第一关键字斜率升序,第二关键字截距降序排序。

第一条直线(a)和最后一条直线(b)显然是可见的嘛。

然后算出它们的交点(x1,y1),再从(a,b)范围内查找在x1时y最大的一条直线(c),这个也可见。

分别把a和c,c和b拖出来重复如上操作,然后就没有然后了。

来吧,下一题。

P1008 [HNOI2008]越狱 (Accepted)

这题应该就是普通的组合数学?……其实是快速幂模板题。

用Python交了一波…忘记取模(捂脸)

用C++交了一波…居然对指数取了模(捂脸)

没脸见人了……

P1009 [HNOI2008]GT考试 (Accepted)

一眼看上去好像是组合。

仔细一想好像哪里不对啊…

这题怎么列式子啊…

Google之,发现这玩意是DP(捂脸)

Google还说是AC自动机(KMP)。

KMP是退化的AC自动机,即模式串只有一个的情况。这里参考这篇博文来学习。

题解的话,这篇博文好像可以参考一下。但是他没说P是什么东西。

说实话我还是不太懂KMP和这题的关系orz

看了这里的代码好像懂了DP长什么样。

可是KMP?

这题的DP似乎要用到矩阵乘法x快速幂来加速。

不过我现在被编辑追着,先打点稿子…

最后我对着别人的代码打了一遍。

然后我打出了一个

num[i] = str[i] - 0;

被自己蠢到了……

但是我还是没搞太懂怎么推出来的。回头问叶犇……

Day 3 [December 29, 2016]

今天早上花了好多时间在P1009上Orz。

P1010 [HNOI2008]玩具装箱toy (Accepted)

待会我要打这个玩w。

O(n2) 的做法倒是比较显然,就是一个区间动规,但是这样显然过不去,需要斜率优化

这题参考这里,说得比较清楚。

说起来我又忘了加long long int。刚才不小心在机房睡着,班主任进来把我叫醒,差点没吓死orz

说起来题解里面也提到了凸包…?

代码里有两个while是用来维护队列的left和right,但是条件不是很懂。

#753A Santa Claus and Candies (Accepted)

轻松愉快的水题。

#753B Interactive Bulls and Cows (Easy) (Accepted)

这是我第一次做交互式题目,想想还有点兴奋呢w

题目大意是这样的,有四个互不相同的数字给你猜,每次反馈是正确位置的数字个数和错误位置的数字个数。

比方说答案是2378,猜2113的话就会得到1/1的结果。

Problem B的确简单,因为你可以猜50次。一个数字一个数字试下去都没问题;或者也可以经由0000 / 1111 / … 来找出四个数字,然后next_permutation搞下去。(我是这么做的)

好了,那么我的问题是,Problem C的Hard限制在7次 — 换句话说,在6次内要算出正解。怎么搞呢?

P1011 [HNOI2008]遥远的行星 (Accepted)

虽然我还是迷迷糊糊的,但是总算来到了HNOI2008的最后一题。

今天好困啊,效率不行。中午还挪出来打稿子了…不过终于一件落着(等等,我好像拖了一个月?那我是不是要开始打下一篇了…)

这题是瞎搞题吧……

需要数的数字在一定以下就暴力算,否则把j全部当成平均值一次算出来……气哭.jpg

P1012 [JSOI2008]最大数maxnumber (Accepted)

简单的线段树模板题,据说还有一些玄学做法?

因为是单点修改所以连lazy都不用打,轻松加愉快。

当初是对着这篇博文学的。

Day 4 [December 30, 2016]

如果不出意外的话,今晚打 Good Bye 2016

早上吃饭的时候突然对会考感到了不安Orz

P1013 [JSOI2008]球形空间产生器sphere (Accepted)

这题要用高斯消元来做。一开始我还在想怎么解一堆方程orz

自己写了个O(n^2)的算法,显然不对orz

好像还是不太懂(趴)。

参考Wiki写的

P1014 [JSOI2008]火星人prefix (Suspended)

黄学长的题解表示这题是splay维护字符串,然后二分+hash判断。

叶犇表示splay可以先鸽掉……真的没问题吗?

那就咕咕咕咕咕……

Day 5 [December 31, 2016]

昨晚打了比赛,Solve 2 out 8 Orz

Problem B不知道为什么WA掉了。该死的北极熊(。

Problem F明明知道解法,在时限前没打出来,垃圾网络毁我青春(打滚)

心好累……

P1015 [JSOI2008]星球大战starwar (Accepted)

反向并查集。

好像还是不太懂(趴)。

Day 6 [January 1, 2017]

喵喵喵。

Day 7 [January 2, 2017]

感觉会考不妙了啊orz恐怕得开个Page整理文科知识点了……(慌张)

P1016 [JSOI2008]最小生成树计数 (Accepted)

这题用到的性质我大概是没法自己想出来的罢(望天)

大体上的思路我明白了,就是同一张图的最小生成树中,相同边权的边的数量是固定的。所以只要搜索每种边权可能的组合数乘起来就好了。

搜索函数是这样的:

int fu = findSet(e.u), fv = findSet(e.v);
if (fu != fv) {
	fa[fu] = fv;
	search(id, p + 1, step + 1);
	fa[fu] = fu;
	fa[fv] = fv;
}
search(id, p + 1, step);

问题有两个:

  1. 为什么不能用路径压缩呢?
  2. 回溯的时候为什么是fa[fu] = fu而不是fa[e.u] = fu呢?

第二个问题其实跟第一个一样,因为那么做了就相当于路径压缩。

第一个问题大约是因为路径压缩了就不好回溯到原来的状态了吧。

Day 8 [January 3, 2017]

P1017 [JSOI2008]魔兽地图DotR (Accepted)

听这名字像是最短路对不对?不过这大概是DP。

时间限制30s,看起来非常的诡异……

是这样的,可以用金币来购买低级装备,然后有些装备可以合成高级装备,求M个金币能够获得的最大力量值。

这个嘛……说起来有点想at选课,不过不一样呢。

没有高级装备的话,那就只是一个普通的多重背包。

可是有了高级装备…也不是拆分开来那么简单的事情,数量限制源于低级装备,毕竟。有可能出了A装备和B装备就出不了C装备这样的。

看了眼vlk的博客,好神啊……不过……Orz

树型DP吗(望天)

我还是比较喜欢这种简单的题解

设f[i][j][k]表示对于第i个点,向父节点贡献j个已合成的装备,花费了k的代价,最多获得的力量值。
那么我们转移时枚举一共要合成几个道具i。然后再做个背包,大概是前i个节点花费代价为k最多可以提升多少点力量值。

简单的说,找到根 —— 那个没有被任何装备用作素材的高级装备就是根了。

然后开始dp,首先是递归dp同时求出每个装备的limit和cost,然后就是上面说的那样了。

exm?我怀疑数据有毛病。

调了一个早上加一节课,就因为答案还要找一遍最大值而不是f[i][0][m]……

加了个assert确定了,数据里面有长得不是一个树的点。傻逼管理员。艹。还得加个多重背包(反正这数据直接01bp干下去算了)。

为什么我的跑了8k ms啊Orz

为什么前面那些大神都是200ms啊Orz

算了开始杠历史。

Day 9 [January 4, 2017]

P1018 [SHOI2008]堵塞的交通traffic (Accepted)

听说这是道线段树好题(远目)

听说这题还可以分治并查集,那是啥(远目)

算了我也不搞事情了,想想线段树怎么写。

最后打了180行的线段树,调了一个下午带一个晚上,不给数据要死。

Day 10 [January 5, 2017]

P1019 [SHOI2008]汉诺塔 (Accepted)

按理说这其实是一道比较水的DP。

P1020 [SHOI2008]安全的航线flight (Suspended)

思路大概明白了,把每条“裸露”的线段拉出来二分。

可是我要怎么找到那些“裸露”的线段呢?

计算和所有边的交点?

好像也不是不行,我甚至不需要知道哪些边是陆地。

可是感觉光这样就很麻烦了……

P1021 [SHOI2008]Debt 循环的债务 (Suspended)

好像是个简单的DP,不过怎么定义状态呢……

P1022 [SHOI2008]小约翰的游戏John (Suspended)

其实这题我还想了挺久的(趴)

双方均为最优策略的情况下,要么必胜(W),要么必负(L)。下面的A和B代非1自然数,N代所有自然数。

只有一堆时,1是L,A是W;

有两堆时,1-N是W,A-A是L,A-B是W;

有三堆时,1-1-1是L,1-1-A是W,A-A-N是W,A-B-C好像不能断言。1-2-3是L,但是1-2-N,1-3-N,2-3-N都是W。然后我就开始纠结了。

换个角度看吧,比如全都是1,奇数堆就是L,偶数堆就是W。

然后呢(抓头)

P1023 [SHOI2008]cactus仙人掌图 (Suspended)

仙人掌DP?晚安。

Day 11 [January 6, 2017]

P1024 [SCOI2009]生日快乐 (Accepted)

简单的DFS就过去了。果然一早上起来碰到水题心情会好一点。

P1025 [SCOI2009]游戏 (Suspended)

这东西怎么搞…

等价于问许多个数,和为n,它们的最小公倍数有多少种可能?

为啥啊。

P1026 [SCOI2009]windy数 (Accepted)

说实话,我DP已经写完了,但是TM就是算不出来答案…

这叫数位DP来着?但是就算我拿着F,这玩意的结果怎么算啊。

折腾了半天一怒之下祭出了差分打表。不过我觉得我打表打得最牛逼的一次还是那次按质数间隔双重打表(

Something else

过一遍这些算法

《FJOI倒数21天》有6个想法

发表评论

电子邮件地址不会被公开。