2 青烟绕指柔!

尚未进行身份认证

我要认证

我不怕千万人阻挡,只怕自己投降。

等级
TA的排名 4k+

跳舞的线 - 乱拐弯

题目链接:跳舞的线 - 乱拐弯显然到一个点之后,方向是有关系的,所以我们多加一个状态存方向即可。AC代码:#pragma GCC optimize("-Ofast","-funroll-all-loops")#include<bits/stdc++.h>//#define int long longusing namespace std;const int N=1e3+10;int n,m,mi[N][N][2],mx[N][N][2]; char g[N][N];sign

2020-07-02 13:24:35

毒瘤之神秘通道

题目链接:毒瘤之神秘通道因为边权和之前通过的人数有关,所以我们需要先一遍拓扑求出边权。然后第二次拓扑求出dp[i]以i为起点到0的答案。AC代码:#pragma GCC optimize("-Ofast","-funroll-all-loops")#include<bits/stdc++.h>#define int long longusing namespace std;const int N=1e6+10;int n,m,to[N],w[N],dp[N],res=-1,

2020-07-02 12:43:21

Cow Jog G

题目链接:Cow Jog G显然我们只和第一个位置,和最后的位置有关。速度其实无所谓。然后就变成一个一个序列的最少LIS划分数,根据dirworth定理,也就是最长反链。AC代码:#pragma GCC optimize("-Ofast","-funroll-all-loops")#include<bits/stdc++.h>#define int long longusing namespace std;const int N=1e5+10;int n,t,a[N],d[

2020-07-02 10:51:48

kry loves 2048

题目链接:kry loves 2048显示是每次选最小的两个组合,然后一直求max。这个数据范围可以直接桶排序,然后用两个队列维护最小值。AC代码:#pragma GCC optimize("-Ofast","-funroll-all-loops")#include<bits/stdc++.h>//#define int long longusing namespace std;typedef long long LL;const int N=1e7+10;LL cnt[

2020-07-02 10:28:29

Censoring S

题目链接:Censoring S因为每次都是找一个个位置,所以我们可以考虑用一个栈维护最早出现的位置。然后怎么判断当前栈顶的字符串是否满足呢?AC自动机或者字符串hash都可。AC代码:#pragma GCC optimize("-Ofast","-funroll-all-loops")#include<bits/stdc++.h>#define int long longusing namespace std;const int N=1e6+10;const int mo

2020-07-01 23:47:06

[CCO 2014]Troy 与三角形

题目链接:[CCO 2014]Troy 与三角形我们对每一个点作为三角形的最上面顶点然后向下考虑,并且利用前缀和优化。复杂度是n^3的。但是我们如果知道上一个点的答案,那么之后的就可以少判断很多,相当于是记忆化,每一行最多访问一次。AC代码:#pragma GCC optimize("-Ofast","-funroll-all-loops")#include<bits/stdc++.h>//#define int long longusing namespace std;c

2020-07-01 22:43:46

[BalticOI 2018]火星人的 DNA

题目链接:[BalticOI 2018]火星人的 DNA显然我们对每个限制取max即可。然后每次维护当前有几个满足的。尺取即可。AC代码:#pragma GCC optimize("-Ofast","-funroll-all-loops")#include<bits/stdc++.h>//#define int long longusing namespace std;const int N=2e5+10;int n,K,R,vis[N],res,mx[N],cnt,a[N

2020-07-01 21:44:40

River Jumping

题目链接:River Jumping显然我们可以发现如果连续的3个之中,最后一个减去第一个都小于s则无解,否则我们可以贪心能跳就跳,因为连续两个之中小于s是不影响的,因为我们特判了连续3个的情况。然后我们最后反向扫一遍第一次未跳的,如果都是满足的则输出。AC代码:#pragma GCC optimize("-Ofast","-funroll-all-loops")#include<bits/stdc++.h>//#define int long longusing namesp

2020-07-01 21:05:13

LYZ-Ice Skates

题目链接:LYZ-Ice Skates显然是一个二分图匹配问题,所以我们可以想到用霍尔定理来做。但是我们不能暴力枚举左边点的所有情况,但是我们其实只需要找到左边所有情况的最小值即可。我们显然可以发现最小值一定是一个连续的区间。因为这样重叠是最多的。所以我们等价于找一个区间:(r-l+1+d)*k>=sum(l,r)在极端情况都是满足的,所以我们维护区间最大子段和即可。AC代码:#pragma GCC optimize("-Ofast","-funroll-all-loops")#inc

2020-07-01 12:08:57

夜游 ECNU

题目链接:夜游 ECNU显然有一个n*n的dp方程。但是我们可以按照x排序,之后用fenwick维护y的前缀和,然后计数即可。AC代码:#pragma GCC optimize("-Ofast","-funroll-all-loops")#include<bits/stdc++.h>//#define int long longusing namespace std;const int N=2e5+10,mod=1e9+7;int n,d[N],m,res[N];stru

2020-06-30 23:54:35

数螃蟹

题目链接:数螃蟹感觉大家的做法似乎都很复杂。其实有一个简单的做法,因为只有3个数字不一样,那么我们随机取两个数字,取到合法的数字概率为:(n-3)/n。当n很大时,这个概率是很高的。计算过程中会爆LL,所以我们用int128即可。然后暴力check即可。AC代码:#pragma GCC optimize("-Ofast","-funroll-all-loops")#include<bits/stdc++.h>#define int __int128using namesp

2020-06-30 17:44:24

Codeforces - Reading Books (hard version)

题目链接:Codeforces - Reading Books (hard version)我们可以发现如果我们选择(1,1)的物品确定之后,那么其他物品的选择则变成了必然的。然后可以枚举选择几个(1,1)的物品,那么复杂度太高了,需要用数据结构维护选的物品。其实还有一个方法,我们可以发现选择(1,1)类型的物品是具有三分性的,必然存在某个中间点是最优的。所以直接三分之后暴力找即可。AC代码:#pragma GCC optimize("-Ofast","-funroll-all-loops"

2020-06-29 20:16:00

[HEOI2014]南园满地堆轻絮

题目链接:[HEOI2014]南园满地堆轻絮首先我们可以想到二分。然后发现每个数字的实际区间就是显然的了。如果合法那么就是前面的一个区间的最小值,小于后面一个区间的最大值。然后我们发现其实就和前面减后面的一个最大差值有关了,就不用二分了。AC代码:#pragma GCC optimize("-Ofast","-funroll-all-loops")#include<bits/stdc++.h>#define int long longusing namespace std;

2020-06-29 10:04:44

线段树:关于时间

题目链接:线段树:关于时间我们以一个基准点建立一个增加的线段树,然后减去一个多余的线段树即可。比如我们以1号为基准点,那么多余的要减去的是已知的,就是到1号节点的距离,然后增加的也就是当前查询的时候的编号。AC代码:#pragma GCC optimize("-Ofast","-funroll-all-loops")#include<bits/stdc++.h>#define int long longusing namespace std;const int N=1e5+1

2020-06-28 23:04:22

Inheritance

题目链接:Inheritance比较有趣的一道题,如果我们暴力去做复杂度是:O(m*k/n),会被n很小的时候卡掉。所以我们考虑对每个人维护一个并查集。然后枚举边,从大到小,然后找到第一个未连通的,然后连接上,复杂度也是很高的,但是我们可以发现未连通的是具有二分性的,二分即可。AC代码:#pragma GCC optimize("-Ofast","-funroll-all-loops")#include<bits/stdc++.h>//#define int long long

2020-06-28 13:22:04

[JXOI2017]加法

题目链接:[JXOI2017]加法显然可以二分,然后我们就可以得到每个点需要被多少个区间覆盖。然后左端点从小到大排序,然后贪心选择即可。但是有区间覆盖的次数计算,我们可以直接差分,从前往后计算前缀和,用fenwick也可以。AC代码:#pragma GCC optimize("-Ofast","-funroll-all-loops")#include<bits/stdc++.h>//#define int long longusing namespace std;const

2020-06-28 10:59:21

Median Sum

题目链接:Median Sum看到中位数,我们就会想到二分,但是子集太多了,二分也不行。我们可以发现,中位数形成的集合,是对称的。设s为所有数的和,如果存在x那么必然存在s-x。所以我们只需要知道某个数字是否存在于某个集合中即可,然后找到大于(s+1)/2的第一个存在的数字。AC代码:#pragma GCC optimize("-Ofast","-funroll-all-loops")#include<bits/stdc++.h>//#define int long long

2020-06-27 14:13:24

Widespread

题目链接:Widespread显然有一个贪心,每次选择最大的,然后减去A,其他的减去B。那么就变成线段树区间减,维护区间max的位置即可。但是显然可以二分,就不用写线段树了。先假设全用B,然后多出来的再用A。AC代码:#pragma GCC optimize("-Ofast","-funroll-all-loops")#include<bits/stdc++.h>#define int long longusing namespace std;const int N=1e5+

2020-06-27 11:11:26

Lotus Leaves

题目链接:Lotus Leaves显然是一个最小割模型。但是我们暴力连边是O(n ^ 3)的。考虑优化:我们可以把每一条竖着的,横着的抽出来,然后就变成O(n ^ 2)了。没什么难度。AC代码:#pragma GCC optimize("-Ofast","-funroll-all-loops")#include<bits/stdc++.h>//#define int long longusing namespace std;const int inf=0x3f3f3f3f;

2020-06-27 10:45:22

Unplanned Queries

题目链接:Unplanned Queries我们单独看每一条链是很麻烦的,简直无法做。但是我们可以发现,如果某个叶子的次数为奇数,那么必然无解,然后删掉叶子有出现新的叶子,显然每个点的次数必然为偶数。AC代码:#pragma GCC optimize("-Ofast","-funroll-all-loops")#include<bits/stdc++.h>//#define int long longusing namespace std;const int N=1e5+10

2020-06-27 09:31:51

查看更多

勋章 我的勋章
  • 签到达人
    签到达人
    累计签到获取,不积跬步,无以至千里,继续坚持!
  • 新人勋章
    新人勋章
    用户发布第一条blink获赞超过3个即可获得
  • 持之以恒
    持之以恒
    授予每个自然月内发布4篇或4篇以上原创或翻译IT博文的用户。不积跬步无以至千里,不积小流无以成江海,程序人生的精彩需要坚持不懈地积累!
  • 1024勋章
    1024勋章
    #1024程序员节#活动勋章,当日发布原创博客即可获得
  • 勤写标兵Lv4
    勤写标兵Lv4
    授予每个自然周发布9篇以上(包括9篇)原创IT博文的用户。本勋章将于次周周三上午根据用户上周的博文发布情况由系统自动颁发。
  • 学习力
    学习力
    《原力计划【第二季】》第一期主题勋章 ,第一期活动已经结束啦,小伙伴们可以去参加第二期打卡挑战活动获取更多勋章哦。
  • 原力新人
    原力新人
    在《原力计划【第二季】》打卡挑战活动中,成功参与本活动并发布一篇原创文章的博主,即可获得此勋章。
  • 原力探索 · S
    原力探索 · S
    在《原力计划【第二季】》打卡挑战活动中,发布 12 篇原创文章参与活动的博主,即可获得此勋章。(本次活动结束后统一统计发放)