链接:https://ac.nowcoder.com/acm/contest/61132/G 来源:牛客网 给定一个长度为n的01串,你需要选择一段任意长度(可以为0)的区间对其翻转,翻转后,求最长的一段连续的全是1的区间的长度。 输入描述: 输入共2行。 第一行一个整数n(1\leq n \leq 10^6)n(1≤n≤10 6 )。 第二行一个长度为n的01序列。 输出描述: 输出一个整数,表示最长的长度。 示例1 输入 复制 10 0111001011 输出 复制 5 说明 翻转区间[5,10],翻转为0111110100。
时间: 2024-04-12 18:34:23 浏览: 26
题目要求我们在一个长度为n的01串中选择一段任意长度的区间进行翻转,然后求翻转后最长的连续全为1的区间的长度。
我们可以使用一个变量count来记录当前连续全为1的区间的长度,使用一个变量maxCount来记录翻转后最长的连续全为1的区间的长度。
遍历整个01串,当遇到1时,count加1;当遇到0时,更新maxCount为count和maxCount的较大值,并将count重置为0。
最后返回maxCount即为所求的结果。
以下是示例代码实现:
```cpp
#include <iostream>
#include <string>
using namespace std;
int main() {
int n;
string s;
cin >> n >> s;
int count = 0;
int maxCount = 0;
for (int i = 0; i < n; i++) {
if (s[i] == '1') {
count++;
} else {
maxCount = max(count, maxCount);
count = 0;
}
}
maxCount = max(count, maxCount);
cout << maxCount << endl;
return 0;
}
```
希望能帮助到你!如果还有其他问题,请继续提问。
相关问题
链接:https://ac.nowcoder.com/acm/contest/61132/G 来源:牛客网 给定一个长度为n的01串,你需要选择一段任意长度(可以为0)的区间对其翻转,翻转后,求最长的一段连续的全是1的区间的长度。c++生成
以下是使用C++编写的解决方案:
```cpp
#include <iostream>
#include <vector>
int max_ones(std::vector<int>& nums) {
int n = nums.size();
std::vector<int> dp(n, 0); // dp数组记录以当前位置结尾的最长连续1的长度
int max_len = 0; // 最长连续1的长度
for (int i = 0; i < n; i++) {
if (nums[i] == 1) {
dp[i] = (i > 0) ? dp[i-1] + 1 : 1; // 当前位置是1,更新dp数组
} else {
dp[i] = 0; // 当前位置是0,重置dp数组
}
max_len = std::max(max_len, dp[i]); // 更新最长连续1的长度
}
return max_len;
}
int main() {
int n; // 01串的长度
std::vector<int> nums;
std::cin >> n;
for (int i = 0; i < n; i++) {
int num;
std::cin >> num;
nums.push_back(num);
}
int result = max_ones(nums);
std::cout << result << std::endl;
return 0;
}
```
请将上述代码保存为一个.cpp文件,然后使用C++编译器进行编译运行。在运行时,首先输入01串的长度n,然后依次输入n个数字,每个数字代表对应位置的元素(0或1)。
注意:上述代码是根据题目描述编写的,但在实际使用中,应该添加输入数据的验证和错误处理机制。
链接:https://ac.nowcoder.com/acm/contest/59840/K 来源:牛客网 给定 n 个坐标,求其中 3 个坐标能表示一个等腰三角形的组数。 三点共线不算三角形,等边三角形为特殊的等腰三角形。
对于这道题,我们可以考虑对输入的每两个点求出它们的中点,然后把这个中点作为哈希表的键值,值为一个列表,存储所有能与该中点构成等腰三角形的点。具体做法如下:
1. 枚举每两个点,计算它们的中点,把该中点作为哈希表的键值,值为一个空列表。
2. 遍历所有点,如果该点与中点的距离等于某个已有中点的距离,则将该点加入到对应的列表中。
3. 对于每个中点对应的列表,如果列表长度大于等于2,则说明存在能与该中点构成等腰三角形的点,计算组合数并累加到答案中。
时间复杂度为 $O(n^2 \log n)$,其中 $n$ 为点的个数。具体实现细节可以参考下面的代码:
```python
from collections import defaultdict
import math
n = int(input())
points = []
for i in range(n):
x, y = map(int, input().split())
points.append((x, y))
# 计算两点之间的距离
def dist(p1, p2):
return math.sqrt((p1[0] - p2[0]) ** 2 + (p1[1] - p2[1]) ** 2)
# 构建哈希表
hash_map = defaultdict(list)
for i in range(n):
for j in range(i + 1, n):
p1, p2 = points[i], points[j]
mid = ((p1[0] + p2[0]) / 2, (p1[1] + p2[1]) / 2)
hash_map[mid] = []
# 遍历所有点
for i in range(n):
for j in range(i + 1, n):
p1, p2 = points[i], points[j]
mid = ((p1[0] + p2[0]) / 2, (p1[1] + p2[1]) / 2)
for k in range(n):
if k != i and k != j:
p3 = points[k]
d1, d2 = dist(p1, p3), dist(p2, p3)
if abs(d1 - d2) < 1e-6:
hash_map[mid].append(p3)
# 计算答案
ans = 0
for mid, points in hash_map.items():
if len(points) >= 2:
n = len(points)
ans += n * (n - 1) // 2
print(ans)
```
相关推荐
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)