- 博客(53)
- 收藏
- 关注
RSS订阅原创 csp2020-S T3 call
本来想趁着离职前的摸鱼时间刷题的。。。结果中途又是原神又是各种摸鱼x，结果一天居然只做了一题。按着luogu比赛的顺序刷的，没想到是个T3，感觉也太水了…T1大模拟不想写了。这题就是显然对于每个位置iii，函数jjj的作用就是kjai+bjk_j a_i + b_jkjai+bj。那先拓扑排序一遍搞出每个函数的作用，然后再dp一遍得到每个函数的调用次数就好了。最后的调用一堆函数也可以看成一个函数，于是就可以很方便的处理了。//// Created by bpm136 on 2020/11
2020-11-11 10:07:31
142
原创 构造以及乱搞以及atcoder专题
这里面的题都来自于atcoderhttps://vjudge.net/contest/345563#overviewagc039A题意：每次给出一个字符串T，是由字符串S重复k次构成的，每次可以修改一个字符成为另一个，问你最小的修改次数使得每两个相邻字符都不相同。其实只用O(len)O(len)O(len)扫一遍就好了，但是这里提供一个O(∣S∣2len+∣S∣4logk)O(|S|^2...
2019-11-29 14:57:37
343
原创 Educational Codeforces Round 77 5/6
A/* ***********************************************Author :BPM136Created Time :2019/11/27 21:55:08File Name :A.cpp************************************************ */ #include <bi...
2019-11-29 14:36:51
156
原创 Educational Codeforces Round 76 7/7
想了想，本来一直都是打打cf，但是没有任何记录，感觉还是记录一下cf的补题比较好A#include <iostream> using namespace std; int main() { int T; cin >> T; while (T--) { int n, x, a, b; cin >> n >> x >>...
2019-11-29 14:31:37
108
原创 2019-2020 ICPC, NERC, Southern and Volga Russian Regional Contest 11/14
A#include <iostream>#include <cstdio> using namespace std; int const N = 100005; int a[N], dfn[N];int mx[N], mi[N]; void update(int x) { mx[x] = max(mx[x], dfn[x]); mi[x] = mi...
2019-11-17 21:55:07
262
原创 2019-2020 Saint-Petersburg Open High School Programming Contest 8/11
A解个方程，就a=b+ca = b + ca=b+c和s−a=s−b=s−cs - a = s - b = s - cs−a=s−b=s−csss是最后做完操作的每个数，aaa是最小的那个数要补多少，然后接这个方程就行。#include <iostream>#include <algorithm> int main () { int a[3]; std::c...
2019-11-17 21:46:29
607
原创 ICPC 2019-2020 North-Western Russia Regional Contest 10/13
A#include <cstdio>#include <cstdint> int main () { int a, b, n; scanf("%d%d%d", &a, &b, &n); auto ans = 1 + 2 * ((n - b + b - a - 1) / (b - a)); printf("%d\...
2019-11-13 18:34:00
897
1
原创 ccpc2019 哈尔滨 8/12
A裸的差分约束，注意用前缀和作为点的时候给前缀和一点限制，以及就是，这题卡常x不过赛后补题我的一发过了x，队友的比赛时T飞了…#include <iostream>#include <cstdio>#include <cmath>#include <cstring>#include <algorithm>#include ...
2019-11-05 14:45:32
255
原创 后缀自动机专题
这个专题只是用来记录刷题的，不放代码了，而且以前刷过不少的都不会放上来。只记录从2019.10.31后的。[Poi2000]公共串给出几个串，问你他们的最长公共子串。SOLUTION：其实这题因为长度太小，所以SAM和广义SAM都随便做。SAM的话，取最小的串建SAM，然后用其他的串在上面跑，每次更新每个节点匹配的最长len，每次再对答案取min就行，这样的复杂度就是O(minlen∗n)...
2019-10-31 19:47:25
104
原创 Maratona de Programing da SBC 2019 11/13
Abfs#include <iostream>#include <cstdint>#include <queue>#include <vector> class Graph { int n; std::vector<std::vector<int>> es; public: Graph...
2019-10-21 12:30:37
451
原创 2016 湖南省赛 9/11
emmm也是有点没打好的场。其实题都会，但是没写完。A这题卡了我们挺久的。。。实际上直接对两边的数mod 2016按余数分类就行。但是我第一反应容斥x直接跑偏，不过容斥还是可以过的！#include <iostream>#include <algorithm>#include <vector>#include <cstdint>#i...
2019-10-19 10:37:46
94
原创 2016 湘潭邀请赛 9/10
这场就没有那么难受了。。。。A看了看标算，标算是直接把n mod 2016，我不知道为什么。。。。。不过直接map循环节也随便搞了。#include <iostream>#include <cstdio>#include <cmath>#include <map>#include <utility>#include &l...
2019-10-19 10:24:17
79
原创 2017 四川省赛 6/12
emmmm四川省赛的题这么难的嘛。。。。也不算难，就是做的很憋屈。。。。A坑人系列x注意数据范围#include <iostream>#include <cstdio>#include <cmath>#include <cstdlib>using namespace std;using ll = long long;void...
2019-10-19 09:54:28
128
原创 2019 沈阳网络赛 8/11
吐槽一下出题人英语还是要好好学一下，然后就是别题意全从问答拿，还有数据不知道什么鬼ABbfs就行，题意问答拿#include <iostream>#include <cstdlib>#include <cstdio>#include <cstring>#include <algorithm>#include <qu...
2019-09-16 13:39:21
98
原创 2019 上海网络赛 12/12
AB#include <iostream>#include <algorithm>#include <vector>#include <cstdio>int main () { // std::ios::sync_with_stdio(false); auto v = std::vector<int>(); int...
2019-09-16 11:26:18
195
原创 2019徐州网络赛 12/13
直到南昌的题都补完了才发现徐州的题我还没补（甚至blog都没写(((((((日哦比完出来拿出手机发现beginend他们10多分钟前就AK了（而我连题都没补xA生搬硬套傻逼题。显然就EXCRT求一下n，然后手推一下，发现，诶2 3 5都可以诶，4 6 7都不可以诶，再看看样例，8也可以诶。这tmd不就是斐波那契数列吗然后大力斐波那契就完事了。#include <iostream...
2019-09-11 15:44:25
160
原创 2019南昌网络赛 9/9
垃圾银川毁我青春害我生命。A最开始以为素数的间隔大约是logloglog级别的，所以里面至少有一个素数，结果就被WA飞了，实际上大力SAI来打表发现素数间隔最大能到200+，那就只能想办法减小这个间隔，实际上你选取一点小的素数，让你判定的集合不只是素数，还包括2p,3p,5p,7p,13p2p, 3p, 5p, 7p, 13p2p,3p,5p,7p,13p这些，那这样最小的间隔就减小到了999...
2019-09-09 17:08:06
117
原创 2019南京网络赛 8/9
日常拖更x不会概率DP死翘翘系列，容斥套容斥飞天系列，队友洗衣服不会倒着思考系列xA定位一下每个位置的数是多少，然后大力树状数组扫描线就好了#include <iostream>#include <cstdio>#include <cmath>#include <cstring>#include <cstdlib>#in...
2019-09-02 21:09:14
150
原创 51nod1237 最大公约数之和V3 杜教筛
首先肯定是求∑d=1nd∑i=1n∑j=1n[gcd(i,j)==d]\sum_{d = 1}^n d \sum_{i = 1}^n \sum_{j = 1}^n [gcd(i, j) == d]d=1∑ndi=1∑nj=1∑n[gcd(i,j)==d]直接莫反一下∑d=1nd∑i=1[nd]∑j=1[nd]∑T∣gcd(i,j)μ[T]\sum_{d = 1}^n d \sum...
2019-08-25 10:18:35
133
原创 51nod1220 约数之和 杜教筛
因为d(ij)=∑p∣i∑q∣i[(p,q)==1]pjqd(ij) = \sum_{p | i} \sum_{q | i} [(p, q) == 1] \frac{pj}{q}d(ij)=∑p∣i∑q∣i[(p,q)==1]qpj那么∑i=1n∑j=1nd(i∗j)\sum_{i = 1}^n \sum_{j = 1}^n d(i * j)i=1∑nj=1∑nd(i∗j)=∑...
2019-08-24 10:52:16
95
原创 2019ccpc网络赛 9/11
打的太菜了1551，05一眼直接反演了然后化成了不可做的形式哭了，04傻逼了5点整才搞出来，结果差了几s1001按位考虑，发现这就是A&BA \& BA&B，但是我们发现题目要求是正数，那么我们还需要把最低的一边是0一边是1的位改成1才行。#include <iostream>#include <cstdio>#includ...
2019-08-24 08:29:11
151
原创 2019 hdu多校第十场 7/11
ccpc网络赛也打残了，没有好好补题了x（我今天又好好的成为了一个辣鸡呢100110021003可以发现小于0.5以下的不断组合可以让数更大，但是大到某种程度的时候就不能再继续变大了，而且显然最开始就用比较大的去组合，答案也会比较大，所以可以直接贪心从最大的开始选，如果选能让答案变大就变大。话说cin无论关不关同步，读浮点数是真的慢，scanf就0.1s，cin就2s以上直接T飞#in...
2019-08-24 07:59:31
133
原创 2019 hdu多校 第九场 7/11
10011002因为切的顺序不受影响，所以我们可以先切上下再切左右，那么每次切左右的时候贡献的数量就是交点数量，那么我们直接二维偏序就行。#include <iostream>#include <cstdio>#include <cmath>#include <algorithm>#include <cstring>#in...
2019-08-22 23:18:59
113
原创 2019 牛客多校第十场 8/10
教书教完了，暑假过去了，不过赶上了牛客的最后一场多校。接下来的时间就是慢慢的补题辣。（* 还有网络赛补题）A比赛的时候想生成函数爆卷，然后每次处理贡献，然而事实说明这是一个排列问题不是一个组合问题（不过化为排列问题那怎么做呢？实际上就是对于任意一个排列，问从左往右加，第一次加爆AAA的位置，如果加爆的时候在(A,B](A, B](A,B]之间，那么就计入答案。那也就是生成函数中要多记录一...
2019-08-22 11:13:16
95
原创 bzoj3522 hotel 长链剖分
DP的状态设置的很厉害。设fi,jf_{i,j}fi,j为只考虑子树离iii距离为jjj的节点的数目。设gi,jg_{i,j}gi,j为有两个点距离他们的LCA的距离为ddd，并且他们的LCA离iii的距离为d−jd-jd−j那么转移就非常显然了。ans+=f[x][j]∗g[y][j+1]+g[x][j]∗f[y][j−1]ans +=f[x][j] * g[y][j + 1] +...
2019-08-22 10:54:51
165
原创 cf1009F Dominant Indices 长链剖分
终于入坑长链剖分了。以前只知道思想但是不会写代码。（因为有些细节没想明白，突然今早睡醒在梦中理解了x因为要O(1)O(1)O(1)继承重儿子的信息，我们可以使用主席树/指针/vector来实现。主席树的话就是直接把重儿子的链直接给就完事了。指针的话非常轻松，每次直接给这条链分配一块内存，每次重儿子移位就好了，轻儿子的内存重新分配。vector的话可能需要倒序，有点蛋疼，每次直接使用重儿子的...
2019-08-17 09:40:08
186
原创 bzoj4001 tjoi2015 概率论 卡特兰数
来大概推理一下卡特兰数的通项公式的证明（折线法不难，这里只写下生成函数版本）这里首先就是求i个点随机有根二叉树的个数，设为fif_ifi其实这个就是卡特兰数我们可以枚举一个儿子的大小那么就会有fi=∑i=0i−1fi∗fn−i−1f_i = \sum_{i = 0} ^ {i - 1} f_i * f_{n - i - 1}fi=∑i=0i−1fi∗fn−i−1那么就会有F(x...
2019-08-16 11:37:42
142
原创 cf960G Bandit Blues 倍增NTT第一类斯大林数
题意是问有多少种长度为n的排列，满足前缀最大值是他本身的数量为A，后缀最大值是它本身的数量为B如果你把每个前缀最大值和他后面的连续一段数放在一起，就相当于一个圆排列，每次断点都是这个最大值前面。从最大值处把左右分开。那么就相当于把长度n−1n - 1n−1为排列分成A+B−1A + B - 1A+B−1个圆排列的方案数。还要乘上一个(A+B−1A−1)\binom{A + B - 1}{A...
2019-08-15 11:07:44
195
1
原创 hdu6309 Absolute 容斥
既然是期望，可以化成积分形式，变成∫l1r1∫l2r2...∫lnrn∣x1+x2+x3+...+xn∣dx1dx2dx3...dxn\int_{l_1}^{r_1} \int_{l_2}^{r_2} ...\int_{l_n}^{r_n} | x_1 + x_2 + x_3 + ... + x_n|dx_1 dx_2 dx_3...dx_n∫l1r1∫l2r2...∫lnrn...
2019-08-14 22:15:47
281
原创 luogu2791 幼儿园篮球题 第二类斯大林数（特）卡常NTT
我真的是***的原本应该是乘以iLi^LiL但是因为iL=∑j=0L\{Lj\}(ij)j!i^L=\sum_{j = 0}^L {L \brace j} \binom{i}{j} j!iL=j=0∑L{jL}(ji)j!于是这题显然就是∑i=0ki(n−mki−i)(mi)∑j=0L\{Lj\}(ij)j!\sum_{i = 0}^{k_i} \binom{n - m}{k...
2019-08-14 15:06:11
204
原创 cf768G The Winds of Winter 主席树
为啥beginend要拉我做这题呢（因为他在cf找题的时候突然发现秋膘-67？？？？？？x（当众处刑然后我们就来大力刷了一下这题这题就是给你一棵树，对于每个点，每次删掉这个点，删除之后树变成了一个森林，然后我们可以做一次把这个森林里面的某棵树的某个子树与父亲分开，然后把这个子树接到森林里其他树上的操作，问操作完之后的（可以不操作）森林里面树大小的最大值最小是多少大概想想就是切开这个点，...
2019-08-13 09:31:17
153
原创 loj556 咱们去烧菜吧 polyExp+调和级数枚举
咋一看就是要算∏i=1n(1−xai(bi+1))∏i=1n(1−xai)\frac{\prod_{i=1}^n (1-x^{a_i(b_i+1)})}{\prod_{i=1}^n (1-x^{a_i})}∏i=1n(1−xai)∏i=1n(1−xai(bi+1))大力分治NTT？完蛋发现好像是O(nmlognlogm)O(nmlognlogm)O(nmlognlogm)的看到一堆...
2019-08-13 09:17:04
188
原创 cf891E Lust
非常有趣（考虑设bnb_nbn为第nnn个数被减去的次数，那么对于KKK次之后的某个局面，答案就是∏i=1nai−∏i=1n(ai−bi)\prod_{i=1}^n a_i - \prod_{i=1}^n (a_i-b_i)i=1∏nai−i=1∏n(ai−bi)的期望值实际上就是∏i=1nai−∑∑bi=kk!nk∏i=1nbi!∏i=1n(ai−bi)\prod_{...
2019-08-09 11:21:36
173
原创 2019杭电多校第六场 5/12
前言发现hdu的多校我怎么才写了1场的blog，咋回事啊。。。决定不贴代码了最近讲了很多课，还在学习生成函数等。。。可能一场比赛补题要比较后了先加在这里以后慢慢补吧（一定会补的！）10011002每次搜出LIS，然后删除不在当前LIS的直接不用理会，否则暴力重构100310041005转化为一个矩阵，找一个最大子矩阵的和最大。大力O(n2logn)O(n^2 logn)O(n...
2019-08-08 21:47:32
194
原创 LOJ2100 TJOI2015 线性代数
考虑把柿子展开，发现会变成∑i=1n∑j=1nAi∗Aj∗Bi,j−∑i=1nAi∗Ci\sum_{i=1}^n \sum_{j=1}^n A_i*A_j*B_{i,j}-\sum_{i=1}^n A_i*C_ii=1∑nj=1∑nAi∗Aj∗Bi,j−i=1∑nAi∗Ci那么也就是说，如果Ai,AjA_i, A_jAi,Aj同时为1，那么就会有Bi,jB_{i,j}B...
2019-08-07 08:47:54
117
原创 51nod 2543 构造最小公倍数
首先答案至少是Z/XZ/XZ/X，但是如果此时不互质，那么每次需要挪一个gcd到答案中（就是考虑标准分解式，每次把若干个不互质的质因数部分给b加上）。这样就是O(mlognlogn)O(mlognlogn)O(mlognlogn)的，因为是在其他的地方做到的，m被加到了1e61e61e6，但还是跑的飞快#include <bits/stdc++.h>using namespac...
2019-08-07 07:38:44
222
原创 LOJ6254 最优卡组 堆模拟搜索
想不出来设计的状态是啥，补题的时候偷看了CQZW的博客这里的状态是一个(val,x,y,z)(val, x,y,z)(val,x,y,z)表示当前的和为valvalval，并且已经固定选了前面xxx个，第xxx个已经选了第yyy个（对于每个卡包都从大到小排序），后面的卡包都是选第一张，此时是从zzz状态转移过来的那么转移有三种第一种是如果y<num[x]y < n...
2019-08-07 07:27:36
179
原创 2019牛客多校第六场 7/10
队友写了题，好评如潮A来自zkp同学#include<iostream>#include<map>using namespace std;int main(){ int n; string a,b; map<char,char>mp; cin>>n; for(int k=1;k<=n;k++...
2019-08-04 12:12:59
100
原创 2019ccpc女生赛 9/11
闲暇之余并没有好好补题而和小南瓜一起开了一场女生赛x然而自己菜死了，没看清I的题目，还分析错了E的复杂度，导致最后只有9题A/* ***********************************************Author :BPM136Created Time :2019/8/2 13:31:09File Name :A.cpp********...
2019-08-02 20:57:41
185
原创 2019 牛客多校第五场 7/10
第四场咕咕咕了，有空补A考虑构造的话就是把n看成一个字符串然后重复n次，考虑数位DP的话就爆搞就行，题解里面说求最小的话就记录一下这个状态的最小位数，以及当前位最小填的是什么，然后暴力往回搜就行/* ***********************************************Author :BPM136Created Time :2019/8/1 12:...
2019-08-02 13:28:01
244
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人