2021牛客寒假算法基础集训营2

https://ac.nowcoder.com/acm/contest/9982#question

D-牛牛与整除分块

大意：构造集合S={x: x =N/i, i=1,2,3...N},求n/x在S中第几大(S去重降序排序)
思路：先看n=10时S中有哪些数。

多列出几个数可以发现当时，,当时，x是多少，那么n/x就第几大。
所以当时，我们先求出n/x在右边集合中排第几，在加上左边的集合大小(左边集合大小为)就是答案。 
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <stack>
#include <queue>
#include <string.h>
#include <cmath>
#include <bitset> 
#include <set>
#include <map>
#include <list>
#define ull unsigned long long
#define ll long long
const int inf = 0x3f3f3f3f;
const int mod = 1e9+7;
const int N = 500005;
const ll ds = 1e15+7;
const double p1 = 3.141592653589793238462643383;

using namespace std;

void solve()
{
	int t,n,x,ans;
	cin >> t;
	while(t--){
		ans = 0;
		cin >> n >> x;
		int m = sqrt(n);
		if(x <= m){
			ans = x;
		}
		else{
			int k = n/x;
			int h = n/(m+1);
			ans = m+h-k+1;
		}
		cout << ans << endl;
	}
}

int main()
{
	solve();
	return 0;
}

E-牛牛与跷跷板：双指针+最短路(bfs/dfs/dijkstra)

思路：看题很容易联想的最短路，但关键是如何将这个图连起来。分成两种情况。
1）两块跷跷板在同一平面，那么比较相邻两块，左边的r等于右边的l就连起来。
2）两块不在同一平面，而是在上下相邻平面，利用双指针l,r,  l指向下平面最左边那块，r指向下平面最右边那块，每一次让l往r移动，如果node[l].l >= node[i].r，那么l和l后面的跷跷板都不可能和i连接(可以画图看看)，那么再来判断第i+1块，同时让j--，因为第i+1块和第i块是可能连接同一块的。如果node[l].r <= node[i].l,那l后面的跷跷板还是有可能和i连接的。
连接完图后，因为相邻跷跷板的路程是1，bfs，dfs，dij都可以解决最短路。
 
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <stack>
#include <queue>
#include <string.h>
#include <cmath>
#include <bitset> 
#include <set>
#include <map>
#include <list>
#define ull unsigned long long
#define ll long long
const int inf = 0x3f3f3f3f;
const int mod = 1e9+7;
const int N = 500005;
const ll ds = 1e15+7;
const double p1 = 3.141592653589793238462643383;

using namespace std;

struct Node{
	int y,l,r,num;
}node[N];

vector<int>a[N];
int n,vis[N],d[N];

bool cmp(Node a,Node b)
{
	if(a.y == b.y) return a.l < b.l;
	return a.y < b.y;
}


void bfs()
{
	queue<int>q;
	q.push(1);
	vis[1] = 1;
	d[1] = 0;
	while(!q.empty()){
	//	cout << 1 <<endl;
		int t = q.front();
		q.pop();
		if(t == n) break;
		for(int i = 0; i < a[t].size(); i++){
			if(vis[a[t][i]]) continue;
			vis[a[t][i]] = 1;
			q.push(a[t][i]);
			d[a[t][i]] = d[t] + 1;
		}
	}
	printf("%d",d[n]);
}

void solve()
{
	scanf("%d",&n);
	for(int i = 1; i <= n; i++){
		int y,l,r;
		scanf("%d%d%d",&y,&l,&r);
		node[i].y = y;
		node[i].l = l;
		node[i].r = r;
		node[i].num = i;
	}
	sort(node+1,node+n+1,cmp);
	int l = 0,r = 0;
	for(int i = 1; i <= n; i++){
		if(node[i].r == node[i+1].l && node[i].y == node[i+1].y) {
			a[node[i].num].push_back(node[i+1].num);
			a[node[i+1].num].push_back(node[i].num);
		}
		while(l <= n && node[l].y == node[i].y) l++;
		r = max(l,r);
		while(r <= n && node[r].y == node[l].y) r++;
		while(l < r){
			//cout << l << endl;
			if(node[l].l >= node[i].r){
				//l++;
				break;
			}
			if(node[l].r <= node[i].l){
				l++;
				continue;
			}
			a[node[l].num].push_back(node[i].num);
			a[node[i].num].push_back(node[l].num);
			l++;
		} 
		if(l > 1) l--;
	}
	bfs();
}

int main()
{
	solve();
	return 0;
}

F-牛牛与交换排序：构造数据结构

大意：牛牛有一个数组，里面的元素为1-n的一个排列，规定一个k为区间的大小，牛牛可以去翻转区间大小为k的子数组，但是每一次翻转的区间一定要在前一个区间的右边，问是否存在k，使得经过若干次翻转后，区间变得有序？
思路：因为每一次翻转的区间一定要在前一个区间的右边，并且数组里面的元素为1-n的一个排列，有序后数组满足a[i]=i，所以在a[i]不等于i的时候，一定要把等于i的数交换到位置i上去，否则下一次翻转的时候区间不可能包含位置i。在第一次进行判断的时候就能确定区间的大小k，然后依次判断翻转后a[i]是否等于i，不等于就再判断从a[i+k-]是否等于i(因为区间大小固定为k)，不等于则不可能翻转成有序，相等则再继续往后判断。 
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <stack>
#include <queue>
#include <string.h>
#include <cmath>
#include <bitset> 
#include <set>
#include <map>
#include <list>
#define ull unsigned long long
#define ll long long
const int inf = 0x3f3f3f3f;
const int mod = 1e9+7;
const int N = 500005;
const ll ds = 1e15+7;
const double p1 = 3.141592653589793238462643383;

using namespace std;

int xb[1000005],a[1000005],pre[1000005];
void solve()
{
	int n,x,k = 0;
	scanf("%d",&n);
	for(int i = 1; i <= n; i++){
		scanf("%d",&x);
		xb[x] = i;
		a[i] = x;
		if(x == i){
			pre[i] = pre[i-1]+1;
		}
		else pre[i] = pre[i-1];
	}
	for(int i = 1; i <= n; i++){
		if(a[i] != i){
			k = xb[i]-i+1;//由第一个不相等的地方确定k的大小。
			break;
		}
	}
	int flag = 0;
	for(int i = 1; i <= n; i++){
		if(a[i] != i){
			if(i+k-1 > n || a[i+k-1] != i){//不相等答案为no
				flag = 1;
				break;
			}
			int l = i,r = i+k-1;
            while(l < r){
                int temp1,temp2;
                temp1 = a[l];
                temp2 = xb[a[l]];
                xb[a[l]] = xb[a[r]];
                xb[a[r]] = temp2;
                a[l] = a[r];
                a[r] = temp1;
                l++;
                r--;
            }
		}
	}
	if(flag) printf("no\n");
	else {
		printf("yes\n");
		if(k) printf("%d",k);
		else printf("%d",k+1);
	}
}

int main()
{
	solve();
	return 0;
}

G-牛牛与比赛颁奖：差分+离散化

思路：看完题首先要想到差分，再看数据范围，1e9，不能开这么大的数组，所以考虑用离散化。将m个l，r离散化存入结构体当中。
最后巧妙的运用过题数和过题人数算排名。 
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <stack>
#include <queue>
#include <string.h>
#include <cmath>
#include <bitset> 
#include <set>
#include <map>
#include <list>
#define ull unsigned long long
#define ll long long
const int inf = 0x3f3f3f3f;
const int mod = 1e9+7;
const int N = 100005;
const ll ds = 1e15+7;
const double p1 = 3.141592653589793238462643383;

using namespace std;

struct Node{
	int xb,num;
}node[N*2];

int cnt[N],pre[N];cnt[i]表示过了i题有多少人。
bool cmp(Node a,Node b)
{
	if(a.xb == b.xb) return a.num < b.num;
	return a.xb < b.xb;
}

void solve()
{
	int n,m,l,r;
	scanf("%d%d",&n,&m);
	for(int i = 1; i <= m; i++){
		scanf("%d%d",&l,&r);
		node[i].xb = l;
		node[i].num = 1;
		node[i+m].xb = r+1;
		node[i+m].num = -1;
	}
	sort(node+1,node+m+m+1,cmp);
	int mmax = 0,sum = 0;
	for(int i = 1; i <= m+m; i++){
		if(node[i].xb - node[i-1].xb != 0){
			cnt[sum] += node[i].xb - node[i-1].xb;
		}
		sum += node[i].num;
		mmax = max(mmax,sum);
	}
	int j,y,t;
	j = y = t = -1;
	for(int i = mmax; i >= 0; i--){
		pre[i] = pre[i+1] + cnt[i];
		if(pre[i] >= (n+9)/10 && j == -1) j = i;
		if(pre[i] >= (n+3)/4 && y == -1) y = i;
		if(pre[i] >= (n+1)/2 && t == -1) t = i;
	//	cout << pre[i] << endl;
	}
	j = max(j,1);
	y = max(y,1);
	t = max(t,1);
//	cout << j << " " << y << " " << t << " " << endl; 
	printf("%d %d %d",pre[y+1]-pre[mmax],pre[y]-pre[j],pre[t]-pre[y]);
}

int main()
{
	solve();
	return 0;
}

I-牛牛与质因数：dfs/dp/输入筛

大意：定义函数F(x) ,它表示将x做质因数分解后得到的数字从小到大升序排列，然后将其“拼接”成一个大整数。求
思路：当n=10时，F(2) = 2，F(3) = 3,F(4) = 22,F(5) = 5,F(6) = 23,F(7) = 7,F(8) = 222,F(9) = 33,F(10) = 25
其实也就是2-10内的质因数的组合，组合的质因数相乘的结果要小于等于n ，现在考虑如何拼接，假设现在已经拼接成res，把质数x拼接上去，拼接完后res = res*10^cnt[x]+x,其中cnt[x]表示x的位数，而不是直接乘上十。2-n内质因数的组合可以用dfs来实现，剪枝是相乘结果大于n则回溯，即return。 
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <stack>
#include <queue>
#include <string.h>
#include <cmath>
#include <bitset> 
#include <set>
#include <map>
#include <list>
#define ull unsigned long long
#define ll long long
const int inf = 0x3f3f3f3f;
const int mod = 1e9+7;
const int N = 500005;
const ll ds = 1e15+7;
const double p1 = 3.141592653589793238462643383;

using namespace std;

int ans = 0,n,cnt;
ll sum = 0;
int v[10000005],prime[10000005],vis[10000005];
void init()
{
    cnt = 0;
    for(int i = 2; i <= n; i++){
        if(!v[i]){
            cnt++;
            prime[cnt] = i;
            v[i] = i;
        }
        for(int j = 1; j <= cnt; j++){
            if(1ll*prime[j]*1ll*i > n) break;
            v[i * prime[j]] = prime[j];
            if(i % prime[j] == 0) break;
        }
    }
}

int ws(int x)
{
	int t = 0;
	while(x){
		t++;
		x /= 10;
	}
	return t;
}

int qpow(int a,int b)
{
	int res = 1;
	while(b){
		if(b&1) res = 1ll*res*a%mod;
		b >>= 1;
		a = 1ll*a*a%mod;
	}
	return res;
}

void dfs(int cur,ll res,ll temp)
{
	sum = (sum+res)%mod;
//	cout << res << " " << temp << endl;
//	cout << cur << " " << res << endl;
	for(int i = cur; i <= cnt; i++){
		if(temp*prime[i] <= n)
	    	dfs(i,(res*qpow(10,ws(prime[i]))+prime[i])%mod,temp*prime[i]);
	    else break;
	}
}

void solve()
{
	scanf("%d",&n);
	init();
	for(int i = 1; i <= cnt; i++){
	//	cout << prime[i] << "\n";
		dfs(i,1ll*prime[i],1ll*prime[i]);
	}
	printf("%lld\n",sum%mod);
}

int main()
{
	solve();
	return 0;
}
输入筛
思路：f[1500] = 223555,去最大的素因子，f[1500/5] = f[300] = 22355,所以f[1500] = f[300]*10+5,同理f[300] = f[60]*10+5.
这样在筛素数时，每次将素数i作为最大素因子，利用f[i] = f[j/i]*10^ws(i)+i求f[i]。倘若某个数的最大素因子不是i也没有关系，在后面比i大的素数去筛的时候会更新。 
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <stack>
#include <queue>
#include <string.h>
#include <cmath>
#include <bitset> 
#include <set>
#include <map>
#include <list>
#define ull unsigned long long
#define ll long long
const int inf = 0x3f3f3f3f;
const int mod = 1e9+7;
const int N = 5000005;
const ll ds = 1e15+7;
const double p1 = 3.141592653589793238462643383;

using namespace std;

bool vis[N];
int f[N];
ll ans = 0;

int ws(int x)
{
    int t = 0;
    while(x){
        t++;
        x /= 10;
    }
    return t;
}
 
int qpow(int a,int b)
{
    int res = 1;
    while(b){
        if(b&1) res = 1ll*res*a%mod;
        b >>= 1;
        a = 1ll*a*a%mod;
    }
    return res;
}

void solve()
{
	int n;
	scanf("%d",&n);
	for(int i = 2; i <= n; i++){
		if(!vis[i]){
			ans = (ans+i)%mod;
			f[i] = i;
			for(int j = i+i; j <= n; j+=i){
				if(f[j/i] != 0)	{
					int t = qpow(10,ws(i))*f[j/i]+i;
					ans = (ans+t)%mod;
					f[j] = t;
				}
				vis[j] = true;
			}
		}
	}
	printf("%d\n",ans);
}

int main()
{
	solve();
	return 0;
}




J-牛牛相成为hacker：构造题

思路：根据题意很容易想到用斐波那契数列来构造，但是题目要求的数的大小不能超过1e9，而斐波那契数列在长度为40是就超过了1e9，所以当n<=39时，构造斐波那契数列就行，那n>=40怎么办呢，同样前面构造斐波那契数列，后面补1，但前面的两个1不要。 
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <stack>
#include <queue>
#include <string.h>
#include <cmath>
#include <bitset> 
#include <set>
#include <map>
#include <list>
#define ull unsigned long long
#define ll long long
const int inf = 0x3f3f3f3f;
const int mod = 1e9+7;
const int N = 500005;
const ll ds = 1e15+7;
const double p1 = 3.141592653589793238462643383;

using namespace std;

ll f[105];
void solve()
{
	int n;
	f[1] = 1,f[2] = 1;
	for(int i = 3; i <= 39; i++){
		f[i] = f[i-1]+f[i-2]; 
	}
	scanf("%d",&n);
	if(n <= 37){
		for(int i = 3; i <= n+2; i++){
			printf("%lld ",f[i]);
		}
	}
	else{
		for(int i = 3; i <= 39; i++){
			printf("%lld ",f[i]);
		}
		for(int i = 40; i <= n+2; i++){
			printf("%d ",1);
		}
	}
}

int main()
{
	solve();
	return 0;
}



全部评论

相关推荐

11-24 15:10
上海师范大学 数据运营
点赞 评论 收藏
分享
11-23 14:49
小红书_社区技术部_前端开发(实习员工)
9.11校招深圳字节一面
呜呜，居然考了我一战字节写的题，但面试官还是说我算法能力有点不达预期自我介绍面向HR的简历分析平台你主要做了些什么你什么时候开始确定学习前端的前端用过些什么技术栈学校这个项目有些什么技术点如果你学校这个项目出现了一些bug，比如网页白屏了，你接下来如何应对开发项目遇到bug时你如何去排查的遇到过哪些非正常的状态码有在浏览器中debugger吗上线项目如何保证用户能用上你的新代码浏览器缓存是基于什么进行缓存的你的项目文件在打包部署过程中做了些什么用过什么vite配置对node，ts和react的学习程度对node的理解你对于一个技术是如何去学习的能够根据原型图用代码还原出项目吗vueRouter...
查看26道真题和解析 面经烤面筋
点赞 评论 收藏
分享
10-28 14:42
门头沟学院 Java
好执着啊，双非本这么有吸引力吗
JAVA回暖了
watermelon1124：因为嵌入式炸了
点赞 评论 收藏
分享
10-11 18:35
中国矿业大学 机械设计师
笑死，我写的吐槽被搬到脉脉了
专心打鱼：互联网搬运工，贴子都要偷
点赞 评论 收藏
分享
头像
11-22 13:56
已编辑
莆田学院 产品经理
点赞 评论 收藏
分享
评论
点赞
收藏
分享

全站热榜

正在热议
# 拼多多求职进展汇总 #
229859次浏览 2025人参与
# 哪些公司校招卡第一学历 #
32253次浏览 100人参与
# 阿里云管培生offer #
56941次浏览 1735人参与
# 25届秋招总结 #
390183次浏览 3895人参与
# ai智能作图 #
18316次浏览 236人参与
# 地方国企笔面经互助 #
6357次浏览 15人参与
# 北方华创开奖 #
65489次浏览 545人参与
# 硬件兄弟们 甩出你的华为奖状 #
77509次浏览 624人参与
# 实习，投递多份简历没人回复怎么办 #
2433278次浏览 34687人参与
# 在职场上，你最讨厌什么样的同事 #
5477次浏览 78人参与
# 实习与准备秋招该如何平衡 #
721702次浏览 8542人参与
# 我的实习求职记录 #
6115122次浏览 83915人参与
# 工作中，你有没有遇到非常爱骂人的领导？ #
4591次浏览 46人参与
# 如果再来一次，你还会选择这个工作吗？ #
107578次浏览 1081人参与
# 如果你有一天可以担任公司的CEO，你会做哪三件事？ #
9584次浏览 200人参与
# 腾讯求职进展汇总 #
206942次浏览 1693人参与
# 实习想申请秋招offer，能不能argue薪资 #
35605次浏览 308人参与
# 牛客租房专区 #
4340次浏览 119人参与
# 中兴求职进展汇总 #
467575次浏览 2439人参与
# 华为工作体验 #
109877次浏览 855人参与
# 如果有时光机，你最想去到哪个年纪？ #
27393次浏览 569人参与
# 实习中的菜狗时刻 #
280438次浏览 2761人参与
牛客网
牛客企业服务