ACdream群原创群赛(3)

转载请注明出处，谢谢http://blog.csdn.net/ACM_cxlove?viewmode=contents by---cxlove

A：当时是暴力水过的，正解O(n)

如果存在b的某个排列使得 for_each( ai^x=bi )

那么我们将a1^x^b1^a2^x^b2……an^x^bn=0 ，我们在两边再同时^x

由于n为奇数，左边总共便有了偶数个x，抵消

变成a1^a2^……an^b1^b2……^bn=x

好喵，到了这里就解决了，将所有的a,b异或之后，再判断x是否为解

B：给出3个点(x1,y1),(x2,y2),(x3,y3)，可以得到三角形面积abs((x3-x1)*(y2-y1)-(x2-x1)*(y3-y1))/2

显然和奇偶性有关，枚举六个数的奇偶性，然后判断

ans=(ans+((x1&1)?(n/2):((n+1)/2))%MOD*((x2&1)?(n/2):((n+1)/2))%MOD*((x3&1)?(n/2):((n+1)/2))%MOD*((y1&1)?(m/2):((m+1)/2))%MOD*((y2&1)?(m/2):((m+1)/2))%MOD*((y3&1)?(m/2):((m+1)/2)))%MOD;

C：当时是记忆化搜索过的，直接广搜也行

D：感觉好神的题目，思维跟不上。

可以得到这个式子，v(A)=∏a∈A(1+a)?∏a∈A(1?a)2

这个式子，刚好能把偶数项的抵消。。。

然后就是分别维护两部分就行了，求一下逆元什么的。貌似数据是multiset吧

E：状态压缩DP，dp[i]表示已经取的数的状态为i时的部分和。

s[i]表示i转换为二进制后1的个数，那么下一个数取的便是a[s[i]][j]。

C[k]=(A[1]+A[2]+?+A[k])?B[k]+(B[1]+B[2]+?+B[k])?A[k]?A[k]?B[k]
或者维护部分和，然后再枚举

H：带花树或者Tutte matrix算法，先留个坑。

I：tree_dp求一下子树的大小，如果是偶数就ans+1

J：数据水了，树DP+背包可以水过，对于链的数据会完T
考虑联通块不包括重心，则最多只能有n2的大小。于是就算包含重心的联通块的最小权值，有一个熟知的动态规划算法可以做到O(N2)。之后点分治即可。复杂度仍然是O(N2)。
"熟知的动态规划算法"可以参见何森的集训队论文。
                       -----ftiasch