首页 > 其他分享 >Codeforces Round 902 (Div. 2, based on COMPFEST 15 - Final Round)

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

时间：2023-10-10 12:22:42浏览次数：45  
标签：902 ch based int kN long now Round getchar

目录

写在前面

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

<iframe border="0" frameborder="no" height="86" marginheight="0" marginwidth="0" src="//music.163.com/outchain/player?type=2&id=1423038384&auto=0&height=66" width="330"></iframe>

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

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

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

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：枚举对象。

标签：902,ch,based,int,kN,long,now,Round,getchar
From： https://www.cnblogs.com/luckyblock/p/17754352.html

相关文章

  • Python 中的round函数
    在python2.7的doc中，round()的最后写着，"Values are rounded to the closest multiple of 10 to the power minus ndigits; if two multiples are equally close, rounding is done away from 0." 保留值将保留到离上一位更近的一端（四舍六入），如果距离两端一......
  • Educational Codeforces Round 152 (Div. 2) D. Array Painting（双指针）
    EducationalCodeforcesRound152(Div.2)D.ArrayPainting//思路：双指针找连续正数段//若段中出现2，则更新两头的0的情况，若为涂色则改为true//若无2，则优先更新左侧0，若左0已经为true，则更新右侧0//数组开头结尾特判#defineintlonglong#defineldlongdoubleusingnam......
  • oracle中to_char(), to_date() ,ROUND(),NVL(), DECODE(), EXTRACT()等函数的使用
    1.to_char()将时间日期按照指定的格式输出，得到的是字符串，而非date类型。只要被转换的是一个日期，yyyy,mm,dd中间加不加连接符，加什么连接符都可以2.todate()将字符串按照指定的格式输出，得到的是日期类型。第一个参数的yyyy,mm,dd之间有没有连接符。如果有，那么第二个参数必须有......
  • 练习记录-cf-Educational Codeforces Round 156 (Rated for Div. 2)(A-C)
    好久没打了还是就出了三道不过还好没掉分A.SumofThree就是问能不能把一个数拆成三个不同的且都不能被三整除的数我的思路就是拆成1+2+一个大于等于4的数如果拆了后另一个数是%3==0那么我拆成1+4它肯定就不被整除然后判下相同#include<bits/stdc++.h>#defineclose......
  • Codeforces Round 902 (Div. 2) C. Joyboard 规律
    CodeforcesRound902(Div.2)C.Joyboard//思路：在k=1，k=2，k=3时有解//当k=1时为全0//当k=2时，若m>=n,则先是0然后为1~n，最后一位可以为n的倍数也符合，即n+m/n-1//若m<n则为1~m即m//当k=3时，只能在n+1位是第3个不同情况（大于n），且不能为n的倍数，即(m-n)-(m/n-1)//只......
  • [902] Get the current file's directory of CMD batch scripts
    Inabatchfile,youcanusethe%~dp0specialvariabletogetthedirectoryofthecurrentlyexecutingbatchfile.Here'showyoucandoit:@echooffechoThedirectoryofthisbatchfileis:%~dp0Whenyourunthisbatchfile,itwilldisplaythe......
  • P8511 [Ynoi Easy Round 2021] TEST_68
    题目传送门看到异或最大值，根据套路不妨考虑\(0-1trie\)。通过\(trie\)找到异或值最大的点对\((x,y)\)。那么除了\((x,y)\)到\(1\)路径上的点之外，其他的点的答案就是\((x,y)\)的异或值。接下来考虑怎么算出这\((x,y)\)到\(1\)路径上的点的答案，可以直接暴力计算！......
  • Codeforces Round 726 (Div. 2) B. Bad Boy
    给一个\(n\timesm\)的平面，一个初始位置\((i,j)\)。需要放两个废弃物在平面上，位置为\((x_1,y_1),(x_2,y_2)\)。使得从\((i,j)\)出发，捡起两个废弃物后，回到原位置，所经过的曼哈顿距离最长。询问一组合法的\((x_1,y_1),(x_2,y_2)\)。性质：二维平面上有关的曼哈......
  • 11g-crsctl_start_crs-failed-workaround
    SYMPTOMScrsctlstartcrsCRS-4124:OracleHighAvailabilityServicesstartfailedCAUSE：InstallofClusterwarefailswhilerunningroot.shonOL7-ohasdfailstostart(DocID1959008.1)InOL7itneedstobesetupasaserviceandpatchfixforBug......
  • (2023年新疆大学、中科院等点云分类最新综述) Deep learning-based 3D point cloud cl
    目录1、引言2、3D数据2.1、3D数据表示形式2.2、点云数据存储格式2.3、3D点云公共数据集3、基于深度学习的点云分类方法3.1、基于多视角的方法3.2、基于体素的方法3.3、基于点云的方法3.3.1局部特征聚合3.3.1.1基于逐点处理的方法3.3.1.2基于卷积的方法3.3.1.3基于图的方法3.3.1......

赞助商

阅读排行

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

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

Copyright © 2020-2023 IPS99 版权所有 IPS99