CF2133A Redstone?题解

· · 题解

CF2133A Redstone?题解

分析

查看样例，注意到：有相同数值的组输出 YES，否则输出 NO。

证明

形式化题意：给出 a_1, a_2, a_3, \dots, a_n，f(1) = 1, f(2) = \frac{a_1}{a_2}, f(n) = \frac{a_{n - 1}}{a_n} \times f(n - 1)，问 f(n) 的值是否为 1？
我们展开一下：

\begin{aligned} f(n) &= \frac{a_{n - 1}}{a_n} \times f(n - 1) \\ &= \frac{a_{n - 1}}{a_n} \times \frac{a_{n - 2}}{a_{n - 1}} \times f(n - 2) \\ & \dots \\ &= \frac{a_{n - 1}}{a_n} \times \frac {a_{n - 2}}{a_{n - 1}} \times \dots \times \frac{a_1}{a_2} \\ &= \frac{a_1}{a_n} \end{aligned}

最后得出结论：f(n) = \frac{a_1}{a_n}。
所以只要给出的 a 数组中有至少 2 个相同的数即可。

代码

#include <bits/stdc++.h>

using namespace std;

int T;

void solve(){
    int n;
    cin >> n;
    vector <int> a(110, 0);
    bool f = 0;
    for(int i = 1, x; i <= n; i++){
        cin >> x;
        a[x]++;
        if(a[x] == 2)
            f = 1;
    }
    if(f)
        cout << "Yes\n";
    else
        cout << "No\n";
}

int main(){
    cin >> T;
    while(T--){
        solve();
    }
    return 0;
}