musik wordpress,北京公司排名seo,高定网站,南阳商城站Codeforces 1091E 题意#xff1a;给定n个点的度数#xff0c;请你添加第n1个点#xff0c;输出所有可能的第n1个点的度数 做法#xff1a;1. 查看链接知道了下面这个定理 A sequence of non-negative integers $ d_1\geq\cdots\geq d_n$ can be represented as the degree… Codeforces 1091E 题意给定n个点的度数请你添加第n1个点输出所有可能的第n1个点的度数 做法1. 查看链接知道了下面这个定理 A sequence of non-negative integers $ d_1\geq\cdots\geq d_n$ can be represented as the degree sequence of a finite simple graph on \(n\) vertices if and only if $ d_1\cdotsd_n$ is even and\(\sum _{i1}^{k}d_{i}\leq k(k-1)\sum _{ik1}^{n}\min(d_{i},k)\) holds for every k in \({\displaystyle 1\leq k\leq n}\). 2.排序之后\([low(p), up(p)]\) 表示在\([p, p1]\) 之间插入新的点度数\(d_t\)的取值范围。 (1) \(d_{p1} \leq d_t \leq d_p\) (2) 当 \(d_t\) 在不等式左侧时\[ d_t \leq k(k1)\sum _{ik1}^{n}\min(d_{i},k1) - \sum _{i1}^{k}d_{i}, p \leq k \leq n \\ \Downarrow \\ up(p) min(up(p 1) , p(p1) \sum_{ip1}^n min(d_i,p1) - \sum_{i1}^p d_i) \] (3) 当 \(d_t\) 在不等式右侧时\[ \sum_{i1}^k d_i - k(k-1) - \sum_{ik1}^n min(d_i,k) d_t , 1 \leq k \leq p \\ \Downarrow\\ low(p) max(\sum_{i1}^p d_i - p(p-1) - \sum_{ip1}^n min(d_i,p), low(p-1)) \\ \] 3.猜测答案为连续的一段值将上一步求出的区间并起来 4.又因为无向简单图每条边对度数贡献为2由此可以确定答案的奇偶性 5.确定上下界时需要维护\(\sum_{i k1}^{n} min(d_i,k)\) 和\(\sum_{i k}^{n} min(d_i,k)\) 我们倒着枚举\(k\)用优先队列维护小于等于当前\(k\)的集合以及这个集合内所有元素的和就可以预处理出这个式子因为k是递减的因此保证了正确性 6.一定要分析清楚再写。。。代码细节很多 #include bits/stdc.h
typedef long long ll;
constexpr int N 600005;
constexpr ll inf 1e18;
using namespace std;
int n;
priority_queuell q;
ll f1[N], f2[N], sum[N], low[N], up[N], d[N];
int main() {scanf(%d,n);for(int i 1; i n; i) scanf(%lld,d[i]);sort(d1,d1n); reverse(d1,d1n);for(int i 1; i n; i) sum[i] sum[i-1] d[i];d[0] n; d[n1] 0;for(int i 0; i n; i) up[i] inf, low[i] -inf;ll tmp 0;for(int i n; i 0; --i) {while(!q.empty() q.top() i) tmp - q.top(), q.pop();f2[i] tmp 1ll*(n - i - q.size())*i;if(d[i] i) q.push(d[i]), tmp d[i];f1[i] tmp 1ll*(n - i 1 - q.size())*i;}for(int i n; i 0; --i) {if(i!n) up[i] min(up[i1], 1ll*i*(i1) f1[i1] - sum[i]);else up[i] 1ll*i*(i1) - sum[i];}for(int i 1; i n; i) {low[i] max(low[i-1], sum[i] - 1ll*i*(i-1) - f2[i]);}for(int i 0; i n; i) low[i] max(low[i], d[i1]), up[i] min(up[i], d[i]);ll L inf, R -inf;for(ll i 0; i n; i) if(low[i] up[i]) L min(L, low[i]), R max(R, up[i]);if(L R) printf(-1);for(ll i L; i R; i) if(!((sum[n]-i)1)) printf(%lld ,i);puts();return 0;
} 转载于:https://www.cnblogs.com/RRRR-wys/p/10203438.html
