【洛谷P9975奶牛被病毒传染最少数量推导,导出多样例】2025-2-26

Source

缘由洛谷P9975 76(WA)_数据结构与算法-CSDN问答

是特征定性分析,分析未传染的数据量较少,如:010、10(首)、01(尾)、0110都为未传染的判定;
若连续数量为奇数则最少为1,若连续数量为偶数则最少为2;
计算所有被传染数量,计算最少的传染量,以判定的是否传染选择输出所有或最少。 

void 奶牛被病毒传染最少数量推导()
{
	std::string a, b; bool k = 1;
	int n = 0, j = 0, x = 0, y = 0, t = 0;
	std::cin >> n >> a;//6 011101//5 11111//6 011110//4 0110
js:if (x < n)
{
	   if (a[x] == '1')
		   ++j, ++y;
	   else
	   {
		   if (x == 0 && y == 1 || x && y == 2)
			   k = 0;
		   if(y)
			   t += (y % 2 ? 1 : 2), y = 0;
	   }
	   ++x;
	   goto js;
}
   if (y == 1)k = 0;
   else if (j && y == j)t += (y % 2 ? 1 : 2);
   std::cout << (k ? t : j) << "\n";
}