Codeforces Round #660 (Div. 2)【A—D思路及题解】_this problem contains several cases. the first lin

A. Captain Flint and Crew Recruitment

time limit per test1 second
memory limit per test256 megabytes
inputstandard input
outputstandard output

Despite his bad reputation, Captain Flint is a friendly person (at least, friendly to animals). Now Captain Flint is searching worthy sailors to join his new crew (solely for peaceful purposes). A sailor is considered as worthy if he can solve Flint’s task.

Recently, out of blue Captain Flint has been interested in math and even defined a new class of integers. Let’s define a positive integer x as nearly prime if it can be represented as p⋅q, where 1<p<q and p and q are prime numbers. For example, integers 6 and 10 are nearly primes (since 2⋅3=6 and 2⋅5=10), but integers 1, 3, 4, 16, 17 or 44 are not.

Captain Flint guessed an integer n and asked you: can you represent it as the sum of 4 different positive integers where at least 3 of them should be nearly prime.

Uncle Bogdan easily solved the task and joined the crew. Can you do the same?

Input
The first line contains a single integer t (1≤t≤1000) — the number of test cases.

Next t lines contain test cases — one per line. The first and only line of each test case contains the single integer n (1≤n≤2⋅105) — the number Flint guessed.

Output
For each test case print:

YES and 4 different positive integers such that at least 3 of them are nearly prime and their sum is equal to n (if there are multiple answers print any of them);
NO if there is no way to represent n as the sum of 4 different positive integers where at least 3 of them are nearly prime.
You can print each character of YES or NO in any case.

Example
input
7
7
23
31
36
44
100
258
output
NO
NO
YES
14 10 6 1
YES
5 6 10 15
YES
6 7 10 21
YES
2 10 33 55
YES
10 21 221 6

Note
In the first and second test cases, it can be proven that there are no four different positive integers such that at least three of them are nearly prime.

In the third test case, n=31=2⋅7+2⋅5+2⋅3+1: integers 14, 10, 6 are nearly prime.

In the fourth test case, n=36=5+2⋅3+2⋅5+3⋅5: integers 6, 10, 15 are nearly prime.

In the fifth test case, n=44=2⋅3+7+2⋅5+3⋅7: integers 6, 10, 21 are nearly prime.

In the sixth test case, n=100=2+2⋅5+3⋅11+5⋅11: integers 10, 33, 55 are nearly prime.

In the seventh test case, n=258=2⋅5+3⋅7+13⋅17+2⋅3: integers 10, 21, 221, 6 are nearly prime.

题意：
每个测试样中，问n是否能够分成4个不同的数字，4个数字中near prime的个数大于等于3。
near prime 的定义：两个素数p和q的乘积，且p < q。如果能的话输出YES，下一行输出那4个数字；不能输出NO。

思路：
由于需要分成4个near prime。而最小的3个near prime为：36、40、44。因此只需要分成6、10、14和n-30。由于要4个数字不同，因此需要特判36、40、44的情况。

#include <bits/stdc++.h>
using namespace std;

int main() 
{
    int n;
    cin>>n;
    for(int i=1,t; i<=n; ++i) 
	{
        cin>>t;
        if(t<31) 
		{
            cout<<"NO\n";
            continue;
        }
        else 
		{
            cout<<"YES\n";
            if(t==36) 
			{
                cout<<6<<" "<<10<<" "<<15<<" "<<5<<endl;
                continue;
            }
            else if(t==40)
			{
                cout<<6<<" "<<10<<" "<<15<<" "<<9<<endl;
                continue;
            }
            else if(t==44) 
			{
                cout<<6<<" "<<7<<" "<<10<<" "<<21<<endl;
                continue;
            }
            else 
			{
                cout<<6<<" "<<10<<" "<<14<<" "<<t-30<<endl;
                continue;
            }
        }
    }
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42

B. Captain Flint and a Long Voyage

time limit per test2 seconds
memory limit per test256 megabytes
inputstandard input
outputstandard output

Captain Flint and his crew keep heading to a savage shore of Byteland for several months already, drinking rum and telling stories. In such moments uncle Bogdan often remembers his nephew Denis. Today, he has told a story about how Denis helped him to come up with an interesting problem and asked the crew to solve it.

In the beginning, uncle Bogdan wrote on a board a positive integer x consisting of n digits. After that, he wiped out x and wrote integer k instead, which was the concatenation of binary representations of digits x consists of (without leading zeroes). For example, let x=729, then k=111101001 (since 7=111, 2=10, 9=1001).

After some time, uncle Bogdan understood that he doesn’t know what to do with k and asked Denis to help. Denis decided to wipe last n digits of k and named the new number as r.

As a result, Denis proposed to find such integer x of length n that r (as number) is maximum possible. If there are multiple valid x then Denis is interested in the minimum one.

All crew members, including captain Flint himself, easily solved the task. All, except cabin boy Kostya, who was too drunk to think straight. But what about you?

Note: in this task, we compare integers (x or k) as numbers (despite what representations they are written in), so 729<1999 or 111<1000.

Input
The first line contains a single integer t (1≤t≤1000) — the number of test cases.

Next t lines contain test cases — one per test case. The one and only line of each test case contains the single integer n (1≤n≤105) — the length of the integer x you need to find.

It’s guaranteed that the sum of n from all test cases doesn’t exceed 2⋅105.

Output
For each test case, print the minimum integer x of length n such that obtained by Denis number r is maximum possible.

Example
input
2
1
3
output
8
998

Note
In the second test case (with n=3), if uncle Bogdan had x=998 then k=100110011000. Denis (by wiping last n=3 digits) will obtain r=100110011.

It can be proved that the 100110011 is the maximum possible r Denis can obtain and 998 is the minimum x to obtain it.

题意：
给出一个 n，需要确定一个n位的十进制数x，将x每一位写成二进制形式（要去掉前导零），再删去二进制的后n位，使得最后剩下的二进制最大。求x的最小可能值。

思路1：
根据样例以及初步分析，因为不能有前导零，并且二进制数必须要长。一位十进制数最多能表示成4位二进制数，分别是9(1001)和8(1000)。这样就很显然了，二进制前面n*3位全部是1001，后面n位全部是1000。
解决方案1：
确定一下多少个9，剩下补8。

#include <bits/stdc++.h>
using namespace std;
const int maxn=200005;
int T,n;
int main()
{
	scanf("%d",&T);
	while(T--)
	{
		scanf("%d",&n);
		int res = n%4;
		int t = n-n/4;
		if(res)  t--;
		for(int i=1; i<=t; i++)  printf("9");
		for(int i=t+1; i<=n; i++)  printf("8");
		printf("\n");
	}
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

解法2：
由于要然这个n位数字最大，因此要让二进制数字尽可能长，因此选择1001或1000，在没有被删除尾数的情况下，尽可能选择1001。然后因为要删除尾数，所以如果被删除的情况下，1001和1000结果一样，为了尽可能小，选择1000。因此：n在1 ~ 4情况下，最后一个为8，前面的为9；在5 ~ 8情况下，最后两个为8，前面为9。(因为每4个一组，会让8和9没有区别，所以只要看有几个4组即可，而且通过分析知道是向上取整的)。

#include<bits/stdc++.h>
using namespace std;

int main()
{
    int t;
    cin>>t;
    while(t--)
    {
        double n;
        cin>>n;
        int limit = ceil(n/4);
        
        for(int i=0; i<n-limit; i++)  printf("9");
        for(int i=1; i<=limit; i++)  printf("8");
        
        cout<<endl;
    }
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

C. Uncle Bogdan and Country Happiness

time limit per test2 seconds
memory limit per test256 megabytes
inputstandard input
outputstandard output

Uncle Bogdan is in captain Flint’s crew for a long time and sometimes gets nostalgic for his homeland. Today he told you how his country introduced a happiness index.

There are n cities and n−1 undirected roads connecting pairs of cities. Citizens of any city can reach any other city traveling by these roads. Cities are numbered from 1 to n and the city 1 is a capital. In other words, the country has a tree structure.

There are m citizens living in the country. A pi people live in the i-th city but all of them are working in the capital. At evening all citizens return to their home cities using the shortest paths.

Every person has its own mood: somebody leaves his workplace in good mood but somebody are already in bad mood. Moreover any person can ruin his mood on the way to the hometown. If person is in bad mood he won’t improve it.

Happiness detectors are installed in each city to monitor the happiness of each person who visits the city. The detector in the i-th city calculates a happiness index hi as the number of people in good mood minus the number of people in bad mood. Let’s say for the simplicity that mood of a person doesn’t change inside the city.

Happiness detector is still in development, so there is a probability of a mistake in judging a person’s happiness. One late evening, when all citizens successfully returned home, the government asked uncle Bogdan (the best programmer of the country) to check the correctness of the collected happiness indexes.

Uncle Bogdan successfully solved the problem. Can you do the same?

More formally, You need to check: “Is it possible that, after all people return home, for each city i the happiness index will be equal exactly to hi”.

Input
The first line contains a single integer t (1≤t≤10000) — the number of test cases.

The first line of each test case contains two integers n and m (1≤n≤105; 0≤m≤109) — the number of cities and citizens.

The second line of each test case contains n integers p1,p2,…,pn (0≤pi≤m; p1+p2+…+pn=m), where pi is the number of people living in the i-th city.

The third line contains n integers h1,h2,…,hn (−109≤hi≤109), where hi is the calculated happiness index of the i-th city.

Next n−1 lines contain description of the roads, one per line. Each line contains two integers xi and yi (1≤xi,yi≤n; xi≠yi), where xi and yi are cities connected by the i-th road.

It’s guaranteed that the sum of n from all test cases doesn’t exceed 2⋅105.

Output
For each test case, print YES, if the collected data is correct, or NO — otherwise. You can print characters in YES or NO in any case.

Examples
input
2
7 4
1 0 1 1 0 1 0
4 0 0 -1 0 -1 0
1 2
1 3
1 4
3 5
3 6
3 7
5 11
1 2 5 2 1
-11 -2 -6 -2 -1
1 2
1 3
1 4
3 5
output
YES
YES
input
2
4 4
1 1 1 1
4 1 -3 -1
1 2
1 3
1 4
3 13
3 3 7
13 1 4
1 2
1 3
output
NO
NO

Note
Let’s look at the first test case of the first sample:

At first, all citizens are in the capital. Let’s describe one of possible scenarios:

a person from city 1: he lives in the capital and is in good mood;
a person from city 4: he visited cities 1 and 4, his mood was ruined between cities 1 and 4;
a person from city 3: he visited cities 1 and 3 in good mood;
a person from city 6: he visited cities 1, 3 and 6, his mood was ruined between cities 1 and 3;
In total,
h1=4−0=4,
h2=0,
h3=1−1=0,
h4=0−1=−1,
h5=0,
h6=0−1=−1,
h7=0.
The second case of the first test:

All people have already started in bad mood in the capital — this is the only possible scenario.

The first case of the second test:

The second case of the second test:

It can be proven that there is no way to achieve given happiness indexes in both cases of the second test.

题解1：
题意：
给出一棵树，每个节点给出人数、不一定准确的心情值。每个人从1号节点出发，在路上可能有些人心情会从good变成bad。每个人沿着最短路径回到自己的节点，求每个节点给出的心情值是否可能都是准确的。（心情值=good人数-bad人数）
思路：
对每一个点求出它和它的子树中的人数，根据这个人数和预估心情值就可以算出多少个人是好心情，多少个人是坏心情。好心情人数算出来是以下情况，必然不合法：1.是负数 2.是小数 3.比子树总人数大 4.比子树的好心情人数少。

#include <bits/stdc++.h>
#define ll long long 
using namespace std;
const int maxn=200005;

struct node {int to,next;} edge[maxn<<1];
int head[maxn],k=0;

void add(int u,int v)
{
	edge[++k].to = v;
	edge[k].next = head[u];
	head[u] = k;
}

int n,T;
ll m,p[maxn],h[maxn];
ll good[maxn],bad[maxn],size[maxn];
bool flag=false;

void dfs(int x,int fa)
{
	size[x]=p[x];
	for(int i=head[x]; i; i=edge[i].next)
	{
		if(edge[i].to==fa)  continue;
		dfs(edge[i].to,x);
		size[x] += size[edge[i].to];
	}
	good[x] = size[x]+h[x];
	
	if((good[x]&1)||good[x]<0)  flag=true;
	good[x] >>= 1;
	bad[x] = size[x]-good[x];
	
	if(bad[x]<0)  flag=true;
	
	int total_good = 0;
	for(int i=head[x]; i; i=edge[i].next)
	{
		if(edge[i].to==fa)  continue;
		total_good += good[edge[i].to];
	}
	
	if(good[x]<total_good)  flag=true;
}

int main()
{
	memset(head,0,sizeof(head));
	memset(good,0,sizeof(good));
	memset(bad,0,sizeof(bad));
	memset(size,0,sizeof(size));
	
	scanf("%d",&T);
	while(T--)
	{
		k=0;
		flag=false;
		scanf("%d%lld",&n,&m);
		
		for(int i=1; i<=n; i++)  scanf("%lld",&p[i]);
		for(int i=1; i<=n; i++)  scanf("%lld",&h[i]);
		
		for(int i=1,x,y; i<n; i++)
		{
			scanf("%d%d",&x,&y);
			add(x,y);  add(y,x);
		}
		
		dfs(1,1);
		if(flag)  printf("NO\n");
		else  printf("YES\n");
		for(int i=1; i<=n; i++)  head[i]=good[i]=bad[i]=size[i]=0;
	}
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77

题解2：

#include <bits/stdc++.h>
using namespace std;

int T,n,m,flg;
int const N = 2e5+10;
int g[N], b[N], h[N], p[N], sz[N];
int e[N*2], ne[N*2], hh[N], idx;

void add(int a, int b) {
    e[idx]=b, ne[idx]=hh[a], hh[a]=idx++;
}

void dfs(int u, int fa) {
    sz[u] = p[u];
    int G = 0;
    for (int i=hh[u]; ~i; i=ne[i]) {
        int j=e[i];
        if(j==fa)  continue;
        dfs(j,u);
        sz[u] += sz[j];
        G += g[j];
    }
    
    g[u] = (sz[u]+h[u])/2, b[u] = (sz[u]-h[u])/2;
    if (g[u]+b[u]!=sz[u] || g[u]<0 || b[u]<0 || g[u]<G || g[u]-b[u]!=h[u])  flg=0;
    return ;
}

int main()
{
    cin>>T;
    while(T--)
	 {
        memset(sz, 0, sizeof sz);
        memset(hh, -1, sizeof h);
        idx = 0;
        flg = 1;
        cin >> n >> m;
        for (int i=1; i<=n; ++i)  scanf("%d", &p[i]);
        for (int i=1; i<=n; ++i)  scanf("%d", &h[i]);
        for (int i=1,a,b; i<=n-1; ++i) {
            scanf("%d%d", &a, &b);
            add(a, b);
            add(b, a);
        }
        dfs(1, -1);
        if(flg)  cout<<"YES\n";
        else  cout<<"NO\n";
    }
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51

D. Captain Flint and Treasure

time limit per test2 seconds
memory limit per test256 megabytes
inputstandard input
outputstandard output

Captain Fint is involved in another treasure hunt, but have found only one strange problem. The problem may be connected to the treasure’s location or may not. That’s why captain Flint decided to leave the solving the problem to his crew and offered an absurdly high reward: one day off. The problem itself sounds like this…

There are two arrays a and b of length n. Initially, an ans is equal to 0 and the following operation is defined:

Choose position i (1≤i≤n);
Add ai to ans;
If bi≠−1 then add ai to abi.
What is the maximum ans you can get by performing the operation on each i (1≤i≤n) exactly once?

Uncle Bogdan is eager to get the reward, so he is asking your help to find the optimal order of positions to perform the operation on them.

Input
The first line contains the integer n (1≤n≤2⋅105) — the length of arrays a and b.

The second line contains n integers a1,a2,…,an (−106≤ai≤106).

The third line contains n integers b1,b2,…,bn (1≤bi≤n or bi=−1).

Additional constraint: it’s guaranteed that for any i (1≤i≤n) the sequence bi,bbi,bbbi,… is not cyclic, in other words it will always end with −1.

Output
In the first line, print the maximum ans you can get.

In the second line, print the order of operations: n different integers p1,p2,…,pn (1≤pi≤n). The pi is the position which should be chosen at the i-th step. If there are multiple orders, print any of them.

Examples
input
3
1 2 3
2 3 -1
output
10
1 2 3
input
2
-1 100
2 -1
output
99
2 1
input
10
-10 -1 2 2 5 -2 -3 -4 2 -6
-1 -1 2 2 -1 5 5 7 7 9
output
-9
3 5 6 1 9 4 10 7 8 2

题意：
给出长度为n的a数组和b数组，一共操作n次（每个位置必须操作一次），若第i次选定位置i，则ans+=a[i]，并且 a[b[i]]+=a[i]，确定一个操作顺序使得取出的ans最大，并输出操作顺序。
思路：
题目中保证了不会出现环，并且a[b[i]]+=a[i]是单向操作，想到有向图的拓扑排序，做DAG dp就好。
解法：
从度数为0的点开始，如果当前值大于0，加到下一个点上就可以使下一个点更优（意义为先选这个点）；如果当前值小于0，那么加到下一个点会使结果更差，就不加（意义为先选下一个点，后选这个点）。最后输出方案按照拓扑序输出，详见代码。

#include <bits/stdc++.h>
using namespace std;
const int maxn=200005;

struct node {int to,next;} edge[maxn<<1];
int k=0,head[maxn];

void add(int u,int v)
{
	edge[++k].to=v;
	edge[k].next=head[u];
	head[u]=k;
}

int n,tot=0,a[maxn];
int degree[maxn],rd[maxn],p[maxn];
long long ans=0,f[maxn];

void toposort()
{
	queue<int> q;
	for(int i=1; i<=n; i++)
		if(!rd[i])  q.push(i);
	while( !q.empty() )
	{
		int x=q.front();
		q.pop();
		p[++tot]=x;
		ans+=f[x];
		for(int i=head[x]; i; i=edge[i].next)
		{
			f[edge[i].to] += max(0ll,f[x]);
			rd[edge[i].to]--;
			if(!rd[edge[i].to]) 
			    q.push(edge[i].to);
		}
	}
}

int main()
{
	memset(f,0,sizeof(f));
	scanf("%d",&n);
	for(int i=1; i<=n; i++) scanf("%d",&a[i]);
	
	for(int i=1,b; i<=n; i++)
	{
		scanf("%d",&b);
		if(b==-1)  continue;
		add(i,b);
		rd[b]++;
		degree[i]++;
		degree[b]++;
	}
	
	for(int i=1; i<=n; i++)  f[i]=(long long)a[i];
	toposort();
	printf("%lld\n",ans);
	
	for(int i=1; i<=n; i++) 
	    if(f[p[i]]>=0)  printf("%d ",p[i]);
	for(int i=n; i; i--) 
	    if(f[p[i]]<0)  printf("%d ",p[i]);
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65