__故人__

题解

CF(8) UOJ(1) 每日一题(3) 牛客小白月赛27(10) 算法模板(10) 随笔(20)

/ 注册

全部文章 / 题解（共116篇）

[SCOI2009]游戏

分析我们先引入一个概念，置换。这里我简单的说一下，就是把个元素的其它排列与原排列的映射关系。可以用一个数组表示。而这个道题就是给出一个置换，求有多少个不同的循环。为什么置换存在循环。不难发现，如果把每个数字看作一个节点，那么每个节点都有一个后驱节点和一个前驱节点，所以出度和入度都为 ...

2020-09-18

9 1450

牛客挑战赛42 F

分析分析题意，我们可以发现它就是要让求。而是可以线性筛求出来的。所以现在问题就是如何维护矩阵中的。因为，所以可以考虑二维莫队这样的时间复杂度为。这道题卡空间，要注意线性筛时可以不用额外数组记录。后话关于牛客挑战赛42的题就算补完了，可以说这套题还是不错的，只是有些题面稍...

2020-09-18

4 535

牛客挑战赛42 E

分析令为以结尾的最小代价。，后面的可以前缀和优化一下。。令为的决策点，那么可以化简为。那么这个就是个一次函数。其中，所以为了让最小，那么我们显然要让最小。那么现在就是要求的最小值，放在坐标轴上，就是求直线与所有一次函数的最小值，这个可以李超线段树来求...

2020-09-17

3 571

联合权值

分析每条边的边权为，由于输入的图是一颗树，那么之间有且仅有一条简单路径，所以合法的点对中间只会有一个点。所以考虑枚举中间的节点。令表示节点为中间节点的权值之和，那么。因为，所以可以先考虑有序点对的值最后再就好了。所以，表示在为中间点，为当前考虑点，已...

2020-09-17

7 795

牛客挑战赛42 D

分析类似这样的式子，其实我们普通的快速幂是没法解决的，所以考虑拓展欧拉定理。而题面上已经保证了，所以可以直接根据的来化简了，我们现在已经把幂降下来了。现在原问题等同于求这个东西。那么我们现在有个初步的想法，令表示，因为这个是在意义下进行的，所以考虑枚举有多少...

2020-09-17

5 561

The XOR-longest Path

分析在一颗树上寻找一条异或值最大的简单路径。先考虑到异或有如下性质。所以异或两个相同的值时等同于没有异或。所以，树上的简单路径的异或值其实可以看做。表示节点到根的异或和。因为的值计算了两次，相当于是抵消了。那么题目转化为，在一个序列上找两个节点使他们的异或值最大。显然这个过程需要...

2020-09-16

6 1122

牛客IOI周赛18-提高组 A

分析这个可以暴力求出一个循环内的变换。这样可以考虑置换乘法的结合率，然后把置换拆成循环。这样是可以通过的。但是其实现在等同于只有一个操作重复次，这个其实可以倍增优化，时间复杂度为。代码 #include<bits/stdc++.h> using namespace std; ...

2020-09-16

4 696

牛客IOI周赛18-提高组 C

分析这题是一个经典的组合数学的题。先说题解的证明我是看不会的，以下给出一个较为简便的理解。先说明不下降和不上升子序列没有本质区别，只需要讨论一种即可。简化问题给你一个长度为的序列，要求每个元素，求不下降子序列的方案数。先考虑到对于一个一个集合一定只对应一个序列。那么我们转化一下 ...

2020-09-16

4 637

牛客IOI周赛18-提高组 B

分析在比赛中没有做出了，对矩阵的掌握还是太菜了。先对与原问题考虑。我们发现这个问题其实并不好考虑，其中涉及的状态太多，但是考虑一下用全部方案减去不合法的方案来计算。。先看前面的。这里有两种理解。考虑在每个点后面是否划分那么总的方案数为。也可以用插板法来理解，那么我们总的方案数为 ...

2020-09-15

5 541

CF522D

分析考虑只有一个区间有一对相同的值时才有答案。所以我们可以把所以点对存下来，这样是。考虑如果有多个相同的话，其实只需要储存相邻的两个即可，这样就只有级别的点对了。再考虑如果有一个大区间包含了一个小区间证明，如何任何时候大区间不可能是最优解，最后做一次区间最小值就好了。代码 #includ...

2020-09-15

9 861