zhangxixi的博客

本文搬运自本人初中博客园博客，若图片加载不出来，可到原文查看：https://www.cnblogs.com/zhangtingxi/p/16180001.html D1T4 小学生计数题 题目 作为 GDOI 的组题人，小 Y 需要整理手中已有的题目，考虑它们的难度以及所考察的知识点，然后将它们组成数套题目。 小 Y 希望先能组出第一套题目，为了整套题目具有良好的区分度，在一套题目中： 所有题目的难度需要能排成等差数列；（也就是说，若将所有题目按难度从小到大排序，那么每相邻两题的难度的差相等，这个差叫做公差） 每道题目的难度都是公差的倍数，公差不为 0； 需要有不少于 LLL 道...

本文搬运自本人初中博客园博客，若图片加载不出来，可到原文查看：https://www.cnblogs.com/zhangtingxi/p/16179819.html D1T3 流水线 题目 在计算机组成原理这门课中，小明的老师布置了实现 CPU 流水线的作业。小明打算设计出一个效率最高的流水线。简单来说，流水线就是将 CPU 分成若干个任务模块，而一个模块又可以继续划分成更小的模块，小模块可以划分成更小的小小模块…根据常识我们知道把一个任务划分后，每一个部分的代价会变少，但是可能会产生额外的代价。所以小明希望你帮助他解决这个问题。 我们可以用一棵以 1 为根的有根树来描述模块之间的关...

本文搬运自本人初中博客园博客，若图片加载不出来，可到原文查看：https://www.cnblogs.com/zhangtingxi/p/16179653.html D1T2 数列游戏 题目 有一个长度为 nnn 的序列 a1,…,ana_1, \dots , a_na1​,…,an​。 如果序列的长度大于 1，那么你就能进行操作，每次操作可以选择两个相邻的数 ai,ai+1a_i, ai+1ai​,ai+1 合并，得到一个新的数 aia_iai​ ⊕ ai+1a_{i+1}ai+1​（“⊕”表示异或），每次操作都会使序列的长度减少 1。例如对将序列 [8,3,5,7,1][8, 3...

本文搬运自本人初中博客园博客，若图片加载不出来，可到原文查看：https://www.cnblogs.com/zhangtingxi/p/16179574.html D1T1 邹忌讽齐王纳谏 题目 齐国人邹忌对齐国国君齐威王说，大王身边的人会因为私情、利益等原因而对大王阿谀奉承，所以不能光听好话，只有广泛接受群众的批评意见，才不会被蒙蔽双眼，齐国才能强盛。齐威王接受了这个意见，于是昭告全国： 如果有臣民当面对齐威王提出建议，则获得价值为 A 的奖励； 如果有臣民以书信的方式对齐威王提出建议，则获得价值为 B 的奖励； 如果有臣民在街市中议论齐威王，意见流传到宫廷，则获得价值为 C ...

本文搬运自本人初中博客园博客，若图片加载不出来，可到原文查看：https://www.cnblogs.com/zhangtingxi/articles/16151398.html 关于多人中3人相认识或4人相不认识研究报告 作者：张霆希 时间：2022.4.15 题目 求至少任意多少个人，必有3个人全都互相认识或者4个人全都互相不认识，不存在A认识B但B不认识A的情况 条件1 3个人全都互相认识 条件2 4个人全都互相不认识 解析 连通块：假如A认识B，B认识C，则A，B，C在一个连通块里，A和C的关系不确定. 连通块的大小：连通块里的人数成为连通块的大小. 连通块的 kkk 值...

本文搬运自本人初中博客园博客，若图片加载不出来，可到原文查看：https://www.cnblogs.com/zhangtingxi/p/16018140.html 题目链接 题目 TBL和X用巧克力棒玩游戏。每次一人可以从盒子里取出若干条巧克力棒，或是将一根取出的巧克力棒吃掉正整数长度。TBL先手两人轮流，无法操作的人输。 他们以最佳策略一共进行了10轮（每次一盒）。你能预测胜负吗？ 思路 以下写作中，“石子”与“巧克力”的意思相同。 先考虑一种特殊情况。 假设此时巧克力全部取出来，则这就是一个Nim游戏。 按照Nim游戏的做法，如果此时石子异或和为0，先手必败。 那如何使巧克力全...

本文搬运自本人初中博客园博客，若图片加载不出来，可到原文查看：https://www.cnblogs.com/zhangtingxi/p/16013639.html 题目链接 题目 小H和小Z正在玩一个取石子游戏。 取石子游戏的规则是这样的，每个人每次可以从一堆石子中取出若干个石子，每次取石子的个数有限制，谁不能取石子时就会输掉游戏。 小H先进行操作，他想问你他是否有必胜策略，如果有，第一步如何取石子。 思路 博弈论，考虑把题目变成Nim游戏。 把 [0,1000][0, 1000][0,1000] 按可行操作变成一个有向图，然后处理出它们的SG函数。 然后，把原先的每堆石子通过SG...

本文搬运自本人初中博客园博客，若图片加载不出来，可到原文查看：https://www.cnblogs.com/zhangtingxi/p/16004931.html 题目 NNN 堆石子，两人轮流从其中一堆取至少一个石子，问先手是否存在必胜策略。 结论 异或不为0，先手必胜。 证明 设 kkk 为某一堆取完后的剩余个数，iii 为被取那堆石子的编号，则取完后的异或和为 x1  xor  x2  xor…xor  xi−1  xor  xi+1  xor…xor  xn  xor  kx_1\;xor\;x_2\;xor\dots xor\;x_{i-1}\;xor\;x_{i+1}\...

本文搬运自本人初中博客园博客，若图片加载不出来，可到原文查看：https://www.cnblogs.com/zhangtingxi/p/15990701.html Part A 单调队列 何为单调队列? 单调队列（Monotone queue ）即单调递减或单调递增的队列。 例：滑动窗口 T1 题目 对于一个长为 NNN 的序列，求所有从左到右长为 KKK 的区间最大值和最小值。 N,K⩽106N,K\leqslant 10^6N,K⩽106 思路 以最大值为例，维护一个从大到小的队列，从队首到队尾单调不升。 这个队列维护的是 [i,i+k−1][i,i+k-1][i,...

本文搬运自本人初中博客园博客，若图片加载不出来，可到原文查看：https://www.cnblogs.com/zhangtingxi/p/15915078.html 【P1084 [NOIP2012 提高组] 疫情控制】 图论；二分；LCA；4星 二分时间，然后每个军队在规定时间内走到最浅的点，这步可以用树上倍增优化，然后再dfs判断是否可行 【P1110 [ZJOI2007]报表统计】数据结构；STL；set；3星 用STL之multiset维护即可