A - Honey practice

Description

n balls are arranged in a row, and the color of the ith ball is ai

The distance between ball i and j is defined as | (i-J) * (AI AJ)|

Find the sum of the distances between all the small balls

i and j and j and i do not have to be calculated repeatedly

100%: n<=1000000，0<=ai<=1

thinking

It is easy to get from the condition that the distance is not 0 only when ai aj is not 0, that is, ai and aj are not equal. In other words, only two small balls with unequal ai and aj can contribute.

Observing the data range, it is easy to find a breakthrough: ai is either 0 or 1. So for a 0 color ball, only 1 color ball can contribute to it, and 1 color ball is the same.

For any small ball i, let there be a1 0 color balls in front of it, and the number sum is a2; There are b1 1 color balls, numbered and b2.

If I is a 0 color ball, the contribution of the previous 1 color ball to it is b1*i-b2, which is a 1 color ball. The same is true. (only the small ball before I needs to be considered, because the title requires that I, J and j, I do not need to be calculated repeatedly)

code

(the code has nothing to do with the above questions except the basic idea. It belongs to my fooling during the competition...)

#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
const int N=1e6;
int n,cnt,tot,a[N+1];
long long ans,s[N+1],p[N+1],q[N+1];
int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
	{
		scanf("%d",&a[i]);
		if(!a[i]) p[++cnt]=i;
		else q[++tot]=i;
	}
	for(int i=1;i<=tot;i++)
	s[i]=s[i-1]+q[i];
	for(int i=1;i<=cnt;i++)
	{
		int k=lower_bound(q+1,q+tot+1,p[i])-q;
		int len=tot-k+1;
		ans+=(s[tot]-s[k-1]-len*p[i])+((k-1)*p[i]-s[k-1]);
	}
	printf("%lld",ans);
	return 0;
}

B -- minimum spanning tree

Description

n people, everyone has an intelligence

People can communicate with each other, and the communication has corresponding expenses. After the communication, they enjoy each other's information

A and B communicate, a and C communicate, and B and C can also enjoy each other

There is a corresponding cost for sending any one of n people to perform the task

Requirements: dispatch personnel to perform tasks. The dispatched personnel shall include all information (not necessarily only one), and ask the minimum cost

thinking

When I saw you in the game, I knew I met you, my smallest spanning tree!

First of all, considering that two people can know each other's intelligence when they meet at a certain cost, it is associated with connecting the two points with one edge. Considering that the dispatched person must get the information of everyone, it is associated with the interconnection of all points in a graph.
Isn't it a minimum spanning tree to make all points connected with each other with the least cost?

Finally, the cost of performing tasks can be regarded as adding an n+1 node in the figure to create an edge with each person, and the edge weight is the cost of performing tasks for this person.

For this n+1 node graph, run the minimum spanning tree algorithm once.

code

#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
const int N=1e6;
struct edge
{
	int u,v,w;
}a[N];
int n,k,cnt,fa[N];
long long ans;
void add(int u,int v,int w)
{
	cnt++;
	a[cnt].u=u;
	a[cnt].v=v;
	a[cnt].w=w;
}
int find(int x)
{
	if(fa[x]==x) return fa[x];
	return fa[x]=find(fa[x]);
}
void join(int x,int y)
{
	int fx=find(x),fy=find(y);
	fa[fx]=fy;
}
bool cmp(edge a,edge b){return a.w<b.w;}
int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
	for(int j=1;j<=n;j++)
	{
		scanf("%d",&k);
		if(i<j) add(i,j,k);
	}
	for(int i=1;i<=n;i++)
	{
		scanf("%d",&k);
		add(n+1,i,k);
	}
	sort(a+1,a+cnt+1,cmp);
	for(int i=1;i<=n+1;i++) fa[i]=i;
	for(int i=1,j=1;i<=n;i++)
	{
		while(find(a[j].u)==find(a[j].v)) j++;
		join(a[j].u,a[j].v);
		ans+=a[j].w;
	}
	printf("%lld",ans);
	return 0;
}

C - maintain the k-th largest number

Description

A sequence a with a length of n is given to describe a full arrangement a with a length of N. AI indicates how many of the first i-1 numbers are greater than AI.
Request this Full Permutation a

thinking

Traverse a from the back to the front. According to the definition in the title, the number of an in the first n-1 number of a is greater than an, in other words, an is the number with the largest An+1 in 1~n. Similarly, an-1 is the largest number of An-1+1 after removing the determined an. By analogy, the problem is transformed into how to maintain the k-th largest number in a sequence.

There are still many algorithms, such as nlogn and merge (nlogn or n). I use the bucket row (n) with better writing and faster speed, and it is stuck to O(n2). However, as soon as the data is large (timeout) or disgusting (beyond the range of the bucket), the bucket row is useless.

The senior taught a better algorithm: using tree array to dynamically maintain prefix and.

For each existing number I, the position subscript i in the array is assigned to 1. For any number I, the size ranking of I can be obtained as long as the prefix sum of array subscripts 1~i is calculated. If this number does not exist or is deleted, assign the position of its corresponding subscript to 0.
The principle is also easy to understand, that is to optimize the bucket row and quickly find out how many numbers are less than i through prefix and.

With this, we only need the subscript of the binary array to get the prefix and the subscript when it is exactly k, that is, the number K.

code

(I'm too lazy to write the optimization of tree array. I've passed it anyway)

#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
using namespace std;
const int N=1e4;
int n,a[N],vis[N],ans[N];
int query(int k)
{
	for(int i=n,cnt=0;i;i--)
	{
		if(!vis[i]) cnt++;
		if(cnt==k) return i;
	}
}
int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
	scanf("%d",&a[i]);
	for(int i=n;i;i--)
	ans[i]=query(a[i]+1),vis[ans[i]]=1;
	for(int i=1;i<=n;i++)
	printf("%d ",ans[i]);
	return 0;
}

D -- difference... Something like that

Description

The problem surface is wrong. It should be the length of the substring. (otherwise the problem will sb explode)

thinking

Considering the idea of difference, assign + 1 to boys and - 1 to girls as prefix and sum.

If the number of men and women in an interval i~j is equal, the sum of all values in the interval is obviously equal to 0 (because equal + 1 and - 1 cancel each other).
It is represented by the prefix and, that is, s[j]-s[i-1]=0. Simple shift can get s[j]=s[i-1].

In other words, if s[j]=s[i], then i+1~j is an equal range of men and women. Use the bucket to record the position of the earliest s array value (because it is required to be the largest). If there is the same value later, subtract the previous position from the current position and compare it with the answer.

code

#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
const int N=1e6;
int n,s[N],h[N],ans; 
int main()
{
	scanf("%d",&n);
	for(int i=1,k;i<=n;i++)
	{
		scanf("%d",&k);
		if(k==0) k=-1;
		s[i]=s[i-1]+k;
	}
	for(int i=1;i<=n;i++)
	{
		int t=s[i]+n;
		if(h[t]==0) h[t]=i;
		else ans=max(ans,i-h[t]);
	}
	printf("%d",ans);
	return 0;
}

Tips

I am AK today!!!!!!!!!!!