codeforces 랭킹전 4

전송문
제면
B. Diverse Garland time limit per test1 second memory limit per test256 megabytes inputstandard input outputstandard output You have a garland consisting of n lamps. Each lamp is colored red, green or blue. The color of the i-th lamp is si (‘R’, ‘G’ and ‘B’ — colors of lamps in the garland).
You have to recolor some lamps in this garland (recoloring a lamp means changing its initial color to another) in such a way that the obtained garland is diverse.
A garland is called diverse if any two adjacent (consecutive) lamps (i. e. such lamps that the distance between their positions is 1) have distinct colors.
In other words, if the obtained garland is t then for each i from 1 to n−1 the condition ti≠ti+1 should be satisfied.
Among all ways to recolor the initial garland to make it diverse you have to choose one with the minimum number of recolored lamps. If there are multiple optimal solutions, print any of them.
Input The first line of the input contains one integer n (1≤n≤2⋅105) — the number of lamps.
The second line of the input contains the string s consisting of n characters ‘R’, ‘G’ and ‘B’ — colors of lamps in the garland.
Output In the first line of the output print one integer r — the minimum number of recolors needed to obtain a diverse garland from the given one.
In the second line of the output print one string t of length n — a diverse garland obtained from the initial one with minimum number of recolors. If there are multiple optimal solutions, print any of them.
Examples inputCopy 9 RBGRRBRGG outputCopy 2 RBGRGBRGR inputCopy 8 BBBGBRRR outputCopy 2 BRBGBRGR inputCopy 13 BBRRRRGGGGGRR outputCopy 6 BGRBRBGBGBGRG
분석하다.
문자열을 한 번 훑어보고, 어떤 문자가 앞의 문자와 동시에, 그를 좌우와 인접한 문자와 다른 문자로 바꾸면 ok
코드

#include
using namespace std;

const int MAX_N=2e5+5;
char str[MAX_N];
char color[5]={"RGB"};

int main()
{
	int n; scanf("%d",&n);
	scanf("%s",str);
	
	int cnt=0; 
	for(int i=1;i<=n-1;i++){
		if(str[i]==str[i-1]){
			
			cnt++;
			for(int j=0;j<3;j++){
				if(color[j]!=str[i-1] && color[j]!=str[i+1]) str[i]=color[j];
			}
		}
	}
	
	cout<<cnt<<endl;
	printf("%s",str);
	
	return 0;
} 

제면
D. Mixing Milk time limit per test1 second memory limit per test256 megabytes inputstandard input outputstandard output Farming is competitive business – particularly milk production. Farmer John figures that if he doesn’t innovate in his milk production methods, his dairy business could get creamed! Fortunately, Farmer John has a good idea. His three prize dairy cows Bessie, Elsie, and Mildred each produce milk with a slightly different taste, and he plans to mix these together to get the perfect blend of flavors.
To mix the three different milks, he takes three buckets containing milk from the three cows. The buckets may have different sizes, and may not be completely full. He then pours bucket 1 into bucket 2, then bucket 2 into bucket 3, then bucket 3 into bucket 1, then bucket 1 into bucket 2, and so on in a cyclic fashion, for a total of 100 pour operations (so the 100th pour would be from bucket 1 into bucket 2). When Farmer John pours from bucket a into bucket b, he pours as much milk as possible until either bucket a becomes empty or bucket b becomes full.
Please tell Farmer John how much milk will be in each bucket after he finishes all 100 pours.
Input The first line of the input file contains two space-separated integers: the capacity c1 of the first bucket, and the amount of milk m1 in the first bucket. Both c1 and m1 are positive and at most 1 billion, with c1≥m1. The second and third lines are similar, containing capacities and milk amounts for the second and third buckets.
Output Please print three lines of output, giving the final amount of milk in each bucket, after 100 pour operations.
Example inputCopy 10 3 11 4 12 5 outputCopy 0 10 2 Note In this example, the milk in each bucket is as follows during the sequence of pours:
Initial State: 3 4 5 1. Pour 1->2: 0 7 5 2. Pour 2->3: 0 0 12 3. Pour 3->1: 10 0 2 4. Pour 1->2: 0 10 2 5. Pour 2->3: 0 0 12 (The last three states then repeat in a cycle …)
분석하다.
시뮬레이션, 100회, 모형을 추출하여 012 순환을 제어합니다
코드

#include
using namespace std;

int a[5],v[5];

int main()
{
	for(int i=0;i<3;i++) scanf("%d%d",&v[i],&a[i]);
	
	for(int i=0;i<100;i++){				
		int j=(i+1)%3 , k=i%3;
		if(a[j]+a[k]<=v[j]) { a[j]+=a[k]; a[k]=0; }
		else a[k]-=v[j]-a[j] , a[j]=v[j];
		
	}
	
	for(int i=0;i<3;i++) cout<<a[i]<<endl;
	
	return 0;
}

제면
E. Binary Tree time limit per test0.5 seconds memory limit per test512 megabytes inputstandard input outputstandard output In computer science, a binary tree is a rooted tree in which each node has at most two children. In this problem, let’s denote n as the number of nodes, l as the number of leaf nodes and h as the height of the tree (a tree consisting of only a root node has a height of 0).
Alice and Bob are playing a game with a binary tree. In this game, Alice and Bob have a binary tree, in which node 1 is the root. They take turns to perform operations on the tree, and Alice always takes the first turn. In each operation, the player taking the turn must choose a node p (any node including the root can be chosen), and remove the subtree rooted at p from the tree. Obviously, the remaining graph, if not empty, is still a binary tree. Then they continue to play with the resulting tree. To make the game more interesting, there is a restriction on which nodes can be chosen as p: the subtree rooted at p (the subtree to be removed) must be a perfect full binary tree. Note that a perfect full binary tree is a binary tree in which all interior (non-leaf) nodes have two children and all leaf nodes have the same depth. It can be easily shown that in a perfect full binary tree, the equation l=2h holds, so does the equation n=2h+1−1. In particular, a tree consisting of only a root node is also a perfect full binary tree. When a player is unable to perform a legal operation, the game ends and that player loses, which means the other player wins.
Three examples of perfect full binary trees. Alice and Bob are both very smart and always play optimally. Can you determine who would win the game?
Input The input contains multiple cases. The first line of the input contains a single positive integer T, the number of cases.
For each case, the first line of the input contains a single integer n (1≤n≤5000), the number of nodes in the binary tree. The following n−1 lines each contains two integers x,y (1≤x≤n,1≤y≤n), which denotes an edge between node x and y. It is guaranteed that the input graph is a binary tree rooted at node 1.
It’s guaranteed that the sum of n over all cases does not exceed 50000.
Output For each case, print the string “Alice” in a single line if Alice would win the game, otherwise print the string “Bob”.
Example inputCopy 1 5 1 2 1 3 3 4 3 5 outputCopy Alice Note In the sample case, Alice removes the subtree rooted at node 3 in the first turn. Then Bob can only choose p=2, which leaves Alice with only the root node 1. Because a tree consisting of only a root node is a perfect full binary tree, Alice can remove the only remaining node and win the game.
분석하다.
우선 완벽한 두 갈래 나무의 결점은 홀수 개가 있다는 것을 알아야 한다. 매번 완벽한 두 갈래 나무를 얻으면 매번의 결점은 홀수 개의 홀수-홀수=홀수-홀수=기a가 마지막 완벽한 두 갈래 나무를 얻으려면 a가 얻기 전의 결점수는 반드시 홀수이다. 그러면 한 걸음 더 나아가는 b가 얻기 전의 결점수는 짝수이다. 이렇게 매번 a가 얻기 전에는 홀수이고 b가 얻기 전에는 짝수이다.그래서 a가 처음 취하기 전, 즉 최초의 결점수 n을 홀수로 하면 a는 반드시 이긴다.
코드

#include
using namespace std;


int main()
{
	int t; cin>>t;
	while(t--){
		int n; cin>>n;					
		for(int i=1;i<=n-1;i++){		
			int x,y; cin>>x>>y;			
		}										 
		if(n%2)puts("Alice");		
		else puts("Bob");
		
	}
	
	return 0;
} 

제면
F. News Distribution time limit per test2 seconds memory limit per test256 megabytes inputstandard input outputstandard output In some social network, there are n users communicating with each other in m groups of friends. Let’s analyze the process of distributing some news between users.
Initially, some user x receives the news from some source. Then he or she sends the news to his or her friends (two users are friends if there is at least one group such that both of them belong to this group). Friends continue sending the news to their friends, and so on. The process ends when there is no pair of friends such that one of them knows the news, and another one doesn’t know.
For each user x you have to determine what is the number of users that will know the news if initially only user x starts distributing it.
Input The first line contains two integers n and m (1≤n,m≤5⋅105) — the number of users and the number of groups of friends, respectively.
Then m lines follow, each describing a group of friends. The i-th line begins with integer ki (0≤ki≤n) — the number of users in the i-th group. Then ki distinct integers follow, denoting the users belonging to the i-th group.
It is guaranteed that ∑i=1mki≤5⋅105.
Output Print n integers. The i-th integer should be equal to the number of users that will know the news if user i starts distributing it.
Example inputCopy 7 5 3 2 5 4 0 2 1 2 1 1 2 6 7 outputCopy 4 4 1 4 4 2 2
분석하다.
어떤 점이 집합된 원소의 개수를 구하면 사용하고 집합할 수 있다. 뿌리 결점의 값은 이 집합된 원소의 개수를 합병하는 동시에 두 결점의 값을 더해서 새로운 뿌리 결점에 부여하여 출력할 때 각 점이 집합된 뿌리 결점을 찾아 그 값을 출력한다.
코드

#include
using namespace std;

const int INF=1e9;
const int MAX_N=5e5+5;
int fa[MAX_N],a[MAX_N],v[MAX_N];
int n,m;

void init(){ for(int i=1;i<=n;i++) fa[i]=i , v[i]=1 ; }	
int get(int x){ return x==fa[x]? x:fa[x]=get(fa[x]); }
void merge(int x,int y){ fa[get(x)]=get(y); }

int main()
{
	scanf("%d%d",&n,&m); init();
	
	for(int i=1;i<=m;i++){
		int k; scanf("%d",&k);
		//if(k==0 || k==1) continue;
		for(int j=1;j<=k;j++){
			scanf("%d",&a[j]);
			int x=get(a[j]),y=get(a[1]);
			if(x!=y) { fa[x]=y; v[y]+=v[x] ;}
		}
		
	}
	for(int i=1;i<=n;i++) printf("%d ",v[get(i)]);
	
	return 0;
}