2 Deep_Kevin

尚未进行身份认证

暂无相关简介

等级
TA的排名 1w+

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

Donation,ARC098F,神仙*(转化+建树)

正题 Portal 首先因为我们要满足每个点都被捐赠过,那么我们可以把经过i点,的条件转化为每次进来和出去,都要满足,因为一个点肯定会在最后一次经过的时候捐赠,也就是说在最后离开的时候要满足这个条件,那么前面的情况必定满足,那么就设。 一个结论就是当有两种选择的时候,捐赠肯定要选当前最大的,如果先选较小的,可能会使得答案更劣。 我们要同时这两...

2019-11-06 21:28:24

Modulo Pairing,AGC032E,性质+二分

正题 Portal 把a排序后,最优的方案就是找到一个断点,使得左边x+y<m,且右边x+y>=m,然后左右分别首尾配对使得最大值最小。 具体证明可以自己想想不合法的方案,发现都可以转化为一种等价或更优的合法方案。 然后怎么找这个断点呢? 可以发现左右的最大值都是随着断点的右移而增大的。 那么要找的就是...

2019-11-06 21:20:54

Mr. Kitayuta vs. Bamboos,CF506C,二分+神仙判定

正题 Portal 很容易发现这个答案具有单调性,所以选择花费1个log的代价取二分。 顺着考虑发现很难,我们倒着考虑,二分到的值为x。 我们就假设一开始全部的高度都为x,每天每根竹子缩短,每天的末尾可以选择k根竹子把它拉高p。 问存不存在一种方案使得每根竹子在任意时刻高度不为负数,而且最后高度,利用放缩法容易证明这是等价的。...

2019-11-06 21:03:35

One Third,AGC032F,巧妙的构造

正题 我们把这个圆分成平均分成三份,以第一刀为第一块与最后一块的边界。 令它们的颜色为红蓝黄(左闭右开)。 然后割下的每一刀的颜色就是所在位置的颜色,然后将每一刀都mod。 现在就是找两个最近异色点对。 可以自己讨论一下,发现很巧妙! 通过简单积分可以得到:将一条长度为1的线段随机取n-1个点,分成n条线段,第k短...

2019-10-31 21:59:48

Balance Beam,AtCoder Grand Contest 040,神仙转化贪心

正题 Portal 很好的题。 设 我们把Snuke和Ringo的 路程-时间 折线投射在一个二维平面上,发现是要求一个最大的p,使得Ringo交x轴于(p,0),且与Snuke的折线有交点。 假设交x轴这条线段是k,那么对于它旁边的线段,需要满足 为什么是,考虑一条路径,从(p,0)开始,沿着Ringo的折线走,...

2019-11-04 17:13:10

Neither AB nor BA,AtCoder Grand Contest 040,巧妙的构造

正题 Portal 题解太巧妙了 我们把奇数位上的A换成B,B换成A。就变成了现在不能删除AA和BB,因为删除两位 剩下位的奇偶是不变的,所以就有唯一对应的A和B。 考虑一个性质,如果A的个数或者B的个数>,那么就无解,反之有解。 感觉挺显然的,考虑A的话,把B和C染黑就好了,反之亦然,发现异色才能抵消,那么>显然无...

2019-11-04 17:06:29

Two Contests,AtCoder Grand Contest 040B,贪心

正题 Portal 考场上花了15分钟左右想的。 首先考虑r最小的一个区间,把它丢进第一个集合里面,其他区间按r排序,枚举一个区间丢到第二个集合里面,作为第二个集合里面r最小的区间,考虑剩下的区间应该怎么丢。 r<枚举的区间的r 的肯定丢到第一个集合里面,剩下的,它们的r显然都没有贡献,只在于最大的l是什么,把剩下的所有区间全部丢到第一...

2019-11-04 16:58:57

时间跳跃,MtOI2019,Dp

正题 Portal 很容易想到如果最小k-1条边之和>最大那条边,那么就可以构成一个k边形。 否则显然构不成一个多边形。 那么很容易可以想到Dp:表示用j条边构成总长度为i的组合有多少种,转移显然,时间复杂度就是,可以获得80分的好成绩。 发现并不需要记下那么多东西,用表示组成总长度为i的方案数,表示组成总长度为i的权值和...

2019-11-04 16:52:44

查看更多

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