下载免费网站模板下载安装,上海网站建设广告语,做特卖网站有哪些,什么样的公司才叫企业连号区间数 原题链接#xff1a;https://www.acwing.com/problem/content/1212/ 初始最小值和最大值的依据是题目给出的数据范围。只要在数据范围之外就可以。 连号的时候#xff0c;相邻元素元素之间#xff0c;差值为1。那么区间右边界和左边界#xff0c;的值的差#…连号区间数 原题链接https://www.acwing.com/problem/content/1212/ 初始最小值和最大值的依据是题目给出的数据范围。只要在数据范围之外就可以。 连号的时候相邻元素元素之间差值为1。那么区间右边界和左边界的值的差就应该等于下标索引的差值。
#includebits/stdc.husing 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 n\log n nlogn意味着最多只能枚举一个数组。 枚举A或C是等价的都是在两边。 以A为例枚举A的时候在考虑B和C的时候B和C都不是完全独立的B和C之间有相互限制。统计数量的时候不能用简单的乘法相乘。 如果选择枚举B那么A和C之间是相互独立的。 A的判断条件就是小于BC的判断条件就是大于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。
#includebits/stdc.husing 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循环的范围参考题目给的数据范围。
#includebits/stdc.husing 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/ 排序
#includebits/stdc.husing 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;
}
忽略行数读入
#includebits/stdc.husing namespace std;
int n;
int a[100010];int main() {int cnt;cin cnt;int maxx0,minn1e5;while(cinn){a[n];maxxmax(maxx,n);minnmin(minn,n);}int res1,res2;for(int iminn;imaxx;i){if(a[i]0)res1i;else if(a[i]2)res2i;}printf(%d %d,res1,res2);return 0;
}
归并排序 原题链接https://www.acwing.com/problem/content/789/ #includebits/stdc.husing 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 ∣ |x_1-x_2||y_1-y_2| ∣x1−x2∣∣y1−y2∣欧几里得距离 ( x 1 − x 2 ) 2 ( y 1 − y 2 ) 2 \sqrt{(x_1-x_2)^2(y_1-y_2)^2} (x1−x2)2(y1−y2)2
这道题求的是曼哈顿距离。 行号n/w 列号n%w 下标从零开始如果行号是奇数那么应将列号翻转。 找到了一种新的判断奇偶的方式x1
