Phecda_

分类

未归档(109)

/ 注册

全部文章（共109篇）

LibreOJ#2362蚯蚓

蚯蚓很奇妙的一道题. 显然的暴力: 用堆维护,好了,没了. 复杂度\(\Theta((n+m)\times log_2{(n+m)})\),当然这个不紧,因为堆的大小不是每时每刻都是\(n+m\)的. 看起来是非常优秀的复杂度,但我们看数据范围: \(n\le 10^5,m\le 7\times...

单调性队列

2019-10-08

0 401

LibreOJ#2359天天爱跑步

天天爱跑步这或许现在不是\(NOIP\)最毒瘤的题了叭. (当然你说是,我还可以肛你说\(NOIP\)没了) 嗯...一个很显然的暴力思路是: 对于每一个玩家,暴力跟着跑,走到\(w_i\)等于当前时间的点就统计. 这显然是对的...但它太慢了,完全跑不过去. 我们发现题目里给的条件其实是个...

差分桶 dfs 线段树合并 LCA

2019-10-08

0 448

ZROI十一集训Day2

ZROI十一集训Day2 比赛链接 1.添开局几何懵逼题. 内心:WOC,这什么毒瘤题? 冷静分析\(\times 1:\)好像答案不会超过\(3?\) 冷静分析\(\times 2:\)这好像是对的... 冷静分析\(\times 3:\)完蛋,举出反例了. 冷静分析\(\times 4:...

线段树贪心分类讨论离散化平衡树

2019-10-07

0 356

CodeForces1230

CodeForces1230A CodeForces1230A 题目并不难,只需要注意不要犯**错误即可. **错误包括但不限于:以为要两两一组分两组和判断两部分是否相等时总和与总和-当前集合比较... #include <algorithm> #include <iostre...

CodeForces

2019-09-27

0 417

模拟退火

Summary 退火总结.退火其实不难...难的是怎么调参. 贡献两页提交才只有$55pts$的经历真是惨不忍睹.这就是调参的艰难. 主要就是这么几个参数: \(T_0,T,d,T_e\). 分别是初温,当前温度,降温系数,终止温度. 主要就说一下降温系数叭. 这个东西,呃,很玄乎,你改个$0.$...

随机化

2019-09-25

0 788

ZROI#1007

ZROI#1007 也是看起来非常不可做的一个题. 仔细思考,发现了一个很$cooooool$的事情: 他是不是让我求最小独立集覆盖... 一个独立集覆盖是指把图划分成若干个子集,每个子集里的点两两互不连通. 然后你$2^n$枚举子集,记录是不是一个独立集,然后在独立集上$DP$. 你就...

DP 状压DP 最小独立集覆盖二进制枚举子集

2019-09-23

0 449

ZROI#1006

ZROI#1006 可能一眼看起来是个很不可做的题,但你仔细思考一下,你发现.....给的是个$n$个点$n$条边的东西... 那么它可能是个啥呢? 是个基环树?是个森林+环?是个基环树+森林? 都是有可能的! 然后我们发现,答案就是连通块个数+环数-1. 为什么呢? 假设有$x$个连通块,$y$...

bfs dfs 找环图论 nature 贪心

2019-09-23

0 409

ZROI#1005

ZROI#1005 非常令人迷惑的一个题... 首先,我们发现,那个$M$并没有什么卵用. 于是我们直接不鸟它. 然后我们发现我们需要找一个最小的糖浆的集合$S$. 使得下式成立: \(\sum_{i\in S}{k_i*v_i}=N\) 其中$k_i$表示第$i$种糖浆选了几份,$v_i$表示糖...

DP 最短路背包

2019-09-23

0 389

ZROI#1004

ZROI#1004 需要一点数学基础的题目叭,我因为比较菜,观察能力不够,所以卡了半个小时叭. 我们化一化原式: \[(x^2+y)^2\equiv (x^2-y)^2\pmod p\] \[x^4+2x^2y+y^2\equiv x^4-2x^2y+y^2\pmod p\] \[2x^2y\e...

数论离散化二分查找逆元

2019-09-23

0 429

DP合集

石子合并区间\(DP\),入门题.环状\(DP\)先考虑线段. 我们用一个区间\([l,r]\)表示石子,意义为该石子是由\([l,r]\)区间的石子合并而来. 显然,最终一定只剩一堆石子\([l,r]\),且\(\exists k\)使得\([l,r]\)先合并为\([l,k]\)和\([k+...

DP

2019-09-19

0 394