3
13
2015
0

Codeforces Round #202 (Div. 1)

这场打得真是烂啊。。。各种逗逼。。。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的所有路径中不相交的路径对数等于以下这个矩阵的行列式:

 M = \begin{pmatrix} e(a_1,b_1) & e(a_1,b_2) & \cdots & e(a_1,b_n) \\ e(a_2,b_1) & e(a_2,b_2) & \cdots & e(a_2,b_n) \\ \vdots & \vdots & \ddots & \vdots \\ e(a_n,b_1) & e(a_n,b_2) & \cdots & e(a_n,b_n) \end{pmatrix} .

其中e(a, b)表示a 到 b的路径条数。所以答案是

我们取初始集合为A((0, 1), (1, 0)) B((n - 1), m - 2) (n - 2, m - 1)即可。

           对于这种题我只能

官方题解:http://codeforces.com/blog/entry/9031

Category: codeforces | Tags: | Read Count: 742

登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter

| Theme: Aeros 2.0 by TheBuckmaker.com