CCF NOI考纲里没有提到构造
构造算法很难出部分分,基本只有暴力和正解
除了少部分构造算法可以要求字典序最小外,几乎一定需要 Special Judge
构造算法在 信息竞赛中比较少见 往往出现在 Codeforces 和 Atcoder 中
https://codeforces.com/blog/entry/46756
https://codeforces.com/blog/entry/62393
https://ipsc.ksp.sk/2014/real/problems/h.html
01101001
s[i] = 'a' + __builtin_parity(i);
可以卡掉 mod 2的次幂的 hash
Hash Killer 2
通过hash值对比两个字符串是否一样
通过hash对n个字符串去重(相当于对比了n*(n-1)/2)
对于 mod p 的 hash
大约对比 p 次会出错
多个模数相当于模 lcm
如果模数是质数,底数可以随机
构造一个DP使得方案数是 mod 的倍数
https://www.luogu.com.cn/problem/P3959
这个题目的数据非常弱,以至于各种错误的贪心,直接搜索都可以通过。
大家可以试图卡一下
https://www.luogu.org/blog/dazade8/solution-p3959
这份题解中的做法。
https://www.luogu.com.cn/problem/P2757
构造一个 NO 的例子
4 2 6 3 7 1 5
0 0 0 0 0 0 0
0 0 0 1 0 0 0
0 1 0 1 0 0 0
0 1 0 1 0 1 0
0 1 1 1 0 1 0
0 1 1 1 0 1 1
1 1 1 1 0 1 1
1 1 1 1 1 1 1
7
0 0 0 0 0 0 0
0 0 0 1 0 0 0
0 1 0 1 0 0 0
0 1 0 1 0 1 0
4 2 6
0 0 0 0
0 1 0 0
0 1 0 1
1 1 0 1
1 1 1 1
2 4 1 3
生成一个长度为N,答案是NO的解:
def solve(N):
if N==1:
return [1]
按奇偶把所有位置分成两部分,分别求解
L = solve(N / 2)
R = solve((N + 1) / 2)
ans = []
for i in L:
ans.append(2 * i)
for i in R:
ans.append(2 * i - 1)
return ans
https://codeforces.com/problemset/problem/1673/F
找到一组解,如何最小化?
https://codeforces.com/problemset/problem/1551/D2
放多米诺骨牌,分类讨论
https://codeforces.com/problemset/problem/1621/D
难点在理解题意,8个点求最小值
https://codeforces.com/problemset/problem/1375/E
生成所有逆序对,排序
https://codeforces.com/problemset/problem/1419/E
生成所有约数,分类讨论
https://codeforces.com/problemset/problem/1353/D
生成所有区间,排序
https://codeforces.com/problemset/problem/1343/F
枚举第一个元素
https://codeforces.com/problemset/problem/1217/D
拓扑排序,边染色
https://atcoder.jp/contests/code-festival-2017-quala/tasks/code_festival_2017_quala_c
重排字符矩阵,使得每一行每一列都回文
每一行每一列
https://codeforces.com/problemset/problem/843/B
https://codeforces.com/blog/entry/54038
Hack固定种子随机算法
Hack Random Solution
甲和乙
甲自己想了8位 00100101 (乙不知道)
乙的目标是让甲的数字变为 00000000
乙的操作是 给甲8位 abcdefgh
甲先把这个数字循环移动一下 fghabcde
再把自己的数字 ^= fghabcde
然后把结果中1的个数告诉乙
现在你是乙,你该怎么操作
考虑最后一步是什么?
甲自己有11111111 乙给甲 11111111 ,只能直接异或
倒数第二步是什么?
甲自己有01010101 乙给甲 01010101 ,甲要么异或成11111111,要么异或成00000000
倒数第三步是什么?
甲自己有00110011 乙给甲 00110011 ,甲要么异或成11111111,要么异或成00000000,要么异或成01010101
甲自己有00001111 乙给甲 00001111 ,甲要么异或成11111111 00000000 00110011 00010001 01110111
00010111
甲内心想了 01
乙给甲2位 00
甲循环移动成 00
然后 01 ^ 00 = 01
然后告诉乙,结果里有1个1
乙给甲2位 01
甲循环移动成 10
然后 01 ^ 10 = 11
然后告诉乙,结果里有2个1
乙给甲2位 11
甲循环移动成 11
然后 11 ^ 11 = 00
乙获胜了
乙最多操作300次