连号区间数
原题链接：https://www.acwing.com/problem/content/1212/
初始最小值和最大值的依据是题目给出的数据范围。只要在数据范围之外就可以。
连号的时候，相邻元素元素之间，差值为1。那么区间右边界和左边界，的值的差，就应该等于下标索引的差值。
#include"bits/stdc .h"
using namespace std;
int P[10010];
int N;
int main() {
cin >> N;
for (int i = 0; i < N; i )cin >> P[i];
int res = 0;
for (int i = 0; i < N; i ) {
int minn = 10010;
int maxx = 0;
for (int j = i; j < N; j ) {
minn = min(minn, P[j]);
maxx = max(maxx, P[j]);
if (maxx - minn == j - i)res ;
}
}
cout << res;
return 0;
}递增三元组
原题链接：https://www.acwing.com/problem/content/1238/
如果选择暴力，那么复杂度是三次方。
数据范围是1e5，这时间复杂度是不被允许的。（暴力杯或许可以）
时间复杂度应控制到
，意味着最多只能枚举一个数组。 枚举A或C是等价的，都是在两边。 以A为例，枚举A的时候，在考虑B和C的时候，B和C都不是完全独立的，B和C之间有相互限制。统计数量的时候不能用简单的乘法相乘。 如果选择枚举B，那么A和C之间是相互独立的。 A的判断条件就是小于B，C的判断条件就是大于B。 当前B的取值的合法三元组的数量，就是合法的A的数量乘合法的C的数量。 那么现在的问题就是求合法的A和合法的C的数量。
前缀和
需要两个数组：
cnt[i]：表示在A中i这个值出现多少次S[i]：表示在A中[0,i]出现多少次
求A中多少个数小于Bi，就是求S[Bi-1]的值。
求C中多少个数大于Bi，就是求S[N-Bi]的值，N为数据范围的最大值。
前缀和的时间复杂度为n。
#include"bits/stdc .h"
using namespace std;
typedef long long LL;
const int N = 1e5 10;
int a[N], b[N], c[N];
int as[N], cs[N];
int cnt[N], s[N];
int n;
int main() {
scanf("%d", &n);
for (int i = 0; i < n; i )scanf("%d", a i), a[i] ;
for (int i = 0; i < n; i )scanf("%d", b i), b[i] ;
for (int i = 0; i < n; i )scanf("%d", c i), c[i] ;
for (int i = 0; i < n; i ) cnt[a[i]] ;
for (int i = 1; i < N; i )s[i] = s[i - 1] cnt[i];
for (int i = 0; i < n; i )as[i] = s[b[i] - 1];
memset(cnt, 0, sizeof cnt);
memset(s, 0, sizeof s);
for (int i = 0; i < n; i ) cnt[c[i]] ;
for (int i = 1; i < N; i )s[i] = s[i - 1] cnt[i];
for (int i = 0; i < n; i )cs[i] = s[N - 1] - s[b[i]];
LL res = 0;
for (int i = 0; i < n; i ) res = (LL) as[i] * cs[i];
cout << res << endl;
return 0;
}特别数的和
原题链接：https://www.acwing.com/problem/content/1247/
一道简单模拟，for循环的范围参考题目给的数据范围。
代码语言：javascript复制#include"bits/stdc .h"
using namespace std;
int n, res;
int main() {
scanf("%d", &n);
for (int i = 1; i <= n; i ) {
int x = i;
while (x) {
int t = x % 10;
x /= 10;
if (t == 2 || t == 0 || t == 1 || t == 9) {
res = i;
break;
}
}
}
cout << res << endl;
return 0;
}错误票据
原题链接：https://www.acwing.com/problem/content/1206/
排序
代码语言：javascript复制#include"bits/stdc .h"
using namespace std;
int n;
int a[100010];
int main() {
int cnt;
cin >> cnt;
string line;
getline(cin, line);
while (cnt--) {
getline(cin, line);
stringstream ssin(line);
while (ssin >> a[n ]);
}
sort(a, a n);
int res1, res2;
for (int i = 1; i < n; i ) {
if (a[i] == a[i - 1])res2 = a[i];
else if (a[i] >= a[i - 1] 2)res1 = a[i] - 1;
}
printf("%d %d", res1, res2);
return 0;
}忽略行数读入
代码语言：javascript复制#include"bits/stdc .h"
using namespace std;
int n;
int a[100010];
int main() {
int cnt;
cin >> cnt;
int maxx=0,minn=1e5;
while(cin>>n){
a[n] ;
maxx=max(maxx,n);
minn=min(minn,n);
}
int res1,res2;
for(int i=minn;i<=maxx;i ){
if(a[i]==0)res1=i;
else if(a[i]==2)res2=i;
}
printf("%d %d",res1,res2);
return 0;
}归并排序
代码语言：javascript复制原题链接：https://www.acwing.com/problem/content/789/
#include"bits/stdc .h"
using namespace std;
int n;
int q[100010], tmp[100010];
void merge_sort(int q[], int l, int r) {
if (l >= r)return;
int mid = l r >> 1;
merge_sort(q, 1, 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 ];
for (i = l, j = 0; i <= r; i , j )q[i] = tmp[i];
}
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;
}移动距离
原题链接：https://www.acwing.com/problem/content/description/1221/
- 曼哈顿距离：
- 欧几里得距离：
这道题求的是曼哈顿距离。
行号：n/w
列号：n%w
下标从零开始，如果行号是奇数，那么应将列号翻转。
找到了一种新的判断奇偶的方式：x&1
