第十五届北京师范大学程序设计竞赛决赛 D. Disdain Chain【思维】

　

disdain

D. Disdain Chain

Time limit: 2000ms

Memory Limit: 262144KB

64-bit integer IO format: %lld      java class name: Main

Submit Status PID: 52503

BNU ACM校队现在有名队员，对于任意两名队员和，要么鄙视，要么鄙视，需要注意的是鄙视关系并不满足传递性，即使鄙视、鄙视，也并不意味着一定有鄙视。小Q同学认为，如果有名不同的队员满足鄙视、鄙视、……、鄙视，那么这就是一条长度为的鄙视链。显然鄙视链越长越不利于团队建设，小Q同学希望你帮他分别算一算有多少种个人之间的鄙视关系满足最长的鄙视链的长度是。

Input

第一行是一个正整数，表示测试数据的组数，

每组测试数据包含一行，只有一个整数，表示校队的人数。

Output

对于每组测试数据，输出行，第行表示最长鄙视链是的鄙视关系的个数。

Sample Input

1
2

Sample Output

0
2

Hint

对于样例，在队伍只有名队员的情况下，无论谁鄙视谁，最长鄙视链的长度都是。

手写几组样例不难发现，因为图是完全图，所以无论怎样设定边的方向，其方案中，最短的最长鄙视链的长度也不会小于N（只会等于N），那么结果显而易见，就是2^(n*(n-1)/2);

Ac代码：

#include<stdio.h>
#include<string.h>
using namespace std;
int main()
{
    int t;
    scanf("%d",&t);
    while(t--)
    {
        int n;
        scanf("%d",&n);
        int bian=n*(n-1)/2;
        int ans=1;
        for(int i=1;i<=bian;i++)
        {
            ans*=2;
        }
        for(int i=1;i<=n-1;i++)printf("0\n");
        printf("%d\n",ans);
    }
}

相关阅读