思路小寄:
\(T1\):
题意:
1.求出最小个数\(num\),同时构造一个方案使得:
\(x_1~x_{num}\)的或为\(x\)。
2.无解则输出\(-1\)。
\(solution1\)
每次询问背包转移,复杂度为\(O(n^3T)\)
\(solution2\)
预处理背包,每次询问\(O(n)\)查询。
复杂度\(O(n^3+nT)\)
结论简化版题意:
1.当\(x\)为\(3\)的倍数,输出\(x\)。
2.求两个\(3\)的倍数\(x\)\(y\),使得\(x|y=a\)。
3.若无解,输出\(-1\)。
\(solution3\)
考虑\(2\)进制,观察发现奇数位模\(3=1\),偶数位模\(3=2\),因此当奇数位\(1\)和偶数位\(1\)数量相等时,该数为\(3\)的倍数。
观察样例,答案无解或非\(0\)即\(1\)。
考虑各种分类构造。
1.消掉多余\(3\)。
2.构造使得奇数、偶数相等的解法。
3.构造奇数、偶数可以互相承受的解法。即根据性质,奇数位最多承受自己两倍数量的偶数位。
预计\(1h\),实际\(4h\)。
期望得分\(100\),实际得分\(100\)。
\(T2\)
考虑到概率转计数,但是不可做。
\(T3\)
不可做。
排名基本还行,\(RANK13\)。在时间分配上有亿点失误,但无伤大雅。