惯性聚合 高效追踪和阅读你感兴趣的博客、新闻、科技资讯
阅读原文 在惯性聚合中打开

推荐订阅源

博客园 - 三生石上(FineUI控件)
S
SegmentFault 最新的问题
Jina AI
Jina AI
OSCHINA 社区最新新闻
OSCHINA 社区最新新闻
IT之家
IT之家
美团技术团队
V
Visual Studio Blog
人人都是产品经理
人人都是产品经理
博客园 - 叶小钗
有赞技术团队
有赞技术团队
GbyAI
GbyAI
宝玉的分享
宝玉的分享
腾讯CDC
M
MIT News - Artificial intelligence
博客园 - 【当耐特】
Google DeepMind News
Google DeepMind News
月光博客
月光博客
MyScale Blog
MyScale Blog
Last Week in AI
Last Week in AI
freeCodeCamp Programming Tutorials: Python, JavaScript, Git & More
钛媒体:引领未来商业与生活新知
钛媒体:引领未来商业与生活新知
博客园 - 司徒正美
Recent Announcements
Recent Announcements
MongoDB | Blog
MongoDB | Blog

静静的小窝

在VPS服务器上面安装OpenClaw并使用OpenRouter的免费API的一些“坑” | Some "pits" about installing OpenClaw and using OpenRouter's free API on a VPS server 五年了啊 | Five years 一个奇怪的估算 | A strange estimation 虚拟直播之路2 | Living as a V 2 虚拟直播之路 | Living as a V AI 写代码?| AI coding? X静评1.1:谷歌,快成了?| XComment1.1 Is Google's Success Coming? X静评0.3:要精致吗?| XComment0.3 Be Dainty? X静评0.2:座位是购买的服务还是赠送的服务?| Xcomment0.2 A Bought Seat or A Gift Seat X静评0.1:一纸限令,毁掉一个政策?| XComment0.1 One Paper, One Dead Policy? hadoop 3.2.2 Cluster Setup | hadoop 3.2.2 的集群启动 894A题解|894A Solution VY223 Journal Smith’s death 第一次翻墙|first cross wall 2021年蓝桥杯|LanQiaoCup2021 参赛|Attending Contest 新旧|New and Old 去毛泽东旧居| visit MAO ZEDONG old house 拜登会团结美国吗|Will Biden unite the USA? 出生|Birth 背包问题|knapsack problem 冒泡排序与排序的稳定性|Bubble Sort and Stability 看完哔哩哔哩上的NASA的火星车直播后的一些话|My words after watching NASA's launch of the Mars 2020 perseverance rover live on Bilibili 选择排序|Selection Sort 饭圈与特郎普|fandom and Trump 不盲目|No Blindness 从3到n——一道数学题|a math problem from 3 to N 公权与私权|public and private rights 我在第几层|Where I Am
[题解]异或三角形|2021蓝桥杯国赛|xor triangle
静静 · 2021-06-06 · via 静静的小窝

此文使用了mathjax,请等待公式加载
这是2021年蓝桥杯国赛A组C++的一道题目。

当时没有来得及写暴力对拍,只是测了示例过了,也就是说不确定是否正确。

  首先考虑异或操作的特性,可以交换,所以不妨考虑 $a \geq b \geq c$的情况。随后根据三个数字异或为0,不难看出每一位的异或结果都是0。这也就是说每一位的三个数字只有两种可能,2个1一个0或三个0。不难知道a的首位一定是1,所以另外两个数字在此处必为一1一0。可由此用反证法证明3个数必不相等:
  如果三个数相等,二进制下首位必相等,与首位一1一0矛盾。如果只有两个数相等,那么这两个数在2进制下必定同1同0。为了满足三个数异或为0,第三个数每一位都只能为0,得出第三数为0,无法形成三角形。

  这样一来三个数的排列组合就确定了,直接乘以6即可。
  第一位数已经确定,接下来考虑第二位数,若a为0,则另外2数也只能为0(若都为1则b大于a)。同理从第2位开始的连续的0不会增加可能性。一直递推到(最高位起)第2个1(第一个1为首位,以分析过)。显然另外2数在此处一1一0,因为a为1,所以两种0和1的排列均不会超过a(最多等于)。但是如果所有的1对应的10排列都是b取1,则$a=b$相等,与之前的分析不符,也就是说这么多的排列里面有一种是不可行的。(限制1)再分析0,因为要保证$a>b$,只有在前面已经有a与b不等的情况下才有$a=0,b=1$的可能(c少一位,所以不存在相等的可能)并且不能全为$a=0,b=0$(c为0也不符合条件),即可能情况最多为$2^n-1$(假设有a在这种条件下的1有$n$个)。(限制2)
  另外再分析三角形的条件,若a为1,b与c为0和1,相加不会大于1,若三数均为0,也不会大于a,也就是说至少有一个地方是a为0,另外2数为1。考虑以上条件不难发现需要考虑a的0和1的不同情况进行排列组合。所以不妨从最低位计算到第2高位的1,并且以1作为主要考虑(0依赖与1的情况)。在a为1的位置,为了a为0的方便,不妨假设在这一位b为0,c为1,那么低位的0有$2^n-1$种,低位的1有$2^n$种(n对应各自在低位中的个数)。然后累加一直到第二高位的1。
  在这个过程中一种假设了一个位为$a=1,b=0,c=1$,所以限制1满足,而限制2通过减一也满足了。最后将答案乘以6,即为最大数为a的组合数。
  考虑到输入有多种可能,不妨先根据最大数的大小排序计算,再根据输入顺序排序输出。
代码略(没有复制)。