竞赛讨论区 > 【题解】Wannafly挑战赛4

【题解】Wannafly挑战赛4

头像
王清楚
发布于 2021-11-23 14:30:13 APP内打开
赞 0 | 收藏 0 | 回复0 | 浏览224

T1 解方程

枚举a 和b,那么 c 唯一确定,用数组或者map 判断一下这样子的c 是否存在。

T2 小AA的数列

按位(二进制的位)考虑每位对于答案的贡献。令表示前个元素里 第位为的数字个数的奇偶性。考虑数列中第个元素为区间右端点,对于 第位,我们只要求出中有多少个元素与不相等且 区间长度为偶数就可以了,而这可以用一个前缀和搞定。

ans

其中第一维表示考虑第位,第二维表示考虑的前缀和的位置,第三维表 示前缀里第bit位为1的数字个数的奇偶数,第四维用来满足长度为偶数的要求。

T3 割草机

首先把最后的那些全是空地的行去掉(因为割草机去这些行是完全没有意义 的)。

问题其实等同于割草机在什么位置选择进入下一行。令表示第最右的杂草的位置,表示第行最左的杂草的位置。 简单来说,如果当前行i 为奇数行,那么我们会选取 的位置,偶数行选取 的位置。 没有杂草的行特别处理一下。模拟一下就可以了。

T4 树的距离

首先求出个点的dfs 序,一棵子树对应了dfs 序中的连续一段。我们把所有点按它到根的距离dist 排序。 然后把每组询问排序

T5 方程的解

如果,那么就把分别带进去试一试就好。 如果 ,那么是奇质数,就可以把方程化成 的形式,其中。(注意 在模意义下是乘以 的逆元)这样的话就变成了检验在模意义下是否有二次剩余。 首先特判掉 的情况,这个是显然有唯一解的。之后如果有二次剩余,那么一定可以把 写成 的形式,其中的一个原根,这样的话肯定满足:。相反,如果没有二次剩余,设,那么必然是奇数, 所以也不会是的倍数, 也不等于,而会等于 。综上,我们就只需要看是否等于 就可以判断 是否有二次剩余了。若 有二次剩余,即,则原方程有解,否则就无解。

0条回帖

回帖
加载中...
话题 回帖

本文相关内容

近期热帖

等你来战

查看全部

热门推荐