2个月前

## C++ 代码

### 注意区间

# include <iostream>
using namespace std;
const int N = 1e4;
int main()
{
double x;
cin >> x;
double l = -N, r = N;
while(r - l > 1e-8)
{
double mid = (l + r) / 2;
if (mid * mid * mid >= x) r = mid;
else l = mid;
}
printf("%lf", l);
return 0;
}


2个月前

# C++ 代码

## 利用快速排序算法的模板

1. 首先将原始的数组读取进来，记为q[]
2. 然后分别将q[]数组的奇数和偶数对应的下标记录下来，存在新的数组里面e[]和o[]
3. 然后分别对q[]的e[]下标以及o[]下标进行排序
4. 输出
# include <iostream>
using namespace std;
const int N = 1010;
int n, m, q[N], o[N], e[N];

void quick_sort_up(int q[], int o[], int l, int r)
{
if (l >= r) return;
int x = q[o[l + r >> 1]], i = l - 1, j = r + 1;
while(i < j)
{
do i ++; while (q[o[i]] < x);
do j --; while (q[o[j]] > x);
if(i < j) swap(q[o[i]], q[o[j]]);
}
quick_sort_up(q, o, l, j), quick_sort_up(q, o, j + 1, r);
}

void quick_sort_down(int q[], int e[], int l, int r)
{
if (l >= r) return;
int x = q[e[l + r >> 1]], i = l - 1, j = r + 1;
while(i < j)
{
do i ++; while (q[e[i]] > x);
do j --; while (q[e[j]] < x);
if(i < j) swap(q[e[i]], q[e[j]]);
}
quick_sort_down(q, e, l, j), quick_sort_down(q, e, j + 1, r);
}

int main()
{
scanf("%d", &m);
for (int k = 0; k < m; k ++)
{
scanf("%d", &n);
// 分别作为奇数和偶数的idx
int idxo = 0, idxe = 0;

for (int i = 0; i < n; i ++ )
{
scanf("%d", &q[i]);
// 记录奇数和偶数对应的下标
if(q[i] % 2 == 0) e[ idxe++] = i;
else o[ idxo++] = i;
}
// 快速排序
quick_sort_up(q, o, 0, idxo - 1);
quick_sort_down(q, e, 0, idxe - 1);

printf("Case #%d: ", k + 1);
for (int i = 0; i < n; i ++) printf("%d ", q[i]);
puts("");
}
return 0;
}


2个月前

## 与快排做法相同

# include <iostream>
using namespace std;
const int N = 1e3 + 10;
int n, l, r, a[N];
void sort (int a[], int l, int r)
{
if(l >= r) return;
int x = a[l + r >> 1], i = l - 1, j = r + 1;
while(i < j)
{
do i ++; while(a[i] < x);
do j --; while(a[j] > x);
if(i < j) swap(a[i], a[j]);
}
sort(a, l, j), sort(a, j + 1, r);
}
int main()
{
scanf("%d%d%d", &n, &l, &r);
for (int i = 0; i < n; i ++) scanf("%d", &a[i]);
sort(a, l, r);
for (int i = 0; i < n; i ++) printf("%d ", a[i]);

}


2个月前

## 标准做法

# include <iostream>
using namespace std;
const int N = 1e5 + 10;
int m, n, x, q[N];
int main()
{
scanf("%d%d", &n, &m);
for (int i = 0; i < n; i ++) scanf("%d", &q[i]);
while ( m-- )
{
scanf("%d", &x);

int l = 0, r = n - 1;
while (l < r)
{
int mid = l + r >> 1;
if (q[mid] >= x) r = mid;
else l = mid + 1;
}
if (q[l] != x) printf("-1 -1\n");
else
{
printf("%d ", l);
// while (q[l + 1] == x) l ++;
int l = 0, r = n - 1;
while (l < r)
{
int mid = l + r + 1 >> 1;
if (q[mid] <= x) l = mid;
else r = mid - 1;
}

printf("%d\n", l);
}
}
return 0;

}


## 投机取巧

# include <iostream>
using namespace std;
const int N = 1e5 + 10;
int m, n, x, q[N];
int main()
{
scanf("%d%d", &n, &m);
for (int i = 0; i < n; i ++) scanf("%d", &q[i]);
while ( m-- )
{
scanf("%d", &x);

int l = 0, r = n - 1;
while (l < r)
{
int mid = l + r >> 1;
if (q[mid] >= x) r = mid;
else l = mid + 1;
}
if (q[l] != x) printf("-1 -1\n");
else
{
printf("%d ", l);
while (q[l + 1] == x) l ++;
printf("%d\n", l);
}
}
return 0;

}


2个月前

### 算法1

#### C++ 代码

# include <iostream>
using namespace std;
int main()
{
int a, b, c, x, y, z;
scanf("%d%d%d", &a, &b, &c);
x = min(a, min(b, c)), z = max(a, max(b, c)), y = a + b + c - x - z;
printf("%d\n%d\n%d\n\n%d\n%d\n%d", x, y, z, a, b, c);
}


2个月前

## C++ 代码

# include <iostream>
using namespace std;
const int N = 1e5 + 10;
int q[N], tmp[N], n;
void merge_sort(int q[], int l, int r)
{
// 递归出口
if(l >= r) return;
// 取中间值
int mid = l + r >> 1;
// 递归过程
merge_sort(q, l, mid), merge_sort(q, mid + 1, r);
// 归并过程
int k = 0, i = l, j = mid + 1;
while (i <= mid && j <= r)
if (q[i] <= q[j]) tmp[k ++] = q[i ++];
else tmp[k ++] = q[j ++];
while (i <= mid) tmp[k ++] = q[i ++];
while (j <= r) tmp[k ++] = q[j ++];
// 复制过程
for (i = l, j = 0; i <= r; i ++, j ++) q[i] = tmp[j];
}
int main()
{
scanf("%d", &n);
for (int i = 0; i < n; i ++) scanf("%d", &q[i]);
merge_sort(q, 0, n - 1);
for (int i = 0; i < n; i ++) printf("%d ", q[i]);
return 0;
}


2个月前

## C++ 代码

#### 注意x的取值

# include <iostream>
using namespace std;
const int N = 1e5 + 10;
int q[N];
void quick_sort(int q[], int l, int r)
{
if (l >= r) return;
int x = q[(l + r) / 2], i = l - 1, j = r + 1;
while(i < j)
{
do i ++; while (q[i] < x);
do j --; while (q[j] > x);
if(i < j) swap(q[i], q[j]);
}
quick_sort(q, l, j);
quick_sort(q, j + 1, r);
}
int main()
{
int n;
scanf("%d", &n);
for (int i = 0; i < n; i ++) scanf("%d", &q[i]);
quick_sort(q, 0, n - 1);
for (int i = 0; i < n; i ++) printf("%d ", q[i]);
return 0;
}


## STL

# include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
int a[N], n;
int main()
{
ios::sync_with_stdio(false);
cin >> n;
for(int i = 0; i < n; i ++) cin >> a[i];
sort(a, a + n);
for(int i = 0; i < n; i ++) cout << a[i] << " ";
cout << endl;
return 0;
}


3个月前

## C++ 代码

S = “abababc”
P = “abababab”
p的next数组为：ne = [0,0,1,2,3,4,5,6]
1. next数组的意义：p字符串的每一个位置对应的最小回退长度
2. 回退一步的意义：返回到最长的前面部分已经匹配的长度对应的下标
3. 求next数组方法与kmp匹配方法类似

# include <iostream>
using namespace std;
const int N = 10010, M = 100010;
int n, m;
char s[M], p[N];
int ne[N];
int main()
{
cin >> n >> p + 1 >> m >> s + 1;
//求next的过程
for (int i = 2, j = 0; i <= n; i ++)
{
while (j && p[i] != p[j + 1]) j = ne[i];
if (p[i] == p[j + 1]) j ++;
ne[i] = j;
}
//KMP匹配过程
for (int i = 1, j = 0; i <= m; i ++)
{
while (j && s[i] != p[j + 1]) j = ne[j];
if (s[i] == p [j + 1]) j ++;
if (j == n) // 匹配成功
{
printf("%d ", i - n);
j = ne[j];
}
}
return 0;
}


3个月前

## C++ 代码

1. 构造单调队列解决，数据从队尾进入，从队头输出，队列存的是原始数据的下标
2. 每次输出最小值的时候，从队首到队尾是单调递增的
3. 当队列非空且队列头滑出窗口外了则需要hh++
4. 当队列非空且队尾元素<=（>=）当前数据，tt–
5. 数据入队
6. 输出
# include <iostream>
using namespace std;
const int N = 1000010;

int a[N], q[N];

int main()
{
int n, k;
scanf("%d%d", &n, &k);
for (int i = 0; i < n; i ++) scanf("%d", &a[i]);
int hh = 0, tt = -1;
for (int i = 0; i < n; i ++)
{
if (hh <= tt && i - k + 1 > q[hh]) hh ++;
while (hh <= tt && a[i] <= a[q[tt]]) tt --;
q[ ++tt] = i;
if (i >= k - 1 ) printf("%d ", a[q[hh]]);
}
puts("");

hh = 0, tt = -1;
for (int i = 0; i < n; i ++)
{
if (hh <= tt && i - k + 1 > q[hh]) hh ++;
while (hh <= tt && a[i] >= a[q[tt]]) tt --;
q[ ++tt] = i;
if (i >= k - 1 ) printf("%d ", a[q[hh]]);
}
puts("");
return 0;

}


3个月前

## C++ 代码

1. 构造一个单调递增的栈
2. 比较栈顶元素与即将入栈元素的大小
3. 如果即将入栈的元素小于栈顶元素则栈顶指针tt–，直到为空栈或者都比该元素小
4. 非空则输出栈顶元素，否则输出-1
5. 入栈

# include<iostream>
using namespace std;
const int N = 100010;

int stk[N], tt;

int main()
{
int m, x;
scanf("%d", &m);
for (int i = 0; i < m; i ++)
{
scanf("%d", &x);
while(tt && x <= stk[tt]) tt--;
if(tt) printf("%d ", stk[tt]);
else printf("-1 ");
stk[ ++tt] = x;
}
}