Editorial of Global Round 15 D Array Differentiation

Editorial of Global Round 15 D Array Differentiation
因为n比较小,我们可以考虑时间复杂度较大的算法,我们可以构造一个环(假设环上有m个点),环上的点满足 s 1 a 1 + s 2 a 2 + s 3 a 3 + . . . + s m a m = 0 s_1a_1 + s_2a_2 + s_3a_3 + ... + s_ma_m = 0 s1​a1​+s2​a2​+s3​a3​+...+sm​am​=0 (s是选的符号),我们可以枚举环的长度并枚举s可能的情况,只要有一组环的和为0,即可构造。

#include <cstdio>
#include <iostream>
#include <cstring>
int T,n,a[15];
void solve(){
    memset(a,0,sizeof(a));
    scanf("%d",&n);
    int sum = 0,m = 1;
    for(int i = 1;i <= n;i++){
        scanf("%d",&a[i]);
        m *= 3;
    }
    for(int i = 1;i < m;i++){
        int k = i;
        sum = 0;
        for(int i = 1;i <= n;i++){
            int s = k % 3;
            k /= 3;
            if(s == 2)s = -1;
            sum += s * a[i];
        }
        if(sum == 0){
            puts("YES");
            return;
        }
    }
    puts("NO");
}
int main(int argc,char *argv[]){
    scanf("%d",&T);
    while(T--)solve();
    return 0;
}
上一篇:Mybatis的基础学习01


下一篇:NOIP2021模拟训练31