- 博客(501)
- 收藏
- 关注
RSS订阅
原创 一句话题解
由于有些题是在是不想写就开个坑吧(老年选手的悲哀「MtOI2019」埋骨于弘川题目链接Solution显然所有f(n,k)都是2^x，不如取对数变成加法那么我们有f(n,0)=∑i=142f(n−i,0)∗if(n,0)=\sum_{i=1}^{42}f(n-i,0)*if(n,0)=∑i=142f(n−i,0)∗i，这是一个线性递推并且f(n,k)=f(n−1,k)+f(n,k−1...
2019-09-02 20:25:57
490
原创 一直更新中
各种神奇的东西，包括一些板子，犯错集合，计划写的题目，做的事情。一些板子由于比较懒就直接写在这里了 1.自然数幂和 伯努利数： Ans=1k+1∑i=1k+1Cik+1Bk+1−i(n+1)iAns=1k+1∑i=1k+1Ck+1iBk+1−i(n+1)iAns={1\over {k+1}}\sum_{i=1}^{k+1}C_{k+1}^{i}B_{k+1-i}(n+1)^i ...
2016-03-23 21:46:59
1338
原创 北大集训总结
前言请问我是直接退役还是走形式呢Day 0早上的高铁中午到来之前北京下雪了但是我们到的时候已经停了(什么时候能够真正看一次下雪呢本来以为很快就能住下，结果被前台鸽了一万年点的外卖没地方吃只能去开幕式吃QwQ结果说好1h的开幕式15min就结束了(饭都没吃完试机给了三道看上去能做的题，口胡了做法写个暴力就跑了听说都是去年的题，B似乎有线性做法出题人被爆了。。。在北大饭堂吃饭，发现...
2019-12-17 22:00:09
1633
原创 CSP-S 2019摸鱼记
摸鱼一时爽，一直摸鱼一直爽Day 0Q:CSP和NOIP是什么关系A:没关系不管怎样我这个高三老咸鱼就是去打酱油的酒店好评，但卫生间的玻璃emmmm一言难尽还有WiFi极差，还好我有流量下了一晚上棋Day 1又是在二中，令人怀念呢没什么负担随便打打A是个一眼题B是个一眼题C不是个一眼题然后花了半个钟把A和B写完了，期间发现了A会爆ll要用ull剩2.5h搞C我就不信搞...
2019-11-20 15:21:11
1188
原创 [AGC020F]Arcs on a Circle
Description用n个长度为L[i]的圆弧随机覆盖长度为c的圆环，问圆环被完全覆盖的概率n<=6,c<=50Solution我还以为是一道niubi积分题_(:з」∠)_考虑把圆环在L最大的圆弧的左端点处断开，我们可以把环上的问题变成链上的问题然后，每个圆弧的左端点X[i]=P[i]+R[i]，其中P[i]∈[0,C),R[i]∈(0,1)P[i]\in[0,C),R...
2019-11-06 22:01:03
808
原创 [AGC022F]Checkers
Description令x=10100x=10^{100}x=10100，数轴上有n个点，第i个点的坐标为xix^ixi进行n-1次操作，第i次操作选择两个点A和B，将A变为A关于B的对称点，然后删去B最后会剩下1一个数，问这个数有多少种可能的取值n<=50Solution由于x很大，我们可以只考虑每个数的贡献容易知道每个数的贡献形式为±2^k如果我们选择A和B，就从B向A连...
2019-11-06 15:44:42
843
1
原创 [AGC030E]Less than 3
Description给出两个长度为n的01串s和t你进行若干次操作，每次操作可以更改s中某一个位置上的值，每次操作前后需要保证s中不存在相邻3个一样的字符现在问把s变为t所需要的最小操作次数n<=5000Solutionniubi题我们在0->1之间画一条红线，在1->0之间画一条蓝线默认字符串开头结尾有无限多的红蓝线，我们可以发现两个字符串相等等价于这两个字符...
2019-11-01 11:14:02
526
原创 [CF526G]Spiders Evil Plan
Description给出一棵n个点的树，边有边权q次询问每次询问给出点x和y，问选y条路径，满足这y条路径的并是一个连通块S，S包含x，且S内的边权和尽量大输出最大的边权和强制在线n,q<=10^5Solution先考虑一次询问我们可以以x为根，然后选2y个叶子到根的路径最长容易发现直径的某个端点一定被选，我们可以以某个直径端点为根建树不考虑包含x，问题变成选2y-1个...
2019-10-29 21:32:40
312
原创 [AGC027E]ABBreviate
Description给出一个字符串s，每次操作可以选择子串aa变为b，也可以选择子串bb变为a问能得到的本质不同的字符串数量|s|<=10^5Solutionxjb编了7788还是去看题解了_(:з」∠)_首先，一个字符串能变成一个字符a或b，需要存在一步可行操作，即不为ababa…然后，一个字符串能变成a还是变成b，可以用(cnta+2*cntb)%3计算，若为0则不能变成...
2019-10-26 16:19:42
497
原创 [CF578F]Mirror Box
Description有一个n*m的网格，每个格子是一个斜45°摆放的镜子现在有一些格子上的镜子不见了，你需要求出有多少种摆放镜子的方法，满足：1：从网格某一个边缘的中点射进来的光线会从这条边的一个临边射出2：网格图中每一条网格线都存在1中的一条光线，满足这条光线经过这个网格线n,m<=100，保证空格子的数量<=200Solution考虑把所有格点黑白染色，我们可以发现...
2019-10-26 15:27:55
1013
原创 [AGC032F]One Third
Description一个长度为1的环，随机角度切n刀，对于每一块长度为x的，取最接近1/3的，即|x-1/3|最小的那一块问这个最小值的期望n<=10^6Solution感觉还是有一些不明觉厉首先，对于一次在x的划分，在x画红线，在x+π/3画蓝线，在x-π/3画绿线，问题变成任意两条异色线之间的夹角的最小值由于所有线是对称?的所以可以只看某一段也就是说，令第一次划分的x为...
2019-10-24 10:25:37
283
原创 [CF506E]Mr. Kitayuta's Gift
Description给出一个字符串s，你需要往其中插入n个小写字符得到字符串t，使得t是一个回文串问所有能得到的本质不同的t的个数|s|<=200,n<=10^9Solution先考虑最暴力的做法，我们设F[l][r][k]表示当前s[l…r]还没有被匹配，从外往里做到第k层转移直接考虑第k+1层选什么字符，视情况可以转移到F[l+1][r-1][k+1],F[l+1][...
2019-10-22 14:42:37
342
原创 [CF506C]Mr. Kitayuta vs. Bamboos
Description有n个竹子，第i个竹子长度为h[i]，每天的结束会长高a[i]现在有m天，每一天可以做k次操作，每次操作可以选择一个竹子砍掉p，即高度h[i]=max(h[i]-p,0)你需要最小化m天结束后最高的竹子的高度n<=100000,m<=5000,k<=10Solution先考虑二分答案ans，然后有两种做法：Solution 1：考虑每个竹子，...
2019-10-21 21:10:56
517
原创 百度之星2019决赛旅游记
前言白嫖百度真开心Day 0坐前一天晚上的高铁到了北京成功成为最早到的选手然后就一直颓在酒店里下来拿午饭外卖的时候发现还有报道这个操作(来的比报道还早_(:з」∠)_晚上坐了大半个小时的车来到了不远处的酒店(北京真的堵晚宴emmmm作为南方人表示太辣了(加大力度去试机发现这电脑里面怎么什么都没有花了一万年下好了Dev-cpp，写了个NTT测速，溜了溜了Day 1比赛日题目...
2019-10-17 16:44:05
589
原创 [Atcoder Grand Contest 038]简要题解？
前言放弃了AGC去打Comet OJ回过头来发现这场怎么这么zz啊亏了亏了题目链接01 Matrix这样构造(灵魂画师谢罪了)Code#include <cstdio>#include <cstring>#include <algorithm>#define fo(i,a,b) for(int i=a;i<=b;i++)#defi...
2019-09-23 21:51:40
750
原创 [Comet OJ - Contest #11]简要题解？
前言md又是rk4_(:з」∠)_可惜了要是ilnil过了E我们机房就可以加一个冰箱了题目链接eon模拟Code#include <cstdio>#include <cstring>#include <algorithm>#define fo(i,a,b) for(int i=a;i<=b;i++)#define fd(i,a,b) ...
2019-09-23 10:05:18
278
原创 [The Preliminary Contest for ICPC Asia Shanghai 2019]简要题解？
前言大概是第一场AK的ACM比赛？我太菜了，队友太强了.jpg先把自己负责的题写一写，剩下的咕了题目链接Lightning Routing ILCT模板题对于每条偏爱路维护正着和反着两条直径，用两个set维护所有虚儿子的最长链有板子就很舒服Code#include <set>#include <cstdio>#include <cstring&...
2019-09-15 19:06:36
972
5
原创 [300iq Contest 1]简要题解
前言老年选手的智商训练(1/∞)题目链接Angle Beats考虑建图，发现每个∗*∗和+++的度数都为2，每个...的度数都为1对于每个∗*∗和+++拆两个点，这两个点互相连边对于一个∗*∗点，其中一个点向上/下的...连边，另一个向左右的...连边对于一个+++点，两个点都向上下左右的...连边考虑这张图的最大匹配，可以发现，答案为match-cnt，cnt为∗*∗和+++的数...
2019-09-06 20:40:57
1606
1
原创 带花树模板
背下来就好了。。。。#include <queue>#include <cstdio>#include <cstring>#include <algorithm>#define fo(i,a,b) for(int i=a;i<=b;i++)#define fd(i,a,b) for(int i=a;i>=b;i--)#def...
2019-09-06 11:10:55
342
原创 「MtOI2019」幽灵乐团
Description求∏i=1A∏j=1B∏k=1C([i,j](i,k))f(type)\prod_{i=1}^{A}\prod_{j=1}^{B}\prod_{k=1}^{C}({[i,j]\over (i,k)})^{f(type)}i=1∏Aj=1∏Bk=1∏C((i,k)[i,j])f(type)f(0)=1,f(1)=ijk,f(2)=(i,j,k)f(0)=1,f(1)...
2019-09-02 21:23:46
526
原创 [The 2019 Asia Yinchuan First Round Online Programming]简要题解
前言吃瓜吃瓜顺便我没有做过原题来试一试能打多少由于开学机房只剩我一个人只能单挑了_ (:з」∠) _有的题没时间写就口胡了题目链接Maximum Element In A StackSolution模拟Code#include <cstdio>#include <cstring>#include <algorithm>#define f...
2019-09-01 22:35:55
304
原创 [2019 年百度之星·程序设计大赛 - 初赛三]简要题解？
前言老年贤者选手终于记得打百度之星了Orz mayaohua2003题目链接最短路 1n⊕1n \oplus 1n⊕1最短路 2枚举i，求最短路DAG，Dp算术令n<=mμ(lcm(i,j))=μ(i)μ(j)μ(gcd(i,j))\mu(lcm(i,j))=\mu(i)\mu(j)\mu(gcd(i,j))μ(lcm(i,j))=μ(i)μ(j)μ(gcd(i,j))...
2019-08-24 20:02:32
931
1
原创 [Atcoder Grand Contest 037]简要题解？
Dividing a StringDescription给出一个字符串S，将其分成最多的字符串S1…Sk，使得Si!=Si+1|S|<=2e5Solution显然分成的字符串的长度为1或2设Fn表示前n个的答案，那么如果Sn!=Sn-1那么Fn=Fn-1+1否则Fn=Fn-3+2Code#include <cstdio>#include <cstring&...
2019-08-24 11:38:02
363
1
原创 [校内模拟]点
Description数轴上有n个点，第i个点的坐标为xi你需要把每个点左移d或者右移d，然后用一些线段去覆盖所有点一条线段[l,r]的代价为a+b(r-l)求将所有点覆盖的最小代价n,d,xi<=150Solutionniubi题先把d*2，问题变成，有n个恋恋，每个恋恋可以向左移动d，或者不动考虑d小的情况，我们可以设F[i][s]表示当前做到位置i，i往左d个位置的点...
2019-08-23 16:25:49
286
原创 HDU 2019 Multi-University Training Contest 10 简要题解?
前言在？为什么-12我发现每次我打1004都会出现蜜汁bug并且一直调不对然后晚上突然就发现自己是个sb然后1A技不如人，甘拜下风.jpg博主已经进入贤者模式就只写自己做的了队友做的咕咕咕了Valentine’s DayDescription有n个硬币，第i个硬币有pi的概率正面朝上你需要选择一些硬币，使得恰好有1个硬币正面朝上的概率最大n<=10000Solutio...
2019-08-22 21:51:36
544
原创 HDU 2019 Multi-University Training Contest 9 简要题解?
前言智商回复训练鸽子博主终于开始打ACM了代码有一些是队友写的所以就不贴了Rikka with QuicksortDescription定义gm(i)=0，1≤i≤mg_m(i)=0，1\le i\le mgm(i)=0，1≤i≤mgm(i)=i−1+1i(∑j=1igm(j−1)+gm(i−j)),i>mg_m(i)=i-1+{1\over i}(\sum_{j=...
2019-08-19 21:44:54
306
原创 [Comet OJ - Contest #7]简要题解？
似乎由于是NOI前所以没什么dalao打混了个rk4_(:з」∠)_签到题相邻两个数gcd=1#include <cstdio>#include <cstring>#include <algorithm>#define fo(i,a,b) for(int i=a;i<=b;i++)#define fd(i,a,b) for(int i=a;...
2019-07-21 23:26:27
211
原创 [Comet OJ - Contest #6 E]字符串
Description给出一个长度为n的字符串S，定义f(S)为S的所有n∗(n+1)/2n*(n+1)/2n∗(n+1)/2个子串，两两求LCP的和对于每个i，求出f(S[i…n])，答案对998244353取模n<=200000Solutionlog^2的做法有很多这里就不一一说了数据结构学傻了.jpg先考虑两个后缀l和r的所有前缀互相匹配的答案，显然只和后缀长度和LCP有...
2019-07-11 15:23:08
309
原创 [Comet OJ - Contest #6 F]permutation
Description给出n，求有多少个长度为n的排列没有长度为2~n-1的连续段n<=10^5Solution生成函数学艺不精.jpg特判掉n<=2，我们考虑一般情况首先数排列等价于数析合树，我们考虑根节点的形态若根为合点，则儿子排列为单调上升/下降，且不存在一个儿子为合点，且这个儿子的儿子也为上升/下降显然上升=下降，设G(x)表示根为合点且儿子单调上升的析合树数量...
2019-07-10 20:23:01
354
原创 [模板]BM优化线性递推
又水了一篇博客=w=namespace BM{ vector<int> h[N]; int cnt,fail[N],d[N],an[N],mx,k,f[N],g[N],p[N],trs[30][N]; void mult(int *a,int *b,int *c) { fo(i,0,2*k-2) g[i]=0; fo(i,0,k-1) fo(j,0,k-1) (g[i...
2019-07-04 17:08:20
281
原创 [LOJ6677]EntropyIncreaser 与菱形计数
Description求将边长为a,b,c的六边形分解成若干个小菱形的方案数如图为a=b=c=6的情况当a=b=c=2时答案为20，如图所示a,b,c<=10^6Solution这东西怎么看都是一个3维的东西。。。你感受一下，这个想当于在一个a*b的网格上堆箱子，第i个格子最多堆c个箱子，且个数要<=其左边和上边的箱子数这个还是没法做，但是还是可以看成下图的网格图，从左...
2019-07-03 20:44:30
748
原创 [校内模拟]光影交错
Description有一个盒子，每个时刻有pl的概率往里面放一个白球，有pd的概率往里面放一个黑球，1-pl-pd的概率什么都不干，然后每个时刻末尾有p的概率直接结束过程问所有满足“白球数量大于黑球数量”的时刻的数量的期望所有读入的实数均保留5位小数Solution其实是JS的省队集训考虑设f[i]表示，所有满足有i个球的时刻的期望，g[i]表示，i个球中，白球>黑球的概率那...
2019-07-03 17:43:38
1783
原创 [校内模拟]三格骨牌
DescriptionT次询问，每次将一个nm的棋盘分成nm/3块大小为3的四连通块，再给每个四连通块标号，使得每块的标号不同，并且对于一个格子，其左边和上边的标号要小于等于其本身的标号问方案数，对10^9+7取模T<=10,n,m<=10^4Solution考虑按标号从小到大填连通块，那么每次填完后的图形必然是左上角的一块考虑这一块的轮廓线，必然只有往上和往右的，那么我们...
2019-07-01 17:41:18
541
原创 [校内模拟]为了部落
DescriptionT次询问，每次询问给出n,m,k,P，问n个点的所有有标号生成森林中，连通块数为m的方案中，从每棵树中选择一个度数<=k的点的方案数对P取模的方案数n<=10^9,m,k<=100Solution我们先选关键点，再数生成树显然任意m个点的方案数是相等的，我们只需要指定m个关键点，答案乘上(nm)\binom{n}{m}(mn)考虑枚举这m个点的...
2019-07-01 17:18:42
756
原创 [Comet OJ - Contest #6 ]简要题解？
图游戏n-1-m的奇偶性#include <cstdio>#include <cstring>#include <algorithm>#define fo(i,a,b) for(int i=a;i<=b;i++)#define fd(i,a,b) for(int i=a;i>=b;i--)using namespace std;in...
2019-06-29 22:23:48
515
原创 [校内模拟]字符串
Description定义一个字符串S的权值f(S)为，其所有不同后缀两两的LCP的最大值给出一个字符串S，每个位置有权值aim次询问，每次询问给出[l,r,x]，求一个[l,r]的子区间[a,b]，满足f(S[a,b])>=x，且max(ai)最小n,m<=5e4Solution这题分成两部分1:给出[L,R]，求f(S[L,R])考虑SAM，枚举parent树上的一...
2019-06-29 22:13:17
231
原创 [校内模拟]抬头仰望梦的脚步
Description一棵二叉搜索树，插入n次，第i次插入的节点权值为(a+bn)%m，问第n次插入的点的深度T<=5e4,n<=1e16,a,b,m<=1e8Solution定义val(n)表示第n个数的权值，suf(v)表示所有的(a+bn)%m中，大于v的最小的数，pre(v)表示小于v的最大的数当n>m/gcd(m,b)时，后面的点构成循环，只需要计算第一...
2019-06-29 22:01:34
375
原创 [校内模拟]喜欢最最痛
Description有一棵n个点的树，边有边权。有m条额外边，第i条的边权为ai，对于每个i∈[0,m]，问加入前i条额外边后，从1出发经过所有树边至少一次最后回到1的最短路径的长度。n,m<=10^5Solution容易发现这题分为两部分，先求出an[i]表示选择树上i条不相交的链的长度最大值，然后对于每个前缀i，求一个j，使得an[j]-前i个a的前j小最大an的话可以考虑...
2019-06-27 22:14:13
481
原创 [APIO2019]桥梁
Description给出一张n个点m条边的图，每条边有边权di有q次操作，第i次操作会修改一条边的边权，或者问从点x出发，只经过边权>=y的边，能到达多少个点n<=50000,m,q<=10^5Solution数据结构学傻了.jpg考虑对操作分块，我们只考虑一段操作带来的影响将这个操作块内的询问和修改分开，将询问按权值排序，将所有边按边权排序，先不考虑修改操作的边...
2019-06-26 16:20:30
338
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人