一衍一

分类

cf补题(1) 区域赛真题练习(6) 未归档(44) 题解(71)

/ 注册

全部文章（共133篇）

Running Median

题意:输出数组的中位数懵逼的题解:每次数组排序...我不知道为什么这个能过,时间复杂度:我怎么算这个时间复杂度也会炸的呀....... //ac code #include<bits/stdc++.h> typedef long long ll; using namespace s...

2020-04-08

0 612

黑白树

题意:给一颗白色的树,然后进行染色,问最少要多少次可以,把整颗树染成黑色,染色标准是:每个节点都有一个值, 节点到根的链上（包括节点与根）所有与节点i距离小于的点都会变黑.题解:贪心,根据题意可以将树退化成,一条线,如:对于下图,圈内表示,所以我们答案应为2次,可以选择倒数第二个节点,一直到根...

2020-04-07

0 749

树

题意:给一棵树进行染色,并且要保证(x,y)成立,也就是从X节点到y节点的颜色相同题解:因为题目没有对节点进行要求(虽然给定节点的边的关系)此题看上去是一个染色，其实任意两个相同颜色的点对，之间都的一个颜色，那就是一个联通分量全是一个颜色。树，就可以看做是一个点集合，挑哪些点染同一种颜色。显然是DP...

2020-04-06

1 719

数码

题意:给定两个整数 l 和 r ，对于所有满足1 ≤ l ≤ x ≤ r ≤ 10^9 的 x ，把 x 的所有约数全部写下来。对于每个写下来的数，只保留最高位的那个数码。求1～9每个数码出现的次数。题解:最先想到的是枚举[L,R]区间内的每一个数,然后求和,即便最快的也要 ,超时我们发现只用写出最...

2020-04-04

2 873

Shortest Path

题意:把图中所有节点分成对点,然后把分成的每对点的距离求和,并且要求和最小题解: 典型的树形结构所以我们考虑的时候,如果当前节点的子节点数为偶数那是否表示,不需要额外添加边如图(图有点丑.....)对于下面的那个节点他有偶数个节点,两两配对即可而对于子节点有奇数个,那么两两配对,对于小小根还剩余1...

2020-04-03

0 644

月月查华华的手机

题意:给定字符串S,以及给定T,可以按照字符出现顺序在S中任意挑取,判断是否可以构成T例如: S=abcde,T=bd--->输出YES S=abcde,T=bb--->输出NO题解:预处理,反向存储第个字符出现的位置就是表示从第位开始, 的每个字母出现的,距离的最近位置所...

2020-04-01

0 661

Rinne Loves Edges

题意:把输入的S点做为根节点,然后把输入的图看成一棵树,使的树中的所有叶子节点与跟节点都不存在一条通路为什么说是可以看成树, 因为n个节点m条边的无向连通图,又因为M条边,M+1个节点,emmm...数据结构教材上树的定义魔改后可以这样看题解:树形DP(今天刚学,逃..........)什么是树形D...

2020-03-31

0 574

滑动窗口

题意:就是一个区间k向右移动,然后先输出区间每次移动后的区间里面最小的,结束后,换行,再下来再输出最大的题解:板子st表 #include<cstdio> #include<algorithm> #include<iostream> ...

2020-03-29

0 720

数学考试

题意:在长度为n的区间上选取长度为k的两个区间,且两个区间不相交,然后输出两个区间求和,并且最大题解:先求一个前缀和sum,然后正着dp1数组,就是dp1[i]=max(dp1[i-1],sum[i]-sum[i-k])再按照dp1的原理反着求dp2数组然后再过一遍求最大值 #include<...

2020-03-27

0 548

合并回文子串

题解:假设a[i][j]与b[k][l]可以构成,那么就是可以得到:dp[i][j][k][l]表示上述状态,然后根据回文性质推出上图转载自:https://blog.csdn.net/weixin_39909619/article/details/90256332时间复杂度:四个for,........

2020-03-26

0 733