pinkyHead's blog

本场摘要 D 题没有涉及到什么前置知识，蛮适合作为某些笔试中的压轴题的，如果对滑动窗口类型的 DP 的了解变得生疏的话，这道题目还是有一定难度的。 E，F，G 难度相差不大，不过要在两小时内全部通过还是比较困难，自己做的时候wa了若干次——还是再接再厉吧。 传送门： 题目 代码仓库 C. 题目大意： 输入三个数字 A，B，X。求如下式子： Min⁡{∣(A⊕x)−(B⊕x)∣},0⩽x⩽X\operatorname{Min}\{|(A \oplus x)-(B \oplus x)|\}, 0 \leqslant x \leqslant X Min{∣(A⊕x)−(B⊕x)∣},0⩽x⩽X 题解： 不妨设A>BA>BA>B, 且将 A 和 B 都用二进制表示。 由于 A 和 B 都要和 X 进行异或操作，如果某一个位上 A 和 B 都为 1 或者 0 ，那么将 x 的对应位置为 0 即可。这样一来，异或操作的作用，可以理解成将一个数字中某个位置上的 1，移动到另一个数字中的对应位置中去。 所以期望最小的方案就是，A 的最高的 1 不动，然后尽可能地通过异或 x 将 ...

本场摘要 传送门： 题目 题解代码 这场总体难度较小，没有很难的题目。但是会在刁钻的地方恶心人，也许是出题的印度老哥故意设计的。。。总之题目出得非常奇怪，不过作为复健场来说也还算有练习的价值。 总体做下来体验有点差——特别是最后的F题。幸好只是拿来训练，不然参赛的话可能会一直WA。 D. Good Trip 题目大意： 在nnn个元素中等可能地选取两个元素，选完后放回，等可能地选mmm轮。每对元素可能是朋友或不是朋友，如果是朋友则对应的“友好值”为一个整数。每当一对元素被选中后，如果这对元素是“朋友”，则会将该友好值加到sumsumsum中，并且其“友好值”会+1+1+1。问最终sumsumsum期望多大。 题解： 将sumsumsum分成两部分，即「基础部分」和「增加的部分」。 「基础部分」是很显然的： k∗∑i=1mfiCn2k * \frac{\sum_{i=1}^m f_i}{C_n^2} k∗Cn2​∑i=1m​fi​​ 「增加部分」稍微有些棘手。可以注意到，如果只考虑增加值的话，每对朋友都是等价的，所以只要算出一对朋友的贡献，最后乘以朋友对数就行了。 而在增加值中，一对 ...

最近的生活 再过两天就是2024年了，距离我的22岁生日也过去了三个月。 现在是晚上八点三刻，公司里现在就我一个人，除了耳机里的Thom Yorke，陪伴我的就只有我的打字声。 毕业之后的这段时间里，我过上了点外卖不用看价格的滋润生活。每天正常上班下班，工作的压力也还算可以接受，回家后依然有时间继续朝着自己认准的方向做些事情。前段时间，我买了一个声卡，并在公司发的Mac上装上了一大堆软件，期待能继续学起电吉他；每隔几天，我就会在离家不远的“沙龙”去清一次痘，希望能有朝一日解决我的脸部皮肤问题；今天下午，我去报了一个声乐的班，老师说我声音条件还蛮不错，经过十几节课后一定能唱出Radiohead的曲子；后天，我盘算着去买一把宣尧推荐的yamaha LL16，一是因为我发现我现在最喜欢的都是原声吉他的曲子，二来打算尝试一下弹唱… Where is my mind? 一切似乎都走在正轨上，除了有些孤独之外，似乎没什么事情是值得我难过的。 可是，我最近的心里负担却异常地大，因为我遇到了人生中第一个难以逾越的坎————至少目前为止，我对此有些手足无措，看不到任何可以将其跨越的迹象。 这段时间里 ...

毕业之前心血来潮开了一场vp，就当作是追忆青春了吧（大雾 平时比较懒，打了这么多cf都没写过题解，还是蛮可惜的，如果再多写点，说不定还能给还在校队的学弟们参考参考，也不知道以后是否还会再登录cf，也许这篇博客就是休止符？希望我某天还是再上号打打吧，毕竟当年立下的上红名的flag还没实现呢… 从2022年12月杭州站结束后退役算起，已经过了快一年了，会看过去的题解博客，颇有一番悲凉的感觉。自己就像是推石头的西西弗斯，做着很多毫无意义的事情————虽然自己乐在其中。 “是谁来自山河湖海，却囿于昼夜厨房与爱”。不论自己有多么多不切实际的幻想，但总是要面对现实的呀。 C. Ranom Numbers 只需要考虑每个字母的最左和最右出现的位置即可。 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061#include <iostream>#include <vector>#include <m ...

一些流水账 4.15 因为疫情的缘故，西一楼要封楼且断电，机房不让用了。还好可宝在仲英楼借了个教室，比赛的场地总算有了着落。晚上搬东西的时候，下着淅淅沥沥的小雨，梧桐东道上几乎没什么人，还算是挺有意境的吧。这时的心情蛮复杂的，除了有些激动和紧张，其实更多的是这个赛季结束后对未来的迷茫。 4.16 我们队打了最后一场训练赛，选的是ICPC上海#2019。结果还行，做出来五个题（在正式赛时这个成绩能拿个银吧，大概?）。记得D题是个树剖，我写了个250行的代码然后过了，特别高兴。不过作为签到题的K题我们三个人却始终没做出来，还挺搞的。 晚上打完昆明站的热身赛，就早早回去睡觉了，可是因为感冒喉咙不舒服，咋都睡不着 4.17 早上八点半我就到了比赛的教室，调整好设备后就坐在椅子上让自己静下来，看了一下昆明的队伍数量，整整700多支正式参赛队伍，拿牌的难度相较于之前的场次大了很多。这时候忽然发现自己特别的紧张。史耀睿来了之后，也说昨晚上他因为紧张没睡好。的确，作为这个赛季的最后一搏，这场比赛对我们而言实在是太重要了。 11点，比赛开始。我一上来就开了Ｂ，我感觉不太难，想好DP式子和判断涂满 ...

The 2021 ICPC Asia Nanjing Regional Contest E. Paimon Segment Tree tyy很快意识到额外维护一个前缀和即可求解，则现在只需要处理一个平方和即可。 但是看到需要维护平方和，naive的我以为线段树无法解决，再加上看到5e4的数据量，所以训练的时候想了个分块的做法。 可惜需要维护的变量太多，导致一直没有调出来，下来补题却最后一直在第23个点TLE 无奈查看题解，居然真的是线段树…其实使用矩阵乘法来维护，继而就可利用懒标记来优化了… 注意矩阵乘法的常数极大，又观察得知，矩阵中仅有6个参数是变量，所以可以极大的优化乘法运算的复杂度。 最后在cf上面使用64位测评机，刚好卡过去… 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293 ...

Diamond_Sea#Day5 E. Company 容易想到使用st表来维护区间的lca（注意实现的过程中，位运算的优先级） 我们发现如果是改变一个点就能使得lca的深度变大的话，那这个点去掉之后，剩余点的lca必须是原lca的后代节点废话 相当于，剩下的点在原lca的最多两个不同子节点的子树中，且其中有一个子树只含有一个在当前区间中的点，我们要删除的就是这个点。 这里采用了分治的方法，具体可参见实现过程 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132#in ...

D. Chemical table 最开始想了一个比较复杂的解法，调整了很久依然WA5。下来看题解才发现这个题目其实十分简单，把行和列看为点，然后输出联通块的数量减一即可。 证明如下： 首先，每一个二维平面上的点(r,c)(r,c)(r,c)都可以看成是点r和点c之间连的一条边。显然这是一个二分图。题意要求我们覆盖满所有的二维平面上的点，就相当于要让每一行和每一列之间都要互相连通。由于是二分图，所以我们要连接的点之间的边一定是奇数条。易知，对于任意一个连通块，其内部的行点和列点一定连通。 这里还是贴一下我的wa代码吧 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768// WA#include<bits/stdc++.h>using namespace std;typedef long long ll;typedef pair<int,int>pii;ty ...

D. Sonya and Matrix 超级恶心的一个构造题…在训练的时候被折磨了两个小时，完全想偏了 首先要明确的是，只要知道了数字零的位置和矩形的长宽后，可以O(n)O(n)O(n)判断是否合法。显然我们可以暴力在sqrt(n)sqrt(n)sqrt(n)的时间内枚举长和宽，然后可以发现，如果有一个数字出现的次数不是4∗i4*i4∗i，那么该数字一定是数字零的行或列坐标。再通过序列中最大数的值，即可求出行加宽的值（简单画个图就能看出来了，当然最直接的方法还是像题解那样老老实实列方程算） 剩下的难点就是计算每个数字的合法出现次数了，这里把矩形按照边分成了四段和四个顶点。每段单独考虑，这样会简单一点。 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879808182#include<bits/stdc++.h>using name ...

餐巾计划问题 将每天的早晚分开，分成两个点，然后建图 如果要让最大流等于每天用到的餐巾数量之和，那么一定要满足每天都要向汇点连一条容量为当天餐巾数量的边。 如何体现餐巾的重复利用呢？答案是从源点向每天晚上连容量为当天餐巾数量的边。 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103#include<bits/stdc++.h>using namespace std;typedef long long ll;const int MAXN=4e3+5;const int MAXM=2e4+5;const int INF=1e9;int N;int cp,dm,cf,dn,cs,lim[MAXN];int head[MAXN], c ...