Dear㉿You

题解

未归档(1)

/ 注册

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

2020牛客国庆集训派对day5 部分题解来自专栏

前言自己还是好菜啊qwq B Hyperdrome 题意：给一个整数n以及一串长度为n的字符串。求他有多少个子区间中的字符能够通过重新排列形成一个回文串。分析：因为能够重新排列，所以不能直接用manacher(这是一个悲伤的故事)。那我们就考虑一个区间能够通过重新排列形成回文串的...

2020-11-02

4 574

2020牛客国庆集训派对day6 部分题解来自专栏

前言好题很多 A Fractions 题意：给出一个n，构造两个数组满足分析：让我们推导一下，假设存在两个数x/a,y/b使得上式成立(为最简式)那么可以得知 a * b = n,枚举n的因数，然后可以得到b，因为是分数，再通过枚举x来计算出y的结果，即for (ll i=2;i<...

2020-10-28

4 568

2020牛客国庆集训派对day7 部分题解来自专栏

前言从23号26号，终归还是找了时间来补了几道题，确实还是太菜了。只勉强A了6道，只要涉及到一些数论或是高级数据结构or 算法，基本上就没思路了。但总归还是得总结一下，也希望能对补题的同学尽绵薄之力 A Laminar Family 题意：有n个点组成的树，有n-1条边。给出m条树上的路径...

2020-10-26

4 648

hdu.5542-The Battle of Chibi 来自专栏

The Battle of Chibi 分析这题不用优化?状态设计：设f [ i ] [ j ] ：长度为 i ，以 a [ j ] 为结尾的严格上升子序列如果要优化的用树状数组+离散化，可以减少一重循环代码(普通) int T;scanf("%d",&T); for (...

2020-10-23

2 732

POJ2376 Cleaning Shifts 来自专栏

Cleaning Shifts 分析此类问题似被统称为——最小区间覆盖问题。首先考虑最简单的转移方程表示覆盖[1,b[i]]的区间的最小代价。考虑优化——快速找到区间最小值。只需要建立一棵线段树，每次查询对应区间，更新。代码 //#pragma GCC optimize(3,"inlin...

2020-10-23

3 665

起床困难综合症来自专栏

起床困难综合症分析为什么有人说他是dp呢可以发现直接枚举m可以得到30分的好成绩ヽ(￣▽￣)ﾉ虽然m不能枚举完，但是把其表示成二进制枚举每一位还是可以做到的。因为每一位只有0|1的情况，根据贪心，从高位开始，判定每一位为0|1能否造成伤害，肯定是先判定0能否使这一位最终答案为1，否则去判断1能...

2020-10-22

3 731

CF337D Book of Evil 来自专栏

Book of Evil 分析如果想要作为一个放置点，那么一个点距离一个魔鬼的最大值不能超过 d 。考虑到最大距离的产生方式——子树内部以及外部。那么可以分两步做求出一个节点距离子树内部的鬼的最远距离从叶子结点更新到根节点开始更新子树外的最远距离，dfs一遍，从上往下更新。更新方式：记...

2020-10-22

3 746

飞扬的小鸟来自专栏

飞扬的小鸟分析直接进入正题单取一个位置来看，假设当前为第 i 列，高度为 j ，这个高度要么是从位置 i - 1 落下来，要么则是点击屏幕飞上来的，这难道不是一个状态转移方程？即枚举当前位置和高度，设为f [ i ] [ j ]，则但是注意，这个空间是有限的——高度不可能低于1或高于...

2020-10-21

4 714

[ZJOI2006]物流运输来自专栏

[ZJOI2006]物流运输分析方法一：这是我一开始想到的一种方法。我可以先预处理出所有的可行路径，因为m范围较小。一个dfs深搜过去，加一个状态压缩，就能得到路径上所有的节点以及路径的花费。剩下的就是dp的事情了。选出每一天的可行路径，然后枚举前一天走的路径。似乎是2^18*2^18，复杂度...

2020-10-19

3 682

对称二叉树来自专栏

对称二叉树分析也没什么好说的。看个图。对于一个节点来说，如果他对称，那么他的每一个节点都一一对应。于是只要跑一遍每一个点及其子树，判断一下每个节点与其对应的节点是否相等(值相等，且子树大小相等)就行了代码 #include<bits/stdc++.h> #define l...

2020-10-19

3 663