ErikTse Runtime

  • 首页 / Home
  • | 算法学习 / Algorithm
    • 所有 / All
    • 简单 / Easy
    • 中等 / Medium
    • 困难 / Hard
  • | 技术分享 / Technology
    • 所有 / All
    • 网络技术 / NetWork
    • 资源共享 / Resource
    • 项目实践 / Event
  • ETOJ在线评测系统
Keep Going.
温故而知新.
  1. 首页
  2. 算法学习
  3. 中等
  4. 正文

牛客小白月赛48题解A - D

2022年4月30日 1144点热度 0人点赞 0条评论

比赛传送门:(5条未读通知) 牛客小白月赛48_ACM/NOI/CSP/CCPC/ICPC算法编程高难度练习赛_牛客竞赛OJ (nowcoder.com)

比赛感受

C过题数居然还没D高,不过C我也卡了很久,我理解错题意了。

A - 孤独的数组

根据题意不难看出答案只能是0或者-1,因为两个原本互质的数字不可能通过乘一个正整数k使得他们不互质。

所以就是判断是否存在不互质的数字对即可。

代码 / code

#include <bits/stdc++.h>
using namespace std;

const int maxn = 1e5 + 9;

int a[maxn];

int gcd(int a,int b){return a == 0 ? b : gcd(b % a, a);}

signed main()
{
	ios::sync_with_stdio(0);
	int N;cin >> N;
	for(int i = 1;i <= N; ++ i)cin >> a[i];
    int ans = 0;
	for(int i = 1;i < N; ++ i)
		if(gcd(a[i], a[i + 1]) != 1)
			ans = -1;
	printf("%d\n", ans);
	return 0;
}

B - 博弈大师

这题是二分、等差数列求和公式再加判断一个奇偶性。

#include <bits/stdc++.h>
#define int long long
using namespace std;

int f(int x){return x * (x + 1) / 2;}

void solve()
{
	int n, a, b;cin >> n >> a >> b;
	int x = min(a, b);
	a -= x, b -= x;
	
	int l = 0,r = 1e9;
	while(l + 1 != r)
	{
		int mid = (l + r) / 2;
		if(f(mid) > n)r = mid;
		else l = mid;
	}
	int ans = 1;//1牛牛赢,0牛妹赢 
	if(r & 1)ans = 1;
	else ans = 0;
	
	if(ans == 0 && a)ans = 1;
	if(ans == 1 && b)ans = 0;
	
	printf("%s\n",ans ? "niuniu" : "niumei");
}

signed main()
{
	ios::sync_with_stdio(0);
	int T;cin >> T;
	while(T --)solve();
	return 0;
}

C - 可疑的区间

区间题嗷,我一开始用优先队列,前缀和,map,甚至用了set搞了好久,后面发现理解错题意了。md

先记录每条线的起点和终点,以及编号。然后直接一波暴力就行了。

i作为区间头,i - len作为区间尾,如果头遇到区间起点,就要加上对应的数量和权重,如果尾遇到区间终点,就要减去对应的数量和权重,然后时刻更新一个Max_Interval即可。

代码 / Code

/*Copyright (C) Eriktse 2022*/
#include <bits/stdc++.h>
#define int long long
#define fi first
#define se second
using namespace std;

const int maxn = 1e7 + 9;

int add[maxn], sub[maxn];
int L[maxn], R[maxn];

signed main()
{
	ios::sync_with_stdio(0);
	int N, len, ed = 0;cin >> N >> len;
	for(int i = 1;i <= N; ++ i)
	{
		int l, r;cin >> l >> r;
		
		add[l] ++, sub[r] ++;
		L[l] += i, R[r] += i;
		
		ed = max(ed, r + 1);
	}
    //max_itv => Max_Interval
	pair<int, int> max_itv = {0, 0}, tmp = {0, 0};
	int ans = 0;
	for(int i = 1;i <= ed + len; ++ i)
	{
		tmp.fi += add[i];
		tmp.se += L[i];
		
		if(i < len)continue;
		
		tmp.fi -= sub[i - len];
		tmp.se -= R[i - len];
        
		if(max_itv < tmp)max_itv = tmp, ans = 0;
		if(tmp == max_itv)ans ++;
	}
	printf("%lld\n", ans);
	return 0;
}

D - 交替加乘

规律 + 贪心。

因为每个在前面的加数都要乘一个后面的乘数,要使得结果最大,就要从中间开始往两边加和乘,先排序(升序),一开始的数字位a[N / 2 + 1],加数从N / 2开始,以此减小,乘数从N / 2 + 2开始以此增大。

代码 / Code

#include <bits/stdc++.h>
#define int long long
using namespace std;

const int maxn = 1e5 + 9, p = 1e9 + 7;
int a[maxn];

signed main()
{
	ios::sync_with_stdio(0);
	int N;cin >> N;
	for(int i = 1;i <= N; ++ i)cin >> a[i];
	sort(a + 1,a + 1 + N);
	int ans = a[N / 2 + 1];
	for(int i = N / 2, j = i + 2; i > 0; -- i, ++ j)
	{
		ans += a[i];
		if(j <= N)ans *= a[j];
		ans %= p;
	}
	printf("%lld\n",ans % p);
	return 0;
}
本作品采用 知识共享署名-非商业性使用 4.0 国际许可协议 进行许可
标签: C++ 二分 区间 思维 牛客网 算法竞赛
最后更新:2022年7月9日

Eriktse

18岁,性别未知,ACM-ICPC现役选手,ICPC亚洲区域赛银牌摆烂人,CCPC某省赛铜牌蒟蒻,武汉某院校计算机科学与技术专业本科在读。

点赞
< 上一篇
下一篇 >

文章评论

取消回复

Eriktse

18岁,性别未知,ACM-ICPC现役选手,ICPC亚洲区域赛银牌摆烂人,CCPC某省赛铜牌蒟蒻,武汉某院校计算机科学与技术专业本科在读。

文章目录
  • 比赛感受
  • A - 孤独的数组
  • 代码 / code
  • B - 博弈大师
  • C - 可疑的区间
  • 代码 / Code
  • D - 交替加乘
  • 代码 / Code

友情链接 | 站点地图

COPYRIGHT © 2022 ErikTse Runtime. ALL RIGHTS RESERVED.

Theme Kratos | Hosted In TENCENT CLOUD

赣ICP备2022001555号-1

赣公网安备 36092402000057号