8月18日 2018百度之星复赛 题目链接：http://bestcoder.hdu.edu.cn/contests/contest_show.php?cid=827
思路： 一个很简单的贪心吧。。。对于每一个节点选出它最大和最小的儿子（注意还可以不选），然后在没有选的里面贪心找一个最大和最小值加入答案。
代码：
1 | #include <iostream> |
思路： 一道蛮好的期望题。我们可以先枚举最大值$h$，然后计算最大值为$h$时对答案的贡献。最大值恰好为$h$是的贡献不方便计算，我们可以先计算最大值小于等于$h$和最大值小于$h$的期望，利用一个容斥相减就好了。
代码：
1 | #include <iostream> |
思路： 首先观察式子，就可以发现我们可以对每一个联通块分开维护。对于每一个联通块里面的权值我们不难想到$v_i&v_j$可以按位来维护，对于每一位分别记录有多少个数字在这一位上出现过。然后$max(v_i, v_j)$可以比较巧妙的先将权值排序进行维护，从小到大依次按顺序计算贡献。大概的思路就是这样，详细的看代码吧（懒）
代码：
1 | #include <iostream> |
传统的Nim游戏是这样的：有一些火柴堆，每堆都有若干根火柴（不同堆的火柴数量可以不同）。两个游戏者轮流操作，每次可以选一个火柴堆拿走若干根火柴。可以只拿一根，也可以拿走整堆火柴，但不能同时从超过一堆火柴中拿。拿走最后一根火柴的游戏者胜利。
本题的游戏稍微有些不同：在第一个回合中，第一个游戏者可以直接拿走若干个整堆的火柴。可以一堆都不拿，但不可以全部拿走。第二回合也一样，第二个游戏者也有这样一次机会。从第三个回合（又轮到第一个游戏者）开始，规则和Nim游戏一样。
如果你先拿，怎样才能保证获胜？如果可以获胜的话，还要让第一回合拿的火柴总数尽量小。
第一行为整数$k$。即火柴堆数。第二行包含$k$个不超过$10^9$的正整数，即各堆的火柴个数 （$k<=100$）
输出第一回合拿的火柴数目的最小值。如果不能保证取胜，输出-1
如果已经弄清了NIM游戏的话，那么这道题应该也不难想到。
根据结论，如果要先手必胜，显然应该满足第三回合时所有堆的火柴数异或和大于0。既然这样，第一回合取完后所有堆的火柴数都应该线性无关。如果有一组数它们线性相关的话，它们的异或和就应该为0，那么这样第二回合就可以只留下这一组数，这样就先手比败了。
因此我们就可以直接求出这些数的线性基。还有一点就是题目要求拿的数目最小，所以我们就希望线性基里面的元素和最大。根据贪心，我们先将它们从大到小排个序就好了。
1 | #include <iostream> |
8月11日 Codeforces Round #503 题目链接：http://codeforces.com/contest/1020
过水，不说。。
思路： 算是一个比较简单的模拟（但是好像有大佬有$O(nlogn)$的做法）。。。枚举要得到多少选票，设为$x$，如果有其他党的选票大于x，就直接花钱买直到那个党选票小于x，如果这样最后选票不够x的话，就随便买选票直到有x张。这里买选票当然是尽可能买便宜的，然后总复杂度是$O(n^3)$的。
比赛时T了一发，然后大力卡了一下常数过了pretest。结果就很愉快地的因为TLE FST了….后面把最外层循环从1-n改为1-n/2+1就A了，想想自己真TM傻，卡常时这个都没有注意到。
代码：
1 | #include <iostream> |
思路： 交互题，比赛时少看到一个条件连题目都没有弄懂。菜死了QWQ
相邻的同学手上数字不会相差超过1，这是一个很神奇的条件。我们设数组$b[i]=a[i]-a[i+n/2]$，根据上面的条件可以发现$b[i]-b[i+1]$只能为$\lbrace -2, 0, 2 \rbrace$，在某种意义下我们可以把数组$b$的取值视为是连续的，这个性质也很有意思。
显然有$b[i]=-b[i+n/2]$，答案也就是求一点$i$使得$b[i]=0$。因为上面的性质，我们就可以使用二分求解。有一点要注意的是如果$b$中有一个元素为奇数时，那么$b$中的所有元素都是奇数，这样就直接输出-1。
代码：
1 | #include <iostream> |
思路： 神题啊。。。首先有一个很简单的思路，假设一个确定了$1~i-1$号节点的集合，那么对于$i$号节点，如果集合中的点不与节点$i$相邻，那么就把$i$号节点加入集合中。
那么这样就会有一个问题，就是可能会有节点无法加入集合，并且集合中的点无法到达它（CF上第三个点就能够HACK掉）。于是我们先从小到大扫一遍确定出一个集合，集合内编号小的点不会向编号大的点连边。然后从大到小扫一遍这个集合，如果编号大的点有一条边连向了集合内编号小的点，那就把编号小的点移除集合。这样就可以保证满足题目的条件，因为第二遍移出集合的点一定能一步内到达，第一遍移出集合的点一定能两步内到达。
代码：
1 | #include <iostream> |
给定整数$N$，求$1<=x,y<=N$且$gcd(x, y)$为素数的数对$(x, y)$有多少对
一个数$N$（$1<=N<=10^7$）
满足条件的对数
这题有莫比乌斯反演的做法。。。其实不用反演的做法感觉更好想。
看完数据范围，做法应该就是在$O(n)$左右的。我们可以先筛出范围内的素数，然后可以暴力对每个素数$pri[i]$计算范围内$gcd(x, y)=pri[i]$的对数。
范围内$gcd(x, y)=pri[i]$的对数也就相当于在$1<=x,y<= N/pri[i]$范围内互素的个数。在某个范围内互素的个数就是欧拉函数的前缀和*2+1，因此这个我们可以$O(1)$求出。
1 | #include <iostream> |
给你一个$n*n$的矩阵$A$和一个整数$k$，需要你求出矩阵$S=A+A^2+A^3+···+A^K$
第一行三个整数$n(n<=30), k(k<=10^9), m(m<=10000)$
输出模$m$意义下的矩阵$S$
一道矩阵的好题。我们一般都是将矩阵用于加速递推上，这道题却是让你求一个矩阵。
虽然要你求一个矩阵，然而一样可以使用矩阵加速递推的思路。我们可以将式子$A+A^2+A^3+···+A^K$看作是由$A+A^2+A^3+···+A^{k-1}$乘上$A$再加$A$递推而来，递推的初始值就是$A$。
1 | #include <iostream> |