这场打得真是烂啊。。。各种逗逼。。。rank不知道跌到哪里去了。。。
A.n个人，每个人想要玩a[i]次游戏，每次游戏可以有n-1个人参加，问最少多少次游戏能够让所有人玩够。n<=10W
题解：其实这个是可以二分的。。。假设二分的这个值为x，那么x>=max{a[i]},然后每个人可以有x-a[i]次不参加游戏，如果sigma{x-a[i]}>=x说明x可行。
然后发现答案其实是max（{a[i]}，『sigma{a[i]}/(n-1)』）。。。
B.n个点的树，每个点的f[i]定义为sigma{f[j]} j是i的儿子。并且f[k]=a[k] k是叶子。我们称一棵树是平衡的当且仅当对于每个i来说f[j]=f[k]其中j和k都是i的儿子。
我们可以任意减少叶子节点的a[i]，请问最少减少总和。n<=10W
题解：逗逼。。。说一下我的做法。。。
注意到如果确定了f[1]，那么ans就确定了，因为每个节点的f[i]就确定了。那么f[1]必须要满足这样分下去每个叶节点分到的数都是整数。
我们每到一个分叉，就将当前的tmp*=s[x]，s[x]表示x的儿子个数，那么到一个叶节点的时候表示f[1]/tmp=a[i]，记这个叶节点的g[i]=tmp。那么f[1]必须是tmp的倍数。
我们把所有的tmp取lcm即可。这样我们就可以继续下去：每个叶节点i所能承受的最大的f[1]为g[i]*a[i]，那么在这里面去最小就是ans。
当然只这样做是过不了的，因为这个lcm可能超过long long，虽然题目保证一定有解，所有的a[i]都为0当然是可行解。
所以当lcm>long long 的时候直接退出，让lcm=0即可。
因为后面的坑点考场上一直没过，考后怒改成long double结果就过了。。。特判了一下改成long long居然time 就rank1了 嘎嘎
C.给了一个n个数的数列，然后给出m个set，S1-m每个里面有若干个1-n的数。接下来有q个操作：
1）输入x，询问sigma{a[i]}i属于Sx
2）输入x，y。将所有满足i属于Sx的a[i]+=y
n，m，q<=10W sigma{size(S)}<=10W
题解：这题真是神呀！！！先Orz一下。
我们把大小超过sqrt（n）的集合称为重集合，其他的为轻集合。这样重集合的个数不会超过sqrt（n）个。我们就可以暴力搞一些东西了
考虑四个操作：
1）修改重集合。因为不能一个一个修改，所以我们直接打一个标记，表示到目前为止该重集合一共被+了多少。O（1）
2）修改轻集合。直接修改a[i]，但还要考虑对重集合答案的影响，不然回答重集合的时候没法回答。对每个重集合i贡献|Si∩Sx|*y的ans O（√n）
3）查询轻集合。读取所有的a[i]，然后在考虑重集合打的标记对这个答案的影响，与上面类似。O（√n）
4）查询重集合。考虑重集合之间的影响即可。O（√n）
预处理每个重集合与每个集合的交集的大小即可。其实还是看代码比较清楚。
D.求一个n*m的方格（部分格子是障碍）上从（1,1）到（n，m）不经过同一个点的路径对的个数。
题解：结论题Orz。。。搬运网上的题解：
两个点集，A， B， 从A中一个点到B的所有路径中不相交的路径对数等于以下这个矩阵的行列式：
.
其中e（a， b）表示a 到 b的路径条数。所以答案是
我们取初始集合为A（（0， 1）， （1， 0）） B（（n - 1）, m - 2） （n - 2, m - 1）即可。
对于这种题我只能
评论 (0)
