19-大数据一班-杨文冠

题解

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

/ 注册

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

Off by One 来自专栏

思路：首先，判断极角相同可以用斜率表示。用一组最小正整数表示一个极角。我们可以将没个极角标号，而对于一个点，我们可以看作它是把两个不同的极角连边。那么问题就变成了：给定一张图，两条边可匹配当且仅当它们连接一个相同的点，求每条边唯一匹配的最大匹配数量。最大边匹配这里有个结论：对于一个无向图，使用...

最大边匹配

2021-05-04

1 562

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 732

Making the Grade 来自专栏

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

线性DP dp

2021-04-17

1 637

LCIS 来自专栏

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

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

2021-04-17

1 643

Mr. Young's Picture Permutations 来自专栏

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

线性DP dp

2021-04-17

1 900

Telephone Lines

思路：如果号点到号点是连通的，那么一定可以完成，反之一定不能完成，输出-1；解法一：分层图最短路图中的每个节点不仅限于“整数编号”，可以扩展到二维，用二元组代表一个节点，表示该点的编号以及第几层，显然在同层移动需要支出费用，向高层移动不需要支出费用。从到有长度为的边，表示端点为的电缆需要付费；从...

分层图最短路二分答案双端队列循环队列 BFS

2021-04-17

1 603

Divide by Zero 2021 and Codeforces Round #714 (Div. 2) 来自专栏

A. Array and Peaks 思路：构造个峰需要个元素，所以如果那么无法构成，否则可以从第二个位置开始放最大的数，每隔一个位置再放一个差值为1的数，放满k个，然后从头往后依次将没有填数的位置填上，依次从剩余的中没有的取掉的数从小到大取。 MyCode: #include <bits...

贪心思维构造分类最小生成树 kruskal算法

2021-04-15

1 828

P7492 序列来自专栏

思路：区间或、求区间最大连续字段和。求区间最大连续字段和就是一个板子，用经典做法线段树维护一个分别表示从左开始的最大子段和，右边开始的，区间的和，区间的答案。因为一个数的二进制位只有30位，而或操作只有将至少一个0变成1才对某个值有影响，所以有效的操作最多只会影响30n次改变，每次区间修改用单点修...

最大连续子段和线段树区间或

2021-04-10

2 801

Parallel Sort

题意：给定长度为n的排列，一次操作你可以选择任意个下标数对：(x1,y1)，(x2,y2)，…(xn,yn)。要求每个下标最多只出现一次。问最少需要几次操作能够将排列恢复为原排列，同时输出每次操作选择的下标。思路：之间连一条边，如果不形成环，那么一次操作就行，如果环上只有两个点，那么也只需要一次...

第45届ICPC昆明思维

2021-04-08

3 658

Cities

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

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

2021-04-08

8 588