我得到了一个nxn网格，其中填充有1或0。我想计算转角瓦片均为1的子网格的数量。我的解决方案遍历所有行对并计算匹配的1的数量，然后使用公式numOf1s *（numOf1s-1）/ 2并将其添加到结果中。但是，当我在https://cses.fi/problemset/task/2137上提交解决方案时，n = 3000（可能是由某些错误引起）的输入上没有输出。错误可能是什么？
int main()
{
int n; cin>> n;
vector<bitset<3000>> grid(n);
for(int i=0;i<n;i++){
cin >> grid[i];
}
long result = 0;
for(int i=0;i<n-1;i++){
for(int j=i+1;j<n;j++){
int count = (grid[i]&grid[j]).count();
result += (count*(count-1))/2;
}
}
cout << result;
}
此解决方案将导致超过时间限制。最坏的情况下bitset :: count（）为O（n）。您的代码的总复杂度为O（n ^ 3）。在最坏的情况下，操作数将为3000 ^ 3> 10 ^ 10，这太大了。
本文收集自互联网，转载请注明来源。
如有侵权，请联系[email protected] 删除。
我来说两句