2020-team1-C015

从 Trac 迁移的文章

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

原文章内容如下：

[/wiki/2020-team1 返回]
== 概述 ==
solved: 7/10  dirt: 50%
rank: 45
[[Image(Rank.png,800px)]]
== 总结 ==
D +4 00:27  太对了鸽

== 题解 ==
A: 
B: 
C: 
D: n<=5暴力判，否则yes
E: 若四个数a,b,c,d中有重复的数，比如a=b,那么必有c=d，因此若有数字出现次数>=4则yes，或有2个数字出现次数>=2也为yes，否则可以直接去重，接着可以发现a^b^c^d=0等价于 a^b = c^d，那么可以用fwt对每个x求出a^b=x的(a,b)数（要去重并去掉一个数xor自己），若有个x的次数>=2也为yes，否则no
F: 从左往右考虑每个位置动不动：设左边第一个不动的位置距离L，右边第一个不动的位置距离R，则到左边概率为R/(L+R)，到右边概率为L/(L+R)；算出动和不动的期望取较优的；如果当前位置要动则继续往左考虑直到一个不动的位置，最后扫一遍求答案。
G: dp[n][k]表示第n天决策完后sad k次的最小均绩
H: dp打表，分解质因数，发现答案是(nm)!*min(n,m)/C(n+m-1,min(n,m)-1)
I: 
解法1：二分，f[mask]表示当前选了mask这些数，后缀最大和最小是多少。
解法2：三进制mask，f[mask]，mask中1表示这个数被选了并且在后缀最大和中，2表示这个数被选了并且不在后缀最大和中，0表示这个数未被选，n3^n dp，需要优化一下常数
J: 枚举区间交集中第一个关键点i，统计这样的区间集合个数，那么要求区间[l,r]的r>=i，l<=i并且对于i的前一个关键点p，至少存在一个区间的l>p，用线段树合并找这些区间的数量，算一算。

[/wiki/2020-team1 返回]

概述

solved: 7/10 dirt: 50%

rank: 45

总结

D +4 00:27 太对了鸽

题解

A:

B:

C:

D: n<=5暴力判，否则yes

E: 若四个数a,b,c,d中有重复的数，比如a=b,那么必有c=d，因此若有数字出现次数>=4则yes，或有2个数字出现次数>=2也为yes，否则可以直接去重，接着可以发现abcd=0等价于 ab = cd，那么可以用fwt对每个x求出ab=x的(a,b)数（要去重并去掉一个数xor自己），若有个x的次数>=2也为yes，否则no

F: 从左往右考虑每个位置动不动：设左边第一个不动的位置距离L，右边第一个不动的位置距离R，则到左边概率为R/(L+R)，到右边概率为L/(L+R)；算出动和不动的期望取较优的；如果当前位置要动则继续往左考虑直到一个不动的位置，最后扫一遍求答案。

G: dp[n][k]表示第n天决策完后sad k次的最小均绩

H: dp打表，分解质因数，发现答案是(nm)!*min(n,m)/C(n+m-1,min(n,m)-1)

I:

解法1：二分，f[mask]表示当前选了mask这些数，后缀最大和最小是多少。

解法2：三进制mask，f[mask]，mask中1表示这个数被选了并且在后缀最大和中，2表示这个数被选了并且不在后缀最大和中，0表示这个数未被选，n3^n dp，需要优化一下常数

J: 枚举区间交集中第一个关键点i，统计这样的区间集合个数，那么要求区间[l,r]的r>=i，l<=i并且对于i的前一个关键点p，至少存在一个区间的l>p，用线段树合并找这些区间的数量，算一算。

附加文件