负担集训-Test11(多校联合训练-4)
负担集训-Test13

负担集训-Test12

YYY posted @ 2017年8月04日 23:15 in ACM with tags 懒得写了 , 438 阅读
_THIS_IS_START_OF_ARTICLE_
-------------------------------------------------------
辣鸡1005,题面的数据范围不对,卡了我们队两个小时。

-------------------------------------------------------
1001:
题意是说给你$n$个不相同的数$a[i]$,问那些数不是给出的数的约数(不算自己)
$n\leq 10^5 , a[i]\leq 10^7$
 
先把所有$a[i]$存到桶里,然后每次枚举一个数的倍数看有没有出现过就好
 
-------------------------------------------------------
1005:
题意是说现在有一个选举,有$n$个投票人,$m$个候选人,每个投票人可以投任意一个候选人或者弃权,现在你要钦定第$k$个候选人赢得选举,要求是他的票数严格大于其他任意一个候选人,如果你要强迫第$i$个投票人投$j$,需要付出$a[i][j]$的代价,如果要强迫他弃权需要$a[i][m+1]$的代价,求最少花多少代价让$k$赢得选举
$n\leq 100,m\leq 10,a[i]\leq 10^9$
 
首先枚举k的得票数,比如说为$r$,然后费用流验证,建图如下:
源->投票人,费用为$0$,流量上界为$1$
投票人->候选人/垃圾桶(容纳弃权票),费用为$a[i][j]$,流量上界为$1$
第$k$个候选人->$t$,费用为$0$,流量上下界都为$r$
候选人->$t$,费用为$0$,流量上界为$r-1$
垃圾桶->$t$,费用为0,流量上界为$+\infty$
然后每次更新一下答案就好
至于怎么获得方案,只需要去检查投票人->候选人的边,看哪些边被用过就好了
 
-------------------------------------------------------
1006:
题意是说现在让你构造一个自动机,使得他能且仅能接收所有$b$进制的$m$的倍数,并且让他的点数最小。
$b\leq 16,m\leq 10^5$
 
首先一种基本的想法是,第$i$个点的$j$出边往$(bi+j) mod\ m$连,然后有且仅有$0$是终止节点,这样可以保证能且仅能接收所有$b$进制的$m$的倍数,但是不是最小的。
现在考虑把走一步之后的点相同的点合并起来,再把走两步之后的点相同的点合并起来...这样
现在假设走了$k$步,如果i和j走了k步相同的话那么显然有$b^ki=b^kj(mod\ m)$
那么就有$m|b^k(i-j)$,假设$d=gcd(m,b^k)$,也就是说$b^k$可以提供$d$这部分的约数,于是${n\over d}$这一部分的约数要由$(i-j)$来提供,也就是把所有编号差值是${n \over d}$的节点连起来。
但是还有一个例外,就是如果一个点走$k$步以内可以到达$0$点,那么就说明这样合并的话有可能把不是$m$的倍数的串也接收了,因此要判断一下每个点到达$0$的最短距离(反向建边然后spfa),如果$k$大于这个距离的话那么他就不参与这次合并。
至于怎么合并,用并查集就好。
 
 
-------------------------------------------------------
1011:
题意是说现在给你一个长度为n的数字串$s$,一个素数$p$,$t$个询问,每次询问给你一个$a[i]$,问你有多少对$(l,r)$使得$s[l,r]=a(mod p)$,并且任意输出一个方案
$n\leq 10^5,p\leq 10^9+33,t\leq 100$
 
现在假设维护了一个数组$b$,$b[i]=s[i,n] mod p$
那么$s[l,r]$就等于$(s[l] - s[r+1])10^{r-n}$
因此题意就相当于要求满足$(s[l] - s[r+1])10^{r-n} = a[i]$
也就是$s[l] = 10^{n-r}a[i] + s[r+1]$
那么只需要倒着搞,每次把$10^{n-j}a[i] + s[j+1]$丢到哈希表里面去,再用s[j]在哈希表里面询问
这样方案数和任意一个方案都是可以询问出来的。
 
-------------------------------------------------------
 

 

_THIS_IS_END_OF_ARTICLE_

登录 *


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