首页 > 其他分享 >Codeforces Round 969 (Div. 2)

Codeforces Round 969 (Div. 2)

时间:2024-10-07 12:22:55浏览次数:6  
标签:cnt int scanf 969 Codeforces ++ 节点 Div mx

一万五参赛,赛时(VP)排名 80

A. Dora's Set

比较新的结论题。显然,一个合法三元组最多只能有一个偶数。每个偶数都可以跟相邻两个奇数组成合法三元组。

因此,答案为奇数个数的二分之一(下取整)。

#include<bits/stdc++.h>
using namespace std;
int T, l, r;

int main() {
	scanf("%d", &T);
	while(T --) {
		scanf("%d%d", &l, &r);
		int num2 = r / 2 - l / 2;
		if(l % 2 == 0) num2 ++;
		printf("%d\n", (r - l + 1 - num2) / 2);
	}
	return 0;
}

B. Index and Maximum Value

简单结论题。显然,每次修改不会改变最大值的地位,要么最大值跟着变小或者变大,要么最大值没有影响。

因此每次只需要判断最大值是否在变化区间内即可。

VP时看错题了,白白耽误了 15 min

#include<bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
int T, n, m, a[N];

int main() {
	scanf("%d", &T);
	while(T --) {
		int mx = 0;
		scanf("%d%d", &n, &m);
		for(int i = 1; i <= n; i ++)
			scanf("%d", &a[i]), mx = max(mx, a[i]);
		for(int i = 1; i <= m; i ++){
			char op[2]; int l, r;
			scanf("%s%d%d", op, &l, &r);
			if(op[0] == '+' && r >= mx && l <= mx) mx ++;
			if(op[0] == '-' && r >= mx && l <= mx) mx --;
			printf("%d ", mx);
		}
		puts("");
	}
	return 0;
}

C. Dora and C++

裴蜀定理。显然,根据裴蜀定理,每个数都可以加减任意次 gcd(a,b) ,且这是最小最优的数。

因此,对每个数取模,框定在 gcd(a,b) 范围内,并且从小到大依此加一次 gcd(a,b) ,动态更新答案即可。

#include<bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
int T, n, a, b, c[N];

int gcd(int a, int b) {
	if(!b) return a;
	return gcd(b, a % b);
}

int main() {
	scanf("%d", &T);
	while(T --) {
		scanf("%d%d%d", &n, &a, &b);
		int gd = gcd(a, b);
		for(int i = 1; i <= n; i ++) {
			scanf("%d", &c[i]);
			c[i] %= gd;
		}
		sort(c + 1, c + n + 1);
		int ans = c[n] - c[1];
		for(int i = 2; i <= n; i ++)
			ans = min(ans, c[i - 1] - c[i] + gd);
		printf("%d\n", ans);
	}
	return 0;
}

D. Iris and Game on the Tree

怎么还是结论题。。。

手玩一下可以发现,一个叶子节点代表的 01 串的权值只能为 0 或者 1 ,且只跟首尾字符是否一致有关,与中间无关。

分类讨论。

若根节点可以填,优先填在叶子出现最多的字符,若一样多,先填中间无关紧要的(此时后手填根节点更优)。

若根节点固定,则抢占叶子节点的有利字符即可。

#include<bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
int T, n, w[N], cnt[4];
vector<int> g[N];
char s[N];

void dfs(int x, int fa) {
	bool is_leaf = true;
	for(auto y: g[x]) {
		if(y == fa) continue;
		dfs(y, x);
		is_leaf = false;
	}
	if(is_leaf) cnt[w[x]] ++;
	else if(x != 1 && w[x] == 2) cnt[3] ++;
}

int main() {
	scanf("%d", &T);
	while(T --) {
		scanf("%d", &n);
		for(int i = 1; i <= n; i ++) g[i].clear();
		cnt[0] = cnt[1] = cnt[2] = cnt[3] = 0; 
		for(int i = 2; i <= n; i ++) {
			int u, v;
			scanf("%d%d", &u, &v);
			g[u].push_back(v);
			g[v].push_back(u);
		}
		scanf("%s", s + 1);
		for(int i = 1; i <= n; i ++) {
			if(s[i] == '0') w[i] = 0;
			if(s[i] == '1') w[i] = 1;
			if(s[i] == '?') w[i] = 2;
		}
		dfs(1, 0);
		if(w[1] != 2) printf("%d\n", cnt[w[1] ^ 1] + (cnt[2] + 1) / 2);
		else {
			if(cnt[0] != cnt[1])
				printf("%d\n", max(cnt[1], cnt[0]) + cnt[2] / 2);
			else
				printf("%d\n", cnt[0] + ((cnt[3] & 1) ? (cnt[2] + 1) / 2 : cnt[2] / 2));
		}
	}
	return 0;
}

E. Iris and the Tree

没错还是结论题。。。

显然,若 dis(i,i+1) 中间有无权边,可以将这条无权边的边权设置成最大,因此我们只需要知道含无权边的路径有多少即可。

又显然,每条边会被经过两次,对于 i 节点对应边,分别是 dis(i-1,i) 和 dis(mx,mx+1) ,mx 是 i 节点所在子树的最大节点。

因此每次加一条边权,两条对应路径的无权边减一。计算相应答案即可。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 2e5 + 10;
ll T, n, w, cnt, cur;
ll mx[N], dis[N], p[N];
vector<int> g[N];

void dfs(int x) {
	if(x == cur + 1) {
		dis[cur] = cnt;
		cnt = 0; cur ++;
	}
	mx[x] = x;
	for(auto y: g[x]) {
		cnt ++;
		dfs(y);
		mx[x] = max(mx[x], mx[y]);
	}
	if(x != 1) cnt ++;
}

int main() {
	scanf("%lld", &T);
	while(T --) {
		scanf("%lld%lld", &n, &w);
		for(int i = 1; i <= n; i ++)
			g[i].clear();
		for(int i = 2; i <= n; i ++) {
			scanf("%d", &p[i]);
			g[p[i]].push_back(i);
		}
		cur = 1; cnt = 0;
		dfs(1);
		dis[cur] = cnt;
		cnt = n;
		ll sum = 0;
		for(int i = 2; i <= n; i ++) {
			ll x, y;
			scanf("%lld%lld", &x, &y);
			if(-- dis[x - 1] == 0) cnt --;
			if(-- dis[mx[x]] == 0) cnt --;
			sum += y;
			printf("%lld ", sum * 2 + cnt * (w - sum));
		}
		puts("");
	}
	return 0;
}

标签:cnt,int,scanf,969,Codeforces,++,节点,Div,mx
From: https://www.cnblogs.com/lingo12321/p/18449749

相关文章

  • Codeforces Round 977 (Div. 2)
    手速局,因为水平不够三题遗憾离场。A.MeaningMean题意你一个序列,你每次可以选择两个数删掉,并把他们的平均数加入到序列的末尾。当序列长度为\(1\)的时候,剩下的数最大值是多少。思路当时比赛的时候唐了,耽误了好几分钟。想的是先奇数和奇数相加,偶数和偶数相加,这样能避免下取......
  • Codeforces Rund 977 div2 个人题解(A~E1)
    CodeforcesRund977div2个人题解(A,B,C1,C2,E1)Dashboard-CodeforcesRound977(Div.2,basedonCOMPFEST16-FinalRound)-Codeforces火车头#define_CRT_SECURE_NO_WARNINGS1#include<algorithm>#include<array>#include<bitset>#includ......
  • Codeforces Round 977 (Div. 2, based on COMPFEST 16 - Final Round)
    CodeforcesRound977(Div.2,basedonCOMPFEST16-FinalRound)A.MeaningMean题目链接:Problem-A-Codeforces题目描述:给定一个包含(n)个正整数的数组(a)。你可以执行如下操作直到数组中只剩下一个元素:从数组中选择两个不同的元素(a_i)和(a_j......
  • 【CodeForces训练记录】Codeforces Round 977 (Div. 2, based on COMPFEST 16 - Final
    赛后反思做红温了,太菜了,每题都需要WA几次才能过,B题看到MEX选择性害怕,时间复杂度又算错了A题每次选择一对\(a_i,a_j\)把均值插入数组最后面,要想结果最大,对于两个数求均值,最后的结果一定是小于等于其中的较大值,我们可以考虑如何最大化最后一次操作,想到将最大值保留在最后再......
  • 组织: 阶级: 组织+管理+授权+组织结构设计+ 角色 + 分工: individual类型: 体力+普工+
    组织:阶级:组织+管理+授权+资源管理+组织结构设计+角色社会:教育分科+分工:individual类型:体力:普工:砖头,销售文职:上传下达,文书专业:一招鲜,专家管理:人精高管:人上人企业主:金富民官员:高官:分封贵族:家族尊贵,出生关系帝王:砖头:哪里需要哪里搬,价值:自我:社......
  • 自动滚动和循环内容DIV
    <!--HTMLVersionDeclaration--><!DOCTYPEhtml><!--HTMLRootElement--><html><!--HTMLHeadSection--><head><!--HTMLDocumentTitle--><title>ThisisTitle</title><stylety......
  • 2024.10.4 ROS第五章结束,复习背包问题模型 + codeforces刷刷题
    项目学习总结ROS第五章主要是学习了坐标变换,实际用途还是好理解的,比方说地面基地控制无人机追鸟。坐标变换主要是用tf这个包实现的。可以实现静态坐标变换,动态坐标变换和多坐标变换。静态和动态变换的关键函数:ps_out=buffer.transform(ps,"base_link");动态变换里面主要是......
  • Codeforces 杂题
    CF1994E\(*2000,\texttt{Tag:}\)贪心,位运算题意:给出一片森林,每次你可以选择一个点删去它的子树,求所有删去的子树大小的按位或结果的最大值。Solution按位或可以看做在二进制下的不进位加法,因此,若一棵树不管怎么拆分,它拆分出来的子树大小或的结果不会大于它本身。若一棵树......
  • 【处理元组有关的题型的技巧】codeforces 1677 A. Tokitsukaze and Strange Inequalit
    题意第一行输入一个正整数\(T(1\leqT\leq1000)\),代表共有\(T\)组测试用例,对于每组测试用例:第一行输入一个正整数\(n(4\leqn\leq5000)\),第二行输入\(n\)个正整数\(p_i(1\leqp_i\leqn)\)。对于\(1\leqi<j<k<l\leqn\),若有\(a_i<a_k,a_j>a_l\)成......
  • Codeforces2020D Connect the Dots(观察 + 并查集 + 差分)
    题意多组数据。数轴上有\(n\)个点,编号为\(1\simn\),对这些点做$m$次操作。每次操作给出三个整数\(a_i(1\lea_i\len)\\\d_i(1\led_i\le10)\\\k_i(0\lek_i\len)\)。将点\(a_i,a_i+d_i,a_i+2\timesd_i,a_i+3\timesd_i,\cdot\cdot\cdo......