2020-team0x06-037

从 Trac 迁移的文章

这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。

原文章内容如下：

[/wiki/2020-team0x06 返回]

[[Image(Standings.png, 1000px)]][[BR]][[Image(Submissions.png, 600px)]]

== 概述 ==

2020 - XX Open Cup, Grand Prix of Nanjing

== 流水账 ==

开场各自看题。czyh签J，由于找错规律WA了一发，'''J2Y12'''，随后开出L，'''L1Y43'''。期间fx和lmh讨论出A和D，fx上机写A，'''A1Y69'''，lmh上机写D，'''D1Y112'''。fx和czyh讨论出B，发现和D很类似，于是扔给lmh，lmh把D的代码复制了一份，'''B1Y144'''。

fx单开出G上机，czyh对着I找规律，并趁着fx静态调试的空隙写了个暴力，又抄了个BM的板子。不久'''G1Y206'''，czyh发现暴力跑不出BM需要的项数，对着方案又找了个规律，这下暴力跑得快了许多，但跑出7项也跑不动了，勉强列出两个方程。

czyh把现有的信息丢出来，并很快发现了两个规律，现在未知数只剩下了1个，不久lmh也找出1个规律，于是czyh开始手动解3个方程。解出方程后把系数丢进BM里跑，居然TLEon1，发现出了UB，czyh稍微修改了一下，'''I2Y272'''。

== 总结 ==

=== ntwbvdbl_oe ===

hash好耶!不要sa!


=== Orange_User ===

BM牛逼！（或许未来可以尝试学一下？好像还是拖板子更方便一点）

=== functionendless ===
我讨厌带double的DP!

== 题解 ==

A: 先把所有的x异或起来, 问题转换为是否要再异或使之变成y,进而逐位确定. 首先把两组的线性基都建出来,矛盾聚集在AB都可以对当前位进行选择,若A选1,B必选0,反之同理. 为解决当前步的决策,将两种决策值的异或塞到A的线性基里,以便A在后面"反悔"

B: 对于一个长度为i的分割方案，其出现的时间是从第i次操作后的连续一段，二分这个右端点并检查i分割是否合法

C:

D: 枚举循环节长度len，每len一节将s分割成若干段(与B题分割方法相同)，可知总段数是nlogn的。然后求出每一段与后一段的lcp及与前一段的lcs，若对于连续k-1段相同且首段的lcs+末段的lcp>=len则统计进答案，用了二分+hash总复杂度2个log

E: 

F: 

G: 暴力: 对每个数,让它成为"关键数字",即操作序列中最后一个选的数字,那么排除它,剩下的数字进行DP,就可以得到相应的答案,
f[i][j][k]:考虑前i个, 选了j个, 当前总和是k的概率(方案数应该也可,但我不知道哪里跪了,死也调不出来). 转移显然.
但这样做是n^4^的, 我们注意到方程中只有四则运算, 进而发现这个DP实际是'''顺序无关'''的, 于是DP到最后就可以进行一步反悔.

H: 

I: 打表找规律+BM可以推出m<=5的递推式，然后发现暴力跑不出m=6时BM需要的数据，那么找一找递推式的规律列方程解一下就行了。

J: 卢卡斯定理or找规律

K:

L: 离散化+DFS

M:

[/wiki/2020-team0x06 返回]


概述

2020 - XX Open Cup, Grand Prix of Nanjing

流水账

开场各自看题。czyh签J，由于找错规律WA了一发，J2Y12，随后开出L，L1Y43。期间fx和lmh讨论出A和D，fx上机写A，A1Y69，lmh上机写D，D1Y112。fx和czyh讨论出B，发现和D很类似，于是扔给lmh，lmh把D的代码复制了一份，B1Y144。

fx单开出G上机，czyh对着I找规律，并趁着fx静态调试的空隙写了个暴力，又抄了个BM的板子。不久G1Y206，czyh发现暴力跑不出BM需要的项数，对着方案又找了个规律，这下暴力跑得快了许多，但跑出7项也跑不动了，勉强列出两个方程。

czyh把现有的信息丢出来，并很快发现了两个规律，现在未知数只剩下了1个，不久lmh也找出1个规律，于是czyh开始手动解3个方程。解出方程后把系数丢进BM里跑，居然TLEon1，发现出了UB，czyh稍微修改了一下，I2Y272。

总结

ntwbvdbl_oe

hash好耶!不要sa!

Orange_User

BM牛逼！（或许未来可以尝试学一下？好像还是拖板子更方便一点）

functionendless

我讨厌带double的DP!

题解

A: 先把所有的x异或起来, 问题转换为是否要再异或使之变成y,进而逐位确定. 首先把两组的线性基都建出来,矛盾聚集在AB都可以对当前位进行选择,若A选1,B必选0,反之同理. 为解决当前步的决策,将两种决策值的异或塞到A的线性基里,以便A在后面"反悔"

B: 对于一个长度为i的分割方案，其出现的时间是从第i次操作后的连续一段，二分这个右端点并检查i分割是否合法

C:

D: 枚举循环节长度len，每len一节将s分割成若干段(与B题分割方法相同)，可知总段数是nlogn的。然后求出每一段与后一段的lcp及与前一段的lcs，若对于连续k-1段相同且首段的lcs+末段的lcp>=len则统计进答案，用了二分+hash总复杂度2个log

E:

F:

G: 暴力: 对每个数,让它成为"关键数字",即操作序列中最后一个选的数字,那么排除它,剩下的数字进行DP,就可以得到相应的答案,

f[i][j][k]:考虑前i个, 选了j个, 当前总和是k的概率(方案数应该也可,但我不知道哪里跪了,死也调不出来). 转移显然.

但这样做是n4的, 我们注意到方程中只有四则运算, 进而发现这个DP实际是顺序无关的, 于是DP到最后就可以进行一步反悔.

H:

I: 打表找规律+BM可以推出m<=5的递推式，然后发现暴力跑不出m=6时BM需要的数据，那么找一找递推式的规律列方程解一下就行了。

J: 卢卡斯定理or找规律

K:

L: 离散化+DFS

M:

附加文件