UVALive 5963 Confusion in the Problem Set 思维题、Interesting

UVALive 5963 Confusion in the Problem Set 思维题、Interesting

source

UESTC 2016 Summer Training #11 Div.2

UVALive 5963

My Solution

把输入的数字全转化为0 到 (n -1)/2

cnt[min(val, n - 1 - val)]++;

并记录

则如果符合条件则每个数出现2次， 比如2个1， 2个2，...

此外如果奇数则 则第 (n - 1)/2 + 1 也就是中间那个数对应的数字(n - 1)/2只出现一次， 如果偶数则 n/2 - 1 这个数出现2次。

复杂度 O(n)

#include 
#include 
#include 
using namespace std;
typedef long long LL;
const int maxn = 1e6 + 8;


int cnt[maxn], n;
bool flag;
/*果然TLE ⊙﹏⊙‖∣
void dfs(int k)
{
    if(k == n){
        flag = true;
        return;
    }
    if(flag) return;
    if(cnt[k] == 0 && cnt[n - 1 - k] == 0) return;
    if(cnt[k]) { cnt[k]--; dfs(k + 1); cnt[k]++;}
    if(cnt[n - 1 - k]) { cnt[n - 1 - k]--; dfs(k + 1); cnt[n - 1 - k]++;}

}
*/
int main()
{
    #ifdef LOCAL
    freopen("a.txt", "r", stdin);
    //freopen("b.txt", "w", stdout);
    #endif // LOCAL
    int T, val, kase = 0;
    scanf("%d", &T);
    while(T--){
        memset(cnt, 0, sizeof cnt);
        scanf("%d", &n);
        for(int i = 0; i < n; i++){
            scanf("%d", &val);
            cnt[min(val, n - 1 - val)]++;
        }
        flag = true;
        //dfs(0);

        for(int i = 0; i < (n - 1)/2; i++){
            if(cnt[i] != 2){flag = false; break; }
        }
        if(!flag) {printf("Case %d: non", ++kase); continue;}

        if(n&1 && cnt[(n - 1)/2] != 1) {printf("Case %d: non", ++kase); continue;}
        else if(!(n&1) && cnt[n/2 - 1] != 2) {printf("Case %d: non", ++kase); continue;}

        if(flag) printf("Case %d: yesn", ++kase);
    }
    return 0;
}

非特殊说明，本博所有文章均为博主原创，未经许可不得转载。

https://www.prolightsfxjh.com/

Thank you!

                                                                                                                                             ------from ProLightsfx