题意： 给定一张n{n}n个点m{m}m条边的无向图。定义割集E{E}E为去掉E{E}E中的边后使得图不连通的边集。定义一个bond{bond}bond为一个极小割集（即bond{bond}bond中边的任意一个真子集都不是割集）。 对每条边，求它在多少个bond{bond}bond中. n<=10,n−1≤m≤n∗(n−1)2{n<=10,n-1\le m\le \frac{n*(n-1)}{2}}n<=10,n−1≤m≤2n∗(n−1)​ bond{bond}bond会将图分为两个连通块。 对每条边，求它在多少个bond{bond}bond中=bond{bond}bond...

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∗(i−d)),[d∣i]{dp_i=max(dp_i,dp_d+cnt_i*(i-d))},[d|i]dpi​=max(dpi​,dpd​+cnti​∗(i−d)),[d∣i]，可以直接用调和级数转移O(Nlog⁡N){O(N\log N)}O(NlogN) 求cnti{cnt_i}cnti​可以直...

考虑最简单的情况，如果三个数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的；反之是terrible{terrible}terrible的。那么一个数组中如果存在相邻三个数的差分递减，那么这个数组不是good{good}good的。 考虑任意三个数的差分不递减，如图所示： 我们只需要满足bk−bk−1>=bk−1−b1{b_k-b_{k-1}>=b_{k-1}-b_1}bk...

在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-1)}{2}+...+\frac{a_n(2*x_n+a_n-1)}{2}=0}2a1​(2∗x1​+a1​−1)​+2a2​(2∗x2​+a2​−1)​+...+2an​(2∗xn​+an​−1)​=0，{xi∣xi∈Z}{\{x_i|x_i\in \Z\}}{xi​∣xi​∈Z} (2∗x1−1...

题解 拍照 从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被选到，所以要分别从前和从后跑一遍最长上升子序列 code 素数 明显的，对于能拆分出奇数个素数的数来说，它们两两之间要么互质，要么大数/小数为非素数。对能拆分出偶数个素数的数也是同理。 按拆分出的素数个数的奇偶把整数集合中的数分为两个集合，两个分别连接源点和汇点，商为质数的两个数连边。那么其实就是求这张图的最小割，然后答案就n−{...

假设当前置顶了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​条信息包含mi{m_i}mi​的概率为min⁡(ki,x)x{\frac{\min(k_i,x)}{x}}xmin(ki​,x)​ 明显的，如果确定了x{x}x，那么每条信息的期望都能确定，取出期望前x{x}x大的信息，就是置顶了x{x}x条信息时能得到的最大期望。 考虑min⁡(ki,x)x{\frac{\...

使得长度大于等于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{k-1}k−1：第一组的点走到第二组，一直走到第k{k}k组。 同理，长度为k∗3{k*3}k∗3的分为一组，属于同一组内的两个点间还没有染色的边都染上颜色 3 所以最少需要kn{\log _kn}logk​n种颜色。 #include <bits/stdc++.h> #define ...

对每个数先分解质因数，每个质因数就能单独计算。那么对于同一个质因子，我们发现问题可以转为合法括号序列问题。 定义l[i]{l[i]}l[i]表示以第i{i}i个数字结尾时，对于所有左端点pos<=l[i]{pos<=l[i]}pos<=l[i]的pos{pos}pos，pos∼i{pos\sim i}pos∼i都可以构成合法区间（前提是l[pos]=pos{l[pos]=pos}l[pos]=pos）。 这么处理l[i]{l[i]}l[i]呢。开一个数组vector<int>st[1e6+7]{vector<int>st[1e6+7]}vector&l...

考虑是把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​之间值在bi∼bj{b_i\sim b_j}bi​∼bj​之间的元素有x{x}x个，值大于bj{b_j}bj​的元素有y{y}y个，值小于bi{b_i}bi​的元素有z{z}z个，那么交换bi{b_i}bi​和bj{b_j}bj​插入的相对位置后当前的逆序数个数为ans+x+1{ans+x+1}ans+x+...

假设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 当n>x{n>x}n>x时，所有的情况都满足条件，所有的人都会在第一回合结束后死亡，dp[n][x]=xn{dp[n][x]=x^n}dp[n][x]=xn 当n≤x{n\le x}n≤x时，先考虑第一回合后还有人存活的情况，假设第一回合结束后有i{i}i个人死亡，为保证不能有赢家i...

import numpy as np import pandas as pd df = pd.read_csv('WA_Fn-UseC_-HR-Employee-Attrition.csv') df.nunique().nsmallest(10) df.drop(['StandardHours'], axis=1, inplace=True) df.drop(['EmployeeCount'], axis=1, inplace=True) df.drop(['Over18'], axis=1, inplace=True) df.isnull().sum() df[df.duplicated(...

我们发现k{k}k可以是答案的前提是线段的长度总和不超过n{n}n。即k∗(k+1)2≤n\frac{k*(k+1)}{2}\le n2k∗(k+1)​≤n，k≤447k\le 447k≤447 令dpi,jdp_{i,j}dpi,j​表示长度为jjj的段的最大和，同时我们已经考虑了后缀iii上所有的元素，并且选择了长度为j,j−1,...,1{j,j-1,...,1}j,j−1,...,1的段，其中段的总和增加。 1.我们可以在长度为j{j}j的段中包含元数i{i}i： dp[i][j]=dp[i+1][j] 2.或者包含元素i{i}i，前提是dpi+j,j−1dp_{i+j,j-1}dp...

nnn为起点，要跳到地面上，每次向上跳需要比之前里地面更近（假设存在状态i−>j,j<ii->j,j<ii−>j,j<i，如果当前有x−>y,j<y<x<ix->y,j<y<x<ix−>y,j<y<x<i，那么之前就跑过i>xi>xi>x了）（i−>ji->ji−>j表示从地面以下iii米跳到地面以下jjj米）。用队列从起点向外扩散，维护前面所有状态能够到达的最高高度mmm，从点iii每次向上跳i−a[i]∼m−1i-a[i]\sim m-1i−a[i...

求递增子序列所有不同的异或值 显然，对于递增子序列x<y<z,ax XOR ay XOR az=Ax<y<z,a_x\ XOR\ a_y\ XOR\ a_z = Ax<y<z,ax​ XOR ay​ XOR az​=A，如果有d>z,ad>azd>z,a_d>a_zd>z,ad​>az​，那么可以得到A XOR dA\ XOR\ dA XOR d 于是有两种方法来通过动态规划转移： 方法一： 按序列的下标...