这是一个比较常见的trick,但是我蓝桥杯cb省赛上面没写出来,所以在这边进行笔记 1蓝桥杯原题链接. 贪心的思考,我们肯定是对当前能提升的倍数最大的进行+b操作,但是数据范围这么大,我们得把系数变换一下,并且寻找一个阈值 如果对于位置已经进行了k次操作,那么接下来再操作一次的倍数贡献:(sum+b[i])/(sum)=1+b[i]/(a[i]+k*b[i]),发现对于后面那个数越大,优先级越高,所以后面那个数的倒数越小,优先级越高,倒数为a[i]/b[i]+k,这就是我们寻找的优先级系数,因为这个优先级系数是每次操作+1,所以我们一定能找到一个整数阈值,使得当每个数到操作到>=阈值后,...

A.2026 %4讨论即可,每4位有2个2,202620262026%4为剩下的单独计算 B：子序列 钦定当前遍历到j cnt1[i]记录j以前,%6==i的当前下标个数 cnt2[i]记录j以前,%6==i的当前下标两两组合个数 所以cnt2[(6-a[j])%6]即为以当前下标的合法子序列个数 注意是先更新ans再更新cnt2[i]和cnt1[i] 时间复杂度:O(n) #include<bits/stdc++.h> using namespace std; #define int long long const int mod=1e9+7; const int N=5e6+1...

如题,有些状态很容易描述,状态较多,且转移起来较为容易,但不好用dp表述的题目,只要状态数<=1e6,甚至<=1e7,且转移(边)数<=1e6甚至<=1e7,我们就直接最短路做 1.调色题Ⅱ 链接 赛时这题我使用了很奇怪的写法状压,写的很烦,但赛后看题解才发现可以最短路 我们记录a[i]可以到达的所有值域的最短路,如果能访问到的话cnt[值域]++,之后,若cnt[值域]==n,我们就可以利用dis sum[值域]来更新答案了 2.2026杭电春季联赛1.力的平衡  这里有一个引理: 二维 Steinitz 引理给出： 若一组二维向量的和为 0，且每个向量都落在关于原点...

有些题目,我们需要判断一个区间某个元素出现的次数奇偶,如果元素的种类不多,我们可以使用异或哈希 1.炼金术士的配方(杭电2026春季联赛1)  你可以发现,a[i]<=1e6,质数的种类很少,所以我们可以给每一个质数随机分配一个不同的哈希值,如果区间异或值是0,那么这个区间合法 异或值生成代码: mt19937_64 rnd(98275314); int gen(){ int x=0; while(x==0) x=rnd(); return x; }  本题代码 #include<bits/stdc++.h> using namespace std; #define ull ...

有一种题型,是对于一个下标的值作为max/min时,对雨某种满足题目要求性质的子段的计数,而我们知道,值满足堆的性质,下标满足二叉线索树的性质,就是笛卡尔树,处理一个区间,我们只要遍历左右里面长度小的区间,再通过预处理的东西算出结论(可能是预处理,可能是二分) 例1.Max to the Right of Min 链接 由题意我们产生了一种思路,钦定区间的最小值进行统计,如果原题不是排列,只要钦定a[idx]是区间的最小值并且左侧只能包括<a[i]的才行. 我们dfs遍历笛卡尔树,遍历左右侧长度更小的区间就行,并使用pre和suf来记录对于一个下标而言,左侧第一个比自己大的值和右侧第一个...

前言:我们再做一些最短路题目时候,往往会因为一些特殊限制导致建的边太多,所以我们建立一种虚拟点作为中转站,大大减少边数 1.HDU春季联赛10.小塔的梦境迷宫 题面:  对于走的边数为%3=0,%3=1,%3=2的情况,可以直接拆点,但是如果对于"瞬移"这种情况要建图,那最坏情况将会多见nn条边,所以我们建立不同属性的虚拟点,这样只会多建立2n条边.一个点进入对应属性的虚拟点需要cost 1的dis和x的金币,出来需要cost 0的dis和0的金币,这样就完成了题目 #include<bits/stdc++.h> using namespace std; #define ull u...

A.2026(个人难度评价:洛谷红) 枚举模拟即可,如果数据范围较大可以使用数位dp #include<bits/stdc++.h> using namespace std; #define ull unsigned long long #define int long long #define i128 __int128 #define pii pair<int,int> #define tp tuple<int,int,int> #define db double const db INF=1e18; const db pi=acos(-1); cons...