Codeforces Round #572 Div2 A~E problem solution

Site link: Codeforces Round #572 Div2

gossip

It was a great fight, with 148 in the end However, this is mainly a conclusion question, so I won't do much explanation D2 is more immortal, so you can fill it out later

A. Keanu Reeves

Given a binary string s, defining a string is awesome if and only if the number of zeros and 1s in the string is different Now we want to divide this s into several continuous substrings, and each substring is awesome. At least we should divide it into several segments and output the specific scheme
Data range:
\(1 \leq |s| \leq 100\)

thinking

Because the data range is too small, it can be messed up Because each substring must be continuous, an obvious greedy idea is to look back from the beginning to see where the right endpoint of the longest substring can be found. We can find that this is correct, because the combination of two shorter schemes must correspond to a scheme with the longest plus one section

code

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

int main()
{
	ios::sync_with_stdio(0);cin.tie(0);
	int n;cin >> n;
	string s;cin >> s;
	vector<string> p;
	for(int i = 0;i < n;++i)
	{
		if(s[i] == '#')	continue;
		int m = i,z = 0,o = 0;
		
		for(int j = i;j < n;++j)
		{
			if(s[j] == '0')	++o;
			else ++z;
			if(z != o)	m = j;
		}
		string res;
		for(int j = i;j <= m;++j)	
		{
			res += s[j];
			s[j] = '#';
		}
		p.push_back(res);
	}
	cout << p.size() << endl;
	for(auto& v : p)	cout << v << " ";
    return 0;
}

B. Number Circle

Given a sequence a of \ (n \) elements, it is required that each element on the whole ring satisfies that the sum of two adjacent elements is strictly greater than him It is required to construct a specific scheme or explain that there is no solution

thinking

One of the most direct ideas is to sort and output directly But obviously this question can't be done like this. For example, the data: 5 2 3 5 7 If you sort directly, you will think that 7 is illegal, because the left and right elements are 2 and 5 respectively But there is obviously another construction scheme: 732335 is legal The problem is that the smallest and the second largest may be the same as the largest. In other words, the construction scheme of this problem should be an evenly distributed sum, rather than a direct ranking sum from small to large
Therefore, the idea is relatively clear. Since it is necessary to distribute evenly, sort first, and then distinguish the elements according to parity. Finally, judge whether there is a solution and output it

code

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e5+7;
int a[N];
int main()
{
	int n;scanf("%d",&n);
	for(int i = 1;i <= n;++i)	scanf("%d",&a[i]);
	sort(a + 1,a + n + 1);
	vector<int> res;
	for(int i = 1;i <= n;i += 2)	res.push_back(a[i]);
	reverse(res.begin(),res.end());
	// for(auto& v : res)	cout << v << " ";cout << endl;
	for(int i = 2;i <= n;i += 2)	res.push_back(a[i]);
	for(int i = 1;i <= n;++i)	a[i] = res[i - 1];
	// for(int i = 1;i <= n;++i)	cout << a[i] << " ";cout << endl;
	int ok = 1;
	if(a[n] + a[2] <= a[1])	ok = 0;
	if(a[n - 1] + a[1] <= a[n])	ok = 0;
	for(int i = 2;i <= n - 1;++i)
		if(a[i - 1] + a[i + 1] <= a[i])
			ok = 0;
	if(!ok)	puts("NO");
	else
	{
		puts("YES");
		for(int i = 1;i <= n;++i)	printf("%d ",a[i]);
	}
    return 0;
}

C. Candies!

Given a sequence a, make sure its length is a power of 2 An operation is now specified. For a subsequence whose interval length is a power of 2, every two consecutive adjacent elements are divided into a group, and then the sum of two elements in each group is calculated. If a sum is greater than 10, a candy is added, and the sum \ (\% 10 \) is the new value, and the process is repeated until there is only one element in the whole sequence Give \ (q \) queries. Each query contains an interval. Ask this interval and you can finally get several sweets
Data range:
\(1 \leq n \leq 10^5\)
\(1 \leq s_i \leq 9\)
\(1 \leq q \leq 10^5\)

thinking

Because the data range of this question is too strong, it can be estimated that the processing complexity of each query is either \ (O(1) \) or \ (O(logn) \) Since it is the sum of the whole interval, it is not difficult to think that it should be the sum of the whole interval. The contribution of the whole interval is that the whole interval contains several \ (10 \) Just divide it
Why is he right It can be understood perceptually: if the sum is less than 10, then this part will inevitably pass to the next. If it exceeds 10, then the whole 10 will be removed and then go to the next step. No matter what the situation is, there will not be a situation where the combination of both sides exceeds 10, but after taking the mold respectively, it is only 10, that is, the situation of contradiction

code

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e5+7;
int a[N];
int main()
{
	int n;scanf("%d",&n);
    for(int i = 1;i <= n;++i)	scanf("%d",&a[i]);
    for(int i = 1;i <= n;++i)	a[i] += a[i - 1];
    int q;scanf("%d",&q);
    while(q--)
    {
    	int l,r;scanf("%d%d",&l,&r);
    	printf("%d\n",(a[r] - a[l - 1]) / 10);
    }
    return 0;
}

D1. Add on a Tree

Given a rootless tree with \ (n \) points, two leaf nodes can be found at a time. Add or subtract a real number from all edges on the simple path between the two leaf nodes Q: for this tree, is it possible for any situation to occur in a limited number of operations, that is, there is no situation that cannot occur in a limited number of operations at all
Data range:
\(2 \leq n \leq 10^5\)

thinking

At first glance, this topic is very awesome However, after simulating the example, it can be found that for a point with degree 2, if one side is 1 and the other side is 0, the problem will not be solved, because the two sides must pass through together, and it is impossible for one side to be different from the other side However, this conclusion cannot be generalized. For example, it is possible to have a point with a degree of \ (4 \), and a point is connected with four points. In this case, there is a solution Continue to guess that this should be the conclusion of the whole topic Just check it directly

code

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e5+7;
int deg[N];
int main()
{
	int n;scanf("%d",&n);
	for(int i = 1;i < n;++i)
	{
		int u,v;scanf("%d%d",&u,&v);
		++deg[u];++deg[v];
	}
	int ok = 1;
	for(int i = 1;i <= n;++i)
	{
		if(deg[i] == 2)
		{
			ok = 0;
			break;
		}
	}
	if(!ok)	puts("NO");
	else puts("YES");
    return 0;
}

D2 is too awesome. Write it later

E. Count Pairs

Given a sequence a with a length of \ (n \), find the number that satisfies \ (1 \ Leq I < J \ Leq n \) and \ ((a_i+a_j)*(a_i^2+a_j^2)\equiv k (mod p) \), where \ (k \) is a positive integer and \ (P \) is a prime number
Data range:
\(2 \leq n \leq 3*10^5\)
\(2 \leq p \leq 10^9\)
\(0 \leq k \leq n - 1\)
\(0 \leq a_i \leq p - 1\)

thinking

This form is sum of squares on one side and sum on the other, which is a little ugly There are several directions you can try, such as cubic and expansion. After trying some, you find that they are not very good The correct idea is to multiply both sides by a \ ((a_i - a_j) \) so that the left is a square difference and a square sum, and then continue to reduce the form to obtain this formula: \ (a_i^4-a_j^4\equiv k(a_i-a_j) (mod p) \), continue to pull the right to the left, and find that this expression is equivalent to \ (p| a_i ^ 4-a_j ^ 4-K (a_i-a_j) \), and continue to get a centralized form: \ (p| a_i (a| I ^ 3-K) - A_ J (a_j ^ 3-K) \) is then equivalent to defining a \ (c_i = a_i(a_i^3-k) \), and requires that for each \ (c_i \), how many \ (c_j \) before him satisfy the congruence with its module \ (P \) Use \ (map \) to make statistics
Pay attention to the form of subtraction and prevent negative numbers from taking remainder You can easily get through this problem by typing a fast power and fast multiplication

code

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 3e5+7;
ll a[N];
ll qmul(ll a, ll b, ll P) 
{
  	ll L = a * (b >> 25LL) % P * (1LL << 25) % P;
  	ll R = a * (b & ((1LL << 25) - 1)) % P;
  	return (L + R) % P;
}
ll qpow(ll a,ll b,ll p)
{
	ll res = 1 % p;
	while(b)
	{
		if(b & 1)	res = qmul(res,a,p);
		a = qmul(a,a,p);
		b >>= 1;
	}
	return res;
}
int main()
{
	ios::sync_with_stdio(0);cin.tie(0);
	ll n,p,k;cin >> n >> p >> k;
	map<ll,int> tb;
	int res = 0;
	for(int i = 1;i <= n;++i)	cin >> a[i];
	for(int i = 1;i <= n;++i)
	{
		ll r = ((qpow(a[i],3,p) - k) % p + p) % p;
		r = qmul(r,a[i],p);
		if(tb.count(r))	res += tb[r];
		++tb[r];
	}
	cout << res;
    return 0;
}

Tags: CodeForces

Posted by Hillary on Mon, 23 May 2022 11:47:20 +0300