zcmimi's blog

categories/刷题记录/共653篇文章

avatar
zc
2019-12-21 19:47:00
查看原题

点击跳转

avatar
zc
2019-12-21 19:47:00
查看原题

点击跳转

排序 贪心

avatar
zc
2019-12-21 19:47:00
查看原题

点击跳转

因为有两条不同的路径,而且没有重边,所以这两个点就在同一个强连通分量里,直接tarjan一遍就可以

avatar
zc
2019-12-21 19:47:00
查看原题

点击跳转

玄学的最短路优化

一看数据范围这么大,一定不能直接做

当你删掉某条边(u,u+1)时,最短路路线为:1->x(<=u)->y(>u)->n,并且x->y一定不会属于原最短路

就是最短路->其他边->最短路

ban:(禁用)

先把所有堵车的边ban掉,然后跑最短路

接着依次加边,跑最短路,就不用清空dis了

d(x,y)xy的最短距离

每个点的答案就是d(1,x)+d(x,n)

所以开一个堆,

枚举被ban的边

把答案和没被ban的边的编号扔进去就可以了

avatar
zc
2019-12-21 19:47:00
查看原题

点击跳转

avatar
zc
2019-12-21 19:47:00
查看原题

点击跳转

先筛选出d_a,d_b,d_c

如果a,b,c的约数都不相同,那么ans = d_a \cdot d_b \cdot d_c

我们来考虑要减去的部分

(a,b,c) , (b,a,c)这样的是不符合的,减去其中一个

也就是减去d(gcd(a,b))\times(d(gcd(a,b)-1))

同理,(a,c,b),(c,b,a)也要减去.

这样的话会多减了一个d(gcd(a,b,c))*(d(gcd(a,b,c))-1),要加回来

...

https://www.luogu.com.cn/blog/lingchi/solution-cf1008d

avatar
zc
2019-12-21 19:47:00
查看原题

点击跳转

avatar
zc
2019-12-21 19:47:00
查看原题

点击跳转

avatar
zc
2019-12-21 19:47:00
查看原题

点击跳转

avatar
zc
2019-12-21 19:47:00
查看原题

点击跳转

36/66
Search
search