票数统计

By jiry_2

这题数据是瞎随的，所以好像出现了一些奥妙重重的得分分布QAQ

算法一

爆枚所有可能的情况，检验每一个限制是否合法。

时间复杂度 $O(T{2}^{n}m)$，期望得分 $30$ 分。

算法二

不难发现当 $x>y$ 时后 $y_i$ 位用户中，恰好有 $x_i$ 位投了通过肯定是不成立的，当 $x<y$ 时后 $x_i$ 位用户中，恰好有 $y_i$ 位投了通过也肯定不成立。

所以只有当 $x\ne y$ 时限制是唯一确定的。

因此如果有解，本质不同的限制最多只有 $O(n)$ 个，可以先把不同的限制去重掉，然后再爆枚所有情况判断。

时间复杂度 $O(T{2}^{n}n)$，期望得分 $50$ 分。

算法三

对于第六个点，所有限制都是针对前缀的。

不难发现这时限制把整个序列分成了 $O(m)$ 段并对每一段限制了 $1$ 的个数，因此每一段的方案数都是组合数，直接把它们都乘起来就好了。

时间复杂度 $O(Tn+n^2)$，结合算法二期望得分 $60$ 分。

算法四

先考虑 $x\ne y$ 的情况，这时考虑把对后缀的限制转化成对前缀的限制。

枚举所有人中投通过的人数，这样后缀的限制就变成了前缀的限制，直接用算法三求解就好了。

存在 $x=y$ 时，不难发现所有 $x=y$ 的限制中只需要考虑 $x$ 最大限制就行了，因为这个限制满足了剩下的 $x=y$ 的限制一定也满足了。

枚举限制 $x=y$ 被哪一边满足，答案就是前缀满足的方案数加上后缀满足的方案数减去两端都满足的方案数，这样就把 $x=y$ 转化成了只对前缀或者只对后缀的限制。

时间复杂度 $O(T{n}^2)$，期望得分 $100$ 分。

寻找罪犯

By sevenkplus，题解By C_SUNSHINE

算法一

暴力枚举每个人是否是罪犯，然后扫描所有证言判断是否为真，并判断是否满足条件，时间复杂度$O(2^{m}m)$。

算法二

对于每个人，建立一个$01$变量表示他是否是罪犯，对每一条证言，建立一个$01$变量表示它是否为真，那么就可以把要求转化为一些条件。

对于一条供词$i$，建立条件：“若此供词为真，则某个人是/不是罪犯”。

接着对于每个人，建立条件：“若此人不是罪犯，则其说的每一条证言都为真”。

由于一个人最多说一句假的供词，则对于同一个人说的任意两条供词，建立条件：“若供词A为假，则供词B为真”。

条件都可以写成“若$x_i=a$则$x_j=b$”的形式，这是一个2-SAT问题，可以使用经典的强连通分量算法求解。

时间复杂度$O(n+m^2)$。

算法三

对于完全图的情况，可以先特判所有人都是罪犯的情况，否则必有一个人不是罪犯，枚举任意一个人不是罪犯，则通过他的供词可以得知其他所有人是否为罪犯。

时间复杂度$O(n^3)$。

算法四

考虑推广算法二，对一个有$k$条供词的人，建立$3k$个$01$变量，分别表示第$i$条供词是否为真，前$i$条供词是否都为真，后$k-i+1$条证词是否都为真。

那么若前$i$条供词为真，则前$i-1$条供词也为真，且第$i$条证词也为真，对于后缀也是一样，这部分边数是$O(m)$的。

那么可以建立条件的时候就可以使用前缀后缀来优化，若一个人为真，只要长度为$k$的前缀都为真即可。

对于一个人最多说一条假的供词这个限制，若一个人的第$i$条供词为假，则前$i-1$条和后$n-i$条证词都为真，这部分的条件数就变成$O(m)$的了。

于是变量数和条件数都是$O(n+m)$的，总复杂度就是$O(n+m)$。

逃跑

By SkyDec

算法一

考虑化简方差，设d为每次经过的点的个数。

$$E=\sum (d-avg{)}^2=\sum d^2-2\ast d\ast avg+av{g}^2=(\sum d^2)-avg\ast 2\ast (\sum d)+av{g}^2\ast all$$

根据平均数的定义，有

$$avg=\frac{\sum d}{all}$$

所以有

$$E\ast all=(\sum d^2)\ast all-(\sum d{)}^2$$

$all$可以很简单地计算，于是问题就变成了：求$\sum d^2$和$\sum d$，即经过的点的个数的平方之和，经过的点的个数之和。

我们可以$O(4^n)$枚举每次往哪个方向走，统计一下经过了几个点，就可以直接计算了。

时间复杂度$O(4^n)$，期望得分20分

算法二

考虑部分分$w_3=w_4=0$

即不可能往左右走，也就是说行走的区域只有一维了。

一维区域经过的点显然是一个区间，经过的点就是这个区间里整点的个数。

令$f[i][j][k][x]$表示走了$i$步，当前经过的区间为$[j,k]$，当前的位置是$x$的方案数，直接模拟下一步往哪儿走转移即可。

时间复杂度O(n^4)，期望得分20分

算法三

考虑如何快速地计算$\sum d$。

考虑计算$\sum (n+1-d)$，也就是经过一个点时上次早已经过这个点的点的个数。

显然$\sum d=(n+1)\ast all-\sum (n+1-d)$。

考虑一段长度为$n$的序列$L$，每个元素是$(0,1),(0,-1),(1,0),(-1,0)$中的一种。

那么如果对于坐标$(x,y)$，设序列$c_1..c_k$为满足$(\sum _{i=1}^{t}L[i])=(x,y)$的所有$t$按顺序排列的序列

那么对应的，对于$1\le i\le k-1$，有($\sum _{j=c_i+1}^{c_{i+1}}L[j])=(0,0)$

可以发现，一个出现了$k$次的点产生了$k-1$段没有前缀$(0,0)$的和为$(0,0)$的序列。

而显然出现了$k$次的点对我们要求的答案的贡献是$k-1$。

所以根据期望的线性性，我们只要计算有多少段连续子序列满足和为$(0,0)$且没有前缀$(0,0)$即可。

设$f[i]$表示长度为$i$的答案。

设$g[i]$表示长度为$i$的和为$(0,0)$的序列有几种。显然$i$是奇数时，$g[i]=0$。

$$g[i]=\sum _{j=0}^{i/2}\frac{i!}{j!j!\frac{i-j\ast 2}{2}!\frac{i-j\ast 2}{2}!}\ast w_1^j{w}_2^j{w}_3^{\frac{i-j\ast 2}{2}}{w}_4^{\frac{i-j\ast 2}{2}}$$

相当于枚举每种向量的个数，排列组合了一下。

然后$f$的计算就很显然了。

$$f[i]=g[i]-\sum _{j=0}^{i-1}f[j]\ast g[i-j]$$

统计答案时只要算$\sum _{i=1}^{n}f[i]\ast al{l}^{n-i}$就行了

时间复杂度$O(n^2)$，期望得分$0$分

算法四

在上个算法里，我们通过比较直观的转换将题目转化成了求无前缀$(0,0)$的和为$(0,0)$的段数。

然而当我们求$\sum d^2$时，就无法直接用期望的线性性计算了。

设$p=(n+1-d)$，即上个算法里的重复计算次数。有：

$$\sum d^2=\sum (n+1-p{)}^2=all\ast (n+1{)}^2-2\ast (n+1)\ast \sum p+\sum p^2$$

$\sum p$我们已经可以轻易地计算了，现在就考虑计算$\sum p^2$了。

设布尔数组a[l][r]表示$[l,r]$是否满足条件。

那一个数列的贡献就是$(\sum _{l\le r}a[l][r]{)}^2$

即$$\sum _{l\le r}\sum _{x\le y}a[l][r]\ast a[x][y]$$

然后现在就有期望的线性性了，我们只要对于每对$(l,r)$，$(x,y)$计算他们同时满足条件的方案数即可。

当区间不相交时，他们互相几乎不影响，直接计算即可。

当只有一段时我们可以简单地记录坐标$dp$，并保证中途不经过为$(0,0)$的点即可。

那么当有两个区间时，我们可以先$DP$第一个区间，然后中途加入一个区间，当一个区间和变为$(0,0)$时就意味着他终止了。

当区间相交时，考虑$f[i][x1][y1][x2][y2][2]$表示当前长度为$i$，第一段的和为$(x1,y1)$，第二段的和为$(x2,y2)$。当前有几个区间。每次转移考虑下一步走哪个方向，要不要加入区间即可。

时间复杂度$O(n^5)$，期望得分40分

算法五

考虑第七个点，他的$w_1=w_2=w_3=w_4$，显然$w$之间是一种比例关系，全部相等就等价于全为$1$，我们用上个算法的程序打个表即可。

期望得分10分

算法六

区间的相交分为两种情况：包含和不包含。

我们先考虑不包含的情况，这样肯定分成了三段：只属于第一段的，重合的，只属于第二段的，我们设他们分别为$A$,$B$,$C$。

考虑$A$，我们枚举$A$的和，设为$(Ax,Ay)$，那么我们可以轻易地推导出：B的和为$(-Ax,-Ay)$，C的和为$(Ax,Ay)$。

考虑$A$需要满足什么条件，由于只属于第一段，所以只需要满足没有前缀$(0,0)$即可。

设$g[i][x][y]$表示和为(x,y)，长度为$i$，没有前缀$(0,0)$的方案数，这个可以用简单的$O(n^3)$dp得到。

考虑$C$需要满足什么条件，由于只属于第二段，所以只需要满足没有前缀$(Ax,Ay)$即可，即没有后缀$(0,0)$。

没后缀$(0,0)$跟没前缀$(0,0)$显然是等价的问题。

考虑$B$需要满足的条件，这个就比较复杂了，毕竟是重合的部分，他要满足第一段，所以他需要没有前缀$(-Ax,-Ay)$，即没有后缀$(0,0)$

他也需要满足第二段，即没有前缀$(0,0)$。

设$o[i][x][y]$表示和为$(x,y)$，长度为$i$，没有前缀$(0,0)$和后缀$(0,0)$的方案。

考虑容斥计算$o$。我们可以用$g[i][x][y]$作为总方案，那么考虑枚举最短的长度为$j$的后缀和为$(0，0)$。

那么前$(i-j)$的和就是$(x,y)$，他们只需要满足没有前缀$(0,0)$，也就是$g[i-j][x][y]$。

考虑长度为$j$的部分，他们的和为$(0,0)$，由于要求最短，所以他们也不能有后缀$(0,0)$，并且由于整段里不能有前缀$(0,0)$，所以他也不能有哪个前缀和前面的$(i-j)$构成$(0,0)$，即没有前缀$(-x,-y)$。

于是设$v[i][x][y]$表示长度为$i$，和为$(0,0)$，不能有前缀$(0,0)$和前缀$(x,y)$的方案数。

考虑容斥，设$f[i][x][y]$表示长为$i$，和为$(x,y)$的段数，那么可以以$f[i][0][0]$作为$v[i][x][y]$的初值。

考虑枚举第一次违反，设长度为$j$。

$(1)$当违反的是不能有前缀$(0,0)$时，相当于要求长度为$j$，和为$(0,0)$，不能有前缀$(0,0)$和前缀$(x,y)$的序列个数，可以由$v[j][x][y]\ast f[i-j][x][y]$转移过来。

$(2)$当违反的是不能有前缀$(x,y)$时，相当于要求长度为$j$，和为$(x,y)$，没前缀$(0,0)$和前缀$(x,y)$的序列个数，即前后缀都不为$(0，0)$的序列个数。可以由$o[j][x][y]\ast f[i-j][0][0]$转移过来。

而上面的$o$是从$v$转移过来的，并且每次转移长度都会变大，我们可以枚举长度从小到大后一起计算$v$和$o$。

考虑计算答案：

$$\sum _{l<=r}\sum _{(x,y)}\sum _{i=1}^{l-1}\sum _{j=1}^{n-r}g[i][x][y]\ast o[r-l+1][-x][-y]\ast g[j][x][y]\ast al{l}^{n-(r-l+1)-i-j}$$

设$sum1[i][x][y]=\sum _{j=1}^{i}g[j][x][y]\ast al{l}^{-j}$

那么答案就是

$$\sum _{l<=r}\sum _{(x,y)}o[r-l+1][-x][-y]\ast al{l}^{n-(r-l+1)}\ast sum1[l-1][x][y]\ast sum1[n-r][x][y]$$

以上大多数$dp$状态数都是$O(n^3)$，转移都是$O(n)$容斥，所以复杂度是$O(n^4)$。

考虑包含的情况，类似的，我们把他分成三段$A,B,C$，并枚举$A$的坐标为$(Ax,Ay)$。

那么$B$的坐标和为$(0,0)$，$C$的坐标和为$(-Ax,-Ay)$。

$A$只要满足没有前缀$(0,0)$，$C$只要满足没有后缀$(0,0)$。

$B$要满足没有前缀$(0,0)$且没有前缀$(-Ax,-Ay)$，即$v[j][-Ax][-Ay]$。

考虑计算答案：

$$\sum _{l<=r}\sum _{(x,y)}\sum _{i=1}^{l-1}\sum _{j=1}^{n-r}g[i][x][y]\ast v[r-l+1][-x][-y]\ast g[j][-x][-y]\ast al{l}^{n-(r-l+1)-i-j}$$

我们可以类似上面地优化一下即可。

时间复杂度$O(n^4)$，由于很多状态其实是没用的，可以在$1s$内通过

期望得分$100$分