1月做题记录

1月做题记录
最后一个1月份了,年份都不用写了;即使实力不强也希望这份题单能给后人一些帮助

CF457D Bingo!

请先思考后再展开

$2^k明示转化成\sum_{i=0}^k C_k^i$,于是枚举子集统计概率即可;$\sum_{a=0}^n \sum_{b=0}^n C_n^aC_n^b \frac{C_{m-s}^{k-s}}{C_m^k},S=(a+b)n-ab,后面化化式子就是\frac{k^{\underline S}}{m^{\underline S}}$,预处理就没有精度问题了,cf不知为何无法提交

1
2
3
4
5
6
7
8
9
double C[1001][1001],pp[N];
void main()
{
C[0][0]=1;fo(i,1,1000){C[i][0]=1;fo(j,1,i) C[i][j]=C[i-1][j-1]+C[i-1][j];}
int n=qread(),m=qread(),k=qread();
pp[0]=1;fo(i,1,m) pp[i]=pp[i-1]*(k-i+1)/(m-i+1);
double ans=0;fo(a,0,n) fo(b,0,n) ans+=C[n][a]*C[n][b]*pp[(a+b)*n-a*b];
chmin(ans,1e99);printf("%.10lf",ans);
}

CF1187F Expected Square Beauty

题意:给出$n \le 1e5$个离散随机变量的取值范围$[l_i,r_i]$,问$E(( \sum_{i=1}^n [x_i!=x_{i+1}] )^2)$

请先思考后再展开

$P(x_i \ne x_{i+1})=并集大小/s_i/s_{i+1},E(x^2)=\sum p_i+2\sum[x_i \ne x_{i+1}且x_{i+1} \ne x_{i+2}]+2\sum_{i+1<j} p_ip_j$

code

abc150F F Xor Shift

题意:给出长度$n \le 2e5$的序列a和b,问多少组$(k \in [0,n),X \ge 0)满足 \forall b_i=a_{(i+k) \% n} \oplus X$

请先思考后再展开

我的思路是搞成$B_i=b_i \oplus b_0,\forall i,B_i=a_k \oplus a_{k+i}$,然后这个好像没法做,遂自闭

正解是考虑$X=b_i \oplus a_{i+k}=b_{i+1} \oplus a_{i+1+k},即\forall b_i \oplus b_{i+1}=a_{i+k} \oplus a_{i+k+1}$,于是就是个字符串匹配,枚举k维护hash即可

code

一道字符串题

题意:给定n的置换p,判断字符串S的每个长度为n的子串T是否满足$[T_1,T_2..T_n]=[T_{p_1},T_{p_2}..T_{p_n}]$,$|S| \le 5e5$

请先思考后再展开

每个轮换字符相同,然而没法做

考虑hash判断,对于$[j+1,j+n],f_j=\sum S_{j+i}b^{p_i},g_j=\sum S_{j+i}b^i$,优化卷积即可

一道最短路题

题意:给定$n \le 1e3$点$m \le 1e5$边权为一的有向图,求每条边$(x \to y)$被删除后x到y的最短路

请先思考后再展开

考虑x的最短路树且此时$dis_x(y)$,x到y的新最短路肯定是$x沿着树上路径到达y子树外的z \to 完全y子树内部走$,所以枚举每条跨子树的那种边更新初始为无穷大的变量$dd_x(y)$,然后用dd跑最短路,这个最短路可以用n个队列模拟堆实现,复杂度为$O(nm)$

「SCOI2015」小凸玩矩阵

请先思考后再展开

显然转化为判定能否$第k大 \le T$,再转化为$[\le T] \ge n+k-1$,即在不大于T的数中选最多个使得不会在同一行或同一列,经典的拆行和列跑二分图最大匹配,网络流即可

「SHOI2017」寿司餐厅

题意:n种寿司,每种寿司有代号$a_i$,可以任意次选择区间$[l,r]$,然后将给出的表格d中$(l..r,l..r)$这个矩形内所有数求和并清零,和就是本次的收益;给定常数m,一个方案的付出就是$\sum_{代号i} mi^2*[cnt_i>0]+cnt_i*i$,最大化净利润

$n \le 100,a_i \le 1e3,m=0/1,d_{i,j} \in [-500,500]$

请先思考后再展开

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