連號區間數

原題鏈接：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，這時間復雜度是不被允許的。（暴力杯或許可以）
時間復雜度應控制到$n\log n$，意味著最多只能枚舉一個數組。
枚舉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循環的范圍參考題目給的數據范圍。

#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/

排序

#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;
}

忽略行數讀入

#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;
}

歸并排序

原題鏈接：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/

• 曼哈頓距離：$|x_1?x_2|+|y_1?y_2|$
• 歐幾里得距離：$\sqrt{(x_1?x_2{)}^2+(y_1?y_2{)}^2}$

這道題求的是曼哈頓距離。
行號：n/w
列號：n%w
下標從零開始，如果行號是奇數，那么應將列號翻轉。
找到了一種新的判斷奇偶的方式：x&1