竞赛讨论区 > 【题解】2020牛客寒假算法基础集训营第六场
头像
珩月
编辑于 2020-02-15 18:26
+ 关注

【题解】2020牛客寒假算法基础集训营第六场

写在题解前:
这次比赛的10道题,std的代码量都非常小,但是需要一点点思维来做保障。
相信能活跃大家的思路,以及优化大家的切题体验。(认真.jpg)
以及即使场上不会做,补完这套题还是会给大家收获的~
槽点举例:
Q:J我怎么随便写就过了?
A:这题真的怎么写都是对的,即使你没想清楚所有细节。(滑稽)
Q:怎么B题就是个Tarjan模板题?
A:我不是我没有,强行用Tarjan明显要比std难很多嘛。


A 配对
我们要使得第K大的和尽可能大,显然可以贪心:
首先,组成这K对数字的显然是A中最大的K个数字和B中最大的K个数字。
问题转化为怎样配对使得最小的和最大:
我们发现,如果A1<A2,B1<B2,那么一定是由A1和B2配对较优。
经过简单的归纳可以得到,倒序配对是最优的,这样就解决了问题。
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>

using namespace std;
const int N = 100050;

int a[N], b[N], n, k, ans = 2e8;
int main()
{
	int i, j;
	scanf("%d%d", &n, &k);
	for(i = 1; i <= n; i ++)
		scanf("%d", &a[i]);
	for(i = 1; i <= n; i ++)
		scanf("%d", &b[i]);
	sort(a + 1, a + n + 1);
	sort(b + 1, b + n + 1);
	for(i = n; i > n - k; i --)
        ans = min(ans, a[i] + b[n - k + n + 1 - i]);
	printf("%d\n", ans);
	
	return 0;
}




B 图
这是一个简单的有关基环树的问题。
可以证明,每个点出度都为1的有向图是一个基环内向树森林。
关于这一部分的内容,可以自行查阅资料。
这里我们要用到的结论是:从一个点出发,沿着出边一路走下去,一定会走到一个环。
所以我们选择dfs,当遍历到一个已在dfs栈中的节点时,就说明找到了环,可以结束统计。
但这样是会超时的,于是我们选择带“记忆化”的dfs,从一个点开始沿着出边走下去,每当走到一个在之前某次dfs中经过的点时,就可以利用上一次的答案完成求解。
实现上有一些细节,要注意不要让复杂度退化。
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>

using namespace std;
const int N = 1000050;

int to[N], siz[N], n, vis[N], ins[N], sta[N];
int dfs(int x){
	if(siz[x]) return siz[x];
	return siz[x] = 1 + dfs(to[x]);
}
int main()
{
	int i, j, k, h;
	scanf("%d", &n);
	for(i = 1; i <= n; i ++)
		scanf("%d", &to[i]);
	for(i = 1; i <= n; i ++){
		if(vis[i] == 0){
			j = i;
			while(vis[j] == 0){
				sta[++ sta[0]] = j;
				vis[j] = ins[j] = 1;
				j = to[j];
			}
			if(ins[j]){
				k = j, h = 0;
				do{
					k = to[k];
					h ++;
				}while(k != j);
				do{
					k = to[k];
					siz[k] = h;
				}while(k != j);
			}
			while(sta[0]){
				ins[sta[sta[0]]] = 0;
				sta[0] --;
			}
		}
	}
	for(i = 1, h = 0; i <= n; i ++)
		h = max(h, dfs(i));
	printf("%d", h);
	
	return 0;
}



C 汉诺塔
将木板按照Xi从小到大排序,将这时的Yi数列记为Zi数列,则问题变成将Zi划分为尽可能少的若干组上升子序列。
根据Dilworth定理,最小组数等于Zi的最长下降子序列长度。
要求最长下降子序列的长度,我们有一种经典的二分优化dp的方法,在这里不再详述。 借助这种做法我们能给出一种构造方法,在求出最小组数的同时得出方案。
将状态数组的每个位置变为栈,用入栈操作代替修改元素操作,即可在求出组数的同时,用这些栈来完成对数列的划分。
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>

using namespace std;
const int N = 100050;

struct node{
	int x, y, loc;
	inline bool operator < (const node &b)const{
		return x < b.x;
	}
}a[N];
int n, m, ot[N], S[N];

int main()
{
	
	int i, j, k;
	scanf("%d", &n);
	for(i = 1; i <= n; i ++){
		scanf("%d%d", &a[i].x, &a[i].y);
		a[i].loc = i;
	}
	sort(a + 1, a + n + 1);
	for(i = 1; i <= n; i ++){
		int lb = 1, rb = m;
		while(lb <= rb){
			int md = lb + rb >> 1;
			if(S[md] < a[i].y)
				rb = md - 1;
			else
				lb = md + 1;
		}
		S[lb] = a[i].y;
		if(lb > m) m = lb;
		ot[a[i].loc] = lb;
	}
	printf("%d\n", m);
	for(i = 1; i <= n; i ++)
		printf("%d ", ot[i]);
	
	return 0;
}



D 重排列
容易知道按升序将A和B排序不影响结果。
按标号从小到大考虑A的每个位置填什么数。
例:A(1,2,3);B(1,3,4)
则考虑第一个位置时,只能填1。
考虑第二个位置时,可以填2或3。
但是由于2和3在这里是完全等价的,也就是说我们并不关心填了谁。
那么我们只需要记录每一步有多少个数可填就好了,这个答案与之前填入的方案无关。
具体实现的时候只需要用双指针进行一轮扫描就可以了。
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>

using namespace std;
typedef long long LL;
const int N = 100050;
const LL mod = 1000000007;

int a[N], b[N], ans = 1, n; 
int main()
{
	
	int i, j, k;
	cin >> n;
	for(i = 1; i <= n; i ++)
		scanf("%d", &a[i]);
	for(i = 1; i <= n; i ++)
		scanf("%d", &b[i]);
	sort(a + 1, a + n + 1);
	sort(b + 1, b + n + 1);
	for(i = 1, j = 0; i <= n; i ++){
		while(j < n && a[j + 1] <= b[i])
			j ++;
		ans = (LL)ans * max(0ll, j - i + 1ll) % mod;
	}
	printf("%d", (ans + mod) % mod);
	
	return 0;
}



E 立方数
考虑直接一些的做法
尝试对每个N作质因数分解,经简单的统计可得出答案,复杂度O(TN^(1/2))
我们先做简单一点的优化,容易发现其实只要枚举10^6(N^(1/3)以内)的质数就好,复杂度O(TN^(1/3)/ln(N^(1/3)))
再作进一步的分析,如果我们仅使用N^(1/4)(记为W)以内的质数去试除,那么最后余下的数X仅具有大于W的因子
此时X要么是一个完全立方数,要么对答案没有任何贡献,只需要使用二分法来验证X是不是一个完全立方数即可
复杂度O(TN^(1/4)/ln(N^(1/4))),不卡常数,真的!
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <time.h>

using namespace std;
typedef long long LL;
const int N = 31700;

int is[N], n, pri[N]; LL x, p_tri[N], p_ss[N];
int main()
{
	
	int i, j, k;
	for(i = 2; i < N; i ++){
		if(is[i] == 0){
			pri[++ pri[0]] = i;
			p_tri[pri[0]] = (LL)i * i * i;
			p_ss[pri[0]] = (LL)i * i * i * i;
			for(j = i * i; j < N; j += i)
				is[j] = 1;
		}
	}
	scanf("%d", &n);
	while(n --){
		int ans = 1;
		scanf("%lld", &x);
		for(i = 1; p_ss[i] <= x; i ++){ 
			if(x % pri[i] == 0){
				while(x % p_tri[i] == 0){
					ans *= pri[i];
					x /= p_tri[i];
				}
				while(x % pri[i] == 0)
					x /= pri[i];
			}
		} 
		int lb = 1, rb = 1000000;
		while(lb <= rb){
			int md = lb + rb >> 1;
			if((LL)md * md * md < x)
				lb = md + 1;
			else
				rb = md - 1;
		}
		if((LL)lb * lb * lb == x)
			ans *= lb;
		printf("%d\n", ans);
	}
	 
	return 0;
}



F 十字阵列
设3个数组a[],b[]和ab[][],分别统计对行,列和每格造成的伤害
进行操作(xi,yi,zi)时,a[xi],b[yi],ab[xi][yi]都加上zi
每次询问一格的答案时,只要查询a[x]+b[y]-ab[x][y]就好了
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>

using namespace std;
const int N = 2010;
const int mod = 1000000007;

int x[N], y[N], xy[N][N], n, m, H, ans; 
int main()
{
	int i, j, k, h;
	scanf("%d%d%d", &n, &m, &H);
	for(i = 1; i <= H; i ++){
		scanf("%d%d%d", &j, &k, &h);
		x[j] += h, y[k] += h, xy[j][k] += h;
	}
	for(i = 1; i <= n; i ++)
		for(j = 1; j <= m; j ++)
			ans = (ans + (long long)(x[i] + y[j] - xy[i][j]) * (i + j) % mod) % mod;
	printf("%d", (ans + mod) % mod);
	
	return 0;
}



G 括号序列
括号序列合法的一个充要条件是:
设'('为1,')'为-1,则:①序列所有位置前缀和非负;②'('与')'数量相等
为了保证条件1,我们可以用栈模拟括号序列的匹配过程
碰到一个'('就加入栈中,碰到一个')'就消去栈顶的一个'('
如果栈中没有没有'('则这个')'必须要删去
在这个过程结束之后,如果'('比')'多,则从后向前删去多余的'(',直到序列合法即可
可以证明这样一定能得到满足要求的括号序列:两个步骤中删除的括号都是必须删去的
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>

using namespace std;
const int N = 1000050;

int T, n, l, r, sum, ans; char s[N];
int main()
{
	int i, j, k;
	scanf("%d", &T);
	while(T --){
		scanf("%d", &n);
		scanf("%s", s + 1);
		l = r = sum = ans = 0;
		for(i = 1; i <= n; i ++){
			if(s[i] == '(')
				l ++, sum ++;
			else if(sum > 0)
				r ++, sum --;
			else ans ++;
		}
		printf("%d\n", ans + l - r);
	}
	
	return 0;
}




H 云
直接考虑问题较难,因为两种云都在运动。
但是我们可以考虑相对运动,将这个过程等效为左下角的云朝右上方移动。
在这个背景下我们容易发现:将所有的云投影成y=-x这条直线上的一条线段,则两朵云会相遇当且仅当他们的投影有交点。
这是一个简单的扫描线问题,将线段拆成端点后排序统计即可。
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;
typedef long long LL;
const int N = 400050;

struct node{
	int loc, lr, typ;
	inline bool operator < (const node &b)const{
		if(loc == b.loc && lr == b.lr)
			return typ < b.typ;
		if(loc == b.loc)
			return lr > b.lr;
		return loc < b.loc;
	}
}A[N];
int n, m, a, b, c, d, k;
LL cnt[2], ans;

int main()
{
	
	for(scanf("%d%d", &n, &m); n --;){
		scanf("%d%d%d%d", &a, &b, &c, &d);
		A[++ k] = (node){d - c, 1, 0};
		A[++ k] = (node){b - a, -1, 0};
	}
	while(m --){
		scanf("%d%d%d%d", &a, &b, &c, &d);
		A[++ k] = (node){d - c, 1, 1};
		A[++ k] = (node){b - a, -1, 1};
	}
	sort(A + 1, A + k + 1);
	for(int i = 1; i <= k; i ++){
		cnt[A[i].typ] += A[i].lr;
		if(A[i].lr == 1)
			ans += cnt[A[i].typ ^ 1];
	}
	printf("%lld\n", ans);
	
	return 0;
}




I 导航系统
显然数据给出的原图是一棵树。
容易发现,如果将输入的N(N-1)个距离看做N(N-1)条无向边的话,那么如果数据合法,原树就是这张新图的最小生成树。
证明:由于边权是非负的,可以考虑Kruskal算法的过程,每一次引入的边都是尽可能短的,所以一定是树中的边,通过简单的归纳即证。
所以求出最小生成树之后再进行验证就好了。
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>

using namespace std;
const int N = 510;

struct edge{
	int u, v, c;
	bool operator < (const edge &b)const{
		return c < b.c;
	}
}w[N * N], ans[N];
int a[N][N], n, m = 0, T[N], to[N][N], siz[N], len[N][N], dis[N][N];

int path(int x){
	if(T[x] == 0)
		return x;
	return T[x] = path(T[x]);
}
void dfs(int x, int fa, int st, int d){
	dis[st][x] = d;
	for(int i = 1; i <= siz[x]; i ++)
		if(to[x][i] != fa)
			dfs(to[x][i], x, st, d + len[x][i]);
}
int main()
{
	int i, j, k;
	scanf("%d", &n);
	for(i = 1; i <= n; i ++)
		for(j = 1; j <= n; j ++)
			scanf("%d", &a[i][j]);
	for(i = 1; i <= n; i ++){ 
		for(j = 1; j <= n; j ++){
			if(a[i][j] != a[j][i]){
				puts("No");
				return 0;
			}
			if(i < j){
				m ++;
				w[m].u = i;
				w[m].v = j;
				w[m].c = a[i][j];
			}
		}
	}
	sort(w + 1, w + m + 1);
	for(i = 1, j = 0; i <= m && j < n - 1; i ++){
		int x = path(w[i].u), y = path(w[i].v);
		if(x != y){
			T[x] = y;
			ans[++ j] = w[i];
			siz[ans[j].u] ++, siz[ans[j].v] ++;
			to[ans[j].u][siz[ans[j].u]] = ans[j].v;
			to[ans[j].v][siz[ans[j].v]] = ans[j].u;
			len[ans[j].u][siz[ans[j].u]] = len[ans[j].v][siz[ans[j].v]] = ans[j].c;
		}
	}
	for(i = 1; i <= n; i ++)
		dfs(i, 0, i, 0);
	for(i = 1; i <= n; i ++){
		for(j = 1; j <= n; j ++){
			if(a[i][j] != dis[i][j]){
				puts("No");
				return 0;
			}
		}
	}
	puts("Yes");
	for(i = 1; i < n; i ++)
		printf("%d\n", ans[i].c);
	
	return 0;
}



J 签到题
对没错它就是签到题,只要会解一个简单的方程就好了。
可以证明“No”是不存在的,所以不论怎么写都能对。
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>

using namespace std;

double a[3], b[3];
int main()
{
	cin >> a[0] >> a[1] >> a[2];
	sort(a, a + 3);
	if(a[0] + a[1] <= a[2]){
		puts("wtnl");
		return 0;
	}
	puts("Yes");
	b[1] = (a[2] - a[1] + a[0]) / 2;
	b[0] = a[0] - b[1], b[2] = a[2] - b[1];
	printf("%.2lf %.2lf %.2lf", b[0], b[1], b[2]);
	
	return 0;
}
到此整个集训营就结束啦!祝大家的AK姿势都能有进步!
如果这场比赛给你带来了收获,就是坠吼的!

全部评论

(31) 回帖
加载中...
话题 回帖

等你来战

查看全部

热门推荐