线性筛素数
题目描述
如题，给定一个范围 n，有 q 个询问，每次输出第 k 小的素数。
输入格式
第一行包含两个正整数 n,q，分别表示查询的范围和查询的个数。
接下来 q 行每行一个正整数 k，表示查询第 k 小的素数。
输出格式
输出 q 行，每行一个正整数表示答案。
示例 1：
输入 #1复制
100 5
1
2
3
4
5
输出 #1复制
2
3
5
7
11
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
|
#include<stdio.h>
#include<string.h>
int main() {
int n, q, a;
int x[1001000];
bool y[100100000] = {0};
int t = 0;
scanf("%d %d", &n, &q);
for (int i = 2; i <= n; i++) {
if (!y[i]) {
x[t++] = i;
}
for (int j = 0; j < t && i * x[j] <= n; j++) {
y[i * x[j]] = 1;
if (i % x[j] == 0) break;
}
}
for (int i = 0; i < q; i++) {
scanf("%d", &a);
if (a <= 0 || a > t) {
printf("Invalid input\n");
} else {
printf("%d\n", x[a - 1]); // 改成0-based索引
}
}
return 0;
}
|
解法
欧拉筛，线性筛，总体思路是先筛2（最多两倍），然后读入一个素数，然后再筛2，3（最多3倍），然后读入一个素数，这样一直添加。可以保证添加的一定为素数
模板 快速幂
给你三个整数 a,b,p，求 a b mod p。
输入格式
输入只有一行三个整数，分别代表 a,b,p。
输出格式
输出一行一个字符串 a^b mod p=s，其中 a,b,p 分别为题目给定的值， s 为运算结果。
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
|
#include<stdio.h>
#include <stdlib.h>
long long x[47483648] = {};
long long fx(long long a, long long b, long long p)
{
long long lld, e;
if (b == 1)
return a % p;
long long c = b / 2;
if (c< 47483648&&x[c] != 0)
lld = x[c];
else
lld = fx(a, c, p);
if(b< 47483648)
x[b] = lld * e % p;
return lld * e % p;
}
int main()
{
long long a, b, c, lld, p, s;
scanf("%lld %lld %lld", &a, &b, &p);
c = fx(a, b, p);
printf("%lld^%lld mod %lld=%lld", a, b, p, c);
return 0;
}
|
解法
一定要long long 不然中途回爆炸，将幂转换成二进制使用，维护一个答案，当幂上出现奇数的时候对答案乘上一个base，然后将base幂一下，幂指数b也除以二
括号配对II
高级语言程序设计中的各种括号应该匹配，例如：“(” 与 “)”匹配、“[”与 “]” 匹配、“{”与 “}” 匹配等。
输入一字符文件，判断其中的括号是否匹配。假设括号没有优先级差别。
输入格式:
多行，字符个数不超过 65536。
输出格式:
一个单词，表示字符文件中括号匹配的结果，匹配输出“yes”，否则输出“no”.
输入样例:
在这里给出一组输入。例如：
( { } )
{a=(b*c)+free( ) }。
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
|
#include <stdio.h>
char x[1000]={'#'};
int main(void)
{
int a = 1, b = 1, c, d;
char ch;
while (scanf("%c",&ch)!=EOF)
{
if (ch == '(' || ch == '{' || ch == '[')
{
x[a] = ch;
a++;
}
if (ch == ')')
{
if (x[a - 1] == '(' && a >= 1)
{
a--;
x[a] = 0;
}
else
{
b = 0;
break;
}
}
if (ch == ']')
{
if (x[a - 1] == '[' && a >= 1)
{
a--;
x[a] = 0;
}
else
{
b = 0;
break;
}
}
if (ch == '}')
{
if (x[a - 1] == '{'&&a>=1)
{
a--;
x[a] = 0;
}
else
{
b = 0;
break;
}
}
}
if (b == 0 || a != 1)
printf("no");
else
printf("yes");
return 0;
}
|
解法
使用栈结构，使用while (scanf("%c",&ch)!=EOF)来判断是否还有输入
Blah数集
大数学家高斯小时候偶然发现一种有趣的自然数集合Blah。以a为基的集合Ba定义如下：
a是集合Ba的基，且a是Ba的第一个元素；
若x在集合Ba中，则2x+1和3x+1也都在Ba中；
没有其它元素在集合Ba中。
现在小高斯想知道如果将集合Ba中元素按照升序排列，第n个元素会是多少？
输入格式:
多行，每行包括两个数，集合的基a(1<=a<=50))以及所求元素序号n(1<=n<=1000000)
输出格式:
对于每个输入，输出集合Ba的第n个元素值
输入样例:
在这里给出一组输入。例如：
1 5
25 100000
输出样例:
在这里给出相应的输出。例如：
9
34503679
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
|
#include <stdio.h>
long long x[1000000];
int main(void)
{
long long a = 0, b = 0, c = 1, n, i;
while (scanf("%lld %lld", &i, &n) != EOF)
{
x[0] = i;
a = 0;
b = 0;
for (c = 1; c <= n; c++)
{
if ((x[a] * 2 + 1 == x[b] * 3 + 1))
{
x[c] = x[a] * 2 + 1;
a++;
b++;
}
else if (x[a] * 2 + 1 < x[b] * 3 + 1)
{
x[c] = x[a] * 2 + 1;
a++;
}
else
{
x[c] = x[b] * 3 + 1;
b++;
}
}
printf("%lld\n", x[n-1]);
}
}
|
解法
维护2x+1与3x+1两个指针，都大于已有的最后一个数，然后比较，添加进入。
左侧最近小数
对N个非负整数的序列，查询元素A i左侧最近的小于A i
的整数(1≤i≤N)，如果不存在，输出 -1
输入格式:
第1行，1个整数N，表示整数的个数，(1≤N≤100000)。
第2行，N个整数，每个整数x 都满足 0 ≤ x ≤2000000000。
输出格式:
1行,N个整数，表示每个元素A
i
左侧最近的小于A
i
的整数(1≤i≤N)。
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
|
#include <stdio.h>
long long x[100000] = {-1};
int main(void)
{
long long a, b=0, c, d, n, i;
scanf("%lld", &n);
for (a = 0; a < n; a++)
{
scanf("%lld", &i);
for (; x[b] >= i;b--)
{
x[b] = 0;
}
if (i > x[b])
{
if(n-a!=1)
printf("%lld ", x[b]);
else
printf("%lld", x[b]);
b++;
x[b] = i;
}
}
}
|
解法
维护一个单调栈，从左往右读，每次跟最上边比，大就入栈，小就弹栈再比
区间最小值I
对N个整数的序列，从左到右连续查询 M 长度子序列 A
i
,A
i+1
,…,A
i−M+1
(1≤i，M≤N)的最小值。
输入格式:
第1行，两个整数：N和M，表示整数的个数和区间长度，1≤N≤100000.
第2行，N个整数，每个整数x 都满足 │x│≤2000000000。
输出格式:
1行, 用空格分隔的N-M+1个整数，对应从左到右所有连续M长度子序列的最小值。
输入样例:
6 3
1 2 5 3 4 6
输出样例:
1 2 3 3 。
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
|
#include <stdio.h>
long long x[100000][2];
int main(void)
{
long long n, m, a, b, c = 0, d = 0, i;
scanf("%lld %lld", &n, &m);
for (a = 0; a < n; a++)
{
scanf("%lld", &i);
for (b = c; b >= 0; b--) //单调性维护
{
if (b == d || i > x[b - 1][0])
{
x[b][0] = i;
x[b][1] = a;
c++;
break;
}
else
{
x[b - 1][0] = 0;
x[b - 1][1] = 0;
c--;
}
}
if (x[c - 1][1] - x[d][1] >= m) //区间维护
{
x[d][1] = 0;
x[d][0] = 0;
d++;
}
if (a + 1 >= m)
{
if(n-a!=1)
printf("%lld ", x[d][0]);
else
printf("%lld", x[d][0]);
}
}
}
|
解法
使用两个数组，一个存数字，一个存下标，一个移动的指针指向最小，只有递增的加入队列，左指针随着移动，分为单调性维护和区间维护
a+b高精度加法
高精度加法，相当于 a+b problem，不用考虑负数。
输入格式
分两行输入。a,b≤10
500
。
输出格式
输出只有一行，代表 a+b 的值。
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
|
#include<stdio.h>
#include<string.h>
char a[10010];
int x[10010];
int main(){
scanf("%s",&a);
int n=strlen(a);
for(int i=0;i<n;i++){
x[i]+=a[n-1-i]-'0';
}
scanf("%s",&a);
n=strlen(a);
for(int i=0;i<n;i++){
x[i]+=a[n-1-i]-'0';
}
for(int i=0;i<10000;i++){
x[i+1]+=x[i]/10;
x[i]=x[i]%10;
}
int t=0;
for(int i=10010;i>=0;i--){
if(x[i]!=0){
t=1;
}
if(t==1){
printf("%d",x[i]);
}
}
if(t==0){
printf("0");
}
return 0;
}
|
解法
用一个字符数组记录读入的数字，用一个数字数组翻转，再使用模10计算进位，最后从后往前打印，存在第一个非0的打印，0单独考虑
[NOIP 2015 提高组] 跳石头
一年一度的“跳石头”比赛又要开始了！
这项比赛将在一条笔直的河道中进行，河道中分布着一些巨大岩石。组委会已经选择好了两块岩石作为比赛起点和终点。在起点和终点之间，有 N 块岩石（不含起点和终点的岩石）。在比赛过程中，选手们将从起点出发，每一步跳向相邻的岩石，直至到达终点。
为了提高比赛难度，组委会计划移走一些岩石，使得选手们在比赛过程中的最短跳跃距离尽可能长。由于预算限制，组委会至多从起点和终点之间移走 M 块岩石（不能移走起点和终点的岩石）
输入格式
第一行包含三个整数 L,N,M，分别表示起点到终点的距离，起点和终点之间的岩石数，以及组委会至多移走的岩石数。保证 L≥1 且 N≥M≥0。
接下来 N 行，每行一个整数，第 i 行的整数 D
i
(0<D
i
<L)， 表示第 i 块岩石与起点的距离。这些岩石按与起点距离从小到大的顺序给出，且不会有两个岩石出现在同一个位置。
输出格式
一个整数，即最短跳跃距离的最大值。
输入输出样例
输入 #1复制
25 5 2
2
11
14
17
21
输出 #1复制
4
说明/提示
输入输出样例 1 说明
将与起点距离为 2 和 14 的两个岩石移走后，最短的跳跃距离为 4（从与起点距离 17 的岩石跳到距离 21 的岩石，或者从距离 21 的岩石跳到终点）。
数据规模与约定
对于 20%的数据，0≤M≤N≤10。
对于 50% 的数据，0≤M≤N≤100。
对于 100% 的数据，0≤M≤N≤50000,1≤L≤10
9
。
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
|
#include<cstdio>
int k,n,m;
int pos[50005];
bool check(int mid){
int ans=0,st=0;
for(int i=1;i<=n;++i)
if(pos[i]-st<mid)
ans=ans+1;
else st=pos[i];
return ans<=m;
}
int main(){
scanf("%d%d%d",&k,&n,&m);
for(int i=1;i<=n;++i)scanf("%d",&pos[i]);
int l=0,r=k,mid;
while(l<r){
mid=(l+r)>>1;
if(check(mid))l=mid+1;
else r=mid-1;
}
if(!check(l))l-=1;
printf("%d\n",l);
return 0;
}
|
解法
枚举答案，然后判断答案是否正确，对枚举的答案先进行判断，然后进行二分。
141. 【深基13.例1】查找
题目描述
输入 n 个不超过 10
9
的单调不减的（就是后面的数字不小于前面的数字）非负整数 a
1
,a
2
,…,a
n
，然后进行 m 次询问。对于每次询问，给出一个整数 q，要求输出这个数字在序列中第一次出现的编号，如果没有找到的话输出 −1 。
输入格式
第一行 2 个整数 n 和 m，表示数字个数和询问次数。
第二行 n 个整数，表示这些待查询的数字。
第三行 m 个整数，表示询问这些数字的编号，从 1 开始编号。
输出格式
输出一行，m 个整数，以空格隔开，表示答案。
输入输出样例
输入 #1复制
11 3
1 3 3 3 5 7 9 11 13 15 15
1 3 6
输出 #1复制
1 2 -1
说明/提示
数据保证，1≤n≤10
6
，0≤a
i
,q≤10
9
，1≤m≤10
5
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
|
#include<stdio.h>
#include<math.h>
int x[1001000];
int main(){
int n,m,q;
int l,r,mid,p;
scanf("%d %d",&n,&m);
for(int i=0;i<n;i++){
scanf("%d",&x[i]);
}
for(int i=0;i<m;i++){
scanf("%d",&q);
l=0;
p=0;
r=n-1;
while(l<=r){
mid=(l+r)/2;
if(x[mid]==q){
p=mid;
r=mid-1;
}
else if(x[mid]>q){
r=mid-1;
}
else if(x[mid]<q){
l=mid+1;
}
}
if(x[p]!=q){
printf("-1 ");
continue;
}
else{
printf("%d ",p+1);
}
}
return 0;
}
|
解法
使用二分法，从中间开始判断，mid+1，mid-1
木材加工
题目背景
要保护环境
题目描述
木材厂有 n 根原木，现在想把这些木头切割成 k 段长度均为 l 的小段木头（木头有可能有剩余）。
当然，我们希望得到的小段木头越长越好，请求出 l 的最大值。
木头长度的单位是 cm，原木的长度都是正整数，我们要求切割得到的小段木头的长度也是正整数。
例如有两根原木长度分别为 11 和 21，要求切割成等长的 6 段，很明显能切割出来的小段木头长度最长为 5。
输入格式
第一行是两个正整数 n,k，分别表示原木的数量，需要得到的小段的数量。
接下来 n 行，每行一个正整数 L
i
，表示一根原木的长度。
输出格式
仅一行，即 l 的最大值。
如果连 1cm 长的小段都切不出来，输出 0。
输入输出样例
输入 #1复制
3 7
232
124
456
输出 #1复制
114
说明/提示
数据规模与约定
对于 100% 的数据，有 1≤n≤10
5
，1≤k≤10
8
，1≤L
i
≤10
8
(i∈[1,n])。
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
|
#include <stdio.h>
#define MAX_N 100100
long long x[MAX_N];
int main() {
int n, k;
scanf("%d %d", &n, &k);
long long sum = 0;
long long max_length = 0;
// 读入木材长度，并计算总长度和最大长度
for (int i = 0; i < n; i++) {
scanf("%lld", &x[i]);
sum += x[i];
if (x[i] > max_length) {
max_length = x[i];
}
}
// 如果总长度不足以分成 k 段，直接返回 0
if (sum < k) {
printf("0\n");
return 0;
}
long long low = 1;
long long high = max_length;
long long ans = 0;
while (low <= high) {
long long mid = (low + high) / 2;
long long count = 0;
// 计算以 mid 为长度可以切出多少段
for (int i = 0; i < n; i++) {
count += x[i] / mid;
if (count >= k) break; // 提前退出优化
}
if (count >= k) {
ans = mid; // 当前长度可行，尝试更大的长度
low = mid + 1;
} else {
high = mid - 1;
}
}
printf("%lld\n", ans);
return 0;
}
|
解法
倒着走，不去搜答案而是判断答案，然后通过二分法来加速过程
94. 二叉树的中序遍历
给定一个二叉树的根节点 root ，返回 它的 中序 遍历 。
示例 1：
输入：root = [1,null,2,3]
输出：[1,3,2]
示例 2：
输入：root = []
输出：[]
示例 3：
输入：root = [1]
输出：[1]
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
|
class Solution {
public:
void inorder(TreeNode* root, vector<int>& res)
{
if (root==nullptr) {
return;
}
inorder(root->left,res);
res.push_back(root->val);
inorder(root->right,res);
}
vector<int> inorderTraversal(TreeNode* root) {
vector<int> res;
inorder(root,res);
return res;
}
};
|
解法
传入一个栈，用res.push_back(root->val);压入
104. 二叉树的最大深度
给定一个二叉树 root ，返回其最大深度。
二叉树的 最大深度 是指从根节点到最远叶子节点的最长路径上的节点数。
示例 1：
输入：root = [3,9,20,null,null,15,7]
输出：3
示例 2：
输入：root = [1,null,2]
输出：2
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
|
class Solution {
public:
int deep (TreeNode* root,int d)
{
if(root==nullptr)
{
return d;
}
int l=deep(root->left,d+1);
int r=deep(root->right,d+1);
if(l>=r)
{
return l;
}
else{
return r;
}
}
int maxDepth(TreeNode* root) {
int i=deep(root,0);
return i;
}
};
|
解法
二叉树大部分用的都是递归，取左+取右，比较
226. 翻转二叉树
给你一棵二叉树的根节点 root ，翻转这棵二叉树，并返回其根节点。
示例 1：
输入：root = [4,2,7,1,3,6,9]
输出：[4,7,2,9,6,3,1]
示例 2：
输入：root = [2,1,3]
输出：[2,3,1]
示例 3：
输入：root = []
输出：[]
代码
1
2
3
4
5
6
7
8
9
10
11
12
|
class Solution {
public:
TreeNode* invertTree(TreeNode* root) {
if(root==nullptr) return nullptr;
TreeNode *temp=root->left;
invertTree(root->left);
invertTree(root->right);
root->left=root->right;
root->right=temp;
return root;
}
};
|
解法
二叉树大部分用的都是递归，左子树先换，右子树再换，最后在根节点换
101. 对称二叉树
给你一个二叉树的根节点 root ， 检查它是否轴对称。
示例 1：
输入：root = [1,2,2,3,4,4,3]
输出：true
示例 2：
输入：root = [1,2,2,null,3,null,3]
输出：false
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
|
class Solution {
public:
bool fx(TreeNode* left,TreeNode* right){
if(left==nullptr&&right==nullptr){
return true;
}
if(left==nullptr&&right!=nullptr){
return false;
}
if(left!=nullptr&&right==nullptr){
return false;
}
if(left->val==right->val){
int a=fx(left->left,right->right);
int b=fx(left->right,right->left);
if(a==true&&b==true){
return true;
}
else{
return false;
}
}
return false;
}
bool isSymmetric(TreeNode* root) {
return fx(root->left,root->right);
}
};
|
解法
二叉树大部分用的都是递归，传入左右两个节点，对称的来比较
