2 XSamsara

尚未进行身份认证

暂无相关简介

等级
TA的排名 1w+

LibreOJ 2955. 「NOIP2018」保卫王国【动态DP】

LibreOJ 2955. 「NOIP2018」保卫王国果然是一道裸题,动态DP,必须选就设权值为0,不选设权值为∞\infty∞就可以了。#include<cstdio>#include<cstring>#include<algorithm>using namespace std;typedef long long LL;const int MA...

2019-10-24 14:22:54

【Codeforces】1221D. Make The Fence Great Again【DP】

我们会发现一个规律,每个栅栏的高度最多增加2,所以直接上DP。#include<cstdio>#include<cstring>#include<algorithm>const int MAXN=3e5+5;int T,n,a[MAXN],b[MAXN];long long F[MAXN][3];#include<cctype>int ...

2019-09-26 19:51:42

BZOJ2753: [SCOI2012]滑雪与时间胶囊【最小生成树】

2753: [SCOI2012]滑雪与时间胶囊转化模型,就是最小树形图,有向图最小生成树。看数据范围,好像不能用朱刘算法。我们发现这是一个DAG,那么我们可以先按照高度排序,然后按照权值排序,这样就能保证是一棵树了。#include<queue>#include<cstdio>#include<algorithm>using namespace s...

2019-09-14 16:00:32

BZOJ2395: [Balkan 2011]Timeismoney【最小乘积生成树】

2395: [Balkan 2011]Timeismoney这篇博客写的不错https://www.cnblogs.com/autsky-jadek/p/3959446.html每次求出距离最远的点然后分治就可以了。#include<cstdio>#include<algorithm>const int MAXN=205,MAXE=10005;int n,m,f...

2019-09-13 19:42:57

BZOJ4398: 福慧双修【二进制分组+最短路】

4398: 福慧双修考虑笨蛋,我们可以枚举出边,然后Dij就可以了。显然在菊花图的情况下要T我们考虑分组,对于连1的边,一半强制为出边,一半强制为入边,跑DIJ,然后交换,再做一遍。然后继续分治下去,这样会发现我们所以状态都能做到,复杂度为O(nlog2n)O(n log^2n)O(nlog2n)#include<cstdio>#include<cstring>...

2019-09-09 21:31:29

BZOJ2961: 共点圆【二进制分组|CDQ+凸包+三分】

2961: 共点圆根据圆方程(x−x0)2+(y−y0)2≤(x02+y02)2(x-x_0)^2+(y-y_0)^2 \le (x_0^2+y_0^2)^2(x−x0​)2+(y−y0​)2≤(x02​+y02​)2解得x02+y02≤2xx0+2yy0x_0^2+y_0^2\le 2xx_0+2yy_0x02​+y02​≤2xx0​+2yy0​右边项可以看成(2x,x0)⋅(2y,y0)...

2019-09-09 19:54:39

BZOJ4140: 共点圆加强版【二进制分组+凸包+三分】

4140: 共点圆加强版根据圆方程(x−x0)2+(y−y0)2≤(x02+y02)2(x-x_0)^2+(y-y_0)^2 \le (x_0^2+y_0^2)^2(x−x0​)2+(y−y0​)2≤(x02​+y02​)2解得x02+y02≤2xx0+2yy0x_0^2+y_0^2\le 2xx_0+2yy_0x02​+y02​≤2xx0​+2yy0​右边项可以看成(2x,x0)⋅(2y,...

2019-08-31 22:03:44

BZOJ2428: [HAOI2006]均分数据【模拟退火】

2428: [HAOI2006]均分数据模拟退火就可以了。选择aia_iai​应该放在的位置,然后退火判断一下。#include<ctime>#include<cmath>#include<cstdio>#include<cstdlib>#include<algorithm>const double _T=0.1,EXP_...

2019-08-29 20:38:30

BZOJ2527: [Poi2011]Meteors【整体二分+树状数组】

2527: [Poi2011]Meteors好坑的一题,二分答案,check成功的国家放左边,否则放右边,然后继续分治下去,树状数组维护就可以了。然后就炸longlong了,中间记得check成功就退出。#include<cstdio>#include<vector>using namespace std;const int MAXN=3e5+5;int n,...

2019-08-29 12:18:37

BZOJ1249: SGU277 HERO 动态凸包【凸包+set】

1249: SGU277 HERO 动态凸包我们只需要用一个set维护顺序。#include<set>#include<ctime>#include<cmath>#include<cstdio>#include<cstdlib>#include<algorithm>using namespace std;ty...

2019-08-28 16:16:15

BZOJ2739: 最远点【凸包+决策单调性】

2739: 最远点拆环成链,因为题目给出的是凸包,所以有决策单调性,然后分治就可以了。#include<cmath>#include<cstdio>const int MAXN=500005;typedef long long LL;int T,n,Ans[MAXN];struct point{long long x,y;}p[MAXN];#include&...

2019-08-27 18:38:52

BZOJ2829: 信用卡凸包【凸包】

2829: 信用卡凸包我们不需要考虑圆弧,最后加上一个圆的周长就可以了。然后维护凸包就可以了。以下是维护了上下凸壳求解的。#include<cmath>#include<cstdio>#include<algorithm>const int MAXN=10005;const double pi=acos(-1.0);int n,m,Topsa,...

2019-08-27 12:11:46

BZOJ4372: 烁烁的游戏【动态点分治+线段树】

4372: 烁烁的游戏动态点分治,其实就是将点分树建出来,然后在树上做一些动态操作(不改变树的形态)。对于每一个点,我们用线段树存下这个点的子树中所有原树上距离的权值。然后对于修改直接暴力跳父亲,容斥去重就可以了。询问也同样道理。复杂度O(nlog2n)O(nlog^2n)O(nlog2n)#include<cmath>#include<cstdio>#incl...

2019-08-26 19:27:45

BZOJ3611: [Heoi2014]大工程【虚树+树形DP】

3611: [Heoi2014]大工程首先我们肯定会想到DP求这个答案,但是发现点数实在太多,然后建虚树就可以了。#include<cmath>#include<cstdio>#include<cstring>#include<algorithm>using namespace std;const int MAXN=1e6+5;typ...

2019-08-25 16:59:06

BZOJ3809: Gty的二逼妹子序列【分块】

3809: Gty的二逼妹子序列很容易想到,莫队,然后用树状数组维护,发现复杂度是O(nnlogn)O(n \sqrt{n} logn)O(nn​logn)的。我们考虑如何平衡复杂度用分块代替树状数组,这样询问复杂度O(n)O(\sqrt{n})O(n​),修改复杂度O(1)O(1)O(1),总复杂度O(qn)O(q\sqrt{n})O(qn​)#include<cmath>...

2019-08-24 21:05:04

【Codeforces】848C. Goodbye Souvenir【CDQ】

【Codeforces】848C. Goodbye Souvenir将头尾之差看成各位差。设pre[x]pre[x]pre[x]为与xxx同色的上一个位置。那么答案就是∑i=lr[l≤pre[i]]∗(i−pre[i])\sum_{i=l}^{r} [l \le pre[i]]*(i-pre[i])∑i=lr​[l≤pre[i]]∗(i−pre[i])也就是∑i=1r[l≤pre[i]]∗...

2019-08-24 18:44:56

BZOJ2125: 最短路【圆方树+仙人掌】

2125: 最短路仙人掌上求最短路。将仙人掌转化为圆方树,圆点与方点连的边长为圆点到方点父节点的最短路,Tarjan可以求出。考虑前缀和+LCA,如果LCA为圆点,直接算就可以了。如果为方点,分类讨论是否经过返祖边,就可以了。#include<cmath>#include<cstdio>#include<vector>using namespac...

2019-08-16 20:26:13

BZOJ1023: [SHOI2008]cactus仙人掌图【仙人掌+Tarjan+DP】

1023: [SHOI2008]cactus仙人掌图先考虑树上,那么就是一个DP就可以了考虑环上,我们如果两个点之间距离大于环长一半,那么我们就不可以走这条路径,所以可以先剖环成链,然后单调队列就可以了。#include<vector>#include<cstdio>#include<algorithm>using namespace std;co...

2019-08-16 08:19:00

LibreOJ2305. 「NOI2017」游戏【2-SAT】

2305. 「NOI2017」游戏先不考虑x的地图。这样一看,好像需要3-SAT,其实不需要,我们将每幅图拆成两个点就可以了。但是x就有点恶心了,还好个数不多,所以直接DFS就可以了。数组开小了导致T飞QAQ#include<queue>#include<cstdio>#include<cstring>#include<algorithm&...

2019-08-15 21:32:46

BZOJ4316: 小C的独立集【Tarjan+DP+仙人掌】

4316: 小C的独立集如果这是一棵树,那么很好做,设F[i][0/1]F[i][0/1]F[i][0/1]就可以了。我们考虑每一个环,环的最末端会对最前端有影响。最末端是0,无所谓,最末端为1,那么最顶端只能是0。那我们先处理环外的点,然后考虑一个环,强制最末端为0/1。为1就强制为−∞- \infty−∞ ,分别DP就可以了。#include<cstdio>#incl...

2019-08-15 18:09:32

查看更多

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