列表

详情

NC214490. 母牛烃

描述

CSHwang合成了一种有机物,名为母牛烃.

他由一些特殊的碳原子构成,因为某种原因,这些碳原子的化学键有无数个.

最终这种物质有n个碳原子,主链长度是m.

这种物质的碳原子要么是在主链上,要么是直接和主链上的某个碳原子相连.(但是不会和主链的头尾的碳原子相连)

他们之间有n-1个碳-碳双键,因为某种原因,这些碳-碳双键的能量非常特殊

CSHwang有一种装置,可以给每一个碳原子设定一个势力值，每个碳原子的势力值各不相同且范围在[1,n]。

碳-碳双键的能量取决于它所连接的两个碳原子的势力值的差.

CSHwang,因为某种原因,想要让所有碳-碳双键上的能量都不相同.

他应该如何设定碳原子的势力值.

碳原子从1开始编号到n,按编号顺序输出一种可行的势力值设定方案。

输入描述

第一行读入n,m表示一共n个碳原子，主链长度为m。(2<=n<=10000,m<n)
接下来一行读入m个整数，表示主链上碳原子的编号。
接下来m行，每行读入一个整数数k(0<=k<=n-m)，表示有k个碳原子与当前主链上的碳原子直接相连以及这k个碳原子的编号。

输出描述

按编号顺序输出一种可行的势力值设定方案。

示例1

输入: 

11 5
1 2 3 4 5
0
1 6
2 7 8
3 9 10 11
0

输出: 

6 8 11 2 10 4 1 5 3 7 9

说明:

原站题解

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

C(clang11) 解法, 执行用时: 5ms, 内存消耗: 380K, 提交时间: 2020-12-24 22:02:07 

#include<stdio.h>
int n,m,i,j,k,b[10010],a[10010];
int main()
{
scanf("%d%d",&n,&m);
for(i=1;i<=m;i++){
    scanf("%d",&b[i]);
}
int f[2];
f[0]=1;f[1]=n;
int s=0;
int ans;
for(i=1;i<=m;i++){
    a[b[i]]=f[s];
    f[s]+=s?-1:1;
    scanf("%d",&k);
    if(k>0){
        for(j=1;j<=k;j++){
            scanf("%d",&ans);
            a[ans]=f[1-s];
            f[1-s]+=s?1:-1;
        }
    }
    s=1-s;
}
for(i=1;i<n;i++){
    printf("%d ",a[i]);
}printf("%d\n",a[n]);
 
return 0;
 }

C++(clang++11) 解法, 执行用时: 6ms, 内存消耗: 532K, 提交时间: 2020-12-06 23:24:10 

#include<stdio.h>
int n,m,i,j,k,b[10010],a[10010];
int main()
{
scanf("%d%d",&n,&m);
for(i=1;i<=m;i++){
	scanf("%d",&b[i]);
}
int f[2];
f[0]=1;f[1]=n;
int s=0;
int ans;
for(i=1;i<=m;i++){
	a[b[i]]=f[s];
	f[s]+=s?-1:1;
	scanf("%d",&k);
	if(k>0){
		for(j=1;j<=k;j++){
			scanf("%d",&ans);
			a[ans]=f[1-s];
			f[1-s]+=s?1:-1;
		}
	}
	s=1-s;
}
for(i=1;i<n;i++){
	printf("%d ",a[i]);
}printf("%d\n",a[n]);

return 0;
 }

上一题

© 2025 nowcoder.com