牛客练习赛14

77 阅读 0 评论 51 点赞

我是靠谱客的博主俊逸高跟鞋，最近开发中收集的这篇文章主要介绍牛客练习赛14，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

https://www.nowcoder.com/acm/contest/82#question
A.n的约数
链接：https://www.nowcoder.com/acm/contest/82/A
来源：牛客网

题目描述

t次询问，每次给你一个数n，求在[1,n]内约数个数最多的数的约数个数
输入描述:
第一行一个正整数t之后t行，每行一个正整数n
输出描述:
输出t行，每行一个整数，表示答案

本题简化版
https://vjudge.net/problem/HDU-2521

#include <bits/stdc++.h>
using namespace std;
/*
暴力 素因子，没什么难度，
*/
typedef long long ll;
const int maxn=2000;
ll Stack[1000],top,Cnt[maxn];
int
fenjie(ll k){
memset(Cnt,0,sizeof(Cnt));
top=0;
for(ll i=2;i*i<=k;i++){
while(k%i==0)
Cnt[top]++,k/=i;
Stack[top++]=i;
}
if(k>1){
Cnt[top]++;
Stack[top++]=k;
}
int rel=1;
for(int i=0;i<top;i++){
rel*=(Cnt[i]+1);
}
return rel;
}
ll s;
int main()
{
int t,a,b;
scanf("%d",&t);
while(t--){
scanf("%d%d",&a,&b);
int rel=-1;
int max1=-1;
for(int i=a;i<=b;i++){
int ans=fenjie(i);
if(ans>max1){
max1=ans;
rel=i;
}
}
printf("%dn",rel);
}
return 0;
}

但是这道题明显不可以暴力，1e18的数据范围。
但是我们可以使用质因子分解的逆过程。
首先，一个公式
一个数 s=pow(p1,j1)+pow(p2,j2)+…+pow(pn,jn).
一个数的因子个数=(j1+1)(j2+1)(j3+3)..
那么我们可以枚举j1，j2,j3，并且保证最后的结果要小于等于n（这就要求一个参数），并且我们可以递归的计算因子个数。这样就需要三个参数。
思想类似于爆搜。这里写图片描述
但是这样还是太慢了qwq，存在一个优化，那就是我们发现。
18=3*3*2.
12=2*2*3。
18和12有相同的分解结构，所以我们可以使其j数组的数随着素因子的变大而变小，这样会使其在相同的分解结构中有更小的总值。
参见博客
https://www.cnblogs.com/acSzz/archive/2012/07/24/2606079.html

#include<iostream>
#include<algorithm>
#include<cstdio>
using namespace std;
long long ans;
long long ansnum;//约数个数
long long n;
long long prime[30]={0,2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,51};
long long
tt=2147483647;
//取20个质数
//2^a1 * 3^a2 * 5^a3 * 7^a4
bool solve(int s){
for(int i=2;i*i<=s;i++){
if(s%i==0)return 0;
}
return 1;
}
void dfs(long long m,long long pi,long long m_num,long long pre)//m为当前的数,pi为当前枚举的素数,m_num为m的约数的个数,pre为之前的素数的个数
{
if(m_num>ansnum)//更新最终结果
{
ans=m;
ansnum=m_num;
}
if(m_num==ansnum&&ans>m)//更新最终结果
{
ans=m;
}
for(long long l=1;l<=pre;)//m*(prime[pi]^l)，这里m不断乘以当前枚举的素数，
{
if(n/m<prime[pi]) break;
m*=prime[pi];
if(m>n)
{
break;
}
l++;//计算当前素数被乘了多少次
dfs(m,pi+1,m_num*l,l-1);//此时m的素数的个数为m_num*l
}
}
int main()
{
long long total;
int cnk=0;
//cout<<LONG_MAX<<endl;
cin>>total;
while(total--)
{
ans=1;//最后结果的数
ansnum=-1;//最后的结果的约数的个数
scanf("%lld",&n);//n的输入
//质数连乘开始
dfs(1,1,1,30);//初始时从1开始连乘，从第一个素数2开始，
printf("%lldn",ansnum);
}
return 0;
}

D比较月亮大小
链接：https://www.nowcoder.com/acm/contest/82/D
来源：牛客网

题目描述


点点是一名出色的狼人。众所周知，狼人只有在满月之夜才会变成狼。
同时，月亮的大小随着时间变化，它的大小变化30天为一循环。它的变化情况(从第一天开始)为0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1 然后又再一次循环。
今年夏天点点很无聊，于是开始看月亮。由于点点很忙，所以他只选择一段连续的时间看月亮，并把月亮的大小记录了下来。
现在，他告诉你他记录下东西，让你告诉他下一天(即点点记录下的最后一天的第二天)的月亮是比前一天(即点点记录下的最后一天)大还是小。

输入描述:
给你一个正整数n表示点点记录下的时间个数。下一行n个自然数表示点点记录下的月亮大小。
输出描述:
一个字符串。如果下一天的比前一天的大则输出”UP”如果下一天的比前一天的小则输出”DOWN”如果无法判断则输出”-1”

示例1

输入

5
3 4 5 6 7

输出

UP
思路: 0和15特判就可以，但是遗漏了一个细节，那就是一个数也是可以判断的。。当为15时必定下降，为0时必定上升

#include <iostream>
#include<bits/stdc++.h>
using namespace std;
vector<int>q;
int m,n;
int main()
{
while(cin>>m){
q.clear();
int max1=-1;
for(int i=0;i<m;i++){
scanf("%d",&n);
q.push_back(n);
max1=max(max1,n);
}
int loc=-1;
for(int i=0;i<q.size();i++){
if(q[i]==max1)
loc=i;
}
if(m==1){
if(q[0]==0)
puts("UP");
else if(q[0]==15)
puts("DOWN");
else
puts("-1");
}
else{
if(q[m-1]==0||q[m-1]==15){
if(q[m-1]-q[m-2]<0){
puts("UP");
}
else
puts("DOWN");
}
else{
if(q[m-1]-q[m-2]<0){
puts("DOWN");
}
else
puts("UP");
}
}
}
return 0;
}