文章

1. 题目 传送门=￣ω￣= 2. 题解 我太蒻了，唉。。。写好久 我们首先设 $L[i]$表示在位置 $i$左边的第一个比 $K[i]$大的数字的位置 $R[i]$表示在位置 $i$右边的第一个比 $K[i]$大的数字的位置 那么： 点对 $(L[i], R[i])$可以提供 $P1$的战斗力（显 阅读更多…

题目描述 给你平面上三行的一些点，求一条经过所有点的最短回路。 数据范围 y 坐标小于等于 300，x 坐标小于等于 3000，每一行的点数小于等于 1300. 题目分析 虽然给的 solution 写的挺清晰的，但是我还是没看懂…… 然后打开标程，发现是 pascal 的& 阅读更多…

题目描述 给你一张有向图，求： 1. 图中最大强连通分量的大小 2. 至少加多少条边才能够让其变成一张强连通图 3. 一种加边的方案 数据范围 $n \leq 10^4,m \leq 2 \times 10^5$，至少要加的边数小于等于 1000. 题目分析 首先 tarjan 跑一次缩点，轻松求出 阅读更多…

题目分析 首先把所有等于 0 的 b 值改为等于-1，然后设 $s_i$表示从 i 开始的 b 的后缀和。 1. 对于 $s_1=0$且 $s_i=0$的 i 的数量大于等于 m 个的情况，显然答案是 0，方案就用一个单调队列扫一遍就知道了。 2. 对于 $s_1=0$且 $s_i=0$的数量小于 阅读更多…

感谢 ZYF 同学提供解题思路 思路：考虑面向队长编程 另外听说当年 HNOI 数据有误，正解只有 60 多分 代码： /* * 队长快跑.cpp * This file is part of 队长快跑 * * Copyright (C) 2018 – xzy * * 队长快跑 is free so 阅读更多…

题目分析 有人问起我学会的第一个高级数据结构是什么。 我说是 spaly。 在 HNOI2017 的考场上学会的。 俗话说的好，双旋的 splay，单旋的 spaly，不旋的 saply，O(1) 的 asply，那么我们就来用 splay 做一做这道题。 首先我们手模一发单旋最小值操作。会发现，假 阅读更多…

与素数玩耍 例题： loj6235 区间素数个数 设 $sum(x)$表示小于等于 x 的素数个数。 假设我很蠢（这件事根本不用假设好吗)，连 10 以内的素数有哪些都不知道，只知道 1 不是素数。那么我就会令 $sum(x)=x-1$ 然后我就会做一些事情来扔掉合数，于是我从小到大处理素数。假设 阅读更多…

1. 题目 传送门=￣ω￣= 题意： 设 $\sigma_0(a)$为 $a$的约数个数 设： $$f(a)=\sigma_0(a^3)$$ 求： $$\sum _ {i=1} ^ {n} f(i)$$ 2. 题解 不难发现 $f(x)$是个积性函数。 求前缀和的话直接上扩展埃氏筛即可。 扩展埃氏筛 阅读更多…

1. 题目 传送门=￣ω￣= 2. 题解 好吧我承认我把这题写复杂了 QvQ KB 又把这题秒杀了 Orz 但还是很有意思的 QvQ 蒟蒻我写的是扩展埃氏筛 复杂度约为 $O(L^{0.7}+R^{0.7})$ 并且不需要 $R-L≤1000000$这个条件（也就是说题目把 $R$开到 $10^{ 阅读更多…

题目大意 给定一张 n 个点 m 条边的无向连通图, 初始时每个点均为白色。每次你可以选择一条两个端点颜色相同的边, 并将它们一起变色 (白变黑, 黑变白)。你需要求出将每个点均变为黑色的最少步数。 数据范围 $$1 \leq n \leq 10^5, n-1 \leq m \leq n$$ 题目分 阅读更多…