2019-Sp018-lyk

从 Trac 迁移的文章

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

原文章内容如下：

 [[Image(1.png,800px)]]

 [http://10.71.10.90/pia/trac/wiki/2019-team2 返回Runespoor]

== 流水账 ==


== 总结 ==
zqq：多校题的风格比较诡异。这场完全是数学场（+图论）。多校的榜基本只能看哪些题可以做，而根本不能和其他学校对比，或者具体预估题目难度，很不爽。还好我们的判断没有错，这个A题大家全部粘板，过了一堆，其实非常困难！

今天我们的节奏还行。但是后期仍然不够。B题一开始以为式子很复杂。推完才发现其实非常简单。想清楚真的一点都不麻烦。

感觉计数题一起想的感觉很好，每个人的思维压力都会降低很多。

最后B没有过还是有点遗憾。

明天校赛加油！


== 题解 ==

[http://bestcoder.hdu.edu.cn/blog/2018-multi-university-training-contest-10-solutions-by-%E9%9B%85%E7%A4%BC%E4%B8%AD%E5%AD%A6/ 原来多校题解在bestcoder上]

[https://blog.csdn.net/V5ZSQ/article/details/82684866 A题]

A: 生成函数，还不会

B: 有趣的poly + 推式子 orz heltion

C：推式子，反演，最后化成积性函数直接筛

D： 求sigma(|pi - i|) = 0,1,n ^ 2 - 1的排列个数。

DP，f[i][s][k]前面i个数，当前贡献为s，k个数没有匹配。因为没有匹配的位置和数的个数肯定相同。每次只需要枚举新加入的数和位置分别和前面还是后面的数匹配就好了。感觉还是非常巧的。heltion说枚举pi和i的符号，才想到

E: 线段树合并。一开始就应该想到。还让lyk去写了一个bitset。发现mle了，思维还是应该敏捷一些！

F: 不会

G: 容斥。长度为n的环排列，没有相邻数。

H: 签到

I： 反演 @heltion

J: 6维空间最大曼哈顿距离。直接2^6^枚举符号，查询对应符号（每一维相反）的最大值即可。如果不合法答案只会更小。然而如果是最小是不是只能kd树啊？

K：先把没有的高位用低位凑出来。dp[i][0/1]表示完成前i位，与原码/补码匹配时最小代价。

L: 费用流。直接暴力建图就好。按照时间建点限制流量。然后从A到B的边和A到A的边费用不同


== 补题 ==
* A [zqq]

* B [全队]: 赛后花了30分钟。

* F []

返回Runespoor

流水账

总结

zqq：多校题的风格比较诡异。这场完全是数学场（+图论）。多校的榜基本只能看哪些题可以做，而根本不能和其他学校对比，或者具体预估题目难度，很不爽。还好我们的判断没有错，这个A题大家全部粘板，过了一堆，其实非常困难！

今天我们的节奏还行。但是后期仍然不够。B题一开始以为式子很复杂。推完才发现其实非常简单。想清楚真的一点都不麻烦。

感觉计数题一起想的感觉很好，每个人的思维压力都会降低很多。

最后B没有过还是有点遗憾。

明天校赛加油！

题解

原来多校题解在bestcoder上

A题

A: 生成函数，还不会

B: 有趣的poly + 推式子 orz heltion

C：推式子，反演，最后化成积性函数直接筛

D： 求sigma(|pi - i|) = 0,1,n ^ 2 - 1的排列个数。

DP，f[i][s][k]前面i个数，当前贡献为s，k个数没有匹配。因为没有匹配的位置和数的个数肯定相同。每次只需要枚举新加入的数和位置分别和前面还是后面的数匹配就好了。感觉还是非常巧的。heltion说枚举pi和i的符号，才想到

E: 线段树合并。一开始就应该想到。还让lyk去写了一个bitset。发现mle了，思维还是应该敏捷一些！

F: 不会

G: 容斥。长度为n的环排列，没有相邻数。

H: 签到

I： 反演 @heltion

J: 6维空间最大曼哈顿距离。直接26枚举符号，查询对应符号（每一维相反）的最大值即可。如果不合法答案只会更小。然而如果是最小是不是只能kd树啊？

K：先把没有的高位用低位凑出来。dp[i][0/1]表示完成前i位，与原码/补码匹配时最小代价。

L: 费用流。直接暴力建图就好。按照时间建点限制流量。然后从A到B的边和A到A的边费用不同

补题

  • A [zqq]
  • B [全队]: 赛后花了30分钟。
  • F []
附加文件