首页 / 算法 / 2021牛客寒假算法基础集训营2
2021牛客寒假算法基础集训营2
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了2021牛客寒假算法基础集训营2,小编现在分享给大家,供广大互联网技能从业者学习和参考。文章包含2486字,纯文字阅读大概需要4分钟。
内容图文
![2021牛客寒假算法基础集训营2](/upload/InfoBanner/zyjiaocheng/606/c6d71e18489545e18f8242a40ddb8aeb.jpg)
D.牛牛与整除分块
题解:前根号n个值(包括根号n)没有重复,x即排名;后根号n个,n/x比n/√n小多少排名就在√n上大多少。
#include<bits/stdc++.h>
using namespace std;
int main()
{
int t, n, x, i;
scanf("%d", &t);
while (t--){
scanf("%d%d", &n, &x);
int m = sqrt(n);
if (m * m != n) m++;
if (x <= sqrt(n)) printf("%d\n", x);
else{
//printf("%d\n", m);
int a = n / m, b = n / x;
printf("%d\n", m + (a - b));
}
}
}
F.牛牛与交换排序
题解:如果一个数放错位置,将这个数作为头,那么通过翻转它应该和尾交换过来。如果不能,下一次翻转只能选择更右的区间,那么这个数就不可能回到它应该在的位置。
#include<bits/stdc++.h>
using namespace std;
int a[100010];
int pos[100010];
struct deque//双端队列
{
int l, r, flag;
int qu[200010];
void reverse()
{
flag ^= 1;
}
void push(int x)
{
if (!flag) qu[r++] = x;
else qu[--l] = x;
}
void pop()
{
if (!flag) l++;
else r--;
}
int front()
{
if (!flag) return qu[l];
else return qu[r-1];
}
}q;
int main()
{
int n, i;
scanf("%d", &n);
for (i = 1; i <= n; i++){
scanf("%d", &a[i]);
pos[a[i]] = i;
}
int k = 0;
for (i = 1; i <= n; i++){
if (pos[i] != i){
k = abs(pos[i] - i) + 1;
break;
}
}
if (!k) printf("yes\n1\n");
else{
bool boo = 1;
q.l = 1e5;
q.r = 1e5;
for (i = 1; i <= k; i++)
q.push(a[i]);
for (i = 1; i <= n; i++){
if (q.front() != i){//位置不对翻转
q.reverse();
if (q.front() != i){//翻转之后还是不对,那就翻不过来了
boo = 0;
break;
}
}
q.pop();
q.push(a[i+k]);
}
if (boo){
printf("yes\n");
printf("%d\n", k);
}
else printf("no\n");
}
}
I.牛牛的“质因数”
题解:f[10]=2 * 10 + 5,设x=pi * y,则f[x]=f[y] * k + pi,其中pi为x的最大质因数,k为pi的位数。
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll f[4000010];
ll mod = 1e9 + 7;
ll calc(ll x)
{
ll res = 1;
while (x)
res *= 10, x /= 10;
return res;
}
int main()
{
int n, i, j;
scanf("%d", &n);
for (i = 2; i <= n; i++){
if (!f[i]){
f[i] = i;
for (j = 2 * i; j <= n; j += i)
f[j] = ((f[j/i] * calc(i) % mod) + i) % mod;
}
}
ll res = 0;
for (i = 2; i <= n; i++)
res = (res + f[i]) % mod;
printf("%lld\n", res);
}
J.牛牛想要成为hacker
题解:取前k项,使得这前k项中的任意三项不能组成三角形,或者前k项中的任意两项和后面的任意一项或前k项中的任意一项和后面的任意两项也不能组成三角形。那么,前42项取2为首项的斐波那契数列(第43项大于1e9),后面放1即可。
#include<bits/stdc++.h>
using namespace std;
int f[50];
void init()
{
f[1] = 2, f[2] = 3;
for (int i = 3; i <= 50; i++)
f[i] = f[i - 1] + f[i - 2];
}
int main()
{
init();
int n, i, p = 0;cin >> n;
for (i = 1; i <= n; i++){
if (i <= 42){
!p ? cout << f[i] : cout << ' ' << f[i];
p++;
}
else{
!p ? cout << 1 : cout << ' ' << 1;
p++;
}
}
cout << endl;
}
内容总结
以上是互联网集市为您收集整理的2021牛客寒假算法基础集训营2全部内容,希望文章能够帮你解决2021牛客寒假算法基础集训营2所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错,欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明:本文内容由互联网用户自发贡献,该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 gblab@vip.qq.com 举报,一经查实,本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。