Codeforces Round 875 (Div. 2) A-D

A. Twin Permutations

题意：给出一个由[1,2,...,n]组成的数组a，构造另一个由[1,2,...,n]组成的数组b，使得a[1]+b[1]<=a[2]+b[2]<=...<=a[n]+b[n]

Solution

可以想到只要让他们全为n+1就行了，这样是一定有解的

void solve()
{
	int n;cin>>n;
	for(int i=1;i<=n;i++)
	{
		cin>>a[i];
	}
	for(int i=1;i<=n;i++)
	{
		b[i]=n+1-a[i];
		
	}
	for(int i=1;i<=n;i++)
	{
		cout<<b[i]<<" ";
	}
	cout<<"\n";
}

B. Array merging

题意：给出两个数组a,b，将他们合并，并保持原数组顺序不变，问最长的元素相同的子串是多长

Solution

范围好像不大，直接开了两个数组都存了下来然后遍历一遍

void solve()
{
	int n;
	cin>>n;
	for(int i=1;i<=n;i++)cin>>a[i];
	for(int i=1;i<=n;i++)cin>>b[i];
	for(int i=1;i<=n*2;i++)c[i]=d[i]=0;
	int cnt=0;
	int last=-1;
	for(int i=1;i<=n+1;i++)
	{
		if(i==n+1||a[i]!=last)
		{
			if(last!=-1)c[last]=max(c[last],cnt);
			cnt=1;
			last=a[i];
		}else
		{
			cnt++;
		}
	}
	cnt=0;
	last=-1;
	for(int i=1;i<=n+1;i++)
	{
		if(i==n+1||b[i]!=last)
		{
			if(last!=-1)d[last]=max(d[last],cnt);
			cnt=1;
			last=b[i];
		}else
		{
			cnt++;
		}
	}
	int ans=0;
	for(int i=1;i<=n*2;i++)
	{
		ans=max(ans,c[i]+d[i]);
	}
	cout<<ans<<"\n";
	
}

C. Copil Copac Draws Trees

题意：有一颗树，最开始已经把点1画出来了，然后按给定的n-1边的顺序遍历所有边并依次检查这些边，如果当前检查的边至少有一个点画出来了，那么就把这条边和这条边上的点画出来，问最少要按照给定的边顺序遍历多少次才能完整画出这棵树

Solution

可以发现啊，假设第i个点是在第j条边并且是第k次遍历的时候被第一次画出，那么在它相连的点要么是在第k次遍历被第一次画出，要么是在第k+1次遍历的时候被第一次画出，而且画的顺序肯定是从根节点往外画，因为最开始只有根节点画出来了，那其实我们可以写一个类似bfs的东西，并且以被画出的遍历层数升序在优先队列里排序，把相邻节点都压入即可

struct node
{
	int x,level,p; //x表示这是第x个节点，level表示它第一次被画出的边的位置，p表示它是第p次遍历被画出的
	bool operator < (const node &t)const&{
		return p<t.p;
	}
};
vector<pii>e[N];
int t[N];
int vis[N];
void solve()
{
	int n;cin>>n;
	for(int i=1;i<=n;i++)
	{
		e[i].clear();
		vis[i]=0;
	}
	priority_queue<node>q;
	for(int i=1;i<n;i++)
	{
		int u,v;cin>>u>>v;
		e[u].push_back({v,i});
		e[v].push_back({u,i});
	}
	t[1]=1;
	q.push({1,0,1});
	int ans=0;
	while(q.size())
	{
		node t=q.top();
		q.pop();
		vis[t.x]=1;
		ans=max(ans,t.p);
		for(auto it:e[t.x])
		{
			if(vis[it.first])continue;
			if(t.x==1)q.push({it.first,it.second,1}); //特判一下1
			else 
			{
				if(it.second>t.level)//如果相邻节点第一次被画出的边在当前节点第一次被画出的后面
				{
					q.push({it.first,it.second,t.p});
				}else
				{
					q.push({it.first,it.second,t.p+1});
				}
			}
		}
	}
	cout<<ans<<"\n";
}

D. The BOSS Can Count Pairs

题意：给出两个数组a,b，求(i,j)的对数，满足a[i]×a[j]=b[i]+b[j]，i<j

Solution

没啥好思路，看知乎上面的思路，不贴代码了

写一下我的理解吧

a[i]×a[j]=b[i]+b[j]，题目条件里面写的是所有数都<=n，所以a[i]×a[j]其实是小于等于2n，那么就有min(a[i],a[j])<=sqrt(2n)，这样子我们可以遍历(1,sqrt(2n))的数a[i]，我们由a[i]×a[j]=b[i]+b[j]可知：b[i]=a[j]×a[i]-b[j]，将数组按a[i]的大小排序，然后枚举所有(a[j],b[j])，找到对应的(a[i],b[i])的对数即可