您的位置:首页 > 健康 > 美食 > 写作网站不屏蔽_河北省工程造价信息网官网_自己创建网页_seo是什么的

写作网站不屏蔽_河北省工程造价信息网官网_自己创建网页_seo是什么的

2024/12/25 13:07:33 来源:https://blog.csdn.net/qq_72715438/article/details/142638116  浏览:    关键词:写作网站不屏蔽_河北省工程造价信息网官网_自己创建网页_seo是什么的
写作网站不屏蔽_河北省工程造价信息网官网_自己创建网页_seo是什么的

A. Max Plus Size

分别假设答案为取第偶数位的最大值和取第奇数位的最大值两种情况, 取更优解.

取偶数位的最大值时, 把所有其他都偶数位都取上. 奇数同理.

code:

int solve(int _) {int n;cin >> n;vector<int>a(n + 1);int Maxj = 0, Maxo = 0;for (int i = 1; i <= n; ++i) {cin >> a[i];if (i % 2)Maxj = max(Maxj, a[i]);else Maxo = max(Maxo, a[i]);}int ans2 = n / 2;int ans1 = n / 2 + n % 2;return max(ans1 + Maxj, ans2 + Maxo);
}

B. All Pairs Segments

先把输入的 a 数组 sort 一下.

对于每个 a i a_i ai 分别由有 a i + 1 a_{i+1} ai+1 ~ a n a_n an, 共 n − i n-i ni 个区间有贡献, 只用从前往后遍历每个 a a a, 实时更新当前有多少个区间在做贡献.

当前的总有效区间为 n o w now now 个, 加入第 i i i 个节点时.

  1. 新增了以他为左端点的 n − i n-i ni 个区间, n o w + = n − i now+=n-i now+=ni.
    所以 a [ i ] a[i] a[i] 这个点被 n o w now now 个区间覆盖.
  2. 减少了以他为右端点的 i − 1 i-1 i1 个区间, n o w − = i − 1 now-=i-1 now=i1.
    所以 a [ i ] + 1 a[i]+1 a[i]+1 ~ a [ i + 1 ] − 1 a[i+1]-1 a[i+1]1 n o w now now 个区间覆盖.

注意, a[n] 是一个特例.

code:

#define int long long
void solve(int _) {int n, q;cin >> n >> q;vector<int>a(n + 1);for (int i = 1; i <= n; ++i) {cin >> a[i];}map<int, int>ma;sort(1 + a.begin(), a.end());int now = 0;for (int i = 1; i <= n; ++i) {now += n - i;ma[now]++;now -= i - 1;if (i != n)ma[now] += a[i + 1] - a[i] - 1;}while (q--) {cin >> n;cout << ma[n] << " ";}cout << endl;
}

C. Cards Partition

** 答案没有二分性**, fk, 赛时写了一个小时的二分.

答案的范围为 [ 1 − n ] [1-n] [1n], 只用枚举每个答案, 然后 O ( 1 ) O(1) O(1) 做 check.

check:

对于答案 x x x, 也就是这些牌要排成 x x x 行.

先求至少要多少列 c l m clm clm;

  1. c l m > 最多元素的个数 clm > 最多元素的个数 clm>最多元素的个数, 因为这些不能在同一列.
  2. 如果 M a x e l e m e n t ∗ X > s u m o f a l l e l e m e n t Max_element * X > sum_of_all_element MaxelementX>sumofallelement, 那就是所有牌摆 M a x e l e m e n t Maxelement Maxelement 列用不完, 还要加新列, 此时 i128 clm = max(Max, sum / i + !!(sum % i));

c l m clm clm 求出来了, 检查空的位置是否小于 k k k 就好, 只要有解且 k k k 够用, 就一定能填出来.

code:

#define int long long
#define i128 __int128
int solve(int _) {int n, k;cin >> n >> k;vector<int>a(n + 1);i128 sum = 0;int Max = 0;for (int i = 1; i <= n; ++i) {cin >> a[i];Max = max(Max, a[i]);sum += a[i];}sort(1 + a.begin(), a.end());int ans = 0;for (int i = 1; i <= n; ++i) {i128 clm = max(Max, sum / i + !!(sum % i));if (clm * i - sum <= k)ans = i;}return ans;
}

D. Speedbreaker

注意到: 所有小于 t t t 的数都包含在一个长度不大于 t t t 的区间内时, 对于这个区间, 一定有解 ( 可以从这个区间的最小值开始往两边扩散, 哪边吉往哪边去).

那么对于所有的 t = i t=i t=i 都可以维护一个上述区间. 遍历每一个区间: 此时对于这个区间 [ l , r ] [l,r] [l,r], 可行的答案是 [ m a x ( 1 , r − t + 1 ) , m i n ( n , l + t − 1 ) ] [max(1,r-t+1),min(n,l+t-1)] [max(1,rt+1),min(n,l+t1)]( 分别从区间两头往另一头走长度为 t t t 的区间).

对于所有区间求并集即可. 注意到如果数组中没有小于等于 t 的数, 那它对应的区间就是全部.

code:

int n, a[200010];
int solve(int _) {cin >> n;for (int i = 1; i <= n; ++i) {cin >> a[i];}vector<pair<int, int>>tle(n + 1);tle[n] = {1, n};for (int i = n - 1; i >= 1; --i) {auto [l, r] = tle[i + 1];while (l <= r && a[l] > i)l++;while (r >= l && a[r] > i)r--;tle[i] = {l, r};if (r - l + 1 > i)return 0;}vector<int>pre(n + 2, 0);int cnt = 0;for (int i = 1; i <= n; ++i) {auto [l, r] = tle[i];if (l <= r) {cnt++;int ll = min(l, max(1, r - i + 1));int rr = max(r, min(n, l + i - 1));pre[ll]++;pre[rr + 1]--;}}int ans = 0;for (int i = 1; i <= n; ++i) {pre[i] += pre[i - 1];if (pre[i] == cnt)ans++;}return ans;
}

E. Tree Pruning

所有叶子与根的距离 <=> 保留所有 d e e p deep deep 相同的节点. 于是可以对这个树跑一个层次 bfs, 对每层的答案取 m i n min min.

在每层:

  1. 维护去除高于它的点, 要删除多少边:
    即对每一个高于它的点 x,从 x 往上回溯, 直到到 x 的某个祖先, 且这个祖先有一个深于 x 的孙子, 停止. 同时个每个边打个 id, 回溯到已删除的 边也要停止.
  2. 低于它要删除多少边: 就是这层所有节点的 son 的数量.

code:

#define int long long
#define id(a,b) ((a)*1000000+(b))
const int Maxn = 5e5 + 10;int n, v, u;
int dep[Maxn], son[Maxn], ans[Maxn], fa[Maxn], Maxdep[Maxn];
vector<int>eg[Maxn];
set<int>se;
void getdep(int x, int deep) {dep[x] = deep;Maxdep[x] = deep;for (auto c : eg[x]) {if (c == fa[x])continue;fa[c] = x;getdep(c, deep + 1);Maxdep[x] = max(Maxdep[x], Maxdep[c]);}
}
int getson(int x) {son[x] = 0;for (auto c : eg[x]) {if (c == fa[x])continue;son[x] += getson(c);}return son[x] + 1;
}
int done(int x, int fromdep) {if (x == 1)return 0;if (fromdep < Maxdep[x])return 0;if (se.count(id(x, fa[x])))return 0;se.emplace(id(x, fa[x]));return done(fa[x], fromdep) + 1;
}
int solve(int _) {cin >> n;se.clear();for (int i = 1; i <= n; ++i) {eg[i].clear();Maxdep[i] = 0;}for (int i = 1; i < n; ++i) {cin >> v >> u;eg[u].emplace_back(v);eg[v].emplace_back(u);}int ans = n - 1;getdep(1, 1);getson(1);for (int i = 1; i <= n; ++i) {debug(i, fa[i], son[i])}int last = 1, now = 0, ended = 0, pre_ended = 0;deque<int>q;q.emplace_back(1);while (!q.empty()) {int tis = q.front();q.pop_front();if (dep[tis] != last) { // 上一层删除完了,ans = min(ans, ended + now);debug(last, ended, now)now = 0;ended += pre_ended;pre_ended = 0;last = dep[tis];}now += son[tis];if (eg[tis].size() == 1) {int tp = done(tis, dep[tis]);debug(tis, tp);pre_ended += tp;}for (auto c : eg[tis]) {if (fa[tis] == c)continue;q.emplace_back(c);}}ans = min(ans, ended + now);return ans;
}

版权声明:

本网仅为发布的内容提供存储空间,不对发表、转载的内容提供任何形式的保证。凡本网注明“来源:XXX网络”的作品,均转载自其它媒体,著作权归作者所有,商业转载请联系作者获得授权,非商业转载请注明出处。

我们尊重并感谢每一位作者,均已注明文章来源和作者。如因作品内容、版权或其它问题,请及时与我们联系,联系邮箱:809451989@qq.com,投稿邮箱:809451989@qq.com