首页 > 踩不出足迹（T3）
开通博客写题解
头像 Zxsoul
发表于 2021-09-10 22:23:10
【C.踩不出足迹】题解 通过题目我们可以知道对于每到达一个数我们都会有两种操作 异或 同或 我们来看同或的性质，就拿题目给出的样例来说 ，经观察发现，这种操作等价于异或操作 位取反操作。 知道这个性质之后，发现每次操作都会异或，不同的是是否选择将 位进行取反操作。因为异或存在交换律，所以我 展开全文
去ta的博客 赞 (7) 回复(1) 收起
头像 zwk0518
发表于 2021-09-11 10:00:16
【C.踩不出足迹】题解看见其他大佬的题解，都是得出了一个简单的结论。我来讲讲我的。我们分开考虑0~k-1位二进制数，想要结果最大，最终运算出来的结果第k-1位必然为1，我们任取一种运算方式(比如在代码中，我让前n-1个数字异或，判断和最后一个数字是同或还是异或)，使得k-1位为1。emm之后我们考虑 展开全文
去ta的博客 赞 (3) 回复(0) 收起
头像 5ab
发表于 2021-09-10 22:37:15
一道清新的结论题。 我们通过观察真值表可以发现 ，其中 表示同或。同时，，又因为异或两个相同的数等价于抵消，所以答案只和异或上的 个数的奇偶性有关，即 次或 次。令： 那么答案就是 。 注意 可能爆 unsigned long long，计算 时需要这么计算： ((1ull <&l 展开全文
去ta的博客 赞 (2) 回复(0) 收起
头像 人丑心更黑
发表于 2021-11-11 08:37:13
题目大意： 输入n个数字，每个数字是长度为k的二进制数。现在每输入一个数，可以选择与上一次的结果进行同或或者是异或，问最大的结果。 思路： 显然dp是不行的。因为具有后效性。 没想到是个结论题，首先是可以发现同或的性质：同或=异或以后按位取反 那么我们可以将所有的数先异或起来。然后我们需要知道哪些数 展开全文
去ta的博客 赞 (0) 回复(0) 收起
查看本题
查看本题讨论

相关比赛

等你来战

查看全部
牛客竞赛，专业的竞技算法训练平台

扫描二维码，进入QQ群

扫码关注“比赛自动姬”