2017-Sp91-team2

从 Trac 迁移的文章

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

原文章内容如下：

 [[Image(1.png,500px)]]
== 流水账 ==
开场cjb光速上机写A，获得wa。yzc和sub猜了一发F的结论，上机'''F1y27'''。然后什么题都不会做，把sub赶上机子写H，cjb和yzc妄图开E和G无果，感觉交大能做的题我们也会，读了J，迅速得到了费用流的做法，yzc上机之后cjb假装叉掉了做法，下来怀疑了人生，sub已经偷偷wa了一发，发现最大值开小了，又wa了。cjb表示做法其实是对的呢，复又上机，sub再次表示找到了自己的错误，迫于面子让其上机，'''H4y126'''，随后'''J1y144'''。开心的sub和yzc聊起了G，秒之，'''G1y163'''。之后狂搞结论猛艹出E，yzc long long替换失败获得wa，'''E4y200'''。最后cjb肚子爆炸，yzc和sub口胡了很久的C，把cjb赶上机子搞了网络流，'''C1y289'''。sub从开头到结尾一直刚K，无果。最后rk16，福大rk9，中大rk11，夜幕rk12。
== 总结 ==
=== chenjb ===
这个K....以后一定要多训多校啊md
=== oipotato ===

=== subconscious  ===

== 题解 ==
 * A：等价于Σ(a[i]-b[j])^2^*((a[i]-b[j])^2^-1)等于0，把式子拆开，整合成大概只需要7次的fft，就能卡过去了。

 * B：

 * C：由微积分知识，显然若能选出恰好k项，其积有每种变量恰好一次，此时为No(注意特殊情况为k<n或k>2n，直接输出Yes)。问题转化为有一些二分对和一些单元，要选出恰好k个使得每种变量出现一次，最大流即可。

 * D：假设可以做到M次操作得到大小为k的集合，则考虑集合A，集合B的2M次操作和一个大小为M-1的集合C，将A1变为A+B+C，B1变为A，对于2<=i<=M，将Ai变为Ai+Bi，Bi变为(A-Ai)+Bi+Ci，于是我们可以通过奇偶性得到C。于是我们得到了使用2M次询问得到2K+M-1个答案的方法。从M=1,K=1开始，最后我们可以得到M=256,K=1025。

 * E：数对一定是一奇一偶，于是问题转化为2进制1出现次数为奇数的数字以及总个数，然后观察发现在区间[0,某奇数]中二进制1出现次数为奇数的数字恰好有一半，那么对于[0,某偶数]只需要特判此偶数满不满足即可，对于区间[l,r]显然可以做差得到，用set维护区间端点，最后答案为奇数*偶数。

 * F：暴力存下当前所有可能的gcd，所有gcd和(a[i]-1,a[i],a[i]+1)都做一次gcd，去重后塞回数组。

 * G：next[i]表示位置i往前最近的合法括号序列的位置，last[i][j]表示i这个位置不断往前跳next第一次遇到字母j的位置，于是对于位置i，next[i]就等于last[i-1][s[i]]，考虑f[i]表示以i结尾的合法区间个数，显然f[i]=f[next[i-1]]+1，ans=Σf。

 * H：显然答案由大凸包减去最小的三角形得到，于是对不在大凸包上的点再做一次凸包，用类似旋转卡壳求出最小三角形即可。

 * I：

 * J：由操作一可得只和字符集的差有关，然后观察操作二显然提供了恰好M个把T2[j]变成S2[j]的操作，且只能用一次，源点与+的点连，-的点与汇连，跑费用流即可。

 * K：容斥，两球碰撞视为交换目的地，可以发现式子是个行列式。

 * L：随机得到前800项，x=(w^n-c+1^)^i^，check前c项是否是前800项某个子串，可以先check前32项减少复杂度。
== 补题 ==

流水账

开场cjb光速上机写A，获得wa。yzc和sub猜了一发F的结论，上机F1y27。然后什么题都不会做，把sub赶上机子写H，cjb和yzc妄图开E和G无果，感觉交大能做的题我们也会，读了J，迅速得到了费用流的做法，yzc上机之后cjb假装叉掉了做法，下来怀疑了人生，sub已经偷偷wa了一发，发现最大值开小了，又wa了。cjb表示做法其实是对的呢，复又上机，sub再次表示找到了自己的错误，迫于面子让其上机，H4y126，随后J1y144。开心的sub和yzc聊起了G，秒之，G1y163。之后狂搞结论猛艹出E，yzc long long替换失败获得wa，E4y200。最后cjb肚子爆炸，yzc和sub口胡了很久的C，把cjb赶上机子搞了网络流，C1y289。sub从开头到结尾一直刚K，无果。最后rk16，福大rk9，中大rk11，夜幕rk12。

总结

chenjb

这个K....以后一定要多训多校啊md

oipotato

subconscious

题解

  • A：等价于Σ(a[i]-b[j])2*((a[i]-b[j])2-1)等于0，把式子拆开，整合成大概只需要7次的fft，就能卡过去了。
  • B：
  • C：由微积分知识，显然若能选出恰好k项，其积有每种变量恰好一次，此时为No(注意特殊情况为k2n，直接输出Yes)。问题转化为有一些二分对和一些单元，要选出恰好k个使得每种变量出现一次，最大流即可。
  • D：假设可以做到M次操作得到大小为k的集合，则考虑集合A，集合B的2M次操作和一个大小为M-1的集合C，将A1变为A+B+C，B1变为A，对于2<=i<=M，将Ai变为Ai+Bi，Bi变为(A-Ai)+Bi+Ci，于是我们可以通过奇偶性得到C。于是我们得到了使用2M次询问得到2K+M-1个答案的方法。从M=1,K=1开始，最后我们可以得到M=256,K=1025。
  • E：数对一定是一奇一偶，于是问题转化为2进制1出现次数为奇数的数字以及总个数，然后观察发现在区间[0,某奇数]中二进制1出现次数为奇数的数字恰好有一半，那么对于[0,某偶数]只需要特判此偶数满不满足即可，对于区间[l,r]显然可以做差得到，用set维护区间端点，最后答案为奇数*偶数。
  • F：暴力存下当前所有可能的gcd，所有gcd和(a[i]-1,a[i],a[i]+1)都做一次gcd，去重后塞回数组。
  • G：next[i]表示位置i往前最近的合法括号序列的位置，last[i][j]表示i这个位置不断往前跳next第一次遇到字母j的位置，于是对于位置i，next[i]就等于last[i-1][s[i]]，考虑f[i]表示以i结尾的合法区间个数，显然f[i]=f[next[i-1]]+1，ans=Σf。
  • H：显然答案由大凸包减去最小的三角形得到，于是对不在大凸包上的点再做一次凸包，用类似旋转卡壳求出最小三角形即可。
  • I：
  • J：由操作一可得只和字符集的差有关，然后观察操作二显然提供了恰好M个把T2[j]变成S2[j]的操作，且只能用一次，源点与+的点连，-的点与汇连，跑费用流即可。
  • K：容斥，两球碰撞视为交换目的地，可以发现式子是个行列式。
  • L：随机得到前800项，x=(wn-c+1)i，check前c项是否是前800项某个子串，可以先check前32项减少复杂度。

补题

附加文件