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;
}



全部评论

相关推荐

昨天 14:09
西安电子科技大学 Java
面试官：npm install 之后发生了什么 我：什么❓
小白同学终于迎来了期待已久的二面，然而滴滴面试官的这一问题却让他有些“破防”了。自诩略懂前端工程化的他，听到面试官问“npm&nbsp;install&nbsp;之后究竟发生了什么？”时，陷入了沉默。小白同学：“…什么？”面试官微微一笑，并给出了最后的轻语😭：“那今天的面试就先到这里吧，好吧？”回到家中，小白同学决定好好研究这个问题，想弄明白“npm&nbsp;install&nbsp;后，究竟发生了什么？他开始深入思考，阅读文档，最终发现了其中的奥秘——什么是npm？npm（node&nbsp;package&nbsp;manager），是随同Node.js一起安装的第三方包管理器。通过npm，我们可以安装、共享、分发代码，管理项目的依赖关系。嵌套...
查看1道真题和解析
点赞 评论 收藏
分享
今天 09:49
深信服_JAVA研发工程师(准入职员工)
深信服内推，深信服内推码
🌟工作内容与氛围：&nbsp;我作为实习生能够真正地参与到了小组项目的迭代工作，不是简单地打杂工作。目前我已经接触到两个专题的需求迭代，一个由我完全负责，另一个和leader一起开始需求分析。在短短地两个月内，我对产品认知的八股文（产品经理能力、产品经理工作内容等）有了自己真正的感受和认识，不再是简单地文字理解。当然，实习工作也是对自己产品全方面能力的不断提升。&nbsp;我导师不仅在工作上能及时得解答我的疑问，也会关心生活上我的不便，比如因为体检报告未出推迟入职，leader会主动关心我实习住宿的问题；电话沟通发现我声音和平时不一样，会主动询问我是否感冒不舒服，是否需要请假休息等。深信服的理念之一“简单有爱”...
深信服公司福利 800人发布
点赞 评论 收藏
分享
11-03 18:50
门头沟学院 Java
这咋回呀
🙀
迷茫的大四🐶：问就是马上到，一周五天，6个月以上，全国可飞
点赞 评论 收藏
分享
10-15 19:07
门头沟学院 产品经理
点赞 评论 收藏
分享
12-02 11:33
上海交通大学 嵌入式软件开发
秋招G了,春招还能翻盘吗?
刚刚结束的秋招中，有人欢喜有人忧。欢喜的是，有些同学找到了不错的工作；忧愁的是，也有同学没有心仪的去处。秋招和春招，是学生们心头的两个坎，之前看师兄师姐们或优雅或费力的迈过这些坎，感触并不大。终于，在毕业的前一年，也轮到了我们自己。第一次经历，自然心头有着不少疑惑。今天从计算机行业出发，我带你抽丝剥茧，把事情整清楚。首先抛出三个大家关心的问题：校园招聘的秋招和春招有什么区别秋招零offer，春招还有机会吗秋招已经签约了，能去春招再看看吗春夏秋冬，四季变换，自有顺序。那为啥秋招会在春招之前呢？因为，对于学生来说，在校期间的求职时间有两段，一段是毕业前一年的秋天，在&nbsp;7&nbsp;月&nbsp;~&nbsp;11月之间，称为秋...
点赞 评论 收藏
分享
评论
点赞
收藏
分享

全站热榜

更多

创作者周榜

更多
正在热议
更多
# 为了去实习，我赌上了___ #
10796次浏览 100人参与
# 晒一晒你收到的礼盒 #
86819次浏览 420人参与
# 十二月请对我好一点 #
16052次浏览 237人参与
# 2025年终总结 #
3557次浏览 72人参与
# uu们，春招你还来吗？ #
4343次浏览 38人参与
# 父母对你找工作是助力还是阻力？ #
7297次浏览 137人参与
# 一人推荐一个值得做的项目 #
5523次浏览 91人参与
# 高薪高压 vs 低薪wlb，你怎么选？ #
6080次浏览 82人参与
# 哪一瞬间让你觉得“这班不如不上” #
5087次浏览 86人参与
# 工作前VS工作后，你的心态变化 #
8058次浏览 106人参与
# 工作中出现了XX情况正常吗 #
20176次浏览 172人参与
# 公司福利里最没用的一项是啥 #
4092次浏览 77人参与
# 回顾今年你干过的最“勇”的一件事 #
8337次浏览 119人参与
# 秋招有哪些公司要求提前实习 #
92063次浏览 495人参与
# 一觉醒来，秋招难度下降一万倍…… #
120997次浏览 768人参与
# 我的秋招总结 #
257253次浏览 4256人参与
# 实习打杂，要跑路吗 #
50141次浏览 319人参与
# 第一份工作能做外包吗？ #
84071次浏览 563人参与
# 滴滴工作体验 #
35377次浏览 145人参与
# 如何用一句话描述你的职业 #
28678次浏览 181人参与
牛客网
牛客网在线编程
牛客网题解
牛客企业服务