8.13日测试内容
T1：P1571 眼红的Medusa
题目传送门
一遍过
实现方法
用
陈老师二分函数，找到陈老师目标数字再按照科技创新奖的顺序输出
\(AC\) \(Code:\)
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5 + 7;
int a[maxn], b[maxn];
int n, m;
int chenlaoshi(int x)
{
int l = 1 - 1;
int r = m + 1;
b[l] = INT_MIN;
b[r] = INT_MAX;
while (l + 1 < r)
{
int mid = (l + r) / 2;
if (b[mid] < x)
{
l = mid;
}
if (b[mid] > x)
{
r = mid;
}
if (b[mid] == x)
{
return mid;
}
}
return -1;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin >> n >> m;
for (int i = 1; i <= n; ++i)
{
cin >> a[i];
}
for (int i = 1; i <= m; ++i)
{
cin >> b[i];
}
sort(b + 1, b + 1 + m);
for (int i = 1; i <= n; ++i)
{
if (chenlaoshi(a[i]) != -1)
{
cout << a[i] << ' ';
}
}
return 0;
}
T2：P2249 【深基13.例1】查找
题目传送门
\(Wrong\) \(Code:\)
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e6 + 7;
int a[maxn];
int n;
int chenlaoshi(int x)
{
int l = 1 - 1;
int r = n + 1;
a[0] = -1e9;
a[n + 1] = 1e9;
while (l + 1 < r)
{
int mid = (l + r) / 2;
if (a[mid] > x)
{
r = mid;
}
if (a[mid] < x)
{
l = mid;
}
if (a[mid] == x)
{
r = mid;
}
}
if (a[r] == x)
{
return r;
}
return -1;
}
int main()
{
cin >> n;
int m;
cin >> m;
for (int i = 1; i <= n; i++)
{
cin >> a[i];
}
while (m--)
{
int x;
cin >> x;
cout << chenlaoshi(x) << ' ';
}
return 0;
}
错误原因
数组开小了
错误信息：
Runtime Error.
Received signal 11:
Segmentation fault with invalid memory reference.
翻译过来就是：
运行时错误。
接收到的信号11：
分段故障，内存引用无效。
这不就是数组开小了吗 (^_^^^)
\(AC\) \(Code:\)
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e6 + 7;
int a[maxn];
int n;
int chenlaoshi(int x)
{
int l = 1 - 1;
int r = n + 1;
a[0] = -1e9;
a[n + 1] = 1e9;
while (l + 1 < r)
{
int mid = (l + r) / 2;
if (a[mid] > x)
{
r = mid;
}
if (a[mid] < x)
{
l = mid;
}
if (a[mid] == x)
{
r = mid;
}
}
if (a[r] == x)
{
return r;
}
return -1;
}
int main()
{
cin >> n;
int m;
cin >> m;
for (int i = 1; i <= n; i++)
{
cin >> a[i];
}
while (m--)
{
int x;
cin >> x;
cout << chenlaoshi(x) << ' ';
}
return 0;
}
T3：P1678 烦恼的高考志愿
题目传送门
不会做 前世记忆忘了
实现方法
- 用
lower_bound找最接近的答案- \(But\) 答案可能在左边也可能在右边
- \(So\) 两个做差值
- 如果是左侧边界，只有一个答案，右侧边界也只有一个答案。
\(AC\) \(Code:\)
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5 + 7;
int a[maxn];
int b[maxn];
int m, n;
int main()
{
cin >> m >> n;
for (int i = 1; i <= m; ++i)
{
cin >> a[i];
}
sort(a + 1, a + 1 + m);
long long sum = 0;
for (int i = 1; i <= n; ++i)
{
cin >> b[i];
int pos = lower_bound(a + 1, a + 1 + m, b[i]) - a;
if (pos == m + 1)
{
sum += abs(b[i] - a[m]);
continue;
}
if (pos == 1)
{
sum += abs(b[i] - a[1]);
continue;
}
if (abs(b[i] - a[pos]) < abs(b[i] - a[pos - 1]))
{
sum += abs(b[i] - a[pos]);
}
else
{
sum += abs(b[i] - a[pos - 1]);
}
}
cout << sum << "\n";
return 0;
}
T4：P1918 保龄球
题目传送门
一遍过
实现方法
定义一个
Balls类型的结构体数组输入每一个球道的球数，每一个球道的
id\(=\)i用
sort把a数组排序再输入每一个要找的瓶子数
用陈老师函数查找对应的瓶子数量是否存在
\(AC\) \(Code:\)
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5 + 7;
struct balls
{
int id;
int x;
};
bool cmp(balls a, balls b)
{
return a.x < b.x;
}
balls a[maxn];
int n;
int chenlaoshi(int x)
{
int l = 1 - 1;
int r = n + 1;
a[l].x = INT_MIN;
a[r].x = INT_MAX;
while (l + 1 < r)
{
int mid = (l + r) / 2;
if (a[mid].x > x)
{
r = mid;
}
if (a[mid].x < x)
{
l = mid;
}
if (a[mid].x == x)
{
return a[mid].id;
}
}
return 0;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin >> n;
for (int i = 1; i <= n; ++i)
{
cin >> a[i].x;
a[i].id = i;
}
sort(a + 1, a + 1 + n, cmp);
int m;
cin >> m;
for (int i = 1; i <= m; ++i)
{
int op;
cin >> op;
cout << chenlaoshi(op) << "\n";
}
return 0;
}
T5：P1102 A-B 数对
题目传送门
第一次不记得了，用的暴力，居然拿了 \(76\) 分 (奇迹)！！！
\(Wrong\) \(Code:\)
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5 + 7;
int a[maxn];
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int n, c;
cin >> n >> c;
for (int i = 1; i <= n; ++i)
{
cin >> a[i];
}
int ans = 0;
for (int i = 1; i <= n; ++i)
{
for (int j = 1; j <= n; ++j)
{
if (a[i] - a[j] == c)
{
ans++;
}
}
}
cout << ans << "\n";
return 0;
}
实现方法
lower_bound和upper_bound的另外一个作用就是直接获取相等的个数
lower_bound找到相等的第一个位置 \(l\)
upper_bound找到不相等的第一个位置那么相等的最后一个位置 $r = $
upper_bound\(-1\)相等的个数就是 \(r - l + 1\)。
\(AC\) \(Code:\)
#include <bits/stdc++.h>
using namespace std;
const int maxn = 2e5 + 7;
int a[maxn];
int n, c;
int main()
{
cin >> n >> c;
for (int i = 1; i <= n; ++i)
{
cin >> a[i];
}
sort(a + 1, a + 1 + n);
long long cnt = 0;
for (int i = 1; i <= n; ++i)
{
int b = a[i] - c;
int geshu = upper_bound(a + 1, a + 1 + n, b) - lower_bound(a + 1, a + 1 + n, b);
cnt += geshu;
}
cout << cnt;
return 0;
}
T6：B3799 [NICA #1] 序列
题目传送门
看到题后：
眼睛：我会了
脑子：不，你不会
引用一下陈老师的AC代码 \(↓\)
\(AC\) \(Code:\)
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int maxn = 5e5 + 7;
int a[maxn];
int sum[maxn];
int n, m;
signed main()
{
cin >> n >> m;
for (int i = 1; i <= n; ++i)
{
cin >> a[i];
}
sort(a + 1, a + 1 + n);
for (int i = 1; i <= n; ++i)
{
sum[i] = sum[i - 1] + a[i];
}
int num = 0;
while (m--)
{
int op;
cin >> op;
if (op == 1)
{
int k;
cin >> k;
num += k;
}
else
{
int pos = lower_bound(a + 1, a + 1 + n, -num) - a;
int l = pos;
int r = n;
cout << (sum[r] - sum[l - 1]) + (r - l + 1) * num << "\n";
}
}
return 0;
}