什么是 Ad-Hoc ?
做法是乱搞的,或结论只在这一个题有效的(作用范围太过狭窄),都可以被称为Ad-Hoc”构造题”.
P10033
给一个排列,构造一个每个元素属于[1,n]的数列使不存在 $l\le r$ 满足 给定排列小于1e6.
这个题考验分情况构造的能力.考虑推式子, $\sum_{i=1}^r(p_i-a_i)$ 前缀和不能重(以及为0),意味着我们要让a尽可能小满足前缀和递增,于是所有位置全是1.
考虑特殊情况计算(开始分情况了),1会分配给2,但是入果左右有2那就分配3,同时如果左右有3,那么考虑分配4,同时均衡一下3,因为1+4+1=3+1+2,于是3那个位置变成2.此题解决,复杂度O(n),检查的复杂度是O(nlogn).
CF1722G
构造一个互不相同的数列满足奇数项抑或和等于偶数项抑或和.(构造的数字必须在 $0-2^{31}$ 以内)
乍一看挺吓人?其实,因为值域很宽,各种各样的方法都可以通过.
法1:随机数,最后特判一下,如果重了就上一项抑或上某个数直到不重.
法2:直接排列,在1-n-3位上直接摆1-n-3,然后摆俩大数,n位上摆奇数项抑或偶数项保证相同.
CF1930B
构造一个排列满足不存在 ,样例:1
24 1 2 3
1 2 3
因为倍数首先要满足 ,然后这么构造也就需要满足所有偶数位大于奇数位,同时奇数位递增,偶数位递减即可.
P10635
给一个01矩阵,一次反转会翻转所有该硬币行和列的所有状态,求最少需要几次反转(方阵).1
2
3
4
5
6
74
0101
1000
0010
0101
2
我们不需要反转成全0或者全1,所以二者之间取最小值就行了.
发现,将单个元素反转的方法是,该行和该列上的全部元素全部反转一下就可以了.也就是说,给定矩阵必定有解.我们统计每行每列1的个数,然后遍历每个元素,看 (s[i][j]-'0'+co[i]+ro[j])&1 ,因为如果元素是1,我们要反转,所以要考虑原始矩阵对答案的贡献,不应该直接统计行列1的个数的那个.
CF476D
给一个n和k,构造n个四元组满足:
四元组内任意两个元素的gcd是k.
所有四元组的元素不重.
显然,k是没用的,直接乘上就完了.
先引一个结论: 任意三个连续奇数互质,任意奇数和偶数互质 .
这意味着什么?我们的四元组完全可以通过三个连续奇数一个偶数的方式进行枚举,很快完成.
P9667
给n个元素( $n\le500$ )和m,首先你可以选择任意m个元素直接删掉,在剩下的元素中,对某个元素可以进行以下三选一的操作:1.元素值+1,2.元素值-1,3.元素值>>1,问最后剩下的元素拥有相同非零值的最小操作次数是多少.(时限 $6s,a\le10^9$ )
注意到这个题诡异的数据范围还有很高的时长,可能要暴力枚举某个东西.猜结论:答案一定是某个数字除以2得到的结果,然后暴力检查更新答案.总复杂度 $O(n^2\log^2n)$ .
CF2031D
给一个数列,每个点有一只兔子,向左走只能走到更高的,向右走只能走到更低的,求最高可到达的点(所有).
(题解):首先,最右边的一定能到达最高点.然后考虑转移:
设mxxi表示第i个点的向左最高值,mnni是向右的最低值.如果元素i和i+1的关系是 $mxx_i>mnn_i$ 说明i可以到达i+1,于是答案这俩相同.但是如果不能到达,那就是只能向左走了,就是mxx_i.
GYM105588G
给两个数 $a,b$ ,每次能选一个数减掉 $\gcd(a,b)$ ,问最少几次能让两个数都减成0. 数据: $a\le5000,b\le10^{18}$
这个题奇怪的数据范围…
首先,一个数是0,另一个数一次就减成0.假如两个数字gcd是1,减掉之后,都会变成偶数,gcd就会变成2,依次类推.所以,a最多需要25次就能成0.所以答案最多就是26,暴搜即可,所以就看敢不敢搜了.出题人说实际上跑到26的数据非常少,出题人只构造出来了16的数据.
CF2078C
给一个长度为2*n的数列,告诉你缺少一个数字,原数列满足
你可以随意指代每个数字在哪里,随后按顺序输出就行,要求没有数字重合.
首先我们把式子重新安排一下:
发现前面半部分减后半部分可以排序实现差为正,然后后面两个直接最大化,就能保证 $a_{2n}$ 大于所有数字,也就保证了不重.
CF2078D
有两个数ab,你最多能猜2次,每次会回答 $(x|a)+(x|b)$ 的值,最后求一个输入的数 $(u|a)+(u|b)$ 的值.
0和另一个数是不对的.
标答说,你要尝试一次测试出一半的bit.
所以,令 $x=010101…$ 和 $x=101010…$ 即可.