998244353

题解

Atcoder(3) C/C++(21) Codeforces(6) study(2) 动态规划(2) 图论(1) 基础知识(30) 字符串(2) 思维(15) 技巧(1) 搜索(1) 搜索基础(1) 数论(5) 未归档(14) 简单题解(1) 线段树(8) 贪心(1)

/ 注册

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

涂色PAINT

题意：给定一个长度为的颜色序列，初始颜色序列无颜色每，次可以选择使得都变成一种颜色，问最少多少次可以使得整个区间变成给定的颜色序列。数据范围：，还是baidu才知道的~。题解：由于数据范围很小且涉及到区间操作，所以考虑区间。表示将涂成状态转移：对：当，涂时可以顺便把涂了，涂时可以顺便把涂了，...

2020-07-31

0 447

兔子的区间密码

题意：给定，在中选取两个数使得两数异或值最大。数据范围：题解：考虑二进制形式，则二进制的最高位最高越好，同时选取的两个数二进制位不同的部分越多越好。考虑一个极端情况：即答案的二进制形式为那么取,取则两者异或答案最大。这里的为，则为。对于和,当两者的二进制最高位相同时，无论怎么选择最高位对最终...

2020-07-30

0 515

Xor Path

题意：给定一棵个点的树，每个点有点权，问树上所有两点之间的最短路径异或和为多少，即求树上所有两点的路径所经过的点的点权的异惑和。题解：既然是考虑异或和，那么就要考虑一个点是否对答案有贡献。考虑一个点在所有路径中出现的次数，由异或的性质，可以知道当一个点在所有路径中出现总次数为偶数时，则对答案无贡献...

2020-07-29

2 749

Max Power

题意：给定一个倒三角，共行，第行有个元素，选取必须先选取和，现在要求选择个元素，求选取的个元素可以获得的最大值。题解：学习参考了该篇题解：https://blog.nowcoder.net/n/4f95681bfb9e4bf29b49ce9aa321248d由于选择一个元素，以其作为倒三角的顶点...

2020-07-29

2 631

最短路

题意：给定一个个点条边的无向连通图，所有边边权均为，次询问，每次询问图中两点的最短路径，保证无自环与重边。数据范围：题解：由于是无向连通图，一眼看上去是一个不可做题。卡了很久很久才发现了数据范围有点不寻常，考虑最多有条多余的边，其余边可以组成一棵树。那么如果是一棵树则可以先预处理后用，本题相较于...

2020-07-28

0 640

区间权值

题意：给定长度为的序列和,求，其中，答案对取模数据范围：题解：先计算首先考虑长度为的继续考虑长度为的，考虑取第一项的的，第二项的，...以此到最后一项取的。所以从第二项开始每项的第一个元素都多了出来即多了，即答案为再考虑长度为的，第一项取的，第二项取，第三项取,...最后一项取得；继续取...

2020-07-26

0 414

乌龟棋

题意：共个格子，每个格子有相应的分数，张卡牌，卡牌上的数字表示可以从当前格子往后走格，初始在一号格，自动得到一号格的分数，问选择卡牌进行走格子的方式中可获得的最大值为多少。数据范围：，卡牌数字，每种卡牌数量为，保证题解：这种数据范围自然想到的是爆搜加剪枝。由于最多有个状态，因为先使用一次号牌再使用...

2020-07-25

1 484

小A的柱状图

题意：给定个矩形的宽和高，求可以得到的矩形的最大面积。题解1：本题一眼看上去就是笛卡尔树的题，可惜笛卡尔树当时学到半路放弃了。回想过来笛卡尔树是由单调栈延伸过来的，所以考虑能不能用单调栈瞎搞。本题的难点在于如何处理一定宽度和高构成的矩形面积，即可能更长的宽度和较短的高度也会构成更大的面积。考虑单调...

2020-07-24

0 447

F. Fraction Construction Problem

题意：给定，求出满足的任意一组。数据范围：，，且题解：通分得到：，那么自然会考虑到分子分母对应相等解决。当，令，此时这时候，故直接令，那么可以构造出，那么此时需要分解成两个互质的部分，且均不为，否则判那么预处理内的质数，并处理出每个数的最小质因子，就可以分解了。分解成功后进行[](htt...

2020-07-18

2 573

青蛙过河

题意：类似汉诺塔问题，但是需要分析细节。题解：荷叶数为，石墩数为。当，那么最多先个到荷叶，第个到终点。当，那么最多个到荷叶和石墩，然后荷叶上的个再到石墩。情况转换为的情况，两者相加即当，那么最多先个到荷叶和石墩1，然后荷叶上的到石墩1，之后再有个到荷叶和石墩2，然后这个到石墩1。情况转换为了的情况...

2020-05-13

1 570