2 Deep_Kevin

尚未进行身份认证

暂无相关简介

等级
TA的排名 1w+

「EZEC-1」数列,组合数推导

正题 Portal 比赛的时候不懂一个组合数的公式暴毙。我太菜了 实际上你可以发现,第一行的公差是1,第二行的公差是a+b,第i行的公差是,这是为什么呢? 可以发现从每一行的公差是上一行的(a+b)倍,因为相邻两项之间被*a贡献之间公差为上一层的公差,被*b贡献之间公差为上一层的公差,c可以抵消掉,所以公差就是(a+b)倍。 那...

2020-04-20 12:05:42

Codeforces Round #632 (Div. 2)

正题 Portal 又是掉分的一天,D题看漏一个“至少”,就一直卡在那里,然后最后就只做出来三题。 赛后看了一眼EF,大概半个小时就做出来了。 还是太菜了,要更细心一些,写篇Blog来记录一下。 T1 没什么好说的,直接把一个相邻两项不同的矩阵改一改就是答案。#include<bits/stdc++....

2020-04-09 17:17:32

分拆,WYXkk 的欢乐水题赛,分类讨论

正题 Portal 题解思路优秀 分类讨论mod 4余数: 为1时显然有解,构造出一个n,(n-1)/2个1,(n-1)/2个-1就可以了。 为2,3时肯定无解,具体可以用假设法证明。 为0时,当n=4时无解。 否则,当n=8k时,可以构造解:4k,2,6k-2个1,2k个-1. 当n=...

2020-03-30 09:17:47

Mr. Kitayuta's Gift,CF506E,有限状态自动机+分析状态后矩阵快速幂

正题 Protal 这题很有难度。 首先可以想到一个简单的方程,用表示手动加了k个将两边消掉,中间剩下[l,r]的方案数。 可以想到,为了避免重复,当最后的串中存在bbxxbb的时候,我们把手动加的bb都放在最靠近中间的位置。 那么就可以构造一个有限状态自动机,有三种节点,一种是n24(有24种自环),一种是n25,一种是n26...

2020-03-26 10:29:00

Bombs,CF1326E,求答案转化为判定性问题解决

正题 Portal 这题考场上没想出来,写了一个动态主席树炸掉了。 正解很简单但不显然,考虑现在要将大于等于x的所有数炸掉,炸弹需要满足的充分必要条件就是: 在>=x的数中倒数第一个的右边必须有一个炸弹 在>=x的数中倒数第二个的右边必须有两个炸弹 以此类推 这里的右边是包括当前位置的。...

2020-03-24 09:26:59

洛谷P6158 封锁,平面图最小乘积最短路

好久没有写Blog,这个寒假打比赛打得挺顺利的。正题 Portal 其实是最后不够时间了,这道题两个part我都做过。 如果没有AB两个权值那么就是平面图最小割的问题,转化为最短路就可以解决了,具体做法就是把左下角的空白看成起点,右上角的空白看成终点,如果假设要使一条边不能走相当于穿过这条边,会发现最后的决策其实是新起点到新终点的一条路径。...

2020-03-03 08:38:10

学习笔记第五十六节:概率期望

正题 以前一直都一直在凭感觉做概率期望,直到我遇到了这一公式题:排名估算 如果做不出来的话就让我们一起学习吧! 如果做得出来给您跪了! 首先了解几个符号: 表示A发生的机率。 B发生下A发生的概率 AB同时发生的概率。 你可能觉得这些东西并没有什么用,下面让百度说一个例子:...

2020-01-19 08:41:04

牛客挑战赛36

正题 放假苟在电脑室打比赛懒得回家。 T1:环 因为保证是奇数,所以可以想出一个类似于增添补出或者漏一个的方法。 可以很容易的求出这个序列的id序列,和全部值的和。 处理出偶数位的前缀和和后缀和。对于一个偶数位,它的值就是pre[i]+las[i]-tot,对于一个奇数位,它的值就是tot-pre[i-1]-las[i+1];...

2020-01-18 16:54:59

Median Replace,agc022E,困难的性质推导

正题 首先考虑到3个0的肯定可以先删掉,那么两个1之间最多只有两个0。 把一个序列写成0,1,2三个数字组成的形式,分别表示在第i个1和第i-1个1之间0的个数,首尾情况考虑先插一个1. 然后发现单独的0的情况其实是可以直接删除的,除非只剩下一个0,因为附近肯定有一个1,所以,01不论与1还是与0结合,都会生成一个与结合数字相同的数字,去掉它对正确性并没有...

2019-12-11 18:37:04

牛客OI周赛13-提高组

正题 这次比赛打得不错,想出了两道题,期望230,实际180。 T1 其实挺好玩的,考虑到^0,|0,&1之后数值不会改变,^1翻转,|1变成1,&0变成0。 把第一个数位可以换成|?,然后规定开始为0。 考虑到一个操作序列,有用的位置一定是最后一个“变成”和最后一些翻转,想到可以枚举最后一个变成是哪个位置,该位...

2019-12-09 18:33:31

学习笔记第七节:主席树

正题 主席树看上去很高级(President Tree)。 但是其实理念挺low的,在百度上一查,发现,艾~这不是函数式线段树吗~ 那么说明主席树跟线段树是有着密不可分的联系的。 说白了,我们要学习的就是,如何优化线段树的时间来换更少的空间。前面都是废话 我们可以用这题来引入。 要你求静态区间第k大。 ...

2018-05-20 21:47:04

Comet OJ - 模拟赛 #2 Day2

正题 今天不会做的题是第一题 T1 开场想到T1不会那么难,就直接暴力枚举x的因子,时间复杂度,结果拿到了70分的好成绩。 考虑到x的因子并没有那么多,根本不需要根号去枚举,而是质因数分解之后,暴力dfs枚举因子。 首先50000以内的质数只有大概3000个左右(并没有那么多,用黎曼猜想估算),其次分解是log的,所以就是,题解...

2019-12-01 10:37:35

Comet OJ - 模拟赛 #2 Day1

正题 Portal cometoj出的题质量还是蛮高的,至少让我这种菜鸡选手找到了思考的乐趣。 T1 这题很水,因为要找波浪,所以用a1,a2分别记录以i结尾的降波浪和升波浪的种数,每次交换一下把其中的一边清空为1就可以了。#include<bits/stdc++.h>using namespace std;long ...

2019-11-30 11:52:32

Construction of a tree,agc029f,结论推导+Dinic

正题 Portal 这题好难,首先考虑转化为一棵有根树,令1为根,想办法从每个集合中选出一些边,按照一定顺序加入,使得每一个xi只被选一次,并且按照一定顺序加入,使得已经在树里面就可以了。 首先要满足第一个条件,xi肯定不能为1,所以我们二分图匹配中右边放得点只能为[2,n]。然后向自己集合内的元素连边,若找到了一组匹配,考虑直接用队列加入就可以了,一个x...

2019-11-18 21:50:51

CSP2019 S游记

正题 爆炸了: Day0 跟老王又一次坐在前排,上车之前给我们买了3个全家桶,吃得很爽(退役flag1 去到柏高之后肚子有点难受,去吃饭之后好了很多,晚上把王者下了回来,跟表弟打了两把都输了,叫的外卖炸鸡很难吃(退役flag2 晚上应该是被冷醒了2次,睡眠不怎么好。 Day1 早上5点钟就起来了,洗个...

2019-11-18 11:31:30

CSP2019集训总结

前言 感觉好像什么都没有做,又好像什么都做过。正题 两个月过得好快,梦想着这次CSP考好一点,就可以继续停课? 集训一开始就是比较稀疏的比赛和刷题,在这个期间做了很多51nod上面的神仙数论题,帮我在数论上面的知识拓宽了一步,还帮忙验了很多题。 与此为伴的就是我们自己出的题组的比赛,每场比赛都有很多锅,导致明白题意需要很久,不过题都是挺简...

2019-11-15 19:32:16

Flights for Regular Customers,CF576D,倍增floyd

正题 Portal 有<=m个不同的图,把权值从小到大来排序,每次往边集中加入相等边权的边。 首先可以求出利用前面的边集,走步的邻接矩阵是什么样子的,并且保证前面没有走到过n。 现在可以在当前的图上继续走,看一下在走的过程中是否有到过n。 维护一个邻接矩阵G[i],使其等于,其中加法表示或,乘法表示邻接矩阵转移,E为当前边...

2019-11-12 22:14:30

Comet OJ - 模拟赛 #1

正题 1个半小时就可以AK的题目 A 发现一个点只会被吸一次,那么就是找对应区间,双指针即可,求答案的时候注意一下两边有0的情况。#include<bits/stdc++.h>using namespace std;const int N=100010;int T,n;int a[N],b[N];void read(int&...

2019-11-11 20:16:06

Comet OJ - Contest #14

正题 我好菜啊第二题都可以调40分钟。 Portal A 这题很简单,暴力即可。#include<bits/stdc++.h>using namespace std;int n;long long a,b,r;int main(){ scanf("%d %lld %lld %lld",&n,&a...

2019-11-11 19:54:12

Sum Balance,CF1242C,找环+状态压缩Dp

正题 首先只能交换一次,我们给一个点向丢弃这个点能换来的点连有向边,那么问题就变成了,找到一些环,使得每个集合中只有且仅有一个点在环上,首先可以证明这是一棵基环内向树森林,因为每一个点的出度,在题解中也说到了这是一个"function graph",不可能有两个环有公共点,所以我们直接找强连通分量,注意这里的不能把单点但没有自环的强连通分量算进去,因为不能构成一种方案,如果强连通分量...

2019-11-08 09:43:14

查看更多

勋章 我的勋章
  • 专栏达人
    专栏达人
    授予成功创建个人博客专栏的用户。专栏中添加五篇以上博文即可点亮!撰写博客专栏浓缩技术精华,专栏达人就是你!
  • 持之以恒
    持之以恒
    授予每个自然月内发布4篇或4篇以上原创或翻译IT博文的用户。不积跬步无以至千里,不积小流无以成江海,程序人生的精彩需要坚持不懈地积累!
  • 1024勋章
    1024勋章
    #1024程序员节#活动勋章,当日发布原创博客即可获得
  • 勤写标兵Lv4
    勤写标兵Lv4
    授予每个自然周发布9篇以上(包括9篇)原创IT博文的用户。本勋章将于次周周三上午根据用户上周的博文发布情况由系统自动颁发。