A. Perfectly Imperfect Array:

Title Link: https://codeforces.ml/contest/1514/problem/A

Main idea of the title:

If there is NO data in each group, then there is NO data in each group. If there is NO data in each group, then there is NO data in each group.
Data range: 1 < = T < = 100, 1 < = n < = 100, 1 < = AI < = 10000

Topic analysis:

Without any technical content, it is directly open to judge whether the result of prescription is just an integer. If there is a number that is not an integer, it indicates that there is a number that is not a complete square number. Output YES, otherwise output NO.

Positive solution procedure:

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <algorithm>
#include <queue>

using namespace std;
typedef long long ll;
ll T,n;
int main()
{
	scanf("%lld",&T);
	while(T--)
	{
		ll flag=0;
		scanf("%lld",&n);
		for(ll i=1;i<=n;i++)
		{
			ll temp;
			scanf("%lld",&temp);
			double ano=sqrt((double)temp);
			if(abs(ano-(ll)ano)>1e-8)//eps is the best way to compare the size of double type
				flag=1;//Because all data should be read in, mark it first and then output it at the end
		}
		if(flag)
			printf("YES\n");
		else
			printf("NO\n");
	}
	
	return 0;
}

B. AND 0, Sum Big:

Title Link: https://codeforces.ml/contest/1514/problem/B

Main idea of the title:

There are t groups of data, and each group has an n and a k. It is required to construct an array a with a length of n, so that the array meets three conditions:

• Each number in the array satisfies 0 < = AI < = 2k-1.
• The bitwise sum of all numbers in the array is 0.
• The sum of all numbers in the array is as large as possible.

It is required to output the number of arrays a that can be constructed. Since the answer may be large, the output answer is the remainder of 109 + 7.

Topic analysis:

1. Because all numbers meet 0 < = AI < = 2k-1, they can be converted into k-bit binary numbers.
2. First of all, if the value of bitwise sum of all numbers is 0, it means that n numbers are required to meet that there are some numbers in k-bit binary so that the k-bit is 0. That is, for bit i (1 < = i < = k), at least one number is 0.
3. We consider how to make this array meet the third condition. Because for the ith bit (1 < = I < = k), as long as one number is 0, the ith bit in the final bitwise and result is 0. Making the i-th bit 0 is equivalent to reducing 2i-1, so to make the final sum as large as possible, it is natural to use the least 0 to complete this process. Therefore, only n numbers are needed to bear K zeros.
4. Because a number can bear multiple zeros, the answer is very simple and does not need more knowledge of permutation and combination. For k zeros, each 0 is assumed by one of the n numbers, so the answer is nk, and the final answer is to take the remainder of 109 + 7.

Positive solution code:

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <algorithm>
#include <queue>

using namespace std;
typedef long long ll;
const ll mod=1e9+7;
ll T,n,k;
ll quickmi(ll a,ll p)//Fast power, easy to take remainder
{
	ll ans=1;
	while(p)
	{
		if(p&1)
			ans=ans*a%mod;
		a=a*a%mod;
		p>>=1;
	}
	return ans;
}
int main()
{
	scanf("%lld",&T);
	while(T--)
	{
		scanf("%lld%lld",&n,&k);
		printf("%lld\n",quickmi(n,k));//Find n^k
	}
	
	return 0;
}

C. Product 1 Modulo N:

Title Link: https://codeforces.ml/contest/1514/problem/C

Main idea of the title:

Given an N, it is required to select some non repeated numbers to form an array num, and the numbers in num meet 1 < = Numi < = n-1. Finally, the product of all numbers in array a is 1. The length of the array that meets this condition is required to be as large as possible.

Topic analysis:

1. We set the product of num array as a, so the meaning of the title is roughly equivalent to a ≡ 1(mod n), which is actually: gcd(n,a%n)=1. According to Euclid's law, we can know that gcd(n,a%n)=gcd(a,n)=1. Therefore, all numbers that are not coprime with n cannot appear in this sequence.
2. Multiply all numbers that are not coprime with N, assume that the product is b, and take the remainder of n to obtain b ≡ x(mod n). Obviously, X must be a value of 1~n-1, and from 1, X must be coprime with n. Then the answer is to remove x from the remaining number. Because according to the nature of congruence, there are: b/x ≡ x/x(mod n/gcd(x,n)), that is, b/x ≡ 1(mod n). Of course, for the case of x=1, there is no need to remove it.

Positive solution code:

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <algorithm>
#include <queue>

using namespace std;
typedef long long ll;
const ll maxn=100010;
ll gcd(ll a,ll b)
{
	if(!b)
		return a;
	return gcd(b,a%b);
}
ll ans[maxn],cnt=0,n;
int main()
{
	scanf("%lld",&n);
	ll fina=1;
	for(ll i=1;i<=n;i++)
	{
		if(gcd(i,n)==1)//Judge whether it is mutual quality
		{
			ans[++cnt]=i;
			fina=fina*i%n;//Calculate product
		}
	}
	if(fina!=1)//If x is not equal to 1
	{
		printf("%lld\n",cnt-1);
		for(ll i=1;i<=cnt;i++)
			if(ans[i]!=fina)//Remove fina
				printf("%lld ",ans[i]);
	}
	else//x=1, direct output
	{
		printf("%lld\n",cnt);
		for(ll i=1;i<=cnt;i++)
			printf("%lld ",ans[i]);
	}
	
	return 0;
}

D. Cut and Stick:

Title Link: https://codeforces.ml/contest/1514/problem/D

Main idea of the title:

Give an array of length n a and q groups of queries, each containing L and r. The topic hopes to divide a[l] ~ a[r] into several subsets, so that the subset with length x does not appear more than or equal to the frequency ⌈ \lceil ⌈ x 2 \frac{x}{2} 2x​ ⌉ \rceil ⌉ number of. Ask how many paragraphs a[l] ~ a[r] should be divided into at least.
Data range: 1 < = n, Q < = 3 * 105, 1 < = AI < = n, 1 < = l < = R < = n.

Topic analysis:

1. Because the frequency of questions is greater than or equal to ⌈ \lceil ⌈ x 2 \frac{x}{2} 2x​ ⌉ \rceil ⌉, so this frequency must be the largest in this subset. Maybe some methods to deal with the maximum value are needed.
2. For the question of how many times a number appears in the middle of l ~ r, we can record the position of a number in the array, and then get the answer by dichotomy. This complexity is O(logn) instead of O(n) counted directly. Considering the data range of ai, we can directly use vector to complete this process.
3. Since we are dealing with the maximum value problem on an interval, why can't we use the segment tree to maintain the number with the highest frequency on an interval? So we can first use the segment tree interval to maintain the maximum frequency.
4. So how to calculate the answer? We assume that a subset of length x, the maximum frequency of occurrence is f, and this number is k.

• f< ⌈ \lceil ⌈ x 2 \frac{x}{2} 2x​ ⌉ \rceil ⌉, then the answer is 1.
• f>= ⌈ \lceil ⌈ x 2 \frac{x}{2} 2x​ ⌉ \rceil ⌉ there are x-f of these elements left. Due to the upward rounding relationship, it can be combined with x-f+1 k to form a legal subset, and the remaining k forms a subset by itself. So the final answer is: f-(x-f+1)+1=2*f-x.

Positive solution code:

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <algorithm>
#include <queue>

using namespace std;
typedef long long ll;
const ll maxn=300010;
ll num[maxn],tree[4*maxn];
vector<ll> times[maxn];
ll getnum(ll l,ll r,ll pos)//Two points get the number of pos occurrences between l and r
{
    return upper_bound(times[pos].begin(),times[pos].end(),r)-lower_bound(times[pos].begin(),times[pos].end(),l);
}
ll mymax(ll x,ll y,ll l,ll r)//A user-defined ratio size function is used to maintain the segment tree
{
	ll t1=getnum(l,r,x),t2=getnum(l,r,y);
	if(t1>t2)
		return x;
	return y;
}
void build(ll pos,ll l,ll r)//Construction of line segment tree
{
	if(l==r)
	{
		tree[pos]=num[l];
		return;
	}
	ll mid=(l+r)>>1;
	build(pos<<1,l,mid);
	build(pos<<1|1,mid+1,r);
	tree[pos]=mymax(tree[pos<<1],tree[pos<<1|1],l,r);
}
ll query(ll pos,ll l,ll r,ll s,ll e)//Query of segment tree
{
	if(s<=l && r<=e)
		return getnum(s,e,tree[pos]);//The final answer is frequency, so you have to query the number of occurrences first
    ll mid=(l+r)>>1,t1=0,t2=0;
    if(s<=mid)
    	t1=query(pos<<1,l,mid,s,e);
    if(e>mid)
    	t2=query(pos<<1|1,mid+1,r,s,e);
    return max(t1,t2);
}
int main()
{
	ll n,q;
	scanf("%lld%lld",&n,&q);
	for(ll i=1;i<=n;i++)
	{
		scanf("%lld",&num[i]);
		times[num[i]].push_back(i);//Record num[i] appears at position I
	}
	build(1,1,n);
	for(ll i=1;i<=q;i++)
	{
		ll l,r;
		scanf("%lld%lld",&l,&r);
		printf("%lld\n",max(1ll,2*query(1,1,n,l,r)-(r-l+1)));//Get the answer
	}
	
	return 0;
}