题解loathesome p2903 baler

## 题意 给定正整数 $n$，询问是否存在 $k \ge 2$，使得 $n$ 可以表示成 $k$ 个对 $k$ 取模后的结果互不相同的正整数之和。 （$1 \le T \le 10^5, 2 \le n \le 10^{18}$）。 ## 题解 通过分析可得，对于正整数 $n$，$k$ 满足要求的 ......

# P6772 [NOI2020] 美食家 题解（矩阵加速图上dp常用思路） ## 简要题面 给定一张 $n$ 个点 $m$ 条单向边的图，走这条边需要花费 $w_i$ 的时间（以天为单位），现在有一个人从 $1$ 号点出发，最后回到 $1$ 号点，要求走了 **恰好** 为 $T$ 天。 每经过一 ......

# 来源 以前给自己取了一个游戏ID，叫做“科学的自由诗”，那个时候在看接受很多的关于“科学能够改变命运”的观点，所以当时取了这个感觉很有“水平”的ID，。现在建立博客新分类，我想要慢慢建立一个能够体现我的思想，以及引起这些思想的事实的分类，我第一时间就想起了这个ID。 # 分解 * 什么是科学？ ......

[题目传送门](https://www.luogu.com.cn/problem/CF798B) 一道字符串题。 由于 $n$ 非常小，可以暴力枚举字符串。我们可以枚举其中一个字符串 $s_i$，然后让其他的字符串变成 $s_i$，最后记录一下次数，取一个最小值即可。 在枚举第二个字符串的时候可以将 ......

[题目链接](https://www.luogu.com.cn/problem/P4084) 这题我们可以定义一个二维的 dp 数组， 在 dp[i][j]中： i 表示对于节点 i， j 有 1,2,3 三种状态， 表示当点 i 选择被染成颜色 j 时，以 i 为根的这颗子树有多少种染色方法。 那 ......

## 题目大意 给你一棵树，然后定义一个函数 $ f(x,y) $，接下来给你 $ q $ 组询问 $x_{i},y_{i}$，让你求每一次的 $ f(x_{i},y_{i})$。 ## 分析 首先我们尝试根据这个函数的定义暴力求值，代码实现如下。 ```cpp ll BFquery(int g,i ......

# [A 陷阱](https://hydro.ac/d/xiaozhu0602/p/17) 我们可以从 $l$ 枚举到 $d$，再计算是否满足要求，满足要求加入到数组中，输出第一个和最后一个 ``` #include using namespace std; const int N = 1e5 + ......

闲来无事写篇题解 ### [题面传送门](https://www.luogu.com.cn/problem/P4005) ## 简要题意 一条线段上有 $n$ 个点成对连接，求所连的线最小交点数。 ## 思路 看到题目中 $n \le 44$ 自然想到最终复杂度大约在 $O (2 ^ \frac{n ......

原题 题目描述 joe觉得云朵很美，决定去山上的商店买一些云朵。商店里有n多云，云朵被编号为1，2，……，n，并且每朵云都有一个价值。但商店老板跟他说，一些云朵要搭配来买才好，所以买一朵云则与这多云有搭配的云都要买。但是Joe 的钱有限，所以他希望买的价值越多越好。 输入 第1行：n、m、w，表示n ......

#「BJWC2012」冻结题解 ##一.题目 "我要成为魔法少女！" "那么，以灵魂为代价，你希望得到什么？" "我要将有关魔法和奇迹的一切，封印于卡片之中" 在这个愿望被实现以后的世界里，人们享受着魔法卡片（SpellCard，又名符卡）带来的便捷。 现在，不需要立下契约也可以使用魔法了！你还不来 ......

# #1419. [CSP-J 2022] 上升点列 题解 ## **[题目传送门](https://qoj.fzoi.top/problem/1419)** **欢迎大家指出错误并联系这个蒟蒻** 你是第![](https://counter.likepoems.com/get/@fzqojpos ......

简单贪心。 ### 思路 可以发现一号节点必然连向自己。 由于题目中保证了最初每个点都可以到达一号节点。 那么我们发现改完一后，原图变成了一棵十分优美的树。 考虑在树上进行贪心。 我们贪心的从叶子结点往上走。 知道第 $k$ 个若还没要到 $1$，就直接连向一号节点。 这个贪心也比较容易理解。 实现 ......

# #119. 最大整数 题解 **本文章的访问次数为次**。 ## Part 1 提示 - **[题目传送门](https://qoj.fzoi.top/prob ......

# #105. 「USACO1.3」Ski Course Design 题解 **你是第个看到这篇文章的人。** ## Part 1 提示 - **[题目传送门]( ......

## 题意 给定一个长度为 $n$ 的正整数数列 $a$，求 $$\sum\limits_{i = 1}^{n}\sum\limits_{j = 1}^{n} \gcd\left(a_i, a_j\right) \times \gcd\left(i, j\right)$$ （$1 \le n,a_i ......

## Part I Preface - [原题目$\text{(Luogu)}$](https://www.luogu.com.cn/problem/AT_abc106_c) - [原题目$\text{(AtCoder)}$](https://www.luogu.com.cn/remoteJudge ......

## Part I Preface - [原题目$\text{(Luogu)}$](https://www.luogu.com.cn/problem/AT_abc106_c) - [原题目$\text{(AtCoder)}$](https://www.luogu.com.cn/remoteJudge ......

## Part I Preface - [原题目$\text{(Luogu)}$](https://www.luogu.com.cn/problem/AT_abc106_b) - [原题目$\text{(AtCoder)}$](https://www.luogu.com.cn/remoteJudge ......

## Part I Preface - [原题目$\text{(Luogu)}$](https://www.luogu.com.cn/problem/AT_abc106_a) - [原题目$\text{(AtCoder)}$](https://www.luogu.com.cn/remoteJudge ......

## 题意 有两个长度为 $n$ 的正整数列 $A,B$。表示数 $i$ 可以填到 $A_i$ 或 $B_i$ 两个位置中的一个。问删去空位之后可以形成的排列种数。 （$ 1 \le n \le 5 \times 10^5$，$A_i,B_i$ 取遍 $\left[1, 2n\right]$）。 # ......

[题目链接](https://www.luogu.com.cn/problem/CF858E) 一点模拟下下火。首先一定不能覆盖的，只能一点一点挪。将已经在合法位置上的去掉，剩下的测试分为四类： 1. 不碍事的样例测试。 2. 不碍事的常规测试。 3. 占据了样例测试位置的常规测试。 4. 占据了常 ......

# [A 查找最大元素](http://acm.hdu.edu.cn/showproblem.php?pid=2025) 扫一遍确定最大值，如果是最大值输出字符和"(max)"，不是的话只输出字符 ``` #include #include using namespace std; char max ......

一道很好的矩阵题，可以尝试作为矩阵转移的优质练习题。 ### 思路 考虑由于黑点在原图中处于联通的状态。 分三种情况讨论。 1. 上下左右联通。 考虑这种情况下，不断分形后。 最终产生的依然是一整个的大连通块。 故，答案为一。 2. 上下左右都不连通。 那么每一次分形后就会产生黑色点个连通块。 最终 ......

[problem](https://www.luogu.com.cn/problem/AT_arc145_c) & [blog](https://www.cnblogs.com/liangbowen/p/17640112.html)。 小清新结论题。 ~~提供一个不需要脑子就可以 AC 的方法：看样 ......

[题目链接](https://www.luogu.com.cn/problem/AT_abc284_e) 这题就是很简单的图上深搜，我觉得放在E题太水了，代码里有详细注释。 ```cpp #include using namespace std; #define int long long vect ......

神仙思维题，那我的评价是太妙了。 ### 思路 我们发现正的十分难以维护这个过程。 考虑可以倒着进行这个操作。 容易发现对于整块，我们找到在前面第一个小于它的 $a_i$。 然后就会有一个贡献的转移，$f_i=f_{now}\times \frac{a_{now}}{a_i}$。 至于散块，我们发现 ......

计数题好题。 ### 思路 考虑 $\dbinom{n+k}{k}$ 的几何意义。 即从 $(1,1)$ 到 $(k,n)$ 只往上或往右走的方案数。 由于这个在几何上坐标可以平移。 也就是 $(1-x,1-y)$ 到 $(k-x,n-y)$ 的方案与 $(1,1)$ 到 $(k,n)$ 的方案数是 ......

特别有意思的思维题。 ### 思路 参考题解第一位的神仙思路。 将排列 $a_i$ 变为 $b_{a_i}$。 限制便变为了只能交换相邻的两个差大于 $k$ 的点。 那么这个限制就已经与普通排序很相似。 考虑使用归并排序。 一个点可以跑到其他点的前面要求这一连续段都是比它加 $k$ 都不大。 在归并 ......

可以看做一道比较套路的的 $kruskal$ 重构树。 但或许也是一道复习与入门的好题。 ### 思路 考虑把图论问题转化为树上问题。 发现所求的为路径上最大的最小。 容易想到 $kruskal$ 重构树。 发现由于从两端一起走，不能直接处理。 那么就可以在外面套一个二分，内部直接倍增处理即可。 # ......

比较简单的题。 ### 思路 考虑这个玩意在几何上的意义。 发现就是要么往上走，要么往右走。 那么就十分容易找到规律。 找到规律后也很容易感性理解。 ### Code [AC记录](https://atcoder.jp/contests/agc002/submissions/44663312)。 ......