考试策略

原因竟然是做不出T1和T2,只能去打T3(麻将)的代码...(不不不,其实除了你别人都做出了T1)
首先看了一下T1和T2,都不是很有思路。于是T1打了60分暴力,T2打了40分暴力,然后发现T3就是一个愚蠢的搜索。所以花了一个多小时的时间打了T3,检查一遍感觉没有什么问题,就交了。

T1

期望得分:60 实际得分:60

题目描述

LargeDumpling 最近参加了志愿家教活动,结果第一次小朋友请假了,于是他在纸上玩起了矩阵。
LargeDumpling 在纸上写下了一个 n 行 m 列的 01 矩阵,他可以进行任意次交换任意两行的操作,他想找到操作后的最大的全 1 子矩阵。
LargeDumpling 在 1s 内就在脑中算出了结果,所以你的程序也需要在 1s 内得出结果。

数据范围

对于20%的数据:$1 \leq n,m \leq 8$

对于50%的数据:$1 \leq n,m \leq 50$

对于60%的数据:$1 \leq n,m \leq 200$

对于100%的数据:$1 \leq n,m \leq 1000$

解题思路
如果您是从boshi大佬的博客里过来的,请不要相信他的鬼话,我这里的满分算法也是$O(n^2logn)$的

60分就是枚举宽度的区间,预处理每一行前缀和后统计哪些行这一个区间都是1,这个就是当前区间可能的宽度。

100分算法感谢xzy大神的提供:对于每一个点,统计其左端有多少连续的1.然后枚举子矩阵的右端,将所有行的当前这一列其左端连续的1的数量排序,即移动该矩阵的行,使得当前列是一个三角形(如图),然后在这个三角形里找矩阵。


代码

T2

期望得分:40 实际得分:50

题目描述

圣诞节快到了,jvjhfhg 开始思考给他的儿子们送礼物的事情。
jvjhfhg 有 m 个儿子,由于 Steam 游戏常常打折,他决定给他们买 Steam 游戏作为礼物。Steam 的打折游戏非常多,你可以认为有 无数件,jvjhfhg 根据价格将它们分成了 n 类,每一类的价格为 p i 。他的每个儿子给出了一个幸运数字 a i ,表示他希望得到价值和为 a i 的游戏。作为一个优秀的父亲,jvjhfhg 当然想要尽可能地满足所有儿子的要求,于是他想知道能满足多少个儿子的要求。

数据范围

对于30%的数据:$n \leq 10,m \leq 100,p_i \leq 50,0 \leq a_i \leq 2*10^5$

对于60%的数据:$n \leq 100,p_i \leq 200$

对于另外10%的数据:n=2

对于100%的数据:$n \leq 500,m \leq 300000,p_i \leq 10000,0 \leq a_i \leq 4*10^7$

题目分析

50分啊,30%数据可以一个完全背包瞎搞。10%的数据可以一个扩欧再瞎搞,还有多出来的10分好像是我写的“如果是所有礼物的公约数的倍数,就算作可以满足”这样的一个骗分蜜汁多骗了10分?

而标解的思路是极其巧妙的。我们令物品里最小价格是pmin,对于一个儿子的要求x,如果x模pmin的结果是y,而除了最小价格物品以外的其他物品凑出一个模pmin结果是y的价格z,这个价格比x小,则是x是可以凑出来的(因为x-z的部分可以通过使用pmin来完成)

那么怎么求其他物品凑一个模pmin答案为y的最小价格呢?答案居然是——最短路!

没错,就是最短路,每个取模后得到的数是节点,而路是除了最小价格物品以外的其他物品,路径长度是物品价格,路径终点要自己计算。

具体看代码吧,这题太巧妙了。

代码

T3

期望得分:100 实际得分:35

题目描述

AddEdge 最近沉迷日本麻将。
麻将是一个四人游玩的游戏。麻将牌由以下四类牌组成:
万子:一万至九万,我们用 1m~9m 表示。
索子:一索至九索,我们用 1s~9s 表示。
饼子:一饼至九饼,我们用 1p~9p 表示。
以上三种为数牌。
字牌:包括东、南、西、北、白、发、中七种牌,为了方便,我们依次用1c~7c 表示。
以上每种牌各有 四张。
麻将和牌时有 14 张牌,和牌型通常为四面子加一雀头。面子是指顺子(三张同色且数字连续的数牌,如 1p 2p 3p 或 6m 7m 8m, 字牌不能形成顺子)或刻子(三张相同的牌,如 3s 3s 3s 或 5c 5c 5c),雀头是一对子即两张相同的牌(如1m 1m 或 7c 7c)。
麻将中还有两种特殊和牌型:
七对子:由七个 不同的对子组成(日本麻将不承认“龙七对”手役,即一杠子加五对子)。
国士无双:由 1m 9m 1s 9s 1p 9p 1c 2c 3c 4c 5c 6c 7c 加上这十三张牌中的任意一张组成。
每局麻将开始时四名玩家各有 13 张牌,每一轮每名玩家摸一张牌并打出一张牌。当一副手牌再加上某一张牌构成一个和牌型时,我们称这副手牌听这张牌。
考虑一副未进行吃、碰、杠等鸣牌操作的手牌,判断这副手牌可以听哪些牌。 注意:在此题中, 不能再摸起的牌 即每种牌的第五张 不 能 算 作 听 的 牌

数据范围

本题仅有 2 个测试点,采用 Special Judge 评分。
测试点均由 Part1、Part2 两部分组成
11 仅当全部正确时得分。
Part2(S2 分),每 X 个正确的数据得 1 分。
对于 Part2,为了防止骗分,每 Y 个输出"Nooten"导致答案错误的数据会倒扣1分,最低不会低于0分

对于测试点1(35分):S1=10,S2=25,T=500,X=20,Y=10

对于测试点2(65分):S1=25,S2=40,T=10000,X=250,Y=100

解题思路

出题人我***

不行不行,不能粗鲁,我要心平气和,我要做个淑女...

好吧,所谓解题思路,就是暴力特判国士无双和七对子,然后枚举添加的手牌,然后先确定雀头,再枚举面子。思路非常简单,代码虽然长但是写起来还是很畅快的(然而调起来并不畅快)

我经过一个多小时的写代码,调试,静态查错后确定此代码没有问题——但是我TM被卡了,第二个测试点TLE,时限开大成1.5s就A了。

后来我才发现,原来枚举了一个顺子后,如果答案是不行,也直接return不用枚举下一对顺子,因为在优先枚举刻子的情况下,顺子只要枚举一对,接下来一定会枚举下一对,所以可以避免冗余操作。

代码

最后总结

要敢于承认自己的智障,并为了改变这一现况不断奋斗。

脚踏实地,艰苦努力,赢是我运,输是我命。