zhangxixi的博客

本文搬运自本人初中博客园博客，若图片加载不出来，可到原文查看：https://www.cnblogs.com/zhangtingxi/p/15569311.html 题目链接 这道题正好让我在noip前复习了一次缩点。 首先题目里有这么一句话。 另外，如果存在A到B的连接的同时也存在B到A的连接的话，那么A和B实际上处于同一局域网内，可以通过本地传输，这样花费的传输时间为0。 这不就是在提示我们要用缩点吗？ 他希望知道从他的电脑（编号为1），到小X的电脑（编号为n）所需要的最短传输时间。 最短时间，就是弄个最短路就行。由于缩点后是DAG图，所以可以用dp。 我用的是dp。（其...

本文搬运自本人初中博客园博客，若图片加载不出来，可到原文查看：https://www.cnblogs.com/zhangtingxi/p/15568359.html 题目链接 题外话： 一道纯最小生成树的题，能出道蓝我也真服了… 本文默认使用kruskal算法，主要是因为另一种我不会 首先我们先满足 kkk 条一级道路，对所有道路按一级道路造价排序，然后用最小生成树的做法选出 kkk 条边。 对于剩下的道路按二级造价排序，然后同理继续选即可。 时间复杂度 O(nlog⁡n)O(n\log n)O(nlogn) 需要注意的是题目输出格式有误，后面是输出具体方案。第一个数代表选的边的编...

本文搬运自本人初中博客园博客，若图片加载不出来，可到原文查看：https://www.cnblogs.com/zhangtingxi/p/15564095.html 题目链接 题目 “余”人国的国王想重新编制他的国家。他想把他的国家划分成若干个省，每个省都由他们王室联邦的一个成员来管理。 他的国家有 NNN 个城市，编号为 1…N1\ldots N1…N。 一些城市之间有道路相连，任意两个不同的城市之间有且仅有一条直接或间接的道路。 为了防止管理太过分散，每个省至少要有 BBB 个城市。 为了能有效的管理，每个省最多只有 3×B3\times B3×B 个城市。 每个省必须有一个省会...

本文搬运自本人初中博客园博客，若图片加载不出来，可到原文查看：https://www.cnblogs.com/zhangtingxi/p/15562734.html 题目链接 一道很好的最短路+dp。 先考虑最后结果，设 dpidp_idpi​ 表示前 iii 天的最小费用。设 f(i,j)f(i, j)f(i,j) 为从第 iii 天到第 jjj 天都走同一条道路的最小费用。 f(i,j)f(i, j)f(i,j) 很好求，提前预处理这段时间内哪些点不能走然后再可以走的点内跑一遍最短路即可。 转移： dpi=min⁡j=1i(dpj+f(j+1,i)×(i−(j+1)+1)+k)d...

本文搬运自本人初中博客园博客，若图片加载不出来，可到原文查看：https://www.cnblogs.com/zhangtingxi/p/15558545.html 题目链接 和atc之前的一道题类似，都是暴力广搜+记录状态。 从开始状态开始广搜，然后直接拿个map或者哈希记录状态即可。 时间复杂度为: O(9!)O(9!)O(9!)，因为最多也只有这么多种状态。 Code 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556// ...

本文搬运自本人初中博客园博客，若图片加载不出来，可到原文查看：https://www.cnblogs.com/zhangtingxi/p/15558415.html 题目链接 设 dp(i,j)dp(i, j)dp(i,j) 为前 iii 行放 jjj 个棋子的方案数， lenilen_ileni​ 为第 iii 行的列数。 类似背包的思想，每一行放或不放： dp(i,j)=dp(i−1,j)+dp(i−1,j−1)×(leni−(j−1))dp(i, j)=dp(i-1, j)+dp(i-1, j-1)\times(len_i-(j-1)) dp(i,j)=dp(i−1,j)+dp...

本文搬运自本人初中博客园博客，若图片加载不出来，可到原文查看：https://www.cnblogs.com/zhangtingxi/p/15558214.html 线性求逆元 当初做洛谷模板题的时候还没发现原来这就是线性求逆元，现在发现了才知道原来这么好用。 首先我们要求 [1,n](modp)[1,n]\pmod p[1,n](modp) 的逆元。 第一，我们知道： 1−1≡1(modp)1^{-1}\equiv1\pmod p 1−1≡1(modp) 现在我们要求 i(modp)i\pmod pi(modp) 的逆元，肯定的，我们可以把 ppp 拆分成： p=k×i+rp=k\...

本文搬运自本人初中博客园博客，若图片加载不出来，可到原文查看：https://www.cnblogs.com/zhangtingxi/p/15558203.html 题目链接 考虑每次都做一次拓扑排序。 如果所有节点未遍历，即存在环。 否则的话，如果结果唯一，即拓扑层数为 nnn，判断队尾层数是否为 nnn 即可。 否则结果不唯一。 由于最多只有26个字母，所以时间过得去。 —————————————————————————————————— 说一下我做题时的几个坑点： 每次做拓扑排序时不要修改入度。 输出的是最早能体现出的操作。 至于漏.: 什么的，推荐使用cp edi...

本文搬运自本人初中博客园博客，若图片加载不出来，可到原文查看：https://www.cnblogs.com/zhangtingxi/p/15558033.html 题目大意 我们称一个集合 S=(x1,y1),(x2,y2),…,(xk,yk)S={(x_1, y_1), (x_2, y_2), … , (x_k, y_k)}S=(x1​,y1​),(x2​,y2​),…,(xk​,yk​) 是好的，当且仅当把它们按照 yiy_iyi​ 降序排序后满足： 对于所有满足 3≤j≤k3 ≤ j ≤ k3≤j≤k 的 jjj，有 xj−2<xj<xj−1x_j−2 <...

本文搬运自本人初中博客园博客，若图片加载不出来，可到原文查看：https://www.cnblogs.com/zhangtingxi/p/15553942.html 题目链接 题外话： 这题应该没有蓝题难度吧，就是道树状数组模板题+一些小思维 利用前缀和思想，答案很明显为 rrr 之前的区间总数- lll 之前的区间总数，即 rrr 之前的左端点数目- lll 之前的右端点数目。分别用两个树状数组维护即可。 时间复杂度 O(nlog⁡2n)O(n\log_2n)O(nlog2​n)。 1234567891011121314151617181920212223242526272829...