19-大数据一班-杨文冠

题解

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

/ 注册

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

Bonds

题意：给定一张n{n}n个点m{m}m条边的无向图。定义割集E{E}E为去掉E{E}E中的边后使得图不连通的边集。定义一个bond{bond}bond为一个极小割集（即bond{bond}bond中边的任意一个真子集都不是割集）。对每条边，求它在多少个bond{bond}bond中. n<...

高维前缀和

2021-12-01

1 536

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

D1. Divan and Kostomuksha (easy version) 记dpidp_idpi表示把gcd⁡{\gcd}gcd为i{i}i的一组数放到前面的贡献，cnti{cnt_i}cnti表示含有因子i{i}i的数的个数。状态转移方程有：dpi=max(dpi,dpd+cnti∗...

dp gcd

2021-11-29

1 775

E. AmShZ and G.O.A.T. 来自专栏

考虑最简单的情况，如果三个数a、b、c(a<b<c){a、b、c(a<b<c)}a、b、c(a<b<c)，有b−a<=c−b{b-a<=c-b}b−a<=c−b，那么这三个数是非terrible{terrible}terrible的；反之是ter...

数学贪心

2021-11-25

1 605

D. Not Quite Lee 来自专栏

在bbb中选出n{n}n个数aia_iai，这个子序列是好的当且仅当能找到满足如下条件的x{x}x： a1(2∗x1+a1−1)2+a2(2∗x2+a2−1)2+...+an(2∗xn+an−1)2=0{\frac{a_1(2*x_1+a_1-1)}{2}+\frac{a_2(2*x_2+a_2-...

数学

2021-11-24

1 617

题解 | #校庆#

题解拍照从1∼n{1\sim n}1∼n和从n∼1{n\sim 1}n∼1分别跑一遍最长上升子序列，枚举最高的人i{i}i时，计算1∼i{1\sim i}1∼i和n∼i{n\sim i}n∼i之和，取和最大的i{i}i。（枚举最高的人i{i}i时要保证i{i}i被选到，所以要分别从前和从后跑一遍...

dp 最长上升子序列 ac自动机最大流最小割线段树二分 KM 括号匹配

2021-11-23

2 490

E. Messages 来自专栏

假设当前置顶了x{x}x条信息，学生i{i}i对信息mi{m_i}mi的期望贡献如下：如果mi{m_i}mi没被置顶，那么贡献为0 如果mi{m_i}mi被置顶了，那么选出1{1}1条信息包含mi{m_i}mi的概率为1x{\frac{1}{x}}x1，选出ki{k_i}ki条信息包含...

概率分类

2021-11-23

2 595

F. Defender of Childhood Dreams

使得长度大于等于k{k}k的路径包括至少2种颜色，也就是说只要考虑长度为k{k}k的路径。长度为k{k}k的分为一组，相邻点的边染上1，组内的路径最长是k−1{k-1}k−1 长度为k∗2{k*2}k∗2的分为一组，属于同一组内的两个点间还没有染色的边都染上颜色 2，颜色全为2的路径，最长为k−1...

构造

2021-11-11

1 479

G. Kuzya and Homework

对每个数先分解质因数，每个质因数就能单独计算。那么对于同一个质因子，我们发现问题可以转为合法括号序列问题。定义l[i]{l[i]}l[i]表示以第i{i}i个数字结尾时，对于所有左端点pos<=l[i]{pos<=l[i]}pos<=l[i]的pos{pos}pos，pos∼i{...

栈括号匹配

2021-11-11

1 623

E. Optimal Insertion 来自专栏

考虑是把b{b}b序列中的元素插入到a{a}a序列中，b{b}b序列插入的相对位置一定是值小的在前面。对bi<bj,i<j{b_i<b_j,i<j}bi<bj,i<j，当前得到ans{ans}ans对逆序数，bi、bj{b_i、b_j}bi、bj之间值在...

线段树树状数组逆序数离散化

2021-11-10

1 563

E. Arena 来自专栏

假设dp[n][x]{dp[n][x]}dp[n][x]为有n{n}n个人活着，每个人的体力值范围为1∼x{1\sim x}1∼x的方案数。考虑以下几种情况：当n==2{n==2}n==2时，只有两个人的体力值相同时才满足条件，dp[n][x]=x{dp[n][x]=x}dp[n][x]=x 当...

DP dp

2021-11-05

1 758