社区讨论

疑惑

P2058[NOIP 2016 普及组] 海港参与者 2已保存回复 3

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
3 条
当前快照
1 份
快照标识符
@mkjftkgc
此快照首次捕获于
2026/01/18 15:51
上个月
此快照最后确认于
2026/01/18 16:01
上个月
查看原帖
CPP
#include <bits/stdc++.h>
using namespace std;
int c[100005];
int n,cnt=0;
int k[100005],t[100005];
vector<int> a[100005];
int main(){
	scanf("%d",&n);
	for(int i=1;i<=n;i++){
		scanf("%d%d",&t[i],&k[i]);
		for(int j=1;j<=k[i];j++){
			int x;
			scanf("%d",&x);
			a[i].push_back(x);
		}
	}
	for(int i=0;i<k[1];i++){
		c[a[1][i]]++;
		if(c[a[1][i]]==1)cnt++;
	}
	printf("%d\n",cnt);
	int x=1;
	for(int i=2;i<=n;i++){
		for(int j=x;j<i;j++){
			if(t[j]+86400<=t[i]){
				x=j+1;
				for(int p=0;p<k[j];p++){
					c[a[j][p]]--;
					if(c[a[j][p]]==0)cnt--;
				}
			}else break;
		}
		for(int j=0;j<k[i];j++){
			c[a[i][j]]++;
			if(c[a[i][j]]==1)cnt++;
		}
		printf("%d\n",cnt);
	}
}
这代码时间复杂度不应该是 O(n2k)O(n^2k)吗,为什么过了

回复

3 条回复,欢迎继续交流。

正在加载回复...