3 EM-LGH

尚未进行身份认证

暂无相关简介

等级
TA的排名 6w+

luoguP5445 [APIO2019]路灯 树套树+set

code:#include <vector> #include <cstdio> #include <cstring>#include <map> #include <set>#include <algorithm> #define N 300005 #define MAX 320005 ...

2020-02-15 17:14:00

luoguP5444 [APIO2019]奇怪装置 数论+贪心

本题的关键在于求循环节.如果能想到从循环节入手的话这道题还是比较友好的. code:#include <cstdio> #include <cstring> #include <algorithm> #include <cmath> #define ll long long #define N 1000...

2020-02-15 10:16:00

Comet OJ - Contest #2

Acode:#include <cstdio> #include <algorithm> #define N 1000000 #define ll long long #define setIO(s) freopen(s".in","r",stdin) using namespace std; ll f[N],g[N]; i...

2020-02-14 22:31:00

luoguP6070 [MdOI2020] Decrease 贪心+二维差分

显然从左到右,从上到下依次处理每个格子步数是最少的. 而由于我们的顺序是固定的,每次操作等于是一个区间修改,单点查询.利用二维差分的方式可以轻松实现.code:#include <cstdio> #include <cstring> #include <string> #include <vector&gt...

2020-02-13 16:37:00

luoguP6071 [MdOI2020] Treequery DFS序+主席树

思路自然的码农题. 显然分类讨论一下编号在 $[l,r]$ 的点与 $p$ 的子树关系. 如果都在 $p$ 的子树内就是个区间 $lca$.否则,就二分第一个满足 $p$ 的祖先且子树内部没有 $[l,r]$ 之间的点. 二分验证的话要用主席树.code:#include <cstring> #inclu...

2020-02-13 15:42:00

AT2064 [AGC005F] Many Easy Problems 容斥+NTT

这个题的容斥思路还是非常巧妙的.code:#include <cstdio> #include <cstring> #include <cmath> #include <vector> #include <algorithm> #define ll long long #define N ...

2020-02-13 10:51:00

BZOJ 4650: [Noi2016]优秀的拆分 后缀自动机+启发式合并+线段树合并

将问题转化为统计以 $i$ 结尾的 $AA$ 串个数. 我们将后缀树建出来,然后按照启发式合并的方式每次合并两个 $endpos$ 集合. 那么就有:$[x-mx,x-1] \rightarrow x$ 与 $x \rightarrow [x+1,x+mx]$ 的贡献. 统计第一种贡献的话在线段树上区间查询就行. 第二种贡献的话要在线段树上维护一个 lazy...

2020-02-12 16:58:00

BZOJ 1498: [NOI2006]神奇的口袋 性质分析+高精度

我们发现我们可以直接让 $x_{i}=i$,然后模拟就行了.code:#include <cstdio> #include <cstring> #include <cmath> #include <vector> #include <map> #include <algorithm> ...

2020-02-11 15:57:00

BZOJ 1819: [JSOI]Word Query电子字典 搜索+trie

用 trie 搜索一下就好了.code:#include <bits/stdc++.h> #define N 10008 #define setIO(s) freopen(s".in","r",stdin) using namespace std; char S[24]; int trie[N*20][27],visx[N],p[N*20],...

2020-02-11 11:07:00

BZOJ 1806: [Ioi2007]Miners 矿工配餐 动态规划

滚动数组推一下就行.code:#include <bits/stdc++.h> #define setIO(s) freopen(s".in","r",stdin) using namespace std; int dp[2][4][4][4][4],n; char s[100004]; int sub(int s) { if(s=='...

2020-02-11 10:24:00

BZOJ 1222: [HNOI2001]产品加工 动态规划

这种多线程问题可以采用一维枚举,另一位用 dp 求解最优解来实现.这道题和那个 ZJOI 的食堂排队的题挺像的.code:#include <bits/stdc++.h> #define ll long long #define inf 0x3f3f3f3f #define N 508000 #define setIO(s) freo...

2020-02-11 10:06:00

BZOJ 1037: [ZJOI2008]生日聚会Party 动态规划

code:#include <cstdio> #include <cstring> #include <algorithm> #define ll long long #define MAXN 160 #define MAXK 20 #define mod 12345678 #define setIO(s) freope...

2020-02-10 21:35:00

luoguP5161 WD与数列 后缀自动机+线段树合并+启发式合并

第一次写这个题是好长时间以前了,然后没调出来. 本来以为是思路错了,结果今天看题解发现思路没错,但是好多代码细节需要注意.code:#include <cstdio>#include <vector> #include <map> #include <cstring>#include <algo...

2020-02-09 15:27:00

Codeforces Round #539 (Div. 1)

A - Sasha and a Bit of Relaxcode:#include <cstdio>#include <map> #include <cstring>#include <algorithm>#define N 300006 #define ll long long #define setIO(s) f...

2020-02-07 21:25:00

BZOJ 4371: [IOI2015]sorting排序 二分+贪心

思路很巧妙啊code:#include <cstdio> #include <cstring>#include <algorithm> #define ll long long #define N 1000009 #define setIO(s) freopen(s".in","r",stdin) using namesp...

2020-02-06 16:42:00

BZOJ 4369: [IOI2015]teams分组 单调栈+主席树

这个题的思路还是十分巧妙的.我们发现我们要查询的区域恰好构成了一个梯形.然后用那个单调栈去维护折线,并用主席树做二维数点.code:#include <cstdio> #include <algorithm> #include <stack> #include <cstring> #include <vec...

2020-02-06 15:44:00

BZOJ 4370: [IOI2015]horses马 线段树+贪心+对数

显然如果卖出的话肯定要在同一天卖出.那么我们只需维护 $max(y_{i}\prod x_{i})$ 即可.乘法维护不了,取一个对数就好了.code:#include <cstdio> #include <cmath>#include <cstring>#include <algorithm> #define ...

2020-02-05 14:37:00

luoguP5824 十二重计数法 (12合一)

12种组合计数问题合在一起. code:#include <cmath>#include <cstring>#include <algorithm>#include <cstdio>#include <string>#define ll long long#define ull unsigned long ...

2020-02-04 15:04:00

BZOJ 5296: [Cqoi2018]破解D-H协议 BSGS

模板题呀.code:#include <cstdio> #include <cstring> #include <cmath> #include <map> #include <algorithm> #define ll long long #define setIO(s) ...

2020-02-04 10:12:00

BZOJ 2242: [SDOI2011]计算器 BSGS

这里讲一下普通的 BSGS 如何实现: 我们要求解形如 $y^x \equiv z(\mod p)$ 的 $x$ 的整数解(其中 $gcd(y,p)=1$) 我们将 $x$ 写成 $am-b$ 的形式,原式就变为 $y^{am} \equiv z \times y^b (\mod p)$ 然后 $b<m$,可以枚举右面所有的取值,然后再枚举左面,整个时间复杂度是...

2020-02-04 09:47:00

查看更多

勋章 我的勋章
  • 1024勋章
    1024勋章
    #1024程序员节#活动勋章,当日发布原创博客即可获得
  • 勤写标兵Lv4
    勤写标兵Lv4
    授予每个自然周发布9篇以上(包括9篇)原创IT博文的用户。本勋章将于次周上午根据用户上周周三的博文发布情况由系统自动颁发。