70分求条。

问题讨论区 普及段
1

小信开了一家工厂，工厂中有

n条流水线和相同数量的对应仓库。为了让多条生产线的产品可以流入同一个仓库，小信在相邻流水线之间增加了机械臂，可以将货物从一条生产线转移到另一条。

显然，根据机械臂位置的不同，每个仓库都将接收到多个不同流水线的产品。现给定传送带的数量和机械臂的位置，问每个仓库能接受来自多少条流水线的产品。
第一行输出两个整数
n,m，表示流水线数量和机械臂数量，所有传送带从
x=0开始，延伸到
x=100000。
接下来
m行，每行包含两个整数xi(0<xi<100000),yi(1<=yi<n);表示第
i
i个机械臂的位置，其中xi
是机械臂在x轴上的位置，该机械臂可以在
x=xi;
位置抓取
y
i
或者
yi+1
号流水线上的产品，并转移到相邻流水线。
输出格式
输出一行

n个用空格分隔的整数。第

i个整数表示连接到第

i条流水线的仓库能接收来自多少条不同流水线的货物。

#include<bits/stdc++.h>
using namespace std;
long long n,m,b[200000+20];
vector<int>st[200000+20];
void dfs(int j,int k,vector<int> q){
	b[j]++;
	int f=0,f1=0;
	for(auto t:q){
		if(t==j-1){
			f=1;
		}
		if(t==j+1){
			f1=1;
		}
	}
	q.push_back(j);
	if(j-1>=1&&f==0){
		for(auto t : st[j-1]){
			if(t>=k){
				dfs(j-1,t,q);
				break;
			}
		}
	}
	if(j+1<=n&&f1==0){
		for(auto t:st[j]){
			if(t>=k){
				dfs(j+1,t,q);
				break;
			}
		}
	}
}
int main(){
	cin>>n>>m;
	for(int i=1;i<=m;i++){
		int x,y;
		cin>>x>>y;
		st[y].push_back(x);
	}
	for(int i=1;i<=n;i++){
		sort(st[i].begin(),st[i].end());
	}
	for(int i=1;i<=n;i++){
		vector<int>s;
		dfs(i,0,s);
	}
	for(int i=1;i<=n;i++){
		cout<<b[i]<<" ";
	}
	return 0;
}
1 个赞
2

失踪人口回归！

2 个赞
3

思路的问题
正解思路：
用N个set来存储每条生产线能运输到的物品的原传送带编号
set[i]这个集合里存的是这个传送带能够拿到的物品的原传送带编号
我们先把所有机械臂按位置升序排序，先把set<int> st[N]的st[i].insert(i)，因为本来就可以拿到自己传送带的物品
接着枚举每一个机械臂，把两个传送带的集合合并（其实就是各把自身的元素insert到对方的集合中）
最后枚举每一个传送带，输出集合的size即可

2 个赞
4

伪代码：

struct node {
	int x, y;
	//x代表位置，y代表在两个之间
} a[];
set <int> st[];
//st[i]中的所有元素都是第i个传送带能够接收到的物品的原传送带编号
bool cmp(node c, node d) {
	________//按照位置给机械臂升序排序
}
int main() {
	______//输入
	______//对机械臂进行排序
	for (int i = 1 ; i <= n ; i++) {
		st[i].insert(i);//把每个传送带原来就有的标好计入
	}
	for (int i = 1 ; i <= m ; i++) { //枚举每一个机械臂，进行交换工作
		for (auto it : st[a[i].y]) {
			st[a[i].y + 1].insert(it);
		}
		for (auto it : st[a[i].y + 1]) {
			st[a[i].y].insert(it);
		}
		//各把自己的物品计入对方的集合中
	}
	for (int i = 1; i <= n ; i++) {
		______//输出st[i].size()
	}
	//完结散花ヾ(•ω•`)oヾ(•ω•`)oヾ(•ω•`)o
	return 0;
}

求解决方案

2 个赞
5

@陈洪森 @陈洪森 @陈洪森 在吗？

2 个赞
6

陈洪森：不在

1 个赞
7

帮我叫一下他呗

1 个赞
8

咋了