负担集训-Test12
_THIS_IS_START_OF_ARTICLE_
_THIS_IS_END_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]在哈希表里面询问
这样方案数和任意一个方案都是可以询问出来的。
-------------------------------------------------------
评论 (0)
