题目描述
本题为填空题,只需要算出结果后,在代码中使用输出语句将所填结果输出即可。
素数就是不能再进行等分的整数。比如7,11。而 9 不是素数,因为它可以平分为 3 等份。一般认为最小的素数是2,接着是 3,5,...
请问,第 100002(十万零二)个素数是多少?
请注意:“2” 是第一素数,“3” 是第二个素数,依此类推。
运行限制
最大运行时间:1s
最大运行内存: 128M
直接找,筛质数的话也行
#include<iostream> using namespace std; bool check(int x){ for(int i = 2; i <=
x / i; i++) if(x % i == 0) return false; return true; } int main(){ int ans =
0; for(int i = 2; ; i++){ if(check(i)) ans++; if(ans == 100002) {
cout<<i<<endl; break; } } return 0; }
补充筛质数

题目是,找出1到n的质数个数

埃式筛法

遍历1到n所有的数,找出每个数的倍数,是倍数的变为false
#include<iostream> using namespace std; const int N = 1000010; int n; int
primes[N], cnt; bool st[N]; void get_prime(int n){ for(int i = 2; i <= n; i++){
if(!st[i]){ primes[cnt++] = i; for(int j = i + i; j <= n; j += i) st[j] = true;
} } } int main(){ cin>>n; get_prime(n); cout<<cnt<<endl; return 0; }
线性筛法

只用最小质因子来筛,每个数只会被筛一次,所有是线性的

primes[j] 一定是 i 的最小质因子
#include<iostream> using namespace std; const int N = 1000010; int n; int
primes[N], cnt; bool st[N]; void get_prime(int n){ for(int i = 2; i <= n; i++){
if(!st[i]) primes[cnt++] = i; for(int j = 0; primes[j] <= n / i; j++){
st[primes[j] * i] = true; if(i % primes[j] == 0) break; } } } int main(){
cin>>n; get_prime(n); cout<<cnt<<endl; return 0; }
第二题:图书排列
题目描述
本题为填空题,只需要算出结果后,在代码中使用输出语句将所填结果输出即可。
将编号为 1 ~ 10 的 10 本书排放在书架上,要求编号相邻的书不能放在相邻的位置。
请计算一共有多少种不同的排列方案。
运行限制
最大运行时间:1s
最大运行内存: 128M
全排列问题,全排列枚举,进行判断即可
#include<iostream> #include<algorithm> using namespace std; int main(){ int
a[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}; int ans = 0; do{ bool falg = 0; for(int
i = 1; i < 10; i++) if(a[i] - 1 == a[i-1] || a[i-1] == a[i] + 1) falg = 1;
if(!falg) ans++; }while(next_permutation(a, a + 10)); printf("%d", ans); return
0; }
第三题:日志统计
题目描述
小明维护着一个程序员论坛。现在他收集了一份"点赞"日志,日志共有 N 行。其中每一行的格式是:
ts id
表示在 ts 时刻编号 id 的帖子收到一个"赞"。
现在小明想统计有哪些帖子曾经是"热帖"。如果一个帖子曾在任意一个长度为 D 的时间段内收到不少于 K 个赞,小明就认为这个帖子曾是"热帖"。
具体来说,如果存在某个时刻 T 满足该帖在[T,T+D) 这段时间内(注意是左闭右开区间)收到不少于 K 个赞,该帖就曾是"热帖"。
给定日志,请你帮助小明统计出所有曾是"热帖"的帖子编号。
输入描述
输入格式:
第一行包含三个整数 N,D,K。
以下 N 行每行一条日志,包含两个整数 ts 和 id。
其中,1≤K≤N≤10 5 ,0≤ts≤10 5 ,0≤id≤10 5 。
输出描述
按从小到大的顺序输出热帖 id。每个 id 一行。
输入输出样例 输入 7 10 2 0 1 0 10 10 10 10 1 9 1 100 3 100 3 copy 输出 1 3
贪心加双指针,进行排序,再在时间范围内选取帖子
#include<algorithm> #include<iostream> using namespace std; #define x first
#define y second typedef pair<int, int> PII; const int N = 100010; int n, t, k;
PII logs[N]; int cnt[N]; bool st[N]; int main(){ scanf("%d%d%d", &n, &t, &k);
for(int i = 0; i < n; i++) scanf("%d%d", &logs[i].x, &logs[i].y); sort(logs,
logs + n); for(int i = 0, j = 0; i < n; i++){ int id = logs[i].y; cnt[id] ++;
while(logs[i].x - logs[j].x >= t){ cnt[logs[j].y]--; j ++; } if(cnt[id] >= k)
st[id] = true; } for(int i = 0; i <= N; i++) if(st[i]) printf("%d\n", i);
return 0; }
第四题:杨辉三角

下面的图形是著名的杨辉三角形:

如果我们按从上到下、从左到右的顺序把所有数排成一列,可以得到如下数列: 1,1,1,1,2,1,1,3,3,1,1,4,6,4,1,⋯

给定一个正整数 N,请你输出数列中第一次出现 N 是在第几个数?

输入描述

输入一个整数 N。

输出描述

输出一个整数代表答案。

输入输出样例
输入 6 输出 13
有点傻的做法,骗分,别学我
#include<iostream> using namespace std; const int N = 10000; int n; int a[11];
int main(){ int a[22] = {1,1,1,1,1,1,1,3,3,1,1,4,6,4,1,1,5,10,10,5,1};
scanf("%d", &n); for(int i = 0; i <= 21; i++) if(a[i] == n){ cout<<i + 1<<endl;
break; } return 0; }

技术
今日推荐
PPT
阅读数 96
下载桌面版
GitHub
百度网盘(提取码:draw)
Gitee
云服务器优惠
阿里云优惠券
腾讯云优惠券
华为云优惠券
站点信息
问题反馈
邮箱:ixiaoyang8@qq.com
QQ群:766591547
关注微信