2019.11.11&12题解
程序员文章站
2023-11-08 19:30:28
Day1 考的不是很好,T1T2没区分度,T3想的太少,考试后期几乎都是在摸鱼,bitset乱搞也不敢打,只拿到了35分,跟前面的差距很大 A. 最大或 标签: 二进制+贪心 题解: 首先x,y中一定有一个是R,考虑L的取值:对于每一位分为x中有没有讨论: 1>有 如果这一位不加以后全加可以>=L则 ......
day1
考的不是很好,t1t2没区分度,t3想的太少,考试后期几乎都是在摸鱼,bitset乱搞也不敢打,只拿到了35分,跟前面的差距很大
a. 最大或
标签:
二进制+贪心
题解:
首先x,y中一定有一个是r,考虑l的取值:对于每一位分为x中有没有讨论:
1>有 如果这一位不加以后全加可以>=l则不选,否则选
2>没有 如果这一位选上以后全不加也无法<=r则不选,否则选
因为位数从高到低枚举,所以贪心是正确的
b. 答题
标签:
折半搜索+二分
题解:
2<=n<=40,显然是要折半搜索的,答案满足单调性,可以二分判断,check时复杂度最好是1<<20,而不是2e7的值域
说实话这道题比t1要简单
c. 联合权值·改
标签:
啊啊啊起个标签好蓝啊
题解:
首先证明环的数量是$m*sqrt(m)$的:
考虑最坏情况:一定是一个竞赛图,那么点数就是$sqrt(m)$,环数最多是$m*sqrt(m)$
有了这个性质下面的算法便有了复杂度保证:
1>对于第一问:
把每个点的出边按w[to]降序排序,考虑枚举$ x,y((x,y)\in{edge}),z((x,z)\in{edge}) $
只需要找到第一个不是三元环的z点便可以更新答案,复杂度与枚举到的环有关,而每个环最多会被枚举到3次,所以复杂度是对的
2>对于第二问:
考虑容斥:
用每个点的出点的权值和的平方减去平方的和,
再减去三元环的的情况,我是枚举u,v用bitset求出b[u]&b[v].count()便是有u,v的三元环的个数
day2
t1t2仍然没区分度,t3原题没看出来,总排rk10,翻盘失败
a. 物理课
标签:
物理?
题解:
b. 数学课
c. 地理课
推荐阅读
-
Windows下利用Gvim写PHP产生中文乱码问题解决方法
-
PHP中使用file_get_contents抓取网页中文乱码问题解决方法
-
PHP商品秒杀问题解决方案实例详解【mysql与redis】
-
MySQL中NOT IN填坑之列为null的问题解决
-
Linux中date命令转换日期提示date: illegal time format问题解决
-
MySQL5.7.03 更换高版本到MySQL 5.7.17安装过程及发现问题解决方案
-
MySQL 与 Elasticsearch 数据不对称问题解决办法
-
Pycharm中Python环境配置常见问题解析
-
web.py在SAE中的Session问题解决方法(使用mysql存储)
-
Android关于SeekBar无法点击到最大值问题解决方法记录(推荐)