3 forezxl

尚未进行身份认证

水君一枚

等级
TA的排名 1w+

NOIP2018爆炸记

感觉一年啥都没学Day 0今年去学车考啊,从没去过学车的我感到瑟瑟发抖。而且大部分都是用笔记本考的,感觉很舒服。早上10点出发,车上一直在看昨天FQY安利给我的番(平生第一次看番好鸡冻),不知不觉就到杭州了。在宾馆里颓到4点去学校,把那部番看完了。领了狗牌后开始研究考场,woc什么鬼啊,七百多人全挤一个大厅里,那还不吵死!真羡慕那些被分到机房里的人(不过要是XP的话就好玩了)。一看时间差不...

2018-11-11 22:28:06

BZOJ4059: [Cerc2012]Non-boring sequences

线段树题目传送门这道题正解是启发式分治,不过线段树也能做。和这道题很像,同样记一个nxt[i]nxt[i]nxt[i]表示a[i]a[i]a[i]下一次出现的位置,枚举左端点,撤销[i,nxt[i]−1][i,nxt[i]-1][i,nxt[i]−1],加上[nxt[i],nxt[nxt[i]]−1][nxt[i],nxt[nxt[i]]-1][nxt[i],nxt[nxt[i]]−1],并...

2018-11-07 18:52:19

codeforces Gym 101623 F(BZOJ5200)

启发式分治BZOJ题目传送门codeforces题目传送门题目大意: 有一种二叉树,每个节点有权值 ,并且满足它与所有祖先的权值互质。现在给出一个序列,问这个序列是否是一棵这种树的中序遍历。还有启发式分治这种操作。。。显然如果一个点要是一颗子树的根,那么它一定与这颗子树里的所有点互质。在序列上则为与一段包含它的区间互质。我们预处理出每个位置左右与它互质的第一个位置。对于一个区间,同时用...

2018-11-07 18:31:09

codeforces 992E. Nastya and King-Shamans

树状数组 二分题目传送门题目大意: 维护一个数列,每次操作为先修改一个数,再询问是否存在一个位置iii满足w[i]=sum[i−1]w[i]=sum[i-1]w[i]=sum[i−1]并输出这个位置。妙蛙问题要求出满足 Ax=sumx−1A_x=sum_{x−1}Ax​=sumx−1​ 的位置,这个可以转化为 sumx=2sumx−1sum_x=2sum_{x−1}sumx​=2sumx...

2018-11-06 21:16:38

codeforces 1066E. Binary Numbers AND Sum

前缀和题目传送门疯狂划水题目大意: 两个很大的二进制数a,ba,ba,b,每次把答案加上a&ba\&ba&b并把bbb左移一位。求最终答案。考虑aaa的每一位对答案的贡献。如果这一位是000没有贡献,否则贡献为2i∗sum[i]2^i*sum[i]2i∗sum[i],其中sum[i]sum[i]sum[i]为bbb从最高位到第iii位的1的个数。扫一...

2018-11-06 19:40:28

codeforces 700B. Connecting Universities

贪心题目传送门题目大意: 一棵树上有2k2k2k个关键点,把这些关键点两两配对,贡献为配对点的距离之和。求最大贡献。树上两点之间的距离为dep[x]+dep[y]−2∗dep[lca(x,y)]dep[x]+dep[y]-2*dep[lca(x,y)]dep[x]+dep[y]−2∗dep[lca(x,y)]。对于这2k2k2k个点,它们的深度之和是确定的,那么我们要使尽可能多的lca深度尽...

2018-11-06 16:54:52

codeforces 999F. Cards and Joy

DP题目传送门题目大意: 有nnn个人n∗kn*kn∗k张卡片,每个人都要分到kkk张卡片。卡片上有数字,每个人也有一个数字,当一个人分到iii张和他的数字一样的卡片时会有h[i]h[i]h[i]的贡献,求最大贡献。设g[i][j]g[i][j]g[i][j]表示iii张卡片分给jjj个人的最大贡献,那么有g[i][j]=max{g[i−p][j−1]+h[p]}g[i][j]=max\{g...

2018-11-05 20:03:45

codeforces 1067A. Array Without Local Maximums

DP题目传送门题目大意: 有一个数列,满足a1≤a2,an≤an−1,ai≤max(ai−1,ai+1)a_1\leq a_2,a_n\leq a_{n-1},a_i\leq max(a_{i-1},a_{i+1})a1​≤a2​,an​≤an−1​,ai​≤max(ai−1​,ai+1​)且1≤ai≤2001\leq a_i\leq 2001≤ai​≤200。现在有一些数不知道,问原数列的所...

2018-11-05 14:40:40

BZOJ2662: [BeiJing wc2012]冻结(洛谷P4822)

分层图最短路BZOJ题目传送门洛谷题目传送门同这道题,稍微改一改就好了。代码:#include<queue>#include<cctype>#include<cstdio>#include<cstring>#include<algorithm>#define N 5005#define M 500005#defin...

2018-11-04 21:14:52

codeforces 165E. Compatible Numbers

高维前缀和题目传送门学了一发高维前缀和。一般我们求多维前缀和是用容斥的,但是当维度很高时会很烦,这时就要用另一种求前缀和的方法。打个比方,假设我们要求二维前缀和:for (int i=1;i<=n;i++) for (int j=1;j<=m;j++) a[i][j]+=a[i][j-1];for (int i=1;i<=n;i++) ...

2018-11-04 16:58:32

BZOJ1855: [Scoi2010]股票交易(洛谷P2569)

单调队列 DPBZOJ题目传送门洛谷题目传送门设f[i][j]f[i][j]f[i][j]表示前iii天还剩jjj股的最多钱数。有四种转移方式。1.之前没有股票,直接从这一天开始买,f[i][j]=−j∗APi(j∈[0,ASi])f[i][j]=-j*AP_i\quad(j\in[0,AS_i])f[i][j]=−j∗APi​(j∈[0,ASi​])2.这一天啥也不干,f[i][j]=...

2018-11-02 20:55:52

BZOJ1296: [SCOI2009]粉刷匠(洛谷P4158)

DPBZOJ题目传送门洛谷题目传送门我连背包都不会了做两遍DP,第一遍求出每一行刷kkk次分别最多能刷对多少个格子。第二遍就把第一遍的当作分组背包来选物品就好了。设f[i][j]f[i][j]f[i][j]表示当前这行做到第iii列,刷了jjj次的最多格子数。那么有f[i][j]=max{f[k][j−1]+max{s0i−s0k,s1i−s1k}}f[i][j]=max\{f[k][j...

2018-11-02 18:59:35

BZOJ5334: [Tjoi2018]数学计算(洛谷P4588)

线段树BZOJ题目传送门洛谷题目传送门线段树维护每次操作的数,撤销就把那个位置变成1就好了。代码:#include<cctype>#include<cstdio>#include<cstring>#include<algorithm>#define N 100005#define F inlineusing namespace ...

2018-11-02 10:41:21

洛谷P3522 [POI2011]TEM-Temperature(BZOJ2276)

单调队列洛谷题目传送门BZOJ题目传送门单调队列维护最低温度递减的序列,同时保证队头的最低温度低于队尾的最高温度就好了。代码:#include<cctype>#include<cstdio>#include<cstring>#include<algorithm>#define N 1000005#define F inlineu...

2018-11-02 09:34:37

BZOJ3875: [Ahoi2014&Jsoi2014]骑士游戏(洛谷P4042)

最短路 DPBZOJ题目传送门洛谷题目传送门很显然有f[u]=min(ku,su+∑f[v])f[u]=min(k_u,s_u+\sum f[v])f[u]=min(ku​,su​+∑f[v])。但是这个是有后效性的,那么就用spfa搞(也可以用类似拓扑的方法做)。每次更新一个点后把所有指向它的点都加到队列里更新即可。代码:#include<queue>#include&l...

2018-10-31 14:06:22

BZOJ2462: [BeiJing2011]矩阵模板

哈希题目传送门二维哈希就好了。注意不要用unsigned long long,会T的(BZOJ 32位机子)。代码:#include<cstdio>#include<cstring>#include<algorithm>#define N 1005#define M 105#define F inlineusing namespace std...

2018-10-30 08:34:20

BZOJ2982 combination

BZOJ2982: combinationlucas题目传送门裸题不解释。代码:#include<cstdio>#include<algorithm>using namespace std;const int p=10007;#define N p+5int t,n,m,c[N],iv[N];int C(int n,int m){ if (n<...

2018-10-29 14:52:46

洛谷P3573 [POI2014]RAJ-Rally(BZOJ3832)

拓扑排序 堆洛谷题目传送门BZOJ题目传送门妙蛙注意到这是一个DAG,那么我们可以一遍拓排求出从起点到iii为最长路ds[i]ds[i]ds[i]和iii到终点的最长路dt[i]dt[i]dt[i](s向所有入度为0的点连边,所有出度为0的点向t连边)。若一条最长路lll经过(u,v)(u,v)(u,v),那么必有l=ds[u]+dt[v]+1l=ds[u]+dt[v]+1l=ds[u]+...

2018-10-29 13:52:35

BZOJ1096: [ZJOI2007]仓库建设(洛谷P2120)

斜率优化BZOJ题目传送门洛谷题目传送门设f[i]f[i]f[i]为前iii个工厂且在iii建仓库的最小代价。那么有f[i]=min{f[j]+c[i]+∑k=jip[k]∗(X[i]−X[k])}f[i]=min\{f[j]+c[i]+\sum_{k=j}^ip[k]*(X[i]-X[k])\}f[i]=min{f[j]+c[i]+∑k=ji​p[k]∗(X[i]−X[k])}。因为第nn...

2018-10-28 19:44:32

BZOJ2721: [Violet 5]樱花(洛谷P1445)

数学BZOJ题目传送门洛谷题目传送门来因式分解。1x+1y=1n!xy−n!(x+y)=0(x−n!)(y−n!)=(n!)2\frac1x+\frac1y=\frac1{n!}\\xy-n!(x+y)=0\\(x-n!)(y-n!)=(n!)^2x1​+y1​=n!1​xy−n!(x+y)=0(x−n!)(y−n!)=(n!)2然后算n!n!n!的因数个数就好了。代码:#i...

2018-10-28 15:14:39

查看更多

勋章 我的勋章
  • 专栏达人
    专栏达人
    授予成功创建个人博客专栏的用户。专栏中添加五篇以上博文即可点亮!撰写博客专栏浓缩技术精华,专栏达人就是你!
  • 持之以恒
    持之以恒
    授予每个自然月内发布4篇或4篇以上原创或翻译IT博文的用户。不积跬步无以至千里,不积小流无以成江海,程序人生的精彩需要坚持不懈地积累!
  • 1024勋章
    1024勋章
    #1024程序员节#活动勋章,当日发布原创博客即可获得