CFR602

CFR602 div1

CF1261A Messy

题意:题意鬼长,其实就是给出一个长度为n的括号序列,要求构造操作序列,每次选一个区间并翻转,最后是合法括号序列的前缀恰有k个,$n \le 2e3$

请先思考后再展开

随便设计一个想要的结果序列,从左往右判,如果不同就从后面找一个想要的字符,这样的操作数量最坏为n

code

似乎bzt被这题搞了

CF1261B Optimal Subsequences

题意:给出一个长度为n的序列,m次询问$(k,pos)$,输出k阶子序列的第pos个元素,k阶子序列定义为所有长度为k的子序列中和最大的,在其中字典序最大的序列,$n \le 2e5$

请先思考后再展开

考虑贪心,首先k阶子序列的元素集合是确定的,而且除了最小元素其他具体选哪些位置的数已经确定,然后肯定是取最小元素的前wt个,于是写了个二分+主席树,check就是$[min(wt,左边=mi)]+[左边>wt] \ge pos$,$O(nlog^2n)$,code

$O(nlogn)$的做法可能稍微长一些就没写(其实只是没去想):直接找到第wt个mi在哪里,统计出左边>wt的个数,从而判断出右边还有多少个>wt的数,上面各种都能在主席树上二分实现

upd:其实离线从小到大处理k,那么就是稳定排序后前k个,那么只需要在线段树上二分第pos大就行了……

CF1261C Arson In Berland Forest

请先思考后再展开

无脑的想法是二分,写个二维前缀和判这个点能否放火,最后判断是否所有地方都被烧到,$O(nmlog)$,code

有脑的想法是,对每行的连续段、每列的连续段长度取min,这样直接$O(1)$求出T

CF1261D Wrong Answer on test 233

请先思考后再展开

$相当于n个变量x_i,计数\sum [x_i=a_i]-[x_i=b_i]>0$,设$cnt=\sum [a_i \ne b_i]$,则显然$ans=\sum_{i>c1} [x^i] (1+(k-2)x+x^2)^{cnt}$

然后因为太久没接触多项式相关理论,在exp和分治ntt中选择了exp然后T飞,然后发现可以倍增,然后因为我的多项式板子的封装的常数较大到最后都没有过,然而本机是1.3s,表示很懵逼

吃完饭回来回忆了一下多项式相关理论,想起来这是非常经典的DFT后点值下求快速幂就好了

code

其实直接推式子也是可行的,但当时真的没想到CF上写多项式桶,甚至比本机慢(用自定义测试发现慢了0.7s)

CF1261E Not Same

题意:给出$n \le 1e3$个1到n的变量,构造最多n+1个01串,使得每个数位加起来等于该变量,可直接看样例

请先思考后再展开

不难,再次感觉血亏

很自然的思路是先排序,然后想办法递归下去构造

也很自然地从最大那列入手,但先不要急着放,那么现在相较于n-1我们多了一行一列,这一行肯定是用来负责大小为n的变量的(以保证递归下去的子问题也满足值域不超过个数),这行的n-1列已经确定,然后我们递归(或者说归纳)就是保证了那n行是互不相同的。现在可能这n行中最多一行,与多出来那行相同,这时我们就能用最大那列的0、1将这两行区分

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
bool ans[N][N];int id[N],a[N];
void solve(int n)
{
if(n==1){ans[1][id[1]]=1;return;}
int mx=a[id[n]];fo(i,1,n-1) if(a[id[i]]==n) a[id[i]]--,ans[n+1][id[i]]=1;solve(n-1);
int ret=-1;fo(i,1,n){bool ok=1;fo(j,1,n-1)if(ans[n+1][id[j]]!=ans[i][id[j]])ok=0;if(ok)ret=i;}
fd(i,n+1,1) if(mx and i!=ret) mx--,ans[i][id[n]]=1;
}
set<string> mp;
void main()
{
int n=qread();fo(i,1,n) a[i]=qread(),id[i]=i;
sort(id+1,id+n+1, [](int x,int y){return a[x]<a[y];} );
solve(n);
fo(i,1,n+1){string now="";fo(j,1,n)now=now+char('0'+ans[i][j]);mp.insert(now);}
write2(sz(mp));for(auto str:mp) cout<<str<<endl;
}

CF1261F Xor-Set

题意:给出两个集合A、B,求集合$C = {x | x = a \oplus b, a \in A, b \in B}$内所有元素的和,A和B的给出形式为$n \le 100$个连续段$[L_i,R_i]$

请先思考后再展开

设状态$(S,i)=[S,S+2^i),且S后i位=0$,那么$i>j,(S_1,i) \oplus (S_2,j)=(S_1 \oplus S_2 \oplus (S_2\&(2^i-1)),i)$

于是很自然的想法是枚举每两个连续段,将能产生的区间统计下来,最后排序并合并,排序可以直接sort,也可以用做基排,压7位常数3;于是我们的复杂度为$3*(1e7+n^2*两个连续段产生的区间数G)$

每个连续段按照线段树那套理论分成log段区间,枚举每两个区间,$G=log^2$,可能通过一些奇技淫巧如去重处理一下能通过

正解是$G=O(log)$,具体常数计算起来意义不大,因为通常不会满:

看到上面那个状态的合并,很自然的想法是$\forall j \ge i,S_1 \oplus S_2 \oplus (S_2\&(2^i-1))$相同的S2放在一起处理,但我完全不知道这东西的复杂度为什么是对的(当然如何写对也是一方面)

我们仔细想想S1是怎么去找这种S2的,显然只需要找这一层(类似线段树的层)的,有孩子的节点

枚举层的话会很不同,因为线段树在访问的过程中每层最多4个节点

另外两种比较玄妙的写法:复杂度显然对,但分解得似乎很本质建字典树,基于答案为v去做dfs,维护所有点对现在走到哪里,往下推直到碰到某个终止点,即上面说的那个剪枝,肯定是对的,但复杂度还是搞不懂

当然实现的时候我选择sort

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
vc<pr> real[2];vc<ll> go[2][100];
#define mid (l+r)/2
void split(int op,ll fl,ll fr,ll l=0,ll r=bin(60)-1,int i=60)
{
go[op][i].PB(l);if(l==fl and r==fr){real[op].PB(MP(l,r));return;}
if(fr<=mid) split(op,fl,fr,l,mid,i-1); else if(fl>mid) split(op,fl,fr,mid+1,r,i-1);
else split(op,fl,mid,l,mid,i-1),split(op,mid+1,fr,mid+1,r,i-1);
}
vc<pr> all;
void solve(ll al,ll ar,ll bl,ll br)
{
fo(op,0,1){real[op].clear();fo(i,0,60)go[op][i].clear();}
split(0,al,ar);split(1,bl,br);
fo(op,0,1) for(auto x:real[op])
{
int i=log2(x.SE-x.FR+1);
for(auto y:go[op^1][i]) all.PB(MP( x.FR^y,(x.FR^y)+bin(i)-1 ));
}
}

完整代码

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