首页 > 其他分享 >AtCoder Regular Contest 164 F Subtree Reversi

AtCoder Regular Contest 164 F Subtree Reversi

时间:2023-10-26 21:35:44浏览次数:35  
标签:AtCoder typedef Contest int Reversi long maxn define

洛谷传送门

AtCoder 传送门

非常好题目。

发现每个点颜色被反转的次数是固定的,为其深度(根结点深度为 \(0\))。于是可以看作是,一放棋子就得到分数。

那么先手取偶数层和后手取奇数层都会使先手得分,所以双方的目标都是尽可能多取偶数层的结点。

考虑若一开始有偶数层的叶子,那么当前的先手肯定会取它(不取白不取)。可以先维护这种情况。

那么取完偶数层叶子后就只剩下奇数层了。考虑把树分成一个个极大的“坨”,使得每个“坨”都会使得先后手交换,且取这一坨的人不会得分(对方得分)。

显然双方都会取当前能取的最小的坨。取完一坨可能会产生新的坨,把这一坨的价值并到父亲的父亲即可。优先队列维护一下就行了。

注意最后还剩下根结点。

code
// Problem: F - Subtree Reversi
// Contest: AtCoder - AtCoder Regular Contest 164
// URL: https://atcoder.jp/contests/arc164/tasks/arc164_f
// Memory Limit: 1024 MB
// Time Limit: 2000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>
#define pb emplace_back
#define fst first
#define scd second
#define mkp make_pair
#define mems(a, x) memset((a), (x), sizeof(a))

using namespace std;
typedef long long ll;
typedef double db;
typedef unsigned long long ull;
typedef long double ldb;
typedef pair<ll, ll> pii;

const int maxn = 200100;

int n, p[maxn], ind[maxn], ans, f[maxn];
bool fl = 1;
vector<int> G[maxn];

struct node {
	int u, d;
	node(int a = 0, int b = 0) : u(a), d(b) {}
};

inline bool operator < (const node &a, const node &b) {
	return a.d > b.d;
}

priority_queue<node> pq;

void dfs(int u, int d) {
	for (int v : G[u]) {
		dfs(v, d ^ 1);
	}
	if (ind[u] == 0) {
		if (d) {
			pq.emplace(u, 1);
		} else {
			ans += fl;
			fl ^= 1;
			--ind[p[u]];
		}
	}
}

void solve() {
	scanf("%d", &n);
	for (int i = 2; i <= n; ++i) {
		scanf("%d", &p[i]);
		G[p[i]].pb(i);
		++ind[p[i]];
	}
	dfs(1, 0);
	while (pq.size()) {
		int u = pq.top().u, d = pq.top().d;
		pq.pop();
		if (p[u] != 1 && !(--ind[p[u]])) {
			int v = p[p[u]];
			f[v] += d + 1;
			if (!(--ind[v])) {
				pq.emplace(v, f[v] + 1);
			}
		} else {
			if (!fl) {
				ans += d;
			}
			fl ^= 1;
		}
	}
	ans += fl;
	printf("%d\n", ans);
}

int main() {
	int T = 1;
	// scanf("%d", &T);
	while (T--) {
		solve();
	}
	return 0;
}

标签:AtCoder,typedef,Contest,int,Reversi,long,maxn,define
From: https://www.cnblogs.com/zltzlt-blog/p/17790448.html

相关文章

  • The 2021 ICPC Asia Macau Regional Contest
    \(C.LaserTrap\)根据题意不难判断出需要极角排序,然后对于每个点寻找更小的一个\(180\)度的点数。即使听说是用双指针实现查找依旧没什么思路。后来看了别人的实现方法发现确实比较简单,甚至只需要维护极角就可以了。constlongdoublepi=acosl(-1);voidsolve(){int......
  • AtCoder Beginner Contest(abc) 309
    B-Rotate题目大意给定一个n*n的矩阵,要求把矩阵的最外围按照顺时针转动一个数据,输出转动后的矩阵;解题思路数据不大,暴力即可;神秘代码#include<bits/stdc++.h>#defineintlonglong#defineIOSios::sync_with_stdio(false);cin.tie(0);cout.tie(0);#def......
  • 76th 2023/10/10 Atcoder 10/8-ARC-T3
    这道题题目很有意思,看上去是很简单明显的计数,但一思考会发现要死很多重复状态因为标记的线很容易让人从一个方框开始思考起,所以很容易带入关于重复考虑的误区观察到线是斜着的,思考影响到的范围若涂上一个格子或左一个格子的右下,则该格子不能填涂左上观察到影响范围是一个个斜......
  • [Leetcode Weekly Contest]368
    链接:LeetCode[Leetcode]2908.元素和最小的山形三元组I给你一个下标从0开始的整数数组nums。如果下标三元组(i,j,k)满足下述全部条件,则认为它是一个山形三元组:i<j<knums[i]<nums[j]且nums[k]<nums[j]请你找出nums中元素和最小的山形三元组,并返回......
  • AtCoder Regular Contest 167——B - Product of Divisors
    题目很明显,给定 所有因数的积不断除以最多能除几次。首先,很容易发现,对于每一对因子,都可以对答案得出B的贡献,设A的因子数目为n。将A进行质因数分解,PBa1,PBa2,PBa3……PBam,那么因数个数就是质因子加一的乘积。那么因子对数也就是前者一半。答案就是B乘因子对数除以二注意此处......
  • AtCoder Beginner Contest(abc) 308
    B-DefaultPrice题目大意小莫买了n个寿司,现在给出m个寿司的名称和m+1个价格,如果小莫买的其中一个寿司不在这m个寿司之中就用价格m0;请问小莫买的寿司花了多少钱解题思路数据不大,暴力哈希即可;神秘代码#include<bits/stdc++.h>#defineintlonglong#define......
  • Atcoder Beginner Contest 324 G Generate Arrays 题解-Treap
    为了更好的阅读体验,请点击这里题目链接套上平衡树板子就能做的很快的题,然后因为是指针存树,因此交换只需要把序列大小较小的挨个拿出来插到相应的地方即可。复杂度\(O(N\log^2N)\)。但是一定要记住不可以直接使用std::swap交换包含带有指针的类的实例(如代码中的Treap类)!......
  • AtCoder Regular Contest 167
    Preface补一下上周日的ARC,因为当天白天和队友一起VP了一场所以就没有精力再打一场了这场经典C计数不会D这种贪心乱搞反而是一眼秒了,后面的EF过的太少就没看A-ToastsforBreakfastParty用一个类似于蛇形的放法就好了,比如对于\(n=9,m=5\),放法为:567894321#includ......
  • Japan Registry Services (JPRS) Programming Contest 2023 (AtCoder Beginner Contes
    JapanRegistryServices(JPRS)ProgrammingContest2023(AtCoderBeginnerContest324)赛后总结可悲的是:我没来得及写题解。T1Same秒切。直接输入排一遍序再遍历即可。#include<bits/stdc++.h>usingnamespacestd;intn,a[101];intmain(){cin>>n;f......
  • 比赛总结:Japan Registry Services (JPRS) Programming Contest 2023 (AtCoder Beginn
    比赛:JapanRegistryServices(JPRS)ProgrammingContest2023(AtCoderBeginnerContest324)A-same1.常规方法intmain(){ intn; cin>>n; vector<int>s(n);//利用vector容器可以不需要确定内存大小 for(auto&n:s) { cin>>n; } for(inti=0;i......