【CSP模拟赛】Confess(数学 玄学)
题目描述
小w隐藏的心绪已经难以再隐藏下去了。小w有n+ 1(保证n为偶数)个心绪,每个都包含了[1,2n]的一个大小为n的子集。现在他要找到隐藏的任意两个心绪,使得他们的交大于等于n/2。
输入描述
一行一个整数n。接下来每行一个长度为k的字符串,该字符串是一个64进制表示,ASCII码为x的字符代表着x-33,所有字符在33到33+63之间。转为二进制表示有6k位,它的前2n个字符就是读入的集合,第i位为1表示这个集合包含i,为0表示不包含。
输出描述
一行两个不同的整数表示两个集合的编号。如果无解输出“NO Solution”。
样例输入
10
EVK#
IH=#
676"
R7,#
74S"
6V2#
O3J#
S-7$
NU5"
C[$$
3N.#
样例输出
1 2
对于20%的数据满足n≤100。
对于50%的数据满足n≤1×103。
对于100%的数据满足n≤6×103。
分析
我觉得应该没有人会想到暴力即是正解
首先先看一眼数据规模,好像用int存字符串会炸内存,于是考虑用bitset存
不然就像我一样爆零
然后就可以暴力地O(n3/32)地做啦
我们来验证一下它的正确性
任选出两个子集,考虑每个元素在两个子集中共有的概率,加起来就是期望共有的个数
由于总共有2n个元素,每个子集有n个元素,那么一个元素在子集内的概率就是$\frac 1 2$,
那么一个元素同时在两个子集内的概率就是$\frac 1 4$
所以任选两个子集期望的共有的个数是$\frac 1 4 \times 2n=\frac n 2$
当然,这个期望值是建立在数据纯随机的情况下的
我们接下来可以求一下在出题人控制了数据的情况下我们任选两个子集,子集的共有元素的期望个数
假设第i号元素有Si个子集拥有,那么对于i号元素就有$C_{Si}^2$种情况任选两个子集都包含i号元素,而任选两个子集的情况总数为$C_{n+1}^{2}$
所以对于i号元素,任选两个子集都包含它的概率为
$$\frac {C_{Si}^2} {C_{n+1}^2}$$
任选两个子集的期望共有元素个数为
$$\sum_{i=1}^{2n} \frac {C_{Si}^2} {C_{n+1}^2}$$
显然出题人可以控制每个Si的大小来卡我们,但他无法控制其它数的大小。
我们只要求出这个东西的最小值就可以知道出题人是否能卡我们
而且我们还知道
$$\sum_{i=1}^{2n} Si=n(n+1)$$
所以我们化简一下这个式子
$$\sum_{i=1}^{2n} \frac {C_{Si}^2} {C_{n+1}^2}$$
$$=\frac { \sum_{i=1}^{2n} {C_{Si}^2} } {C_{n+1}^2}$$
$$=\frac {\sum_{i=1}^{2n} { \frac {Si \times (Si-1) } {2} } } { \frac {n \times (n+1)} {2} }$$
$$=\frac {\sum_{i=1}^{2n} {Si \times (Si-1)}} {n \times (n+1)}$$
$$=\frac {\sum_{i=1}^{2n} {Si^2} - \sum_{i=1}^{2n} {Si}} {n \times (n+1)}$$
$$=\frac {\sum_{i=1}^{2n} {Si^2} - n(n+1)} {n(n+1)}$$
接下来只需要根据$\sum_{i=1}^{2n} Si=n(n+1)$求出$\sum_{i=1}^{2n} {Si^2}$的最小值就好啦
我们可以小的情况推到大的情况,比如知道$a+b=x$,求$min(a^2+b^2)$
可以用均值不等式的思想来证明
因为$(a-b)^2 \geq 0$,所以$a^2+b^2 \geq 2ab$
又因为$(a+b)^2=x^2$,所以$2ab=x^2-a^2-b^2$
代入$a^2+b^2 \geq 2ab$就有$a^2+b^2 \geq {\frac {x^2} {2}}$
同理,因为
$$\sum_{i=1}^{2n}\sum_{j=1}^{2n}(Si-Sj)^2 \geq 0$$
所以
$$\sum_{i=1}^{2n}\sum_{j=1}^{2n}(Si^2+Sj^2-2SiSj) \geq 0$$
$$\sum_{i=1}^{2n}\sum_{j=1}^{2n}Si^2 + \sum_{i=1}^{2n}\sum_{j=1}^{2n}Sj^2 - \sum_{i=1}^{2n}\sum_{j=1}^{2n}2SiSj\geq 0$$
$$\sum_{i=1}^{2n}\sum_{j=1}^{2n}Si^2 + \sum_{i=1}^{2n}\sum_{j=1}^{2n}Sj^2\geq 2\sum_{i=1}^{2n}\sum_{j=1}^{2n}SiSj$$
$$2n\sum_{i=1}^{2n}Si^2 +2n\sum_{j=1}^{2n}Sj^2\geq 2\sum_{i=1}^{2n}\sum_{j=1}^{2n}SiSj$$
$$4n\sum_{i=1}^{2n}Si^2\geq 2\sum_{i=1}^{2n}\sum_{j=1}^{2n}SiSj$$
又因为$\sum_{i=1}^{2n} Si=n(n+1)$
所以
$$\left ( \sum_{i=1}^{2n} Si \right )^2=n^2(n+1)^2$$
$$\sum_{i=1}^{2n}\sum_{j=1}^{2n}SiSj=n^2(n+1)^2$$
代入上面的不等式就有
$$4n\sum_{i=1}^{2n}Si^2\geq 2\sum_{i=1}^{2n}\sum_{j=1}^{2n}SiSj=2n^2(n+1)^2$$
$$\sum_{i=1}^{2n}Si^2\geq \frac {n(n+1)^2} {2}$$
我们终于求出了$\sum_{i=1}^{2n}Si^2$的最小值
把它代入我们之前求出的式子里
$$\frac {\sum_{i=1}^{2n} {Si^2} - n(n+1)} {n(n+1)}\geq \frac {\frac {n(n+1)^2} {2}-n(n+1)} {n(n+1)}$$
$$=\frac {n+1} {2} -1=\frac {n-1} {2}$$
所以不管出题人怎么出数据,任选两个字符串共有元素的期望个数最小都是$\frac {n-1} {2}$,所以直接O(n^3/32)是很正确的
代码?我™手贱重启电脑清空了
最新文章
- Listview的Item中有CheckBox、Button等的焦点处理
- linux配置网卡绑定
- zabbix数据库mariadb从服务器迁移到云mysql数据库的操作
- Spring AOP在函数接口调用性能分析及其日志处理方面的应用
- php连接sql server
- 微信支付(APP)集成时碰到的问题(.net提示“无权限”、iOS跳转到微信支付页面中间只有一个“确定”按钮)
- Annotations:注解
- [SinGuLaRiTy] NOIP模拟题 by liu_runda
- Django学习-3-请求流程
- sql Server 创建临时表 嵌套循环 添加数据
- 清除DNS缓存(解决能上QQ但是无法上网页问题)
- android 不同Activity之间数据传递
- android 广播 接收短信
- 编写Shell脚本
- POJ 3660 Cow Contest(Floyd求传递闭包(可达矩阵))
- 03: KindEditor (HTML可视化编辑器)
- (转)Jmeter http请求之content-type
- CentOS下的日志切割
- 帝国CMS7.2新增多图同时上传插件,上传多图效率更高
- APP线上问题收集信息整理
热门文章
- 2019年Amazon AWS-Solutions-Architect-Professional考试最新题库(AWS SAP题库)带考试模拟器
- js文本对象模型【DOM】(十一)
- linux技能五 文件权限
- let 和 var 定义变量的区别
- day 14作业
- Docker CMD ENTRYPOING 和Kubernetes command args对比
- vscode编写html,常用快捷方式与插件
- 摘:JAVA JXL API的详细使用
- centos服务器上git clone下载加速
- myslq数据库用union all查询出现 #1271 - Illegal mix of collations for operation 'UNION'