题目六:
题解:
#include <bits/stdc++.h> using namespace std; int a[100100], b[100100], c[100100]; int main() { int n; scanf("%d", &n); for(int i = 0; i < n; i++) { scanf("%d", &a[i]); } for(int i = 0; i < n; i++) { scanf("%d", &b[i]); } for(int i = 0; i < n; i++) { scanf("%d", &c[i]); } int ans = 0; sort(a, a+n); sort(b, b+n); sort(c, c+n); for(int i = 0; i < n; i++) { int x = lower_bound(a, a+n, b[i]) - a; int y = upper_bound(c, c+n, b[i]) - c; //cout << x << " " << y << endl; ans += (n-y) * x; } cout << ans << endl; return 0; } /* 3 1 1 1 2 2 2 3 3 3 */
这样的解法就省去了很多暴力for循环,
lower_bound(first, last, val)表示第一个大于等于b[i]的位置,
upper_bound(first, last, val)表示第一个大于val的位置。
题目七:
题解:
懒得写具体代码了,主要就是根据
主要根据点(-1,-1)(-x,-x)正好是x个正方形的和(比如(-1,-1)对应的就是sum = 2×4 = 8后面就是sum = sum + 2×x×4,(这是规律)再根据前进后退推出每个点的步数.
题目八:
题解:
#include <bits/stdc++.h> using namespace std; const int maxn = 1e5 + 5; vector<int> num[maxn]; int n, d, k; int judge(int x) { int len = num[x].size(); if(len < k ) return 0; //cout << sort(num[x].begin(), num[x].end()); //cout << x << endl; for(int i = 0; i < k; i++) { //cout << num[x][i] << " " ; } //cout << endl; for(int i = 0; i+k-1 < len; i++) { //cout << num[x][i+k-1] << " " << num[x][i] << endl; if(num[x][i+k-1] - num[x][i] < d) { return 1; } } return 0; } int main() { scanf("%d %d %d", &n, &d, &k); for(int i = 0; i < n; i++) { int ts, id; scanf("%d %d", &ts, &id); num[id].push_back(ts); } for(int i = 0; i < maxn; i++) { if(judge(i)) { printf("%d\n", i); } } } /* 7 10 2 0 1 0 10 10 10 10 1 9 1 100 3 100 3 */
题目九:
题解:很简的一个dfs,就不再写了 代码
先是根据dfs和vis统计岛屿数量,然后根据每个海域的上下左右四个方向均为非岛屿变化,即侵蚀过程,最后再统计一遍岛屿数量,两次记录相减即可。
忽然发现似乎自己这个问题漏掉了一个特殊点,存在有一个岛屿变成两个岛屿的特殊情况要考虑。
题目十: