首页 > 其他分享 >「Log」2023.10.27 小记

「Log」2023.10.27 小记

时间:2023-10-28 09:05:02浏览次数:33  
标签:27 Log color 2023.10 le 即可 此题 blueviolet dis

序幕

\(\text{6:50}\):到校,早上稍微墨迹了一小会。

一直不会的某个结论差不多会证明了,先写一下题再写写题解。

\(\color{blueviolet}{CF1495D}\)

此题是好题。

考虑对于 \(x\) 和 \(y\) 共同的生成树一定包含两者的最短路径。

先假设 \(x, y\) 最短路径有且只有一条,考虑其上一点 \(z\),\(x, y\) 两者中一者到其最短路径依然有且只有一条,为了满足 \(dis(x, z), dis(y, z)\) 不变,必须保留此最短路。

当 \(x, y\) 最短路径不止一条时,对于这两条路径上的点依然需要满足上述 \(z\) 的条件,因此多条最短路都需要保留,此时一定会成环,无法保持树的形态,也就一定无解。

现在对于 \(x, y\) 两点已有一条唯一的链链接,考虑其他点如何挂在树上。对于一个点 \(u\) 有边 \((u, v)\),若保留此边(使得 \(v\) 为 \(u\) 的父节点)必须满足 \(dis(x, v) + 1 = dis(x, u) \land dis(y, v) + 1 = dis(y, u)\)。所以我们对于一个点找出其合法父节点个数,对所有的点乘法原理计数即可。

间幕 \(1\)

找了到 2700 的瞅了瞅,感觉做不出来就直接看题解了,莫队倒是想到了点,就是没想到能卡过去。

这个神秘的单 \(\log\) 算法是真想不出来。

刷了会手机,\(\text{8:20}\) 接着做题。

\(\color{blueviolet}{CF1511G}\)

此题是神仙题。

首先转化问题,对于一个询问只要判断 \(\bigoplus \limits _{l \le c_i \le r} c_i - l\) 是否等于 \(0\) 即可。

设 \(f_{i, j}\) 表示 \(\bigoplus \limits _{i \le c_i \le i + 2 ^ j - 1} c_i - i\),考虑如何倍增转移。

\(f_{i, j}\) 由 \(f_{i, j - 1}\) 与 \(f_{i + 2 ^ {j - 1} - 1, j - 1}\) 两部分组成,前者的异或和可以直接转移过来,后者包括的元素每个会与需要的值相差 \(2 ^ {j - 1}\),所以需要额外异或上后者元素个数个 \(2 ^ {j - 1}\),只需要通前缀和维护一下区间元素个数即可。

\[f_{i, j} = f_{i, j - 1} \oplus f_{i + 2 ^ {j - 1} - 1, j - 1} \oplus \left([(g_{i + 2 ^ j - 1} - g_{i + 2 ^ {j - 1} - 1}) \mod 2 = 1] \times 2 ^ {j - 1} \right) \]

求答案也是类似的,倍增逼近即可。

\(\color{blueviolet}{CF1510B}\)

此题是坏题,它让你输出方案。

首先考虑转化问题,进行简单图论建模,每个状态向可以达到的状态连边,于是得到一张 DAG。

首先考虑最劣情况,对于每一个点单独成为一条路径进行覆盖,贡献是其二进制下 \(1\) 的个数。每一个点可以选择一个出边把自己贡献抵消掉,这个就类似二分图最大匹配,费用流即可。

间幕 \(1\)

午休,中午还吃鱼丸饭,西红柿炒蛋真的太好吃啦!

下两把棋,打会块,然后小睡一会。

两点多苏醒接着做题。

\(\color{blueviolet}{CF1539F}\)

此题是坏题,第一遍打假了。

我们只考虑 \(a_i\) 大于中位数的情况,另一情况可以通过取负反转数组取到相同情况,式子只有一个加减 \(1\) 不同。

区间固定时贡献是 \(\frac{t_l + t_m + t_r}{2} - t_r = \left \lfloor \frac{t_l + t_m - t_r}{2} \right \rfloor\)。

其中 \(t_l, t_m, t_r\) 分别表示小于、等于、大于 \(a_i\) 的 数字个数。

然后运用到一个套路,对于这种中位数的东西离线并从小到大遍历数字,比自己小的设为 \(-1\),比自己大的设为 \(1\),求一下以 \(i\) 结尾的后缀最大、以其开头的前缀最大,求和即可。

间幕 \(2\)

和 iazm 出去逛逛,在操场上瞎聊天,溜达了半小时,回来吃饭,一直墨迹到 \(19:00\),写题写题。

发现任务里的 2600 快写完了,只剩 2700,悲伤的。(虽然我没觉得两者差距很多,反正大部分我都不会做。)

\(\color{blueviolet}{CF1469F}\)

首先注意到先挂长链更优,并且将中点挂在树上是更优的,可以使得整体深度更小。

设 \(fa\) 为链挂在上面的点,则会使得深度为 \(dep_{fa}\) 的点减少一个,并增加连续深度的两段点数,用线段树维护即可,注意分讨奇偶即可,以及注意空间。

尾声

看了一道 2700,就下班了。

回家打会游戏后直接昏迷。

标签:27,Log,color,2023.10,le,即可,此题,blueviolet,dis
From: https://www.cnblogs.com/Eon-Sky/p/17790957.html

相关文章

  • 10.27
    今天学习了分层解耦    ......
  • 2023.10.27——每日总结
    学习所花时间(包括上课):9h代码量(行):0行博客量(篇):1篇今天,上午学习,下午学习;我了解到的知识点:1.mybatis明日计划:学习......
  • 20231027
    23/10/27NOIP模拟赛总结时间安排:7:40-8:30看T1,没啥思路,一开始以为是组合数,写了个递推求组合数发现是最简单的DP,测样例,手搓了几组小样例都过了。8:30-8:50T2只会模拟,写的get函数有点麻烦,耽误了一些时间。9:00-9:30看T3T4都没想到,去写T5暴力。9:30-10:20T5暴力取模的地方......
  • 20231027NOIP训练赛
    20231027NOIP训练赛时间安排7:40-9:20写T19:20-10:20写T210:20-11:10写T3T411:10-11:50写T5总结T1写挂了,T3的set超时了题解T1简单DP题T2把加转化为差分,差分数组进行区间加操作,用线段树维护T3用一个栈维护一下没有被匹配的字符即可T4结论题,答案要么删掉一个点,要......
  • Logstash input插件
    input插件用于指定输入源,一个pipeline可以有多个input插件,我们主要围绕下面几个input插件进行介绍stdinfilebeatkafkahttp2.1stdin插件从标准输入读取数据,从标准输出中输出内容cat/etc/logstash/conf.d/stdin_logstash.conf#从终端中输入,输出到中端input{ stdi......
  • 10.27 鲜花
    crimson今天不写,那我写一个(?经典一堆分段北校在搞什么第三届班主任节(我没记得去年有这玩意啊)然后让我们跟班拍照。。。和我想象的一样。。。一到楼下六七个人问我“你什么时候回来呀”(不管以前问没问过我!)上一次回班他们告诉我由于种种原因我换组了。然后。。。今天五六个人......
  • 10月27日星期五
    今天没课睡到中午才醒,晚上我去基教学习了vue向看看它的作用,发现好像是优化界面的所以就先放下了,打算先学些基础,主要是后端向前端传值还不太会,想学完之后做出一个最基本的项目,今日进度,前端界面已经构建完成并且能够向后端传值实现增加的功能,遇到难点还不会后端向前端传值,......
  • 20231027
    20231027NOIP#25总结时间安排7:40~8:10看题\(A\)一眼切,\(B,C,D,E\)都不会。8:10~8:30写\(A\),但这个题坑真多。8:30~8:50写\(C\),这个好像是原题。8:50~9:50写\(B\),带些许数学的模拟,有点难写。9:50~10:35写\(E\)的前两档,但第二档做法假了。10:35~11:30反应了......
  • 10/27
    10/27https://codeforces.com/problemset/problem/1697/Femm大概就是约束下>=这个东西。https://codeforces.com/problemset/problem/1010/E无趣的数据结构。本质上是三维空间内的长方体求并,对于一个是关着的,当且仅当,我们假设他是开的,与原先关着的矛盾了!https://codeforc......
  • NFLS10.27
    今天挂分10pts,因为数组大小问题/fnT1直接在求素数的时候维护一下两个素数的乘积就好了,切了切了。T2是一个图论建模,可以将这个对应到最短路上面去,也能做。(我刚开始想到dp去了,推了一会儿发现这玩意儿有后效性,寄,迅速转战图论思考)T3好好好,考构造是吧,但是我拿出暴力大法师仍......