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

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

A small confusion in a problem set may ruin the whole contest. So most of the problem setters trytheir best to remove any kind of ambiguity from the set. But sometimes it is not that important. Forexample the mock of last contest. As it was mock contest so we were not that serious with the set. Weprinted two problems, problem A in Page 1 and Problem B in Page 2. Then we remembered we haveto give rule of the contest too. So we printed the rule page. But we did not notice that the rule pagewas printed with Page 2. We were stapling 3 pages together. First rule page, then Problem A and atthe last Problem B. So page numbers were, 2, 1 and 2. This looked odd. But we already printed all thepages and if we want to fix the issue we had no other way but print all the three pages. One amongus suggested an explanation — “Well, first 2 means there are 2 pages after this page. 1 also meansthere is 1 page after this page. But the last 2 means there are 2 pages before this page.” Interestingobservation indeed. So we came up with a rule which is, page numberings of all the n pages are valid,if the page number at a page denotes number of pages before this page or number of page after thispage.

So with this rule, {3, 1, 2, 0} is valid but {3, 3, 1, 3} is not valid.

Input

First line of the input file contains number of tests cases T (< 60).

Then T test cases follow. First line of each test case contains a positive number n (≤ 104) numberof pages in the problem set. Then there are n space separated numbers in the following line each ofwhich ranges from 0 to 10^6.

Output

For each test case output the test case number. Then output ‘yes’ (without the quotes) if the pagescan be shuffled somehow so that the pages numbering is valid. Otherwise output ‘no’.

For the exact format of the output please follow the sample.

Explanation of the samples:

1. The pages can be shuffled in several ways so that the page numbering is valid. One of the validshuffles are 3, 1, 2, 0.

2. There is no valid way to shuffle these.

Sample Input

0 3 1 2

1 3 3 3

Sample Output

Case 1: yes

Case 2: no

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 <iostream>
#include <cstdio>
#include <cstring>
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: no\n", ++kase); continue;}

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

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

Thank you!

------from ProLights

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

相关推荐