列表

详情

NC222341. 智乃酱的配电箱谜题

描述

智乃酱儿童节时想用一些彩色的灯泡装饰，现在她遇到了一些困难。

具体来讲，智乃酱有个开关，和个小灯泡。现在这个开关和灯泡中间通过一个配电箱的两排接线柱连接到一起，两排接线柱每排也是各个。

如上图所示，整个电路网络分为四行，第一行是一排开关。中间第二行和第三行是配电箱的中继接线柱，底部的第四行是小灯泡。

当开关被摁下时，将会向下层网络分别发送一次电信号。当中继接线柱收到一次电信号时，将会往下层相连的部分分别发送一次电信号。注意电信号只能向下传递，不会向上传递。最终达到底部时，如果某个灯泡接受到了偶数次电信号，那么它将保持原状态，否则它的亮灭状态会发生变化。


现在整个电路网络中，第一层到第二层，第三层到第四层的网络已经被给定。即开关到配电箱输入端的电路网络，配电箱输出端的电路网络已经给定。

智乃酱想要通过这个配电箱，最终达到第一个开关只控制第一个灯泡的亮灭，第二个开关只控制第二个灯泡的亮灭...以此类推。

智乃酱只能连接第二层到第三层中的一些接线柱，来达到这个效果，请你帮助她解决配电箱问题。

输入数据保证，至少存在一种合法的连接方案。

输入描述

第一行输入三个正整数 ，表示开关链接配电箱输入端网络的导线数目，配电箱输出端链接灯泡的导线数目，开关，灯泡，以及每排中继接线柱的数目。
接下来N行，每行输入两个正整数表示第个开关连接到配电线输入端的第个接线柱。
接下来M行，每行输入两个正整数表示配电线输出端的第个接线柱连接到第个灯泡。

输入数据保证，无重边且至少存在一种合法的连接方案。

输出描述

首先输出一个正整数表示配电箱中的导线数目。

接下来行，每行输出两个正整数表示配电箱输入端第个接线柱连接配电箱输出端第个接线柱。

示例1

输入: 

6 3 3
1 2
2 1
1 1
2 2
2 3
3 1
1 1
2 2
3 3

输出: 

5
2 1
1 3
3 1
2 3
3 2

说明:

如图所示。
摁下第一个按钮（蓝色），第一个灯泡收到{1}次信号，第二个灯泡收到{0}次信号，第三个灯泡收到{2}次信号，相当于第一个按钮只控制第一个灯。
摁下第二个按钮（绿色），第一个灯泡收到{2}次信号，第二个灯泡收到{1}次信号，第三个灯泡收到{2}次信号，相当于第二个按钮只控制第二个灯。
摁下第三个按钮（黄色），第一个灯泡收到{0}次信号，第二个灯泡收到{0}次信号，第三个灯泡收到{1}次信号，相当于第三个按钮只控制第三个灯。

原站题解

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

C++ 解法, 执行用时: 5ms, 内存消耗: 508K, 提交时间: 2021-06-01 22:27:41 

#include<bits/stdc++.h>
using namespace std;
int i,j,k,n,m1,m2,x,y;

bitset<105> b1[105],b2[105],b3[105],res[105];
vector<pair<int,int>> ans;
void swp(int x,int y){
	swap(b1[x],b1[y]);
	swap(b2[x],b2[y]);
}
#define f(x,y,z) for(x=y;x<=z;x++)
#define fo() f(i,1,n){f(j,1,n)
#define get() f(i,1,m1){scanf("%d%d",&x,&y);b1[x][y]=1;}f(i,1,n){f(j,i,n){if(b1[j][i]){swp(j,i);f(k,1,n){if(k!=i&&b1[k][i]){b1[k]^=b1[i];b2[k]^=b2[i];}}}}}
int main(){
	scanf("%d%d%d",&m1,&m2,&n);
	f(i,1,n){b2[i][i]=1;}get();
	f(i,1,n){b3[i]=b2[i];b1[i].reset();b2[i].reset();b2[i][i]=1;}
	m1=m2;get();
	fo(){if(b3[i][j]){res[i]^=b2[j];}}}
	fo(){if(res[i][j]){ans.push_back({i,j});}}}
	printf("%d\n",ans.size());
	for(auto [i,j]:ans){printf("%d %d\n",i,j);}
}

上一题

© 2024 nowcoder.com