题解：P10295 [CCC 2024 S1] Hat Circle

__galaxy_1202__ · 2024-04-02 19:26:02 · 题解

题目大意：

输入 n 个数，将其围成圈，求对面的数的值是否等于其对面的数，统计其个数。

解题思路：

首先，先不要用圆的视角来看这道题，这样可能会把问题想复杂。我们把头转过来，根据样例 1 列出下表：

可以发现转过来以后，这个图可以转为方阵，只要判断对角线是否相等就好啦。不过考虑到输入顺序，这个问题还能简化，如下：

根据输入顺序填表，就可以直接上下对应，让问题更加简单！

代码实现：

代码方面就按照上面的思路实现，注意以下几点。

• 注意数据范围，直接开二维数组会爆！所以要动动脑，用一维数组即可。
• 由于条件成立一次就会有 2 个小朋友互相看到对方并知道与自己数字相同，所以每次要 cnt \gets cnt + 2 。

其它详见代码（与注释）：

#include <iostream>
using namespace std;
int n, a[1000001], l, r, mid, cnt;
int main()
{
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> a[i];
    mid = n / 2, l = 1, r = mid + 1;//mid是为了仿照二维数组所定义的中间值，l与r是两个区间，可以把mid省去，在r变量赋值时写清楚，但这样更易理解。
    while (r <= n)
    {
        if (a[l] == a[r]) cnt += 2;//注意事项之一，cnt+=2!
        l++, r++;//更新区间别忘了！
    }
    cout << cnt;
    return 0;
}