首页 > 其他分享 >E. IT Restaurants

E. IT Restaurants

时间:2024-05-26 14:33:33浏览次数:15  
标签:nums int back push include 节点 Restaurants

链接:https://www.luogu.com.cn/problem/CF212E
https://codeforces.com/problemset/problem/212/E
题目:

思路:
首先题目说要保证最大的数量,并且每个颜色的点至少有一个,那么很显然染色的点有n-1个,且唯一没染色的点必须有两个及以上的子节点
我们这样去理解没染色的点:它的子节点颜色可以不一样,但是它的子节点为根节点的子树颜色必须一样,所以理解为转色点。

如果1不染色,那么子树的节点数量是3 3 1所以红色的节点数可以且仅可以是1 3 4 6
那么对每个非叶子节点进行分析即可。
主要是01背包的部分编码有点怪?
代码:

#define _CRT_SECURE_NO_WARNINGS 
#include<iostream>
#include<vector>
#include<algorithm>
#include<math.h>
#include<sstream>
#include<string>
#include<string.h>
#include<iomanip>
#include<stdlib.h>
#include<map>
#include<queue>
#include<limits.h>
#include<climits>
#include<fstream>
#include<stack>
typedef long long ll;
using namespace std;
const int N = 5e3 + 10;
vector<int>G[N];
bool vis[N];
void dfs(int u, int& nums)
{
	vis[u] = 1; nums++;
	for (int v : G[u])
	{
		if (!vis[v])
		{
			dfs(v, nums);
		}
	}
}
int main()
{
	ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
	int n; cin >> n;
	for (int i = 0; i < n-1; i++)
	{
		int u, v; cin >> u >> v;
		G[u].push_back(v), G[v].push_back(u);
	}
	map<int,bool>red;
	for (int i = 1; i <= n; i++)
	{
		if (G[i].size() == 1)continue;//叶子节点直接跳
		memset(vis, 0, sizeof(vis));
		vis[i] = 1;//用来写dfs
		vector<int>child;
		child.push_back(0);//每颗子树的节点数,为了方便从1开始,首先push_back一个0
		for (int u : G[i])
		{
			int nums = 0;
			dfs(u, nums);
			child.push_back(nums);
		}
		vector<int>dp;//当前的背包空间
		int childlength = child.size();//固定长度
		map<int,bool>mpr;//判断有没有出现,局部map
		for(int j=1;j<=childlength-1;j++)
		{
			bool isgo = false;
			if (!mpr[child[j]])
			{
				if (!red[child[j]])red[child[j]] = 1;
				mpr[child[j]] = 1;
				dp.push_back(child[j]);
				isgo = true;//如果塞了新的数进去,那么最后一个不能用
			}
			int length = dp.size();//固定长度
			if (isgo)length--;
			for (int k = 0; k < length; k++)
			{
				if (!mpr[child[j] + dp[k]])//局部
				{
					if (!red[child[j] + dp[k]])red[child[j] + dp[k]] = 1;//总体
					mpr[child[j] + dp[k]] = 1;
					dp.push_back(child[j] + dp[k]);
				}
			}
		}
	}
	red.erase(n-1);//涂掉全是红色的节点,因为至少要有1个蓝色
	cout << red.size() << endl;
	
	for (map<int, bool>::iterator it = red.begin(); it != red.end(); ++it)
	{
		
		cout << it->first << ' ' << n - 1 - it->first << endl;
	}
	return 0;
}

标签:nums,int,back,push,include,节点,Restaurants
From: https://www.cnblogs.com/zzzsacmblog/p/18213634

相关文章

  • [ARC067F] Yakiniku Restaurants
    首先考虑暴力。\(\mathcalO(n^2m)\)枚举左右两个端点,再贪心地选其中\(M\)张票的美味度最大那一家餐馆。复杂度不可接受,但是不难感觉到正解应该是\(\mathcalO(n^2)\)的。考虑枚举左端点\(i\),对于当前左端点,记每一个右端点\(j\)的答案为\(now_j\),若暂时不考虑距离,大部分......
  • ARC076D Yakiniku Restaurants
    题意有\(n\)个商店。每个商店有\(m\)个物品。每个物品的价值为\(b_{i,j}\)。每种物品只能被购买一次。你可以选择一个起点,在任意商店结束购买。获得的价值为\(m\)个物品之和减去路程。求最大可获得的价值。\(n\le5e3,m\le200\)Sol不难发现,最优的方案一定是一个......
  • [LeetCode] 1333. Filter Restaurants by Vegan-Friendly, Price and Distance 餐厅过
    Giventhearray restaurants where restaurants[i]=[idi,ratingi,veganFriendlyi,pricei,distancei].Youhavetofiltertherestaurantsusingthreefilte......
  • CodeForces - 212E IT Restaurants
    题意:给一棵树的结点染色,每个结点可以染红色、蓝色或不染色。相邻两个结点必须染同一种颜色,或者一个染色一个不染色。求整棵树染色结点最多,且在整棵树至少有一个结点染红色,......