20191109模拟-lxy

lxy的场

好题:CF1188D Make Equal

CF1188D Make Equal

题意:给出一个长度为n的序列a,每次选一个数加上2的次幂,问最少操作多少次能使所有数相同,$n \le 1e5,a_i \le 1e17$

请先思考后再展开

先明确一些明显的性质,设最后的数为wt,则$A=max\ a_i,wt \ge A,ans=\sum popcount(wt-a_i)$

一个自然的想法是从低到高位dp,$f(k,State)$表示正在考虑第k位是什么,第k-1位的进位情况

给出一个我觉得不显然的结论:设按照$a_i \% 2^{k}$排序得到的序列为$b_k$(可以基排在$O(nloga)$内求出),则State必定是$b_k$的一段后缀

证明很容易,归纳法+讨论:已知第k-1位进位的部分是$b_k$的一段后缀B,不进位为A,然后如果现在选1就是B中当前位是1的,如果选0就是原先所有进位及A中当前位是1的,发现都是$b_{k+1}$的后缀

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
vc<ll> lst,now[2];int f[100][N];//f(i,j)=j..n-1在第i位向第i+1位进位
void main()
{
int n=qread();fo(i,1,n) lst.PB(qread());memset(f,0x3f,sizeof f);f[0][n]=0;
fo(k,0,59)
{
now[0].clear();now[1].clear();for(auto num:lst) now[(num>>k)&1].PB(num);

int to,ad;
//0
to=sz(now[0]),ad=sz(now[1]);chmin(f[k+1][to],f[k][n]+ad);
fd(i,n-1,0) to-=(lst[i]&bin(k))==0,ad+=((lst[i]&bin(k))==0)-((lst[i]&bin(k))>0),chmin(f[k+1][to],f[k][i]+ad);
//1
to=n,ad=sz(now[0]);chmin(f[k+1][to],f[k][n]+ad);
fd(i,n-1,0) to-=(lst[i]&bin(k))>0,ad+=((lst[i]&bin(k))>0)-((lst[i]&bin(k))==0),chmin(f[k+1][to],f[k][i]+ad);

lst.clear();for(auto num:now[0]) lst.PB(num);for(auto num:now[1]) lst.PB(num);
}write(f[60][n]);
}

CF1083D The Fair Nut’s getting crazy

题意:询问有多少个四元组$(a,b,c,d)满足0<a<b<c<d \le n+1且[b,c]内元素互不相同且里面每个a_i在[a,b)和[c,d)中没有出现过$,$序列长度 \le 1e5$

请先思考后再展开

先求出每种值的上次出现lst和下次出现nxt,容易得到$O(n^2)$做法:$对于区间(l,r),lmx=max_{i=l}^r\ lst_i+1,rmx=min_{i=l}^r\ nxt_i-1,lmx<l且r<rmx下,贡献为(rmx-r)(l-lmx)$

然后考虑从左往右处理右端点,贡献拆开为$(rmx-r)*l-(rmx-r)*lmx$,开两棵线段树,每个位置存二元组$(x,y),询问\sum (y-询问的数)*x$,记录分别的和、乘积的和,单调栈+线段树区间修改区间求和,$O(nlogn)$,code

uoj210「UER #6」寻找罪犯

请先思考后再展开

如果你只是单纯地给人定0/1是不行的,必须要给每条信息也建点,那么明显限制都是2-sat的形式,具体如下:

若是犯人点直接忽略(不连向任何信息点),若是好人点则直接相信其所有话连向其他人点

对于信息点,根据其代表的意思连向人点;另外假话点需要连向这个人说的其他真话点,表示最多说一句假话

本文基于 知识共享署名-相同方式共享 4.0 国际许可协议发布
本文地址:http://zory.ink/posts/ffd959be.html
转载请注明出处,谢谢!