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

推荐订阅源

cs.AI updates on arXiv.org
cs.AI updates on arXiv.org
Blog — PlanetScale
Blog — PlanetScale
钛媒体:引领未来商业与生活新知
钛媒体:引领未来商业与生活新知
The Last Watchdog
The Last Watchdog
AI
AI
Recent Announcements
Recent Announcements
Recent Commits to openclaw:main
Recent Commits to openclaw:main
Stack Overflow Blog
Stack Overflow Blog
V
Visual Studio Blog
J
Java Code Geeks
TaoSecurity Blog
TaoSecurity Blog
L
LangChain Blog
Exploit-DB.com RSS Feed
Exploit-DB.com RSS Feed
Project Zero
Project Zero
Microsoft Security Blog
Microsoft Security Blog
量子位
T
Threatpost
CTFtime.org: upcoming CTF events
CTFtime.org: upcoming CTF events
博客园 - Franky
博客园 - 聂微东
L
LINUX DO - 最新话题
Security Archives - TechRepublic
Security Archives - TechRepublic
Hugging Face - Blog
Hugging Face - Blog
T
The Blog of Author Tim Ferriss
P
Proofpoint News Feed
The GitHub Blog
The GitHub Blog
C
Check Point Blog
宝玉的分享
宝玉的分享
G
Google Developers Blog
Spread Privacy
Spread Privacy
Cloudbric
Cloudbric
SecWiki News
SecWiki News
有赞技术团队
有赞技术团队
www.infosecurity-magazine.com
www.infosecurity-magazine.com
W
WeLiveSecurity
Cyber Security Advisories - MS-ISAC
Cyber Security Advisories - MS-ISAC
美团技术团队
V
Vulnerabilities – Threatpost
Cyberwarzone
Cyberwarzone
A
Arctic Wolf
P
Privacy & Cybersecurity Law Blog
P
Palo Alto Networks Blog
H
Help Net Security
cs.CV updates on arXiv.org
cs.CV updates on arXiv.org
Cisco Talos Blog
Cisco Talos Blog
Hacker News - Newest:
Hacker News - Newest: "LLM"
A
About on SuperTechFans
N
Netflix TechBlog - Medium
罗磊的独立博客
月光博客
月光博客

静静的小窝

在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 中国不是欧洲的救世主|China Will Not Save Europe 美国之行|A Travel To The USA 一道数学题|A Math Problem 做一个真正的关注者|Pay true attention 云笔记|inote 闵行高三一模作文|Chinese Composition of First Minghang Mock Exam 一个诡异的脑洞|A strange idea 科学技术的发展离不开艺术 读后感——竞选州长 影评英伦对决——成龙的又一力作 影评2001:太空漫游——最好的科幻电影 关于航空航天探测工程的一点思考 科学营总结 2019科学营Day4 2019科学营Day3 2019科学营Day2 2019科学营Day1 研学中的思考 在研学中学习 北京研学Day1 洛谷P1000题解 探访商飞 读书笔记_2019年寒假 OK!
[题解]异或三角形|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的组合数。
  考虑到输入有多种可能,不妨先根据最大数的大小排序计算,再根据输入顺序排序输出。
代码略(没有复制)。