2 Stargazer.

尚未进行身份认证

有りふれた幸せでいいの

等级
TA的排名 8k+

【Codeforces 538 H】Summer Dichotomy(二分图染色)

传送门显然是不能在一起的连边后二分图染色似乎可以直接用setsetset维护一下可行的点染色不过更简单的是如果有三个[li,ri][l_i,r_i][li​,ri​]互相不交显然无解可以得到若不考虑t,Tt,Tt,T的限制显然n1=max⁡l,n2=min⁡rn_1=\max l,n_2=\min rn1​=maxl,n2​=minr是一个可行解若n1+n2<tn_1+n_2&...

2020-04-02 21:55:54

【Codeforces 538 G】Berserk Robot

传送门好像没用什么算法。。。考虑把坐标(x,y)→(y+x,y−x)(x,y)\rightarrow(y+x,y-x)(x,y)→(y+x,y−x)然后每一步位移变成(+‾1,+‾1)(\underline +1,\underline +1)(+​1,+​1)再每步x,yx,yx,y都额外+1+1+1后除以2那每个信息的(x,y)→((x+y+t)/2,(y−x+t)/2)(x,y)\r...

2020-04-02 21:44:38

【TopCoder 2013 2A 1000】ThePowers(容斥)

传送门考虑对于每个非次方底数求答案考虑所有x满足xr≤A,xr+1>Ax满足x^{r}\le A,x^{r+1}>Ax满足xr≤A,xr+1>A的非次方底数分一组这个可以先二分再容斥求出考虑对于每一个,变成求i∈[1,log⁡xA],j∈[1,B]i\in [1,\log_xA],j\in[1,B]i∈[1,logx​A],j∈[1,B]不同的ijijij个数考虑对于每...

2020-04-02 21:36:16

【HDU 4273】Rescue(三维凸包)

传送门先建出三维凸包求出重心后求到每个面的距离即可求重心的方法是定一个点每个面变成三棱锥,三棱锥的重心为坐标之和然后按体积比例带权求和即为重心点到面的距离用面的叉积点乘点到面上某点即为面的面积乘点到面距离#include<bits/stdc++.h>using namespace std;#define cs const#define re register#de...

2020-04-02 21:28:31

【模板】【洛谷 P4724】三维凸包(增量法)

传送门先随机扰动一下变成每个面都恰好只有三个点考虑增量法每次新加一个点,把所有从这个点能看到的面删去加入新的面大概就是这样(图是洛谷题解区搬来的)判断ppp是否能看到一个面(v1,v2,v3)(v1,v2,v3)(v1,v2,v3)就是看((v2−v1)∗(v3−v2))•(p−v1)((v2-v1)*(v3-v2))•(p-v1)((v2−v1)∗(v3−v2))•(p−v1...

2020-04-02 21:23:56

【2020省选模拟】题解

NoipNoipNoip模拟?T1直接树剖即可维护各凭本事我是维护的轻儿子之和,所以细节要多很多直接维护所有儿子之和似乎好做一些标记永久化了,但似乎还是跑最慢。。。#include<bits/stdc++.h>using namespace std;#define cs const#define pb push_back#define pii pair<i...

2020-04-02 14:32:48

【Codeforces 536 D】Tavas in Kansas(最短路 / 博弈论 / DP)

传送门首先考虑对S,TS,TS,T求出到每个点最短距离后离散化值域变成O(n)O(n)O(n)对于每个点看做a[diss][dist]=paa[dis_s][dis_t]=p_aa[diss​][dist​]=pa​那么问题就变成在二维平面上做设f[0/1][x][y]f[0/1][x][y]f[0/1][x][y]表示先/后手,在≥x,≥y先/后手,在\geq x,\geq y先/后手...

2020-04-01 21:33:31

【洛谷 P3222】【HNOI2012】射箭(半平面交 / 二分答案)

传送门列出限制是li≤axi2+bxi≤ril_i\le ax_i^2+bx_i\le r_ili​≤axi2​+bxi​≤ri​可以变成a,ba,ba,b之间的大于小于关系另外有a>0,b<0a>0,b<0a>0,b<0如果询问某关是否可行半平面交即可由于单调性二分答案即可可以先排序一次,这样复杂度就是O(nlogn)O(nlogn)O(nlog...

2020-04-01 18:54:27

【洛谷 P3249】【HNOI2016】矿区(最小左转法 / 生成树)

传送门最小左转法:用来将平面图转成对偶图先将线段拆成两个有向线段考虑对于每个有向线段(u→v)(u\rightarrow v)(u→v)在vvv连出的有向线段中按极角找(v→u)(v\rightarrow u)(v→u)的下一个这样一定恰好形成一个平面另外将整个图形外面的也看做一个点查找可以用vectorvectorvector按极角排序每次二分复杂度O(nlogn)O(nlog...

2020-04-01 18:50:29

【HDU 6097】Mindis(圆的反演)

传送门先对P,QP,QP,Q关于原点反演,CCC为反演的常数反演前后显然到圆上点距离比为∣C∣/dis(p)|C|/dis(p)∣C∣/dis(p)然后变成找圆上点XXX满足XP+XQXP+XQXP+XQ最小如果PQPQPQ过圆则答案为PQPQPQ否则XXX在PQPQPQ中垂线上#include<bits/stdc++.h>using namespace std;#de...

2020-04-01 18:36:03

【HDU 6158】The Designer(圆的反演)

传送门对切点反演之后就是两个平行线之间赛圆直接做即可,在圆的面积足够小的时候breakbreakbreak即可#include<bits/stdc++.h>using namespace std;#define cs const#define pb push_back#define pii pair<int,int>#define ll long long...

2020-04-01 18:32:05

【HDU 4773】Problem of Apollonius(圆的反演)

传送门定一个常数RRR和反演中心OOO反演就是对于每一个点AAA变换到A′A'A′满足OA∗OA′=R2OA*OA'=R^2OA∗OA′=R2,其中A,A′,OA,A',OA,A′,O共线对于反演有如下性质:1、圆反演之后还是一个圆(过反演中心的变成一条直线,视为特殊的圆)2、一条直线反演之后为过OOO的圆3、反演之后圆之间关系(相交 / 切 / 离)不变圆的反演设反演中心为OOO...

2020-04-01 18:29:04

【LOJ #3273】「JOISC 2020 Day1」扫除(线段树分治 / 线段树)

传送门考虑对于所有被扫除过的点有若xi≤xj,则yi≥yjx_i\le x_j,则y_i\geq y_jxi​≤xj​,则yi​≥yj​即所有灰尘位置是单调的先考虑没有插入的情况对于一次修改,有可能其中一部分地方被之前的一次操作修改过而因此现在这一块没有灰尘,这一块就是这次修改影响不到的地方、考虑用权值线段树维护每个位置可以修改得到的地方比如如果之前有一次l=l0l=l_0l=l...

2020-03-30 20:05:37

【省选模拟】 Fac(生成函数 / 拉格朗日反演 / 组合数学)

题意:∀i∈[0,n),求ki!(ki−i)!\forall i\in[0,n),求\frac{ki!}{(ki-i)!}∀i∈[0,n),求(ki−i)!ki!​考场用快速阶乘的套路整了一个nnlognn\sqrt nlognnn​logn结果只有暴力分考虑求的(kii−1)/i∗((ki−i+1)∗i!){ki\choose i-1}/i*((ki-i+1)*i!)(i−1ki​)/i∗(...

2020-03-29 18:24:06

【UOJ #424】【集训队作业2018】count(矩阵快速幂 / 生成函数 / NTT)

传送门考虑实际上就是深度不超过mmm的nnn个点的笛卡尔树计数设fi(x)f_i(x)fi​(x)为深度不超过iii的生成函数那么有fi(x)=fi−1(x)xfi(x)+1f_i(x)=f_{i-1}(x)xf_i(x)+1fi​(x)=fi−1​(x)xfi​(x)+1fi(x)=11−xfi−1(x)f_i(x)=\frac{1}{1-xf_{i-1}(x)}fi​(x)=1−xfi...

2020-03-28 19:08:14

【LOJ #6268】分拆数(DP / 生成函数)

可以参见EIEIEI的博客传送门首先有一个exp⁡\expexp的O(nlogn)O(nlogn)O(nlogn)做法这里考虑Ferrers图Ferrers图Ferrers图从左上角向右下截一个最大的正方形设正方形边长为hhh那么剩下两部分就都是≤h\le h≤h的整数拆分即可以列出分拆数的生成函数∏i≥111−xi=∑h≥1xh2(∏k=1h11−xk)\prod_{i\geq...

2020-03-28 18:56:10

【AtCoder Grand Contest 043 C】Giant Graph(博弈论 / FWT)

传送门显然贪心直接选i+j+ki+j+ki+j+k最大的更优发现由于建图可以对于每个图分别做小的往大的连形成DAGDAGDAG,发现独立集可以看做组合游戏于是求出SGSGSG函数后fwtfwtfwt即可#include<bits/stdc++.h>using namespace std;#define cs const#define re register#defin...

2020-03-28 18:23:27

【AGC 043 D】 Merge Triplets(DP)

传送门考虑这个排序的过程如果Ai,j≥Ai,j+1A_{i,j}\geq A_{i,j+1}Ai,j​≥Ai,j+1​那么Ai,j,Ai,j+1A_{i,j},A_{i,j+1}Ai,j​,Ai,j+1​在PPP中一定连续也就是说一个AiA_iAi​在PPP中可能分成1,1,1;1,2;31,1,1;1,2;31,1,1;1,2;3几种可能的长度组合考虑DPDPDP这样一个长度组合那么...

2020-03-28 18:16:18

【洛谷 P5282】【模板】快速阶乘算法(倍增 / MTT / 拉格朗日插值)

传送门考虑分成B=nB=\sqrt nB=n​块分别求即设f(d,x)=∏i=1d(x+i)f(d,x)=\prod_{i=1}^d(x+i)f(d,x)=∏i=1d​(x+i)则考虑求出f(B,0),f(B,2B)....f(B,B∗B)f(B,0),f(B,2B)....f(B,B*B)f(B,0),f(B,2B)....f(B,B∗B)剩下的一点直接乘即可对于这个考虑倍增即考虑...

2020-03-28 18:13:58

【Codeforces #1322 C】Instant Noodles

传送门考虑到有gcd(a,b+a)=gcd(a,b)gcd(a,b+a)=gcd(a,b)gcd(a,b+a)=gcd(a,b)所以实际上对于所有可能的N(S)N(S)N(S)只需要统计所有SSS满足不存在子集S′S'S′使得,S−S′和N(S)−N(S′)S-S'和N(S)-N(S')S−S′和N(S)−N(S′)非空即对于右边每个点将左边相连的点集合相同的加在一起,所有取gcdgcdg...

2020-03-25 21:34:56

查看更多

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