CFR429 div1

CFR429 div1

CF840B Leha and another game about graph

请先思考后再展开

保证原图连通下,假如没有-1且度数和为偶,一定有解:当图的n-1个点确定了奇偶性后,根据所有点度数和为偶,最后一个点目前的奇偶性一定等于想要的奇偶性,随便一个点作为根,随便建棵生成树,只考虑与父亲那条边即可调整奇偶性

有-1就更不用说了,取一个-1的点作为根即可

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
vc<int> to[N];map<int,int> id[N];
bool vis[N];int d[N];vc<int> ans;
void dfs(int x)
{
vis[x]=1;
for(auto y:to[x]) if(!vis[y])
{
dfs(y);
if(d[y]==1) {ans.PB(id[x][y]);if(d[x]>=0)d[x]^=1;}
}
}
void main()
{
int n=qread(),m=qread(),sum=0,bk=0;fo(i,1,n) {d[i]=qread();if(d[i]!=-1)sum^=d[i];else bk=i;}
if(sum and !bk){puts("-1");return;}fo(i,1,m){int x=qread(),y=qread();to[x].PB(y),to[y].PB(x);id[x][y]=id[y][x]=i;}
dfs(bk==0?1:bk);write2(sz(ans));for(auto t:ans) write2(t);
}

CF840C On the Bench

请先思考后再展开

另外似乎这题也是:luoguP4448 [AHOI2018初中组]球球的排列

很容易发现,将每个数的次幂模2,转化成有n个带标号有颜色球,要求多少种排列方式使得相邻的球颜色不同

很明显可以直接统计颜色序列,然后乘上$\prod cnt_i!$;然后大致思路也肯定是随便某种顺序依次考虑每种的颜色的所有球

然后这东西应该是不能容斥做的,但其实是可以直接做的,只要记录非法空位数,就能唯一统计了
$$
\\约定cnt_i为颜色i的数量,sum_i=\sum_{j=1}^i cnt_j
\\设f(i,j)=考虑了前i种颜色,恰好有j个非法的空位需要以后在中间插入其他颜色的球
\\枚举这次将球分成b组且解决了之前的a个非法空位
\\f(i,j-(a)+(cnt_i-b))+=f(i-1,j)*C_j^a*C_{cnt_i-1}^{b-1}*C_{sum+1-j}^{b-a}
\\时间复杂度为O(n*n*\sum cnt)=O(n^3)
$$
code

upd:毕竟本题a出很大要分解质因数,n=300可以理解,不过这个计数模型是可以进一步优化的

这里

CF840D Destiny

题意:长度为n的序列,q次询问一段区间,出现次数>$\frac{r-l+1}{k}$的最小数字,$n,q \le 3e5,k \le 5$

请先思考后再展开

我的做法:直接放到主席树上询问,看两侧孩子的大小是否大于这个,如果都行则两边都递归判断,这样复杂度其实是对的,因为这样同时分叉的点很少,极度好写,code

另一种做法:考虑到出现次数大于的数一定会在第wt大、第2wt大……中出现过,找到这些数判断他们的出现次数,稳定$O(nlogn*k)$

CF840E In a Trap

题意:给出$n \le 5e4$点根1的点带权($a_i\in [0,n]$)树,$q \le 150000$次询问x到y路径上(保证x为y祖先),$max\ a_i \oplus dis(i,y)$

请先思考后再展开

设一个阈值$2^T$,每个点x开一个字典树表示向上的$2^T$个点的$a_y \oplus (dep_x-dep_y)$,于是我们可以将权值从$a_x\oplus (ln1+ln2) \to (a_x\oplus ln1) \oplus ln2$,其中括号里的东西是字典树中内容

于是预处理的话直接丢进去,$O(n*(2^T+\frac{n}{2^T})*log_n)$;每次回答询问就往上跳,$O(q*(2^T+\frac{n}{2^T}logn ))$

然而这样空间有点炸,考虑到$2^T|ln2$,于是每个字典树存下每种ln2的答案,空间降低为$O(\frac{n^2}{2^T})$,且q中向上跳不带log,即$O(n*(2^T+\frac{n}{2^T})*log_n+q*(2^T+\frac{n}{2^T} ))$,$T=8为宜$

code

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