首页 > 其他分享 >Educational Codeforces Round 162 (Rated for Div. 2)

Educational Codeforces Round 162 (Rated for Div. 2)

时间：2024-02-25 23:24:31浏览次数：30  
标签：std Educational Rated cin int sum Codeforces kN LL

目录

写在前面

比赛地址：https://codeforces.com/contest/1923。

为唐氏儿的寒假带来了一个构式的结局，飞舞一个。

天使骚骚不太行啊妈的，推了三条线了感觉剧情太白开水了，咖啡馆也是这个熊样子、、、

A

签到。

显然最优的策略是不断地选择最右侧的 1 进行操作，每次操作等价于将最右侧的连续一段左移一位。

操作次数即为第一个 1 与最后一个 1 之间 0 的个数。

//
/*
By:Luckyblock
*/
#include <bits/stdc++.h>
#define LL long long
const int kN = 5e5 + 10;
//=============================================================
int a[kN];
//=============================================================
//=============================================================
int main() {
  //freopen("1.txt", "r", stdin);
  std::ios::sync_with_stdio(0), std::cin.tie(0);
  int T; std::cin >> T;
  while (T --) {
    int n; std::cin >> n;
    int l = 0, r = 0, cnt = 0;
    for (int i = 1; i <= n; ++ i) {
      std::cin >> a[i];
      if (l == 0 && a[i] == 1) l = i;
      if (a[i] == 1) r = i, ++ cnt;
    }
    std::cout << r - l + 1 - cnt << "\n";

  }
  return 0;
}

B

贪心，模拟。

显然最优策略是从近往远攻击。

于是记录距离原点各距离的怪物的总血量，模拟求击败各距离的怪物所需最短时间，若该时间大于距离则输。

//
/*
By:Luckyblock
*/
#include <bits/stdc++.h>
#define LL long long
const int kN = 3e5 + 10;
//=============================================================
int n, a[kN], x[kN];
LL k, suma[kN];
//=============================================================
//=============================================================
int main() {
  // freopen("1.txt", "r", stdin);
  std::ios::sync_with_stdio(0), std::cin.tie(0);
  int T; std::cin >> T;
  while (T --) {
    std::cin >> n >> k;
    for (int i = 1; i <= n; ++ i) {
      std::cin >> a[i];
      suma[i] = 0;
    }
    for (int i = 1; i <= n; ++ i) {
      std::cin >> x[i];
      suma[abs(x[i])] += a[i];
    }

    LL nowt = 0, r = 0, flag = 1;
    for (int i = 1; i <= n; ++ i) {
      if (suma[i] > r) suma[i] -= r, r = 0;
      else r -= suma[i], suma[i] = 0;

      LL need = 1ll * ceil(1.0 * suma[i] / k);
      if (suma[i] % k) r = k - (suma[i] % k);
      nowt += need;
      if (nowt > i) flag = 0;
    }
    std::cout << (flag ? "YES\n" : "NO\n");
  }
  return 0;
}
/*
1
2 1
1 2
1 2
*/

C

构造。

首先 \(b\) 可以随意构造，则数列 \(a\) 中元素的顺序是不重要的，仅需关注某种元素的数量即可。

手玩样例发现，若某数列 \(a\) 不合法，则该数列一定只能被表示为：1 1 1 1 ....（很多 1）的形式，使得无论怎么调整 \(b\) 中元素的顺序都会有某位置同为 1，否则总能通过调整元素的值或是顺序使其合法。考虑将数列 \(a\) 升序排序，令构造的数列 \(b\) 降序排序，则若合法，\(b\) 可以构造类似下列形式：

\[\begin{aligned} &a = 1,1,\cdots 1, 1, &x, y, z \cdots\\ &b = \cdots\ \cdots\ \cdots\ &1, 1, 1 \cdots \end{aligned}\]

设 \(a\) 中原有 \(l\) 个 1，则 \(a\) 合法等价于存在一种 \(b\) 的构造方案使其中 1 的数量至多为 \(m-l\)，即有：

\[\sum_{1\le i\le m} a_i - l \ge 2\times l + 1\times (m - l) \]

即：

\[\sum_{1\le i\le m} a_i\ge l + m \]

前缀和维护区间和与区间 1 的数量即可 \(O(1)\) 查询某区间是否合法。

注意特判区间长度为 1 时必定不合法。

//
/*
By:Luckyblock
*/
#include <bits/stdc++.h>
#define LL long long
const int kN = 5e5 + 10;
//=============================================================
int n, q, a[kN];
LL sum[kN], sum1[kN];
//=============================================================
//=============================================================
int main() {
  //freopen("1.txt", "r", stdin);
  std::ios::sync_with_stdio(0), std::cin.tie(0);
  int T; std::cin >> T;
  while (T --) {
    std::cin >> n >> q;
    for (int i = 1; i <= n; ++ i) {
      std::cin >> a[i];
      sum[i] = sum[i - 1] + a[i];
      sum1[i] = sum1[i - 1] + (a[i] == 1);

    }
    while (q --) {
      int l, r; std::cin >> l >> r;
      LL s = sum[r] - sum[l - 1];
      LL s1 = sum1[r] - sum1[l - 1] + (r - l + 1);
      std::cout << (l != r && s >= s1 ? "YES\n" : "NO\n");
    }
  }
  return 0;
}
/*
1
8 1
1 1 1 1 2 2 2 2
1 8

1
7 1
1 1 1 1 1 1 5
1 7
*/

D

枚举，二分。

首先是非常重要的结论：对于所有不完全相等的区间，都存在一种操作方案使它们可以合并为一个史莱姆，所需时间为区间长度。正确性显然，不断操作其中的最大者即可。

考虑史莱姆 \(i\) 的答案，分吃掉 \(i\) 的史莱姆来自左侧还是右侧讨论。由上述结论，若来自左侧，则用于合成吃掉 \(i\) 的区间 \([l, i - 1]\) 满足：

  • \(1\le l<i\)。
  • \(\sum_{l\le j<i} a_j >a_i\)。
  • \(a_l\sim a_{i - 1}\) 不完全相等。

对于所有满足上述条件的区间合成并吃掉 \(i\) 所需时间为 \(i - l\)，则其中最大的 \(l\) 是最优的。\(a_i\) 为正数，则满足上述条件 2 的位置 \(l\) 可二分求得，为了满足条件 3 仅需再预处理每个数左侧第一个与其不同的数的位置即可。史莱姆来自右侧的情况同理，预处理每个数右侧第一个与其不同的数的位置+二分答案即可求得，上述两种情况取最小值即为答案。

总时间复杂度 \(O(n\log n)\) 级别。

//
/*
By:Luckyblock
*/
#include <bits/stdc++.h>
#define LL long long
const int kN = 3e5 + 10;
//=============================================================
int n, a[kN], fl[kN], fr[kN];
LL sum[kN];
//=============================================================
void Init() {
  std::cin >> n;
  sum[0] = 0;
  a[0] = a[n + 1] = -1;
  for (int i = 1; i <= n; ++ i) {
    std::cin >> a[i];
    sum[i] = sum[i - 1] + a[i];
    if (a[i] == a[i - 1]) fl[i] = fl[i - 1];
    else fl[i] = i - 1;
  }
  for (int i = n; i; -- i) {
    if (a[i] == a[i + 1]) fr[i] = fr[i + 1];
    else fr[i] = i + 1;
  }
}
bool Check(int l_, int r_, LL val_) {
  return sum[r_] - sum[l_ - 1] > val_;
}
void Solve(int pos_) {
  int posl = 0, posr = n + 1;
  for (int l = 1, r = pos_ - 1; l <= r; ) {
    int mid = (l + r) >> 1;
    if (Check(mid, pos_ - 1, a[pos_])) {
      posl = mid;
      l = mid + 1;
    } else {
      r = mid - 1;
    }
  }
  if (posl != 0 && pos_ - posl > 1 && fr[posl] >= pos_) posl = fl[posl];

  for (int l = pos_ + 1, r = n; l <= r; ) {
    int mid = (l + r) >> 1;
    if (Check(pos_ + 1, mid, a[pos_])) {
      posr = mid;
      r = mid - 1;
    } else {
      l = mid + 1;
    }
  }
  if (posr != n + 1 && posr - pos_ > 1 && fl[posr] <= pos_) posr = fr[posr];

  if (posl == 0 && posr == n + 1) std::cout << -1 << " ";
  else if (posl == 0) std::cout << posr - pos_ << " ";
  else if (posr == n + 1) std::cout << pos_ - posl << " ";
  else std::cout << std::min(pos_ - posl, posr - pos_) << " ";
}
//=============================================================
int main() {
  // freopen("1.txt", "r", stdin);
  std::ios::sync_with_stdio(0), std::cin.tie(0);
  int T; std::cin >> T;
  while (T --) {
    Init();
    for (int i = 1; i <= n; ++ i) Solve(i);
    std::cout << "\n";
  }
  return 0;
}

E

dsu on tree。

考虑对于所有节点 \(u\) 维护函数 \(f_{u, c}\) 表示满足下列条件的以 \(u\) 为一端点的路径 \((u, v)\) 的数量：

  • \(1\le c\le n\)。
  • \(a_v = c\)。
  • 除 \(u, v\) 外，路径 \((u, v)\) 上无其他颜色为 \(c\) 的节点。

对于所有 \(u\)，函数 \(f\) 显然可以 dfs \(O(n)\) 求得。考虑枚举节点 \(u\) 并求得以 \(u\) 为 \(\operatorname{lca}\) 的所有合法路径的数量。考虑按顺序枚举 \(u\) 的儿子 \(i\) 进行 dfs 并在求 \(f\) 的过程中求得贡献，若当前枚举到子树 \(i\) 且 \(f_{c}\) 的增量为 \(d_{c}\)，则在更新 \(f\) 前可求得答案的增量为：

\[d_{a_u} + \sum_{c\not= a_u} d_c\times f_c \]

发现仅需令子节点 \(v\) 的 \(f_{v, a_v}=1\) 即可将 \(f_{v, c}\) 变为子树 \(v\) 对 \(f_{u, c}\) 的贡献，存在可继承性，一眼感觉很 dsu on tree 的样子，考虑在 dsu 过程中维护 \(f\) 并在 dfs 求子树贡献时求答案即可。

注意删除子树对 \(f\) 的贡献时也应使用 dfs。

总时间复杂度 \(O(n\log n)\) 级别。

更加显然的做法是基于上述函数 \(f\) 考虑枚举路径两端点的颜色，并在以此颜色为关键点建成的虚树上进行 DP 维护 \(f\) 并计算贡献，复杂度同样为 \(O(n\log n)\) 级别。

//
/*
By:Luckyblock
*/
#include <bits/stdc++.h>
#define LL long long
const int kN = 2e5 + 10;
const int kM = kN << 1;
//=============================================================
int n, a[kN];
int edgenum, head[kN], v[kM], ne[kM];
int dfnnum, sz[kN], son[kN];
int f[kN], vis[kN];
LL ans;
//=============================================================
void Add(int u_, int v_) {
  v[++ edgenum] = v_;
  ne[edgenum] = head[u_];
  head[u_] = edgenum;
}
void AddDfs(int u_, int fa_, int top_) {
  if (!vis[a[u_]]) {
    if (a[u_] != a[top_]) ans += 1ll * f[a[u_]];
  }
  ++ vis[a[u_]];

  for (int i = head[u_]; i; i = ne[i]) {
    int v_ = v[i];
    if (v_ == fa_) continue;
    AddDfs(v_, u_, top_);
  }
  -- vis[a[u_]];
}
void AddDfs1(int u_, int fa_, int top_) {
  if (!vis[a[u_]]) ++ f[a[u_]];
  ++ vis[a[u_]] ;

  for (int i = head[u_]; i; i = ne[i]) {
    int v_ = v[i];
    if (v_ == fa_) continue;
    AddDfs1(v_, u_, top_);
  }
  -- vis[a[u_]];
}
void DelDfs(int u_, int fa_, int top_) {
  if (!vis[a[u_]]) -- f[a[u_]];
  ++ vis[a[u_]];

  for (int i = head[u_]; i; i = ne[i]) {
    int v_ = v[i];
    if (v_ == fa_) continue;
    DelDfs(v_, u_, top_);
  }
  -- vis[a[u_]];
}

void Dfs1(int u_, int fa_) {
  sz[u_] = 1;
  for (int i = head[u_]; i; i = ne[i]) {
    int v_ = v[i];
    if (v_ == fa_) continue;
    Dfs1(v_, u_);
    sz[u_] += sz[v_];
    if (sz[v_] > sz[son[u_]]) son[u_] = v_;
  }
}
void Dfs2(int u_, int fa_, bool son_) {
  for (int i = head[u_]; i; i = ne[i]) {
    int v_ = v[i];
    if (v_ == fa_ || v_ == son[u_]) continue;
    Dfs2(v_, u_, 0);
  }
  if (son[u_]) {
    Dfs2(son[u_], u_, 1);
  }

  for (int i = head[u_]; i; i = ne[i]) {
    int v_ = v[i];
    if (v_ == fa_ || v_ == son[u_]) continue;
    AddDfs(v_, u_, u_);
    AddDfs1(v_, u_, u_);
  }
  ans += f[a[u_]];

  if (!son_) {
    for (int i = head[u_]; i; i = ne[i]) {
      int v_ = v[i];
      if (v_ == fa_) continue;
      DelDfs(v_, u_, u_);
    }
  } else {
    f[a[u_]] = 1;
  }
}
//=============================================================
int main() {
  // freopen("1.txt", "r", stdin);
  std::ios::sync_with_stdio(0), std::cin.tie(0);
  int T; std::cin >> T;
  while (T --) {
    std::cin >> n;
    edgenum = dfnnum = 0;
    ans = 0;
    for (int i = 1; i <= n; ++ i) {
      son[i] = f[i] = sz[i] = head[i] = 0;
    }

    for (int i = 1; i <= n; ++ i) std::cin >> a[i];
    for (int i = 1; i < n; ++ i) {
      int u_, v_; std::cin >> u_ >> v_;
      Add(u_, v_), Add(v_, u_);
    }
    Dfs1(1, 1), Dfs2(1, 0, 0);
    std::cout << ans << "\n";
  }
  return 0;
}

写在最后

学到了什么：

  • D：区间最值。
  • E：发现树上问题中用于统计答案的某函数可由子节点在适当复杂度内转化为父节点的贡献，可考虑 dsu on tree 加速该过程。

标签：std,Educational,Rated,cin,int,sum,Codeforces,kN,LL
From： https://www.cnblogs.com/luckyblock/p/18033328

相关文章

  • Codeforces Round 791 (Div. 2)
     C-RooksDefenders线段树模板，维护：1）v：个数，2）sum：v的个数是否大于0.//#include"bits/stdc++.h"#include"iostream"usingnamespacestd;constintN=2e5;structNode{intl,r,v,sum;}tr1[N*4],tr2[N*4];intn,q;voidbuild(Nodetr[],i......
  • Codeforces 587D Duff in Beach
    不难发现可以按长度为\(n\)分为段。考虑到\(l\)其实并没什么大用，只是说对于选出来的\(b_{1\simx}\)可以都整体移任意段，只需要保证在范围内就行了。进一步的，发现只需要看最后一个数的取值得到其最大可以在的段数即为\(d\)，那么移动的方案数就为\(d-x+1\)。还有的一......
  • Codeforces Round 926 (Div. 2)
    A.升序排列再求和#include<bits/stdc++.h>usingnamespacestd;#defineintlonglongconstintN=1e5+10;#defineinf0x3f3f3f3fvoidsolve(){intn;cin>>n;vector<int>a(n+1);for(inti=1;i<=n;i++)cin>>a[i];sort(a.b......
  • Educational Codeforces Round 162 (Rated for Div. 2)
    EducationalCodeforcesRound162(RatedforDiv.2)A-MovingChips解题思路:模拟一下，不难发现是\(1\)之间\(0\)的个数。代码:#include<bits/stdc++.h>usingnamespacestd;usingll=longlong;usingpii=pair<ll,ll>;#definefifirst#definesesecondusin......
  • Codeforces 1025F Disjoint Triangles
    结论：如果两个三角形不相交，那么一定存在两条内公切线。于是可以考虑枚举这条内公切线的端点\(x,y\)。那么一个三角形的两个端点就会在\(x\toy\)这条线的同一侧，另外一个三角形的两个端点会在这条线的另一侧。同时这条线的一侧与其配对的端点可能是\(x\)也可能是\(y\)。......
  • Codeforces 486E LIS of Sequence
    考虑一个暴力的做法：建立一个超级起点\(a_0=0\)超级终点\(a_{n+1}=\inf\)。求出\(f_i\)代表\(1\simi\)且以\(i\)结尾的\(\text{LIS}\)长度。考虑\(f_i=\max\{f_j+1\}(j<i\landa_j<a_i)\)这个转移的式子，如果\(f_i=f_j+1(j<i\landa_j<a_i......
  • codeforces 1575M Managing Telephone Poles
    假设固定了\((x,y)\)，考虑其和\((x',y')\)的距离\((x-x')^2+(y-y')^2=x^2-2xx'+x'^2+y^2-2yy'+y'^2=(x^2+y^2)+(-2xx'+x'^2)+(-2yy'+y'^2)\)。第一个括号内的式子是个定值，不用管；第二三个式子都是一次函数的形式......
  • Educational Codeforces Round 162 (Rated for Div. 2)
    不会F的场。A答案是最左的\(1\)和最右的\(1\)之间的\(0\)的个数。Code#include<bits/stdc++.h>usingnamespacestd;usingll=longlong;intmain(){ ios::sync_with_stdio(false); cin.tie(0); intt; cin>>t; while(t--){ intn; cin>>n......
  • Educational Codeforces Round 162 [Rated for Div. 2]
    第二次，三道题，剩下的回学校再补，总结：还是需要多练习A：让数列里所有的1都挨在一起，可以看出，相邻1之间有多少个0就需要操作几次，特判：当只有一个1或者原本全是1就输出0；voidsolve(){cin>>n;inttop1=0,top2=0,cnt=0;memset(a,0,sizeof(a));memset(b,0,siz......
  • Codeforces 799E Aquarium decoration
    考虑去枚举能满足\(1,2\)的个数\(l\)，那自然只能满足\(1\)或\(2\)的个数为\(\max\{k-l,0\}\)。对于还剩下的，可以从只能满足\(1,2\)和不能满足任意一个的选出来。显然如果要选就是选最小的。考虑用个数据结构优化这个过程。查询前\(k\)大的和，插入一个数，可以想......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99