第一题：
给定n条直线（参数k，b，即y = k*x+b），求为t（t>=2)条直线的交点数量，依次输出2直线交点数量、3直线交点数量。。。n直线交点数量
限制，直线k,b为满足0<=k<=100,0<=b<=100的非负整数，n<=1e5.
方法：遍历整数交点
long num[201][10011] = { 0 };
int main()
{
int N;
cin >> N;
int k, b;
memset(num, 0, sizeof(num));
for (int i = 0; i < N; ++i) {
cin >> k >> b;
int x = 0;
while (k*x + b < 10001 && x < 201) {
num[x++][k*x + b]++;
}
}
vector<long>res(N - 1);
for (int i = 0; i < 201; ++i) {
for (int j = 0; j < 10001; ++j) {
int p = num[i][j];
if (p > 1) {
res[p - 2]++;
}
}
}
for (auto i : res)
cout << i << ' ';
cout << endl;
return 0;
}
第二题： 简略版合成大西瓜
给定n个数，依次放入，每次只能放左或放右，当单边出现相同数字时，分数+1，消除其中一个数字，求最大得分
方法：双指针+哈希
int main()
{
int N;
cin >> N;
vector<int>data;
int front = -1, cur = 0, res = 0;
for (int i = 0; i < N; ++i) {
cin >> cur;
if (cur == front)
res++;
else {
front = cur;
data.push_back(cur);
}
}
int left = data[0];
unordered_set<int>room;
room.insert(data[0]);
int l = 0, r = 1;
while (r < data.size()) {
while (r < data.size() && room.count(data[r]) == 0)
room.insert(data[r++]);
if (r == data.size())
break;
res++;
while (l + 1< r) {
room.erase(data[l]);
l++;
}
room.insert(data[r++]);
}
cout << res << endl;
return 0;
}
全部评论
(1) 回帖