zhangxixi的博客

本文搬运自本人初中博客园博客，若图片加载不出来，可到原文查看：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维护即可

本文搬运自本人初中博客园博客，若图片加载不出来，可到原文查看：https://www.cnblogs.com/zhangtingxi/p/15905849.html 题目链接 题目 最近 lxhgww\text{lxhgww}lxhgww 又迷上了投资股票，通过一段时间的观察和学习，他总结出了股票行情的一些规律。 通过一段时间的观察，lxhgww\text{lxhgww}lxhgww 预测到了未来 TTT 天内某只股票的走势，第 iii 天的股票买入价为每股 APiAP_iAPi​，第 iii 天的股票卖出价为每股 BPiBP_iBPi​（数据保证对于每个 iii，都有 APi≥BP...

本文搬运自本人初中博客园博客，若图片加载不出来，可到原文查看：https://www.cnblogs.com/zhangtingxi/p/15905471.html 题目链接 题目 原题来自：POI 2005 Byteotian Bit Bank (BBB) 拥有一套先进的货币系统，这个系统一共有 nnn 种面值的硬币，面值分别为 b1,b2,⋯ ,bnb_1, b_2,\cdots , b_nb1​,b2​,⋯,bn​ 。但是每种硬币有数量限制，现在我们想要凑出面值 kkk，求最少要用多少个硬币。 思路 首先不考虑时间复杂度，这个问题应该是可以用多重背包求解的。 同时，我们也可以把...

本文搬运自本人初中博客园博客，若图片加载不出来，可到原文查看：https://www.cnblogs.com/zhangtingxi/p/15901652.html 题目链接 题目 原题来自：POI 2004 John 打算驾驶一辆汽车周游一个环形公路。公路上总共有 nnn 车站，每站都有若干升汽油（有的站可能油量为零），每升油可以让汽车行驶一千米。John 必须从某个车站出发，一直按顺时针（或逆时针）方向走遍所有的车站，并回到起点。在一开始的时候，汽车内油量为零，John 每到一个车站就把该站所有的油都带上（起点站亦是如此），行驶过程中不能出现没有油的情况。 任务：判断以每个车站为...

本文搬运自本人初中博客园博客，若图片加载不出来，可到原文查看：https://www.cnblogs.com/zhangtingxi/p/15897506.html 题目链接 题目 高二数学《绿色通道》总共有 nnn 道题目要抄，编号 1…n1\ldots n1…n，抄第 iii 题要花 aia_iai​ 分钟。小 Y 决定只用不超过 ttt 分钟抄这个，因此必然有空着的题。每道题要么不写，要么抄完，不能写一半。下标连续的一些空题称为一个空题段，它的长度就是所包含的题目数。这样应付自然会引起马老师的愤怒，最长的空题段越长，马老师越生气。 现在，小 Y 想知道他在这 ttt 分钟内写哪...

本文搬运自本人初中博客园博客，若图片加载不出来，可到原文查看：https://www.cnblogs.com/zhangtingxi/diary/15847165.html 六中集训Day6 模拟赛 第一天感觉是个莫队板子，然后打了个莫队套树状数组 第二题想不到，把 n⩽18n\leqslant 18n⩽18 的分打了个状压。 T3第一档部分分感觉不可做，随便打了第二档的分。 T4乱输出一个。 然后出考场。 T1挂成50分了，呜呜呜 树状数组有一个log，这道题要没log hjh有一种 O(nn)O(n\sqrt n)O(nn​)的做法，tql，%%% T2就拿了那30分，正解似乎是...