Codeforces Round 902 (Div. 2, based on COMPFEST 15 - Final Round)

写在前面

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

呜呜铃果唱歌太好听了、、、

我宣布是第二喜欢的声线，第三喜欢是东北切蒲英，第一喜欢绝赞招募中。

这下不得不成为数码推了、、、

A

答案为 \(-\sum a_i\)。

懒得写代数式子推了，赛时看完题直接去手摸样例了，打 ACM 打的。

B

首先进行一次代价为 \(p\) 的通知，然后可以将村长看做一个 \(a = \infin, b = p\) 的人。

发现代价 \(b\) 均为通知一个人的代价，于是显然再选择前 \(n-1\) 小的代价即可。

排个序即可。

//
/*
By:Luckyblock
*/
#include <bits/stdc++.h>
#define LL long long
const int kN = 1e5 + 10;
//=============================================================
int n, p;
struct AdmireVega {
  int a, b;
} a[kN];
//=============================================================
inline int read() {
  int f = 1, w = 0; char ch = getchar();
  for (; !isdigit(ch); ch = getchar()) if (ch == '-') f = -1;
  for (; isdigit(ch); ch = getchar()) w = (w << 3) + (w << 1) + (ch ^ '0'); 
  return f * w;
}
bool cmp(AdmireVega fir_, AdmireVega sec_) {
  return fir_.b < sec_.b;
}
//=============================================================
int main() {
  //freopen("1.txt", "r", stdin);
  int T = read();
  while (T --) {
    LL ans = 0;
    n = read(), p = read();
    a[0].a = n, a[0].b = p;
    
    ans = p;
    for (int i = 1; i <= n; ++ i) a[i].a = read();
    for (int i = 1; i <= n; ++ i) a[i].b = read();
    std::sort(a, a + n + 1, cmp);
    for (int i = 1, j = 0; i < n; ++ i) {
      while (a[j].a <= 0) ++ j; 
      ans += a[j].b;
      -- a[j].a;
    }
    printf("%lld\n", ans);
  }
  return 0;
}

C

呃呃题。

因为是连续地 \(\bmod n\sim 1\)，发现颜色最多只有三段：\(a_{n+1}, a_{n+1}\bmod n, 0\)。

然后手玩下规则，大力特判就行了。

//
/*
By:Luckyblock
*/
#include <bits/stdc++.h>
#define LL long long
//=============================================================
int n, m, k;
//=============================================================
inline int read() {
  int f = 1, w = 0; char ch = getchar();
  for (; !isdigit(ch); ch = getchar()) if (ch == '-') f = -1;
  for (; isdigit(ch); ch = getchar()) w = (w << 3) + (w << 1) + (ch ^ '0'); 
  return f * w;
}
int Solve() {
  if (k == 1) return 1;
  
  int c = m / n;
  if (k == 2) return std::min(n - 1 + c, m);
  if (k == 3) return std::max(0, m - n + 1 - c);
  return 0;
}
//=============================================================
int main() {
  //freopen("1.txt", "r", stdin);
  int T = read();
  while (T --) {
    n = read(), m = read(), k = read();
    printf("%d\n", Solve());
  }
  return 0;
}

D

发现这个先涂黑再涂绿的题面就是劝退的。一种涂黑的方案的贡献，实质上就是所有位于涂黑位置倍数的最大值，则选择 \(a_i\) 涂黑对于某种方案的贡献，即为 \(\max_{i | j} a_j\)，这玩意可以调和级数地预处理，记为 \(f_{i}\)。

以下给出两种做法。

首先是傻逼赛时做法，考虑枚举选数方案中位置最靠后的数 \(a_i\)，在此过程中维护使得贡献为 \(j\) 的方案数 \(g_j\)，考虑在方案中加入了 \(a_i\) 之后对 \(g\) 的影响，显然加入后只会影响 \(j\ge f_i\) 的方案数 \(g_j\)，对于 \(j=f_i\)，有 \(g_{j}\leftarrow \sum_{k\le j} g_{k}\)，对于 \(j>f_i\) 有 \(g_j\leftarrow 2\times g_{j}\)。

于是考虑使用权值线段树维护 \(g\)，支持区间求和、区间加和区间乘即可，总时间复杂度为常数略大的 \(O(n\log n)\) 级别。

特别地，注意需要记 \(g_0 = 1\)。

然后是赛后学习的大神做法，考虑升序枚举以 \(a_i\) 的贡献 \(f_i\)，考虑钦定选择 \(a_i\)，并使 \(f_i\) 为总贡献的方案数。显然对于 \(f_{j} < f_i\) 的 \(a_j\) 可以任意出现在方案中，否则不能出现在方案中，记满足 \(f_j<f_i\) 的数量为 \(c\)，则这样的方案数为 \(2^c\)。

预处理 \(f\) 后排序记录贡献即可，总时间复杂度是超快的 \(O(n\log n)\) 级别。

赛时，295ms：

//
/*
By:Luckyblock
*/
#include <bits/stdc++.h>
#define LL long long
#define ls (now<<1)
#define rs (now<<1|1)
const int kN = 1e5 + 10;
const LL p = 998244353;
//=============================================================
int n, a[kN];
int datanum, data[kN];
//=============================================================
inline int read() {
  int f = 1, w = 0; char ch = getchar();
  for (; !isdigit(ch); ch = getchar()) if (ch == '-') f = -1;
  for (; isdigit(ch); ch = getchar()) w = (w << 3) + (w << 1) + (ch ^ '0'); 
  return f * w;
}
struct Node {
	int L, R;
	LL sum, plustag, prodtag;
}tree[kN << 2];
void Pushup(int now) {tree[now].sum = (tree[ls].sum + tree[rs].sum) % p;}//子区间合并 
void Pushdown(int now)//下传 懒标记 
{
	LL plustag = tree[now].plustag, prodtag = tree[now].prodtag; 
	tree[now].plustag = 0, tree[now].prodtag = 1;
	
	tree[ls].sum = (tree[ls].sum * prodtag % p + plustag * (tree[ls].R - tree[ls].L + 1) % p) % p;
	tree[rs].sum = (tree[rs].sum * prodtag % p + plustag * (tree[rs].R - tree[rs].L + 1) % p) % p;
	tree[ls].prodtag = tree[ls].prodtag * prodtag % p, tree[ls].plustag = (tree[ls].plustag * prodtag % p + plustag) % p;
	tree[rs].prodtag = tree[rs].prodtag * prodtag % p, tree[rs].plustag = (tree[rs].plustag * prodtag % p + plustag) % p;
}
void Build(int now, int L, int R)//建树 
{
	tree[now].L = L, tree[now].R = R, tree[now].prodtag = 1;
	if(L == R) {tree[now].sum = 0; return ;}
	int mid = (L + R) >> 1;
	Build(ls, L, mid), Build(rs, mid + 1, R);
	Pushup(now);
}
void Change(int now, int L, int R, int type, LL add)
{
	if(L <= tree[now].L && tree[now].R <= R) //修改 被覆盖的区间 
	{
	  if(type == 1)
	    tree[now].sum = (tree[now].sum * add) % p, 
	    tree[now].prodtag = tree[now].prodtag * add % p, 
	    tree[now].plustag = tree[now].plustag * add % p;
	  else
	  	tree[now].sum = (tree[now].sum + (tree[now].R - tree[now].L + 1) * add) % p,
	    tree[now].plustag = (tree[now].plustag + add) % p;	
	  return ;
	}
	
	if(tree[now].plustag || tree[now].prodtag != 1) Pushdown(now);
	int mid = (tree[now].L + tree[now].R) >> 1;
	if(L <= mid) Change(ls, L, R, type, add);//修改左右子区间 
	if(R > mid) Change(rs, L, R, type, add);
	Pushup(now);//左右区间合并 
}
LL Query(int now, int L, int R)
{
	if(L <= tree[now].L && tree[now].R <= R) return tree[now].sum % p;//查询 被覆盖区间 
	
	if(tree[now].plustag || tree[now].prodtag != 1) Pushdown(now);
	int mid = (tree[now].L + tree[now].R) >> 1;
	LL ret = 0;
	if(L <= mid) ret = (ret + Query(ls, L, R)) % p;//查询 左右子区间 
	if(R > mid) ret = (ret + Query(rs, L, R)) % p;
	return ret;
}
LL Getans(int now, int L, int R) {
  if (L == R) {
    return 1ll * data[L] * tree[now].sum % p;
  }
  if(tree[now].plustag || tree[now].prodtag != 1) Pushdown(now);
  int mid = (L + R) >> 1;
  return (Getans(ls, L, mid) + Getans(rs, mid + 1, R)) % p;
}

void Init() {
  n = read();
  for (int i = 1; i <= n; ++ i) a[i] = data[i + 1] = read();
  std::sort(data + 1, data + n + 1 + 1);
  datanum = std::unique(data + 1, data + n + 1 + 1) - data - 1;
  for (int i = 1; i <= n; ++ i) {
    a[i] = std::lower_bound(data + 1, data + datanum + 1, a[i]) - data;
  }
  Build(1, 1, datanum);

  Change(1, 1, 1, 0, 1);
}
//=============================================================
int main() {
  // freopen("1.txt", "r", stdin);
  Init();
  for (int i = 1; i <= n; ++ i) {
    int maxa = a[i];
    for (int j = i; j <= n; j += i) maxa = std::max(maxa, a[j]);

    LL sum = Query(1, 1, maxa);
    Change(1, maxa, maxa, 0, sum);
    if (maxa < datanum) Change(1, maxa + 1, datanum, 1, 2);
  }
  printf("%lld\n", Getans(1, 1, datanum));
  return 0;
}

大神， 46ms：

//
/*
By:Luckyblock
*/
#include <bits/stdc++.h>
#define LL long long
const int kN = 1e5 + 10;
const LL p = 998244353;
//=============================================================
int n, a[kN], f[kN];
//=============================================================
inline int read() {
  int f = 1, w = 0; char ch = getchar();
  for (; !isdigit(ch); ch = getchar()) if (ch == '-') f = -1;
  for (; isdigit(ch); ch = getchar()) w = (w << 3) + (w << 1) + (ch ^ '0'); 
  return f * w;
}
//=============================================================
int main() {
  //freopen("1.txt", "r", stdin);
  n = read();
  for (int i = 1; i <= n; ++ i) a[i] = read();
  for (int i = 1; i <= n; ++ i) {
    for (int j = i; j <= n; j += i) {
      f[i] = std::max(f[i], a[j]);
    }
  }
  std::sort(f + 1, f + n + 1);
  
  LL ans = 0, pow2 = 1;
  for (int i = 1; i <= n; ++ i) {
    ans += f[i] * pow2 % p, ans %= p;
    pow2 = 2 * pow2 % p;
  }
  printf("%lld\n", ans);
  return 0;
}

E

懂了，但不好描述。

咕咕先。

//
/*
By:Luckyblock
*/
#include <bits/stdc++.h>
#define LL long long
const int kN = 2e5 + 10;
//=============================================================
int n, a[kN], fa[kN], into[kN];
int color[kN];
// bool vis[kN];
//=============================================================
inline int read() {
  int f = 1, w = 0; char ch = getchar();
  for (; !isdigit(ch); ch = getchar()) if (ch == '-') f = -1;
  for (; isdigit(ch); ch = getchar()) w = (w << 3) + (w << 1) + (ch ^ '0'); 
  return f * w;
}
int Dfs(int u_, int now_) {
  if (color[u_]) return 0;
  color[u_] = now_;
  return Dfs(fa[u_], (now_ == 1) ? 2 : 1) + 1;
}
//=============================================================
int main() {
  //freopen("1.txt", "r", stdin);
  n = read();
  for (int i = 1; i <= n; ++ i) {
    a[i] = read();
    fa[i] = a[i], into[a[i]] ++;
  }
  
  std::queue <int> q;
  for (int i = 1; i <= n; ++ i) {
    if (into[i] == 0) q.push(i), color[i] = 1;
  }
  while (!q.empty()) {
    int u_ = q.front(); q.pop();
    -- into[fa[u_]];
    if (color[u_] == 1 && !color[fa[u_]]) {
      color[fa[u_]] = 2;
      q.push(fa[u_]);
    }
    if (!into[fa[u_]] && !color[fa[u_]]) {
      color[fa[u_]] = 1;
      q.push(fa[u_]);
    }
  }

  for (int i = 1; i <= n; ++ i) {
    if (color[i]) continue;
    if (Dfs(i, 2) % 2 == 1) {
      printf("-1\n");
      return 0;
    }
  }

  int ans = 0;
  for (int i = 1; i <= n; ++ i) {
    if (color[i] == 1) ++ ans;
  }
  printf("%d\n", ans);
  for (int i = 1; i <= n; ++ i) {
    if (color[i] == 1) printf("%d ", a[i]);
  }
  return 0;
}

写在最后

学到了什么：

• D：枚举对象。

本栏目推荐文章
• NSSCTF Round#16 Basic WriteUp
• Center-based 3D Object Detection and Tracking
• AT_cf17_final_j 题解
• An improved LSTM-based model for identifying high working intensity load segments of the tractor load spectrum
• Hey left 1 Codeforces Round 918 (Div. 4)
• Early lameness detection in dairy cattle based on wearable gait analysis using semi-supervised LSTM-Autoencoder
• 基于正则化的图自编码器在推荐算法中的应用 Application of graph auto-encoders based on regularization in recommendation algorithms
• CodeForces 1312G Autocompletion
• Educational Codeforces Round 152 (Rated for Div. 2)
• codeforces 918 div4

Round Codeforces COMPFEST Final basedround codeforces compfest final codeforces compfest round final round codeforces rated based venture final round 2016 educational codeforces round rated codeforces round 911 div codeforces round 864 div codeforces round 887 div codeforces round 863 div codeforces round 913 div