Xiaruize's Blog - Welcome to xiaruize's Blog!

hello-world

Sticky|Created2022-01-20|Updated2022-10-08

Hello World !!! NFLS 202108 一个蒟蒻膜你抄屏幕在深夜微微发亮思想在那虚树路径上彷徨平面的向量交错生长织成忧伤的网剪枝剪去我们的疯狂 SPFA告诉我前途在何方 01背包装下了忧伤笑颜洋溢脸庞键盘微凉鼠标微凉指尖流淌代码千行凸包周长直径多长一进考场全都忘光你在OJ上提交了千百遍却依然不能卡进那时限双手敲尽代码也敲尽岁月只有我一人写的题解凋零在OJ里面 tarjan陪伴强联通分量生成树完成后思路才闪光欧拉跑过的七桥古塘让你心驰神往队列进出图上的方向线段树区间修改求出总量可持久留下的迹象我们俯身欣赏数论算法图论算法高斯费马树上开花线性规划动态规划时间爆炸如何优化我在OI中辗转了千百天却不让我看AK最后一眼我用空间换回超限的时间随重新编译测完样例才发现漏洞满篇原来CE 是因选错语言其实爆0 只因忘写文件如果标算太难请坚定信念不如回头再看一眼题面以那暴力模拟向正解吊唁蒟蒻的蜕变神犇出现终将与Au擦肩屏幕在深夜微微发亮我心在考场

PKUSC2023 游记

PKUSC2023 游记

Created2023-05-08|Updated2023-05-08|游记|OI•游记•pkusc

PKUSC2023 游记 by xiaruize Day -1 早上提前从学校走人，成功水掉whk /tx 高铁座位又挤又硬，差评 Day 0 上午入营仪式感觉是招生讲座(讲招生又不招你/tuu) 属实又被机房的配置震撼到，这机器真的是给写代码用的？只能说，pku有钱任性食堂不错，冰激凌好评，价格极低下午 T1 字符串，求 kmp 后的那个 j ，每次改一个字符说实话，这题没学过 kmp 的都做出来了，学过 kmp 的应该都没做出来因为正解和 kmp 半毛钱关系都没有 /tuu T2 期望 nmsl 题想了3个档的分，实现3h，获得0个档的分，最后思路假了状压 dp 有一个档没打 qwq T3 树上dp + 背包dp 喜提12分总共获得 66 分的好成绩 Day 1 上午继续招生讲座讲了还是不招你qwq 下午 T1 建一棵树打个暴力，可以把随机的档冲过去 Subtask1 好像都是写的块状链表，只有我segment_tree 还 MLE 了。空间限制我cnmd Subtask2 写了一个 8×1078\times 10^78×107 的做 ...

abc293-f

Created2023-03-11|Updated2023-03-11|AtcoderAtcoder Beginner ContestABC293F - Zero or One|Atcoder•Atcoder Beginner Contest

ABC293 F - Zero or One 题意 TTT 组数据，每组一个正整数 nnn，保证 2≤n≤10182\leq n \leq 10^{18}2≤n≤1018 ，对于每个 nnn 求满足条件的 bbb 的个数，使得 nnn 的 bbb 进制表示只包含 000 或 111 思路官方题解给出了一种正经的做法，这里给出一种简单的数据分治做法对于每个数 nnn ，考虑将对答案的贡献分为以下三类: n−1n-1n−1 , nnn 显然这两种情况下的表示分别为 10, 11 位数 ≤3\leq 3≤3 位数为 222 时可以在 n\sqrt{n}n 的周围暴力枚举约 100010001000 个位数为 333 时同理在 n3\sqrt[3]{n}3n 周围暴力枚举枚举进制 bbb ，暴力检查时间复杂度：情况1: O(1)O(1)O(1) 情况2: O(1000∗log⁡n)O(1000*\log{n})O(1000∗logn) 情况3: O(n4)O(\sqrt[4]{n})O(4n) 显然不会超时警示后人不要用 pow !!!不要用 ...

Network-Flow

Created2023-03-05|Updated2023-03-05|CSP|Network-Flow•Knowledge

网络流 - 最大流概念如上图(a)中， sss 为源点 ttt 为汇点 s→as \rightarrow as→a 上的 333 为这条边的流量最大流为：假设从源点有足够的流量进入网络，最后能汇到汇点的最大流量 Ford-Fulkerson 再次观察这个图，容易想到一个感性的做法，即从 sss 开始 dfs，直到不能继续增加流量为止如上图为一种可行的方式但是，反复尝试发现，这个方式并不一定能找到最优解，因为每次 dfs 得到的路径并不一定为最优路径因此，需要在算法中支持撤销操作使用反向边来达成这一目标，即每次通过后建一条流量等于通过流量的反向边如图，即为选定 s→a→d→c→e→ts \rightarrow a \rightarrow d \rightarrow c \rightarrow e \rightarrow ts→a→d→c→e→t 这条路径后的残量网络(显然，流量=最小边权) 上图为该算法的完整流程 1234567891011121314151617181920212223242526272829303132int n, m, s, t ...

CF1775D

Created2023-01-10|Updated2023-01-10|Codeforces1775D. Friendly Spiders|Graph

D. Friendly Spiders By xiaruize p.s.严厉谴责出题人在题目页面放蜘蛛啊，很难受qwq 思路暴力建图显然需要 O(n2)O(n^2)O(n2) , 无法通过本题考虑是否可以优化, 发现同样的公因子可能被建多条边, 导致边数达到 n2n^2n2 级别如何解决这个问题? 可以对于每个公因子建一个点, 将所有有这个因子的数全部与这个点连边, 入边边权为 111 , 出边为 000 进一步优化, 可以发现, 只需要对质因子建点对于这张图跑 Dijkstra 即可 Code 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116/* ...

CF1775C

Created2023-01-10|Updated2023-01-10|Codeforces1775C. Interesting Sequence|math•bitmasks

C. Interesting Sequence By xiaruize 思路手模一下样例一 10=(1010)210 = (1010)_210=(1010)2 , 发现需要将 212^121 位的 111 去掉此时，就需要与一个 212^121 位为 000 的数, 同时其它位不能使 101010 改变, 且这个数 ≥10\geq 10≥10 那么, 这个数的最小值显然为 (1100)2=12(1100)_2=12(1100)2=12 总结上面的过程, 得到以下这些结论 n&x=xn \And x=xn&x=x , 否则是 -1 考虑 n−xn - xn−x 的值的二进制表示 (即 nnn 中需要改为 000 的二进制位的值), 发现所有的 111 必须是 nnn 中最低且连续的, 否则 -1 设 n−xn-xn−x 中最高位的 111 在 2k2^k2k 位上, 那么 2k+12^{k+1}2k+1 位在 nnn 中一定为 000 , 否则 -1 否则答案为 2k+1−n+x2^{k+1}-n+x2k+1−n+x samples n= ...

Loading the Database