19-大数据一班-杨文冠

题解

学习(23) 未归档(1) 练习(1)

/ 注册

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

Codeforces Round #717 (Div. 2) 来自专栏

A. Tit for Tat 思路：(从最高位开始)高位不断减一、最底位不断加一，直到高位都为或者操作了次 MyCode: #include <bits/stdc++.h> using namespace std; const int maxn=1e5+7,maxm=2e5+7,mo...

模拟贪心 XOR 暴力背包 dp 0/1背包思维 LCA 倍增线性筛

2021-04-23

2 737

Making the Grade 来自专栏

题意：给定长度为的序列，构造一个长度为的序列，满足：非严格单调，即不递增或者不递减。最小化思路：这题数据弱，只考虑不递减的情况就可以过，但还要考虑不递增的情况比如我代码中的数据。引理：在满足最小化的前提下，一定存在一种构造序列的方案，使得中的数值都在中出现过。状态表示在完成前个数的构...

线性DP dp

2021-04-17

1 669

LCIS 来自专栏

思路：表示与可以构成以为结尾的的长度。当时，当时，，显然需要满足，因为是以为结尾的。最后枚举为结尾的的长度，找最大的。 MyCode: #include <iostream> #include <cstdio> #include <cstring> #inclu...

线性DP 最长公共上升子序列 dp

2021-04-17

1 653

Mr. Young's Picture Permutations 来自专栏

题目对案例3 2 1解释中，他没有把每个数隔开，注意点就好。思路：满足条件的排列是往右往后都是递减的，求所有的排列数。就像上面图片画的那样，我们对学生的身高降序编号，最高的人编号为，最低的人编号为。那么就是一个简单的填数问题，从依次填入，那么任意时刻每一行中已经填了数一定是从左端开始的连续若干位置...

线性DP dp

2021-04-17

1 913

Cities

题意：把一段相同的形状变成其它任意一个形状，需要使用一次魔法，问最少使用多少魔法能使全是同一个形状。思路：先把连续的缩成一个连续段，假设缩点后有m个段，如果每个互不相同，答案显然是m-1，不管怎样合都对答案没有影响。如果在合并两个区间时，两个区间的左、右端点的值相同，那么可以通过将中间的值赋值成该...

第45届ICPC昆明 dp 区间dp 石子合并

2021-04-08

8 599

Gift

题意：2021年，n个人过生日，做蛋糕需要天，生日那天给第i个人有个好感度，也可以选择送礼物，需要花元，获得个好感度，每个礼物最多买一次。在生日当天做蛋糕，如果只要一天也能赶上。思路：2021年不会出现2月29假设给i个人做蛋糕，j个人发礼物是最优的我们可以爆搜求出表示给j个人发礼物能得到的最大好...

背包第45届ICPC昆明爆搜 dp

2021-04-07

3 623

CodeCraft-21 and Codeforces Round #711 (Div. 2) 来自专栏

A. GCD Sum 思路：虽然，当个位是偶数，然后总体只有奇数个奇数时，一定是大于1的 MyCode： #include <bits/stdc++.h> using namespace std; const int maxn=1e5+10,maxm=2e5+10,mod=1e9+7...

模拟记忆化搜索贪心暴力二进制交互 dp 结论题

2021-03-30

2 618

Educational Codeforces Round 103 (Rated for Div. 2) 来自专栏

总结：A、B、C不是白给题吗，D题dp，需要一些思维，E题拓扑排序(+dfs+字典树)，还是要转个弯cf的题都要转个弯 A. K-divisible Sum 题目大意:构造一个长度为n的数组,每个数是正整数,要求整个数组的和是k的倍数,并且整个数组最大的数最小.输出数组的最大值。思路：首先数组的...

扑朔排序字典树拓扑排序模拟思维 dp

2021-02-01

3 711

E-MAZE 来自专栏

思路：借鉴某位大佬博客，很详细：点击这是一个进阶版的走网格，现在是从上面往左右或者下方走，而且起点和终点是不固定，但起点和终点所在的行数是固定的，同时，还有一些地方是不能走的。我们主要考虑行与行之间的关系，很明显，下一行的某个位置子肯定是由上一行的一些位置走过有来的。假设第行的情况为：那么状态...

线段树 dp

2021-01-27

2 666

P1399 [NOI2013]快餐店

思路：求某个点使得它到图中的所有点的最大距离最小。首先直接找图的直径是不对的，比如环上等距的三个点，然后其中一个点往外扩展了一个点，由于我求出来的点之后按理要放在直径的中点上，但这种情况显然不满足。对于这种带了环的题目（又叫基环外向树），我们一般是断掉环上的某一条边，再作考虑。把环上的某一条边断掉变...

DFS dp

2020-12-18

1 698