2020牛客寒假算法基础训练营6

---

A-配对

题目描述

现在有正整数集合$A$和$B$，每个集合里有$N$个数，你要建立他们间的一一映射。
将每对配对的数字相加可以得到N个和，你要做的就是最大化第K大的和。
$1≤K≤N≤100000$输入的所有数字不超过${10^8}$。

输入描述

第一行2个数字$N,K$
接下来两行，每行$N$个正整数，分别表示$A$和$B$中的元素。

输出描述

一行，表示第 K 大的和的最大值。

示例1

输入
3 2
1 2 3
1 2 3
输出
5

思路

首先，组成这K对数字的显然是A中最大的K个数字和B中最大的K个数字。
问题转化为，有K对数字，怎样配对使得最小的和最大。
经过玄学分析可以得到，倒序配对是最优的。

代码

#include<iostream>
#include<algorithm>
using namespace std;
typedef long long ll;
bool cmp(int x,int y)。
{
	return x>y;
}
void solve()
{
	const int N=100003;
	int a[N],b[N];
	int n,k,ans=1e9;
    cin>>n>>k;
	int i;
	for(i=1;i<=n;i++) cin>>a[i];
	for(i=1;i<=n;i++) cin>>b[i];
	sort(a+1,a+1+n,cmp);
	sort(b+1,b+1+n,cmp);
	sort(b+1,b+1+k);//倒过来
	for(i=1;i<=k;i++) ans=min(ans,a[i]+b[i]);
	cout<<ans;
}
int main()
{
	ios::sync_with_stdio(false); 
	solve();
	return 0;
}

B-图

题目描述

现在有一个N个点的有向图，每个点仅有一条出边
你需要求出图中最长的简单路径包含点的数量。
$(1≤N≤1000000)$

输入描述

第一行一个数字N。
接下来N行，每行一个正整数，第i+1行的数字表示第i个点出边终点的编号
（点从1开始标号）。

输出描述

一行一个数字，最长的简单路径包含点的数量。

示例1

输入
3
2
3
2
输出
3

思路

每一个节点的出度为1的有向图图，是一个基环内向树森林。
如图：

要找到最长的简单路径，显然可以以每一个节点为起点做一次dfs，为了降低时间复杂度，采用记忆化搜索。
假设从节点X开始递归，当搜索到节点P时，会走一个环，再一次走到节点P，这时候我我们已经将节点P的标记改为true，所以说明找到了一个环。当找到一个环时，我们遍历环，将环上的点在环上的标记改为ture，并计算环的长度。于是从节点X开始的最长简单路径长度是：X至节点P的长度加上环的长度。
有一个需要注意的坑，题目需要计算经过最多节点的路径，假设路径长为l，如果路径中有环，那么节点数为l；如果路径是一条链，那么节点数为l+1。

代码

#include<algorithm>
#include<cstdio>
using namespace std;
const int N=1000009;
int to[N];
struct node
{
	bool exist=false;
	int len=0;
}dp[N];//dp[x]:以节点x为起点的最长简单路径长度。
bool vis[N]={false};
int dfs(int x)
{
	if(dp[x].len) return dp[x].len+1;
	else
	{
		if(vis[to[x]])//to[x]走过了，说明在环上。 
		{
			int temp=to[x];
			int res=1;
			while(temp!=x)//走一遍环
			{
				dp[temp].exist=true;
				res++;//记录环的长度
				temp=to[temp];
			}
			dp[x].len=res;
			dp[x].exist=true;
			return dp[x].len+1;
		}
		else
		{
			vis[to[x]]=true;
			dp[x].len=dfs(to[x]);
			vis[to[x]]=false;
			if(dp[x].exist) dp[x].len--;//在环上
			return dp[x].len+1;
		}
	}
}
void solve()
{

	int n;
	scanf("%d",&n);
	int i,j;
	for(i=1;i<=n;i++) scanf("%d",&to[i]);
	int ans=-1;
	for(i=1;i<=n;i++) 
	{
		vis[i]=true;
		dfs(i);
		vis[i]=false;
		ans=max(ans,dp[i].len);
	}
	printf("%d",ans);
}
int main()
{
	solve();
	return 0;
}

C-汉诺塔

题目描述

现在你有 N 块矩形木板，第 i 块木板的尺寸是 Xi×Yi，你想用这些木板来玩汉诺塔的游戏。
我们知道玩汉诺塔游戏需要把若干木板按照上小下大的顺序堆叠在一起，但因为木板是矩形，所以有一个问题：
第 i 块木板能放在第 j 块木板上方当且仅当 Xi<Xj 且 Yi<Yj，于是你很可能没法把所有的木板按照一定的次序叠放起来。
你想把这些木板分为尽可能少的组，使得每组内的木板都能按照一定的次序叠放。
你需要给出任意一种合理的分组方案。
提醒：“任意”意味着你的答案不必和标准输出完全一致，只要正确即可。

输入描述

第一行，一个正整数 N。
接下来 N 行，每行两个正整数表示Xi和Yi。
对于所有的数据，1≤N≤100,000，1≤Xi,Yi≤N，Xi互不相等且Yi互不相等。

输出描述

输出文件包含两行，第一行一个正整数，表示最少组数。
第二行N个正整数，依次表示你的方案中每块木板分在了哪一组。
组的编号必须是从1开始的连续整数。

示例1

输入
3
1 1
2 3
3 2
输出
1 1 2

思路

我们要让每一组的$x_{i},y_{i}$都单调递增。
首先可以将$x$排序，于是$y$被打乱成新的序列，任务就转换为，将数组$y$划分为尽可能少的若干组上升子序列。
有$Dilworth$定理，该定理断言：对于任意有限偏序集，其最大反链中元素的数目必等于最小链划分中链的数目。此定理的对偶形式亦真，它断言：对于任意有限偏序集，其最长链中元素的数目必等于其最小反链划分中反链的数目。所以最小组数等于$y$的最长下降子序列长度。
于是我们可以在$O(nlogn)$内得到答案，当前$dp$数组的长度就是当前木板组的编号。

代码

#include<iostream>
#include<algorithm>
using namespace std;
const int N=100009;
struct node
{
	int x,y,id;
	int ans;
}board[N];
bool cmp1(node a,node b)
{
	return a.x<b.x;
}
bool cmp2(node a,node b)
{
	return a.id<b.id;
}
void solve()
{
	int n,len=-1;
	int dp[N];
	cin>>n;
	int i;
	for(i=1;i<=n;i++) 
	{
		cin>>board[i].x>>board[i].y;
		board[i].id=i;
	}
	sort(board+1,board+1+n,cmp1);
    int l,r;
	for(i=1;i<=n;i++)
	{
		l=1;
		r=len;
		while(l<=r)//找到dp中第一个比board[i].y小的位置。
		{
			int mid=(l+r)>>1;
			if(dp[mid]<board[i].y) r=mid-1;
			else l=mid+1;
		}
		dp[l]=board[i].y;
		len=max(l,len);//确定的长度
		board[i].ans=l; 
	}
	sort(board+1,board+1+n,cmp2);
	cout<<len<<endl;
	for(i=1;i<=n;i++) cout<<board[i].ans<<' ';
}
int main()
{
	ios::sync_with_stdio(false);
	solve();
	return 0;
}

D-重排列

题目描述

一个序列的重排列是指对这个序列中的元素进行若干次（包括0次）交换操作后得到的新序列。
在本题中，序列中可能出现重复的数字，他们被视作不同的元素
例如，序列11的重排列有两种。
现在有两个长度为 N 的非负整数序列 A 和 B，问有多少种 A 的重排列满足对于所有的 $1≤i≤N$，有$A_i≤B_i$。
由于答案可能很大，你只需要输出答案对1e9+7取模的结果。

输入描述

输入第一行，包含一个正整数 N
接下来一行，N 个非负整数表示序列 A
再接下来一行，N 个非负整数表示序列 B
$1≤N≤100,000,0≤A_i,B_i≤10^9$

输出描述

一行一个整数，表示答案。

示例1

输入
4
1 1 2 3
1 2 3 4
输出
8

思路

排序不改变最后的答案，而且能使数据变得有序，必须排序。a的第i位能放的数据个数是可知的，假设有cnt个a中的数字比b[i]小，那么可放(cnt-i+1)个，因为前面已经放了(i-1)个，所以要减掉。按照分部乘法原理，得到答案。

代码

#include<iostream>
#include<algorithm>
using namespace std;
typedef long long ll;
void solve()
{
    const int mod =1e9+7;
    const int N=100006;
    int n;
    int a[N], b[N];
	cin>>n;
    ll ans=1;
    int i;
	for (i=1;i<=n;i++) scanf("%d",&a[i]);
	for (i=1;i<=n;i++) scanf("%d",&b[i]);
	sort(a+1,a+1+n);
	sort(b+1,b+1+n);
	int j=1,cnt=0;
	for (i=1;i<=n;i++)
	{
		while (j<=n)//因为排序的关系，j前面的数字一定比b[i]小，不用每次循环都初始化。
		{
			if (a[j]<=b[i]) 
            {
                j++;
                cnt++;
            }
			else break;
		}
		ans=ans*(cnt-i+1)%mod;
	}
	cout<<ans;
}
int main()
{
	solve();
    return 0;
}

F-十字阵列

题目描述

小 Q 新学会了一种魔法，可以对一个 N行M列 的网格上的敌人造成伤害。
第i次使用魔法可以对网格上的一个十字形区域（即第x_i行和第y_i列的并）中的每个格子上的敌人造成z_i点伤害。
现在小Q一共使用了H次魔法，你需要在所有的施法完成之后统计造成伤害的情况，详见输出描述。
提醒：本题输入规模较大，请使用高效的输入方式。
$1≤H≤500000$
$1≤x_i,y_i,z_i,N,M≤2000$
$1≤x_i≤N$
$1≤y_i≤M$

输入描述

第一行 3 个数字 N,M,H。
接下来 H 行，每行 3 个正整数$ x_i，y_i，z_i$。

输出描述

为了避免大量的输出，假设第$i$行第$j$列受到的总伤害是 $w_{ij}$
你只需要输出$\sum {{w_{ij}}(i + j)} $对1000000007取模的结果即可。

示例1

输入
5 5 5
1 1 1
2 2 2
3 3 3
4 4 4
5 5 5
输出
890
说明
造成伤害的情况是：
1 3 4 5 6
3 2 5 6 7
4 5 3 7 8
5 6 7 4 9
6 7 8 9 5
补充的说明：
890 = 1*(1+1)+3*(1+2)+4*(1+3)+…+5*(5+5）,一共25项累加得到890。

思路

像样例那样记录了每一个点的伤害情况是不明智的，这样做只会TLE。
我们不妨只记录每一行和每一列的伤害情况,分别记为$wx[i],wy[j]$。一个点$(x,y)$的伤亡情况，则为，$wx[x]+wy[y]-repeat[x][y]$。如果小Q在点$(x,y)$施法了，那么$repeat[x][y]=z_{i}$，否则$repeat[x][y]=0$。而每次记录$wx,wy,repeat$都只需要$O(1)$的时间。

代码

#include<iostream>
#include<cstdio>
#define N 2005
using namespace std;
typedef long long ll;
void solve()
{
	const int mod = 1e9 + 7;
	int repeat[N][N]={{0},{0}};
	ll ansx[N]={0},ansy[N]={0};
	ll row=0,column=0;
	int n,m,h;
	int x,y,z;
	cin>>n>>m>>h;
	while(h--)
	{
		scanf("%d%d%d",&x,&y,&z);
		repeat[x][y]+=z;
		ansx[x]=(ansx[x]+z)%mod;
		ansy[y]=(ansy[y]+z)%mod;
	}
	ll ans=0;
	int i,j;
	for (i=1;i<=n;i++)
	{
		for (j=1;j<=m;j++)
		{
			ans=(ans+((ansx[i]+ansy[j]-repeat[i][j])%mod)*(i+j))%mod;
		}
	}
	printf("%lld",ans);
}
int main()
{
	solve();
	return 0;
}

Q-括号序列

题目描述

合法括号序列的定义是：
1.空序列是合法括号序列；
2.如果 S 是一个合法括号序列,那么(S)是合法括号序列；
3.如果 A 和 B 都是合法括号序列,那么 AB 是一个合法括号序列。
现在给定一个括号序列，求最少删去几个括号能得到一个合法的括号序列。
输入包含 T 组数据，每组数据中，设括号序列的长度为 N
$1≤T,ΣN≤1,000,000$
（由于空串是合法的括号序列，所以答案可以是N）。

输入描述

第一行一个数字 T；
接下来 T 组数据共2T行，每组数据第一行是N；
第二行则是一个长度为 N 的括号序列。

输出描述

T行T个数字，表示输入的括号序列最少删去几个括号能得到一个合法的括号序列。

示例1

输入
2
6
())(()
9
()(()()))
输出
2
1

思路

设计一个栈。当遇到’(‘时，’(‘进栈；当遇到’)‘，若栈顶没有’('与之匹配，则进栈，否则栈顶出栈。最后栈内剩余的元素就是需要去掉的。

代码

#include<cstdio>
#include<string>
#include<iostream>
using namespace std;
void solve()
{
    int n;
    scanf("%d",&n);
    int ans=0;
    string s;
    int top=0;
    if(n>0)
    {
        cin>>s;
        int i;
        char a[1000009];
        for(i=0;i<n;i++)
        {
            if(s[i]=='(') a[++top]=s[i];
            else
            {
                if(a[top]=='(') top--;
                else a[++top]=s[i];
            }
        }
    }
    printf("%d\n",top);
}
int main()
{
    int t;
    scanf("%d",&t);
    while(t--)
    {
        solve();
    }
    return 0;
}

J-签到题

题目描述

现有一个边长为正整数的三角形，问能否以其三个顶点为圆心画三个圆，使三个圆两两外切。三边长均不超过$10^8$。

输入描述

三个正整数，表示三角形的边长。

输出描述

如果三条边不能构成三角形，输出“wtnl”。
如果三条边能构成三角形但不能画出符合要求的圆，输出“No”。
否则输出一行“Yes”。
然后在第二行输出一组方案，按升序给出三个圆的半径，保留两位小数。

示例1

输入
2 3 3
输出
Yes
1.00 1.00 2.00

思路

初中几何题。若给的三边能组成三角形，则如图

设三角形三边为$a,b,c$，有

因为两边之和大于第三边，不会有不存在的情况出现。

代码

#include<cstdio>
#include<algorithm>
#include<iostream>
using namespace std;
typedef long long ll;
int main()
{
    ll a,b,c;
    double r[5];
    scanf("%lld%lld%lld",&a,&b,&c);
    if(a+b<=c||c+a<=b||b+c<=a) cout<<"wtnl";
    else
    {
        r[1]=(a+b-c)/2.0;
        r[2]=(a+c-b)/2.0;
        r[3]=(b+c-a)/2.0;
        if(r[1]<=0||r[2]<=0||r[3]<=0) cout<<"No";
        else
        {
            cout<<"Yes"<<endl;
            sort(r+1,r+4);
            printf("%.2lf %.2lf %.2lf",r[1],r[2],r[3]);
        }
    }
    return 0;
}