[SHOI2013]发微博

题目描述

刚开通的 SH 微博共有 \(n\) 个用户（\(1\sim n\) 标号），在这短短一个月的时间内，用户们活动频繁，共有 \(m\) 条按时间顺序的记录：

! x 表示用户 x 发了一条微博；

+ x y 表示用户 x 和用户 y 成为了好友

− x y 表示用户 x 和用户 y 解除了好友关系

当一个用户发微博的时候，所有他的好友（直接关系）都会看到他的消息。

假设最开始所有人之间都不是好友关系，记录也都是合法的（即 + x y 时 \(x\) 和 \(y\) 一定不是好友，而 − x y 时 \(x\) 和 \(y\) 一定是好友）。

问这 \(m\) 条记录发生之后，每个用户分别看到了多少条消息。

输入格式

第 \(1\) 行两个整数 \(n\), \(m\)。

接下来 \(m\) 行，按时间顺序读入 \(m\) 条记录，每条记录的格式如题目所述，用空格隔开。

输出格式

输出一行 \(n\) 个用空格隔开的数（行末无空格），第 \(i\) 个数表示用户 \(i\) 最后看到了几条消息。

样例 #1

样例输入 #1

样例输出 #1

1 1

提示

对于 \(100\%\) 的数据，\(n\leq 200000\), \(m\leq 500000\)

\(50pts\)

最好想的一种做法。

开一个逻辑型二维数组\(frd[N][N]\)来储存好友关系，若\(x\)加\(y\)为好友，则令\(frd[x][y]=1,frd[y][x]=1\)。反之，若解除\(x\)与\(y\)之间的好友关系，则令\(frd[x][y]=0,frd[y][x]=0\)。

当\(x\)发微博时，遍历\(i~n\)，若\(frd[x][i]==1\)，则说明\(x\)与\(i\)存在好友关系，\(i\)看到的微博数\(+1\)。

代码

#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

#pragma comment(linker,"/STACK:102400000,102400000")

using namespace std;

const int N=15005;

int n,m,att[N];

bool frd[N][N];

int main()

{

	scanf("%d%d",&n,&m);

	for(int i=1;i<=m;i++)

	{

		int x,y;

		char op[2];

		scanf("%s",op);

		if(op[0]=='!')

		{

			scanf("%d",&x);

			for(int i=1;i<=n;i++)

				if(frd[x][i])

					att[i]++;

		}

		else if(op[0]=='+')

		{

			scanf("%d%d",&x,&y);

			frd[x][y]=1;

			frd[y][x]=1;

		}

		else if(op[0]=='-')

		{

			scanf("%d%d",&x,&y);

			frd[x][y]=0;

			frd[y][x]=0;

		}

	}

	for(int i=1;i<=n;i++)

	{

		if(i==n) printf("%d",att[i]);

		else printf("%d ",att[i]);

	}

	return 0;

}

缺点很明显，首先因为使用了二维数组，导致空间不够开；其次时间复杂度\(O(n*m)\)，丑。

\(100pts\)

\(O(nlogn)\)

吸取了\(50pts\)算法中空间不够开的教训，我们考虑使用STL，声明 \(set<int> s[200005]\)成功开出想要的数量，\(set[x]\)用于储存\(x\)的朋友圈。

（对set不熟悉的同学看看这篇)

接下来考虑如何给答案作出贡献。

举个具象化的例子。在甲乙交友之前，甲统共发布了3篇微博，乙统共发布了5篇微博；甲乙分手时，甲统共发布了6篇微博，乙统共发布了7篇微博。那么，甲看到乙发的微博为\(7-5=2(篇)\)，乙看到甲发的微博为\(6-3=3(篇)\)。由此可推出结论：

从甲乙成为好友，一直到甲乙分手，甲对乙产生的总贡献一共是

分手时甲的微博数-成为好友时甲的微博数

那么我们就可以用一个数组\(cnt[x]\)来储存目前\(x\)发布的微博数，这个处理无法离线。

对于添加好友：两人各自的微博浏览数减去彼此的目前微博数

对于解除好友：两人各自的微博浏览数加上彼此的目前微博数

由此可见，在解除好友时才会对答案作出贡献。所以最后需要把余下的好友关系进行名义上的解除，以统计截至最后一个时刻的答案。

代码

#include<iostream>

#include<cstdio>

#include<algorithm>

#include<cstring>

#include<set>

using namespace std;

const int N=200005;

int n,m;

int cnt[N],att[N];

set<int> s[N];

set<int>::iterator it;

int main()

{

	scanf("%d%d",&n,&m);

	for(int i=1;i<=m;i++)

	{

		char op[2];

		int x,y;

		scanf("%s",op);

		if(op[0]=='!')

		{

			scanf("%d",&x);

			cnt[x]++;

		}

		else if(op[0]=='+')

		{

			scanf("%d%d",&x,&y);

			att[x]-=cnt[y];

			att[y]-=cnt[x];

			s[x].insert(y);

			s[y].insert(x);

		}

		else if(op[0]=='-')

		{

			scanf("%d%d",&x,&y);

			att[x]+=cnt[y];

			att[y]+=cnt[x];

			s[x].erase(y);

			s[y].erase(x);

		}

	}

	for(int i=1;i<=n;i++)

		for(it=s[i].begin();it!=s[i].end();it++)

			att[i]+=cnt[*it];

	for(int i=1;i<=n;i++)

	{

		if(i==n) printf("%d",att[i]);

		else printf("%d ",att[i]);

	}

	return 0;

}

\(100pts\)

\(O(n)\)

我们可不可以不用\(set\)或是其它二维结构？

我们需要\(set\)来做什么？需要用它来记录每个人的朋友圈。

\(set\)实际上做了什么？可以看到，在第一遍处理输入时，\(set\)的工作只有插入和擦去，真正发挥的作用只有在最后时刻解除好友关系。

为什么需要用\(set\)来解除好友关系？因为最后时刻有余下的好友。

有没有办法使最后没有余下的好友？有，我们可以记录每次操作再倒序处理，这时最后状态就变成了最初状态：即没有任何好友关系的状态。

代码

#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

#pragma comment(linker,"/STACK:102400000,102400000")

using namespace std;

const int N=200005;

const int M=500005;

int n,m,att[N],cnt[N];

int frd[M][2];

char op[M][2];

int main()

{

	freopen("sina.in","r",stdin);

	freopen("sina.out","w",stdout);

	scanf("%d%d",&n,&m);

	for(int i=1;i<=m;i++)

	{

		int x,y;

		scanf("%s",op[i]);

		if(op[i][0]=='!')

		{

			scanf("%d",&frd[i][0]);

		}

		else if(op[i][0]=='+')

		{

			scanf("%d%d",&frd[i][0],&frd[i][1]);

		}

		else if(op[i][0]=='-')

		{

			scanf("%d%d",&frd[i][0],&frd[i][1]);

		}

	}

	for(int i=m;i>=1;i--)

	{

		if(op[i][0]=='!')

		{

			cnt[frd[i][0]]++;

		}

		else if(op[i][0]=='+')

		{

			att[frd[i][0]]+=cnt[frd[i][1]];

			att[frd[i][1]]+=cnt[frd[i][0]];

		}

		else if(op[i][0]=='-')

		{

			att[frd[i][0]]-=cnt[frd[i][1]];

			att[frd[i][1]]-=cnt[frd[i][0]];

		}

	}

	for(int i=1;i<=n;i++)

	{

		if(i==n) printf("%d",att[i]);

		else printf("%d ",att[i]);

	}

	return 0;

}

参考

巴特西

P3998 [SHOI2013]发微博方法记录

[SHOI2013]发微博

题目描述

输入格式

输出格式

样例 #1

样例输入 #1

样例输出 #1

提示

\(50pts\)

\(100pts\)

\(O(nlogn)\)

\(100pts\)

\(O(n)\)

我们可不可以不用\(set\)或是其它二维结构？

最新文章

热门文章

巴特西

P3998 [SHOI2013]发微博 方法记录

[SHOI2013]发微博

题目描述

输入格式

输出格式

样例 #1

样例输入 #1

样例输出 #1

提示

\(50pts\)

\(100pts\)

\(O(nlogn)\)

\(100pts\)

\(O(n)\)

我们可不可以不用\(set\)或是其它二维结构？

最新文章

热门文章

P3998 [SHOI2013]发微博方法记录