列表

详情


NC13815. Disdain Chain

描述

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

输入描述

第一行是一个正整数T(≤ 6),表示测试数据的组数, 每组测试数据包含一行,只有一个整数n(2 ≤ n ≤ 7),表示校队的人数。

输出描述

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

示例1

输入:

1
2

输出:

0
2

说明:

在队伍只有2名队员的情况下,无论谁鄙视谁,最长鄙视链的长度都是2。

原站题解

上次编辑到这里,代码来自缓存 点击恢复默认模板

C 解法, 执行用时: 2ms, 内存消耗: 304K, 提交时间: 2022-03-27 15:37:01

#include<stdio.h>
int main()
{
    int i,n,T;
scanf("%d",&T);
while(T--)
{
    scanf("%d",&n);
    for(i=0;i<n;i++)
    if(i<n-1)printf("0\n");
    else printf("%d\n",1<<n*(n-1)/2);
}
return 0;
}

C++ 解法, 执行用时: 3ms, 内存消耗: 272K, 提交时间: 2022-07-15 14:59:26

#include <cstdio>
using namespace std;
int main(){
	int T,n;
	scanf("%d",&T);
	while(T--){
		scanf("%d",&n);
		for(int i=1;i<n;i++) printf("0\n");
		printf("%d\n",1<<(n*(n-1)/2));
	}
}

Python3 解法, 执行用时: 38ms, 内存消耗: 4472K, 提交时间: 2022-04-30 20:43:34

t=int(input())
g=[]
for i in range(t):
    g.append(int(input()))
for j in range(t):
    y=g[j]*(g[j]-1)//2
    for k in range(g[j]-1):
            print("0")
    print(2**y)

pypy3 解法, 执行用时: 80ms, 内存消耗: 25748K, 提交时间: 2022-02-09 14:28:33

def read()->int:
    return int(input())
T=read()
for i in range(T):
    n=read()
    k=n*(n-1)//2
    for j in range(n-1):
        print('0')
    print(2**k)

Python(2.7.3) 解法, 执行用时: 20ms, 内存消耗: 2828K, 提交时间: 2017-09-07 13:04:06

for i in range(input()):
	n = input()
	for i in range(n-1): print 0
	print 1<<(n*(n-1)/2)

上一题