Antimonysbguy的博客

原创 About Antimony

大家好呀我又回来了！！！高考炸了，现在冲电子神(科)技大学的珠峰计划AFO后路线偏移了一点点，想过走强基学物理学，但高考裂开还有个人兴趣等等还是让我决定学计算机总之就是回来啦，重操旧业第一次是这样写我自己的：兴趣挺多OI音乐法语科幻（还有其他好多好多。。。学长又帅又强头发浓密的dzyo哥哥(我菜我认不到那么多人)同学们fsyo金钩钩冯巨giaohr傻鸡sjyyrZnCuNDMZ_verjungigo_64(高考697巨神)联系方式：Q 3268044712博客园...

原创 [DP] ABC262 D - I Hate Non-integer Number

atcoder ABC262 D题题解

原创 [数学] CF JULY222D Maximize Difference

CF JULY222D Maximize Difference

原创 [复习] 暑假打板

antimony的算法板子库

原创 精灵

结论题好是好，就是有点恶心心你知道结论就会，不会就很不一定做对但是学起来飞快，因为它是结论嘛????题意nnn个数对于每个数xxx有操作：将二进制下第iii位异或1代价f(x,i)=(max⁡(x,x⊕2i))2i mod 19260817+1{f(x,i)=(\max(x,x\oplus 2^i))^{2^i}\bmod 19260817+1}f(x,i)=(max(x,x⊕2i))2imod19260817+1定义a(x,y)a(x,y)a(x,y)位将xxx转化为yyy的总代价求m

原创 [Hall定理] 奖章

题意nnn个人上工，第iii个人连续工作aia_iai​天，休息aia_iai​天每天可以给一个上工的人发奖章，求给每个人发kkk个奖章需要的最少天数正解大家看到这道题第一反应就去LCM了结果这道题二分图qwq复制kkk份工人，每个点与所有能上工的天匹配如果有完美匹配，则这个天数合法显然这个天数可以二分想到Hall定理一句废话二分图存在最大完备匹配的充要条件是某一侧任意kkk个点与另一侧相连的点数≥k\ge k≥k对于每一天，预处理出它连向的人，发现nnn很小，可以状压二分有上界3n

原创 [最大生成树][LCA] 货车运输

还是纪念一下傻逼题Port key题意A 国有 nn 座城市，编号从 11 到 nn，城市之间有 mm 条双向道路。每一条道路对车辆都有重量限制，简称限重。现在有 qq 辆货车在运输货物， 司机们想知道每辆车在不超过车辆限重的情况下，最多能运多重的货物。正解显然走的边在最大生成树上然后感觉是换根DP但是min⁡\minmin抠不掉lcalcalca到根换个思路：直接求lcalcalca，在求LCALCALCA的时候取min⁡\minmin取min⁡\minmin的时候顺序写反了????

原创 [期概DP] 换教室

Port key题意至多换课mmm次从教室cic_ici​换到did_idi​，换课成功概率为pip_ipi​，最小化∑idisc/di→c/di+1\sum_idis_{c/d_i\to c/d_i+1}∑i​disc/di​→c/di​+1​的期望正解图很小，Floyd预处理disdisdis考虑如何求期望：期概DP设状态f[i,j,0/1]f[i,j,0/1]f[i,j,0/1]为第iii节课，使用了jjj次换课机会，这一节课有没有换课 的期望考虑转移：就是很有条理地分类讨论f[

原创 [大模拟] 计算表达式的值

题意给出计算表达式，包含数字、运算（+−×÷ab+-\times\div a^b+−×÷ab）与括号，求值正解大模拟计算表达式→\to→栈对于括号，遇到左括号，开始进栈；遇到右括号，计算栈中的值，此时保证了从栈顶到栈底（左括号处）运算符优先级递减对于运算符，对比其与堆顶运算符优先级，大于等于则入栈，小于则计算50 pts 求debug#include<bits/stdc++.h>using namespace std;#define in Read()int in{ in

原创 [二分图][贪心模拟] 立体几何

哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈假算法90分哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈题意一个由小正方体组成的几何体，给出俯视图，在每个格子上标出小正方体的个数要求一种方案，去掉或移动一些小正方体而三视图不变求最多去掉的小正方体数题解90pts有贪心：尽量使“木桶上最长的那块板子”处在交叉的位置即对于一个高度hhh在正视图和侧视图中均是该行/列中最高的高度，则尽量让它处在这一行与这一列的交叉点上发现有两种情况列中有这个高度，而行中没有（反之亦然）：让它被比它更高的高度在行（列

原创 [队列][数位DP] NOIP数

CSDN实在是太恶心了今天考试T1就不会了，考场上打了个表就走了题意定义一种数，每对相邻的数字相差不超过1求第iii个这种数正解法一队列每个数至多可以生成三个数：在最后一位后数字入队iii次即为所求#include<bits/stdc++.h>using namespace std;#define in Read()#define int long longint in{ int i=0,f=1;char ch=0; while (!isdigit(ch) &am

原创 [2-SAT][线段树优化建图] AT2336 Flags

Port key题意一些旗子，在数轴上有两个可以放置的位置，最大化两个旗子之间的最小距离正解二选一，考虑2-SAT考虑O(n2)O(n^2)O(n2)连边的优化：线段树优化建图优化至O(nlog⁡n)O(n\log n)O(nlogn)二分答案对于每一个长度lll，对于每一个点，位置记为ppp，在[p−l,p+l][p-l,p+l][p−l,p+l]中不能有其他的点线段树建图，然后跑2-SAT判是否有解即可#include<bits/stdc++.h>using namesp

原创 [2-SAT] 学习笔记

原创 [最短路] Milk Pumping G

Port key我是真的没想到这题能最短路全往费用流上想去了还是学得太少这题其实一看就不是费用流费用流要求在最大流前提下的最小费用而这道题不一定能够最大流题意一个图，每条边有限制fff和代价ccc，maximize(min⁡i{fi}∑ci)maximize(\frac{\min_i\{f_i\}}{\sum c_i})maximize(∑ci​mini​{fi​}​)题解将ccc视为边权，求最短路考虑fff的影响发现可以枚举fff，因为它小 (随便欺负人家小是不对的????)O(

原创 [Tarjan LCA] Milk Visits G

奇奇怪怪的算法，这道题竟然可以用tarjan lca做以前的主席树+树剖发现对于路径u↔vu\leftrightarrow vu↔v，要求颜色为ccc如果路径中不包含某个颜色，那么这个颜色可能存在于1↔lca1\leftrightarrow lca1↔lca中想到记录颜色最深位置pcp_cpc​，发现有性质：1↔n1\leftrightarrow n1↔n的pcp_cpc​如果等于1↔m1\leftrightarrow m1↔m的，那么ccc一定不存在于路径n↔mn\leftrightarrow

原创 [校内模拟][并查集][主席树+树剖] Milk Visits 两题

T1 SPortkey以前的题解两种牛，并查集维护连通块起点终点在两个连通块之间则一定合法，因为两种牛都能出现（否则起点终点在同一个连通块种）在同一个连通块中，考虑这个连通块的颜色即可#include<bits/stdc++.h>using namespace std;#define in Read()int in{ int i=0,f=1;char ch=0; while (!isdigit(ch) && ch!='-') ch=getchar(); i

原创 [校内模拟][区间DP] 纸牌Cards

恶心回来NOIP第一道题正解想到了，但是脑子抽了乱分析有优秀的O(n3)O(n^3)O(n3)，规规整整的区间DP，非要写递归记搜题意给出序列，对于一个子区间，如果区间头尾元素相等，则可以消掉这个区间，对答案贡献为头元素的值，最大化答案正解区间DP，记[l,r][l,r][l,r]的答案为fl,rf_{l,r}fl,r​两个操作：合并：fl,r=max⁡l≤k<r{fl,k+fk+1,r}f_{l,r}=\max_{l\le k<r}\{f_{l,k}+f_{k+1,r}\}

原创 [游记] CSP2020游记

谁能想到蒟蒻的第一篇游记竟然就成了最后一篇呢Day0一想到就要离开可爱的数据结构和机房，心里不免有一些小失落呢然后开始颓qwq

原创 [线代] 矩阵求逆

#include<bits/stdc++.h>using namespace std;#define in Read()int in{ int i=0,f=1;char ch=0; while (!isdigit(ch) && ch!='-') ch=getchar(); if(ch=='-') ch=getchar(),f=-1; while (isdigit(ch)) i=(i<<1)+(i<<3)+ch-48, ch=getcha.

原创 [树形DP] 树形DP四例

是时候练一下DP了！我的题单文章目录T1 “访问”美术馆T6 最大子树和T7 [CTSC1997]选课T1 “访问”美术馆Portkey又是一道非常规读入题。。。记fi,jf_{i,j}fi,j​为在iii节点，偷jjj幅画所需最少的时间fi,j=min⁡{flchi,k+frchi,j−k}f_{i,j}=\min\{ f_{lch_i,k}+f_{rch_i,j-k} \}fi,j​=min{flchi​,k​+frchi​,j−k​}T6 最大子树和Portkey菜题#inc

原创 [校内模拟] 201103 NOIP T4

题意求a,b,c∈[l,r],a<b<c,a∣b,b∣ca,b,c\in[l,r],a< b< c,a|b,b|ca,b,c∈[l,r],a<b<c,a∣b,b∣c的三元组(a,b,c)(a,b,c)(a,b,c)个数正解先假设a≤b≤ca\le b\le ca≤b≤c枚举aaa，设b′=ba,c′=cab'=\frac{b}{a},c'=\frac{c}{a}b′=ab​,c′=ac​，则要求b′,c′≤⌊ra⌋b',c'\le \lfloor\frac{r}{

原创 [数论] 线筛求约数个数

线筛求约数个数对于一个数x=∏i=1npiaix=\prod_{i=1}^np_i^{a_i}x=∏i=1n​piai​​其约数个数d(x)=∏i=1n(ai+1)d(x)=\prod_{i=1}^n(a_i+1)d(x)=∏i=1n​(ai​+1)线筛时记录除掉最小质因数后的数rrr，最小质因数的个数cccint cnt,p[N];int d[N],r[N],c[N];bool v[N];void sieve(int n){ d[1]=1; for(int i=2;i<=n;++

原创 [斜率优化] 斜率优化学习笔记

如：板快乐推柿子记fi,jf_{i,j}fi,j​为iii个任务，jjj批完成的最小花费有边界：f0,0=0f_{0,0}=0f0,0​=0，初值赋∞\infin∞有转移：（t,ct,ct,c均为前缀和）fi,j=min⁡0≤k≤i{fk,j+(s×j+ti)×(ci−ck)}f_{i,j}=\min_{0\le k\le i} \{f_{k,j}+(s\times j+t_i)\times(c_i-c_k) \}fi,j​=0≤k≤imin​{fk,j​+(s×j+ti​)×(ci​−ck​

原创 [组合数学] 201102 NOIP T4

题意网格，只能向右或向下走有障碍点，每次经过体力值s→⌈s2⌉s\to \lceil\frac{s}{2}\rceils→⌈2s​⌉从左上角开始，求到右下角的期望体力值（ mod 1e7\bmod1e7mod1e7意义下）正解快乐推柿子不想打代码对于这种单减的递推式（如ai+1=ai,bi+1=log⁡2bia_{i+1}=\sqrt{a_i},b_{i+1}=\log_2b_iai+1​=ai​​,bi+1​=log2​bi​）最终总是会到达一个不变的值0/1这道题最后会到达1因此经过j

原创 [Boruvka] 201103 NOIP T2 Graph

题意给出完全图，两点间边权wu→v=au+av+p∣u−v∣w_{u\to v}=a_u+a_v+p|u-v|wu→v​=au​+av​+p∣u−v∣求最小生成树大小60ptsprim暴搞不要装x写static#define FILE(x) freopen(x".in","r",stdin);freopen(x".out","w",stdout);#include<bits/stdc++.h>using namespace std;#define in Read()#defi

原创 [校内模拟][并查集][线段树] 201031 NOIP T4 Interval

题意两区间满足l1<l2<r1l_1< l_2<r_1l1​<l2​<r1​或l1<r2<r1l_1<r_2<r_1l1​<r2​<r1​则可以互相到达操作：加入区间，询问区间是否可以互相到达正解并查集维护连通性线段树维护条件信息离散化后可以暴力移动区间端点查就完了线段树写法有点奇怪其实就是用vector来update有点奇怪，只有90pts#include<bits/stdc++.h>using n

原创 [校内模拟][Kruscal重构树][线段树合并] 201031 NOIP T3 Garden

题意一张图，点有颜色，边有边权，查询从一个点开始，每次经过边权不大于某值的边，求经过的颜色种经过次数最多且最小的30pts暴力这种值最多且最小的问题，最近写线段树合并写多了就看着很熟但是我不会kruscal重构树，就只写了O(n2)O(n^2)O(n2)的丑陋代码30pts#define FILE(x) freopen(x".in","r",stdin);freopen(x".out","w",stdout);#include<bits/stdc++.h>using namesp

原创 [校内模拟][树形DP] 201031 NOIP T1 BST

题意已知一个二叉搜索树，求依次插入而形成这颗树的序列数量正解建树，手玩发现答案与子树大小有关，可以DP记答案（以uuu为根的子树的序列数）为fuf_ufu​手玩发现答案与子树大小有关考虑转移发现两子树合并其实就是子树的序列合并，两棵子树的序列不能变子树的序列有fsf_sfs​种，子树的序列合起来要填到sizu−1siz_u-1sizu​−1个空位上（−1-1−1是因为根节点一定在第一个）考虑左子树，应该选sizssiz_ssizs​个位置放，组合数所以转移：fu=flchfrch(si

原创 [线段树合并] 线段树合并：从入门到精通 之 刷题

文章目录入门T1 [USACO17JAN]Promotion Counting PT2 Lomsat gelral入门My BlogT1 [USACO17JAN]Promotion Counting PPortkey尴尬第一，忘记空间：动态开点*20第二，数组是从小到大拍的，也就是1小于n，而答案要统计大于p[u]的数量#include<bits/stdc++.h>using namespace std;#define in Read()int in{ int i=0,f

原创 [Debug]C++ cout/cerr

好东西！更深入的用法我就不做探究了，但是下面这个用法感觉挺强大的使用freopencout输入到文件里cerr输入到标准输出里signed main(){ freopen("1.out","w",stdout); for(int i=1;i<=100;++i){ if(i&1) cout<<i<<endl; else cerr<<i<<endl; }}...

原创 [校内模拟][最大生成树] 201030 NOIP T1

TA题意kkk轮操作，每次删除尽量多的边删除，若有多种方案，选择边权和最大的，要求删除边中不存在环正解考场上不敢往这方面想????一眼一个最大生成树边权和最大和边尽量多是平行条件，互不影响有点可持久化的感觉，但是不是考虑分层并查集，层为kkk再一层中一条边被删掉了，更高层中两端点一定不会相连每次找到最后一个相连的层，在更高一层中相连，这一条边就会在这一层中被删除（语文不好qwq，这个层就是这么个东西大家自行体会吧）#include<bits/stdc++.h>using

原创 [校内模拟][思维题/全逻辑] 201030 NOIP T2

TB题意n×nn\times nn×n的黑白棋盘，可以将一行的颜色全部刷到一列上，问将整个棋盘变黑的最少操作次数正解被绕晕了​????​考虑白色ccc记录有白色的列数，注意到如果一行不全黑这个值不会变（显然）如果有一行变为全黑，那么再花费ccc代价即可将整张图变黑于是考虑将一行变黑的最快办法如果第rrr列有一个黑格，则通过一堆操作可以使第rrr行变为黑色，这个操作次数为rrr行白色个数那么求出每行最小的白格个数#include<bits/stdc++.h>using na

原创 [线段树合并] 线段树合并：从入门到精通 之 入门

文章目录基操T1 板/[Vani有约会]雨天的尾巴 /【模板】线段树合并基操T1 板/[Vani有约会]雨天的尾巴 /【模板】线段树合并Portkey多次给树上路径上的点加一个数，求每个节点上加得最多的数差分，然后加回来普通差分：维护一个值即可现在：合并一个数组，使用线段树合并自己查出来70行少打了一个+=✌️就很板#include<bits/stdc++.h>using namespace std;#define in Read()int in{ int i=0,

原创 [莫队] 莫队七例

文章目录基本思想T1 小Z的袜子T2 小B的询问T3 Gty的二逼妹子序列T4 [AHOI2013]作业T5 [HNOI2016]序列题意题解T6 曼哈顿交易基本思想离线暴力区间左端点分块T1 小Z的袜子portkeyprintf("%lld/%lld\n",q[i].A/d,q[i].B/d);把斜杠杠打反就很淦#include<bits/stdc++.h>using namespace std;#define in Read()#define int long long

原创 [分块] 上帝造题的七分钟2 / 花神游历各国

上帝造题的七分钟2 / 花神游历各国Portkey区间开方（见Block5）毒瘤题，竟然输入数据会出现l>rl>rl>r#include<bits/stdc++.h>using namespace std;#define in Read()#define int long longint in{ int i=0,f=1;char ch=0; while(!isdigit(ch)&&ch!='-') ch=getchar(); if(ch==

原创 [二维树状数组][二维差分] 上帝造题的七分钟

就很优秀上帝造题的七分钟二维树状数组板题差分→\to→树状数组二维差分→\to→二维树状数组题意二维数组，区块修改，区块查询类比于一维数组区间修改区间查询题解一维差分数组于前缀和的转化关系：sn=∑i=1nai=∑i=1n∑j=1idj=∑i=1n(n−i+1)dis_n=\sum_{i=1}^na_i=\sum_{i=1}^n\sum_{j=1}^id_j=\sum_{i=1}^n(n-i+1)d_isn​=i=1∑n​ai​=i=1∑n​j=1∑i​dj​=i=1∑n​(n−i+

原创 [分块] 双倍经验/蒲公英

蒲公英求最小众数蒲公英掉紫了????黑色经验-1n≤4e4,ai≤1e9n\le 4e4,a_i\le 1e9n≤4e4,ai​≤1e9，离散化竟然不带修，多美好的世界预处理si,js_{i,j}si,j​表示第iii块中jjj的出现次数pi,jp_{i,j}pi,j​表示第iii块到第jjj块的众数那么[l,r][l,r][l,r]的众数为整块众数和散装中数的并集，统计这些数个数即可用桶统计，pot[i]≤2n+1pot[i]\le 2\sqrt n+1pot[i]≤2n​+1整块类

原创 [校内模拟][最短路] k长最短简单路 201028 NOIP/暴力打得比标程好

T3 C题意给出无向图，nnn点mmm边，求从111到nnn经过kkk条边的简单最短路简单最短路定义为无重边，无重点路径min⁡(n,m,k)≤5\min(n,m,k)\le 5min(n,m,k)≤5暴力比较优秀的79pts暴力#include<bits/stdc++.h>using namespace std;#define in Read()int Read(){ int i=0,f=1;char ch=0; while(!isdigit(ch)&&

原创 [思维题][校内模拟] 201028 NOIP T1

T1 A题意给出一些棋子的位置，对于每一个棋子，可以左移一格或两格，前提是目标位置上无棋子移出棋盘（即坐标≤0\le 0≤0）则记为挂掉，问挂掉的顺序有多少种正解观察发现有如下的情况，棋子挂掉的顺序是任意的[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-2m2WJ5X3-1603874684272)(C:\Users\am\AppData\Roaming\Typora\typora-user-images\image-20201028162744488.png)]

原创 [校内模拟][转图论] 201028 NOIP B题

T2 B题意有一个由a,b,c,d,ea,b,c,d,ea,b,c,d,e个1,0,1,0,11,0,1,0,11,0,1,0,1依次拼接而成的0/1串给出一些区间，一个操作可以将一个区间取反，且花费为区间长度求使原串变为全111串的最小花费，如果不存在方案，输出−1-1−1正解考场上想到正解，没有用奇奇怪怪的方法但是没有打long long????注意到每个区间最多使用一次（使用偶数次不变）然后区间相减（叠加）的操作就感觉和图论特别相似[外链图片转存失败,源站可能有防盗链机制,建议将图