【UVA-10763】解题报告（STL）

原始题目

题目大意

有n个学生想交换到其他学校学习。为了简单起见，规定每个象从A学校换到B学校的学生必须找一个 想从B学校换到A的“搭档”。如果每个人都能找到搭档（一个人不能找多个搭档），学校就会同意他们交换。 每个学生用两个整数A、B表示，你的任务是判断交换是否可以进行。

解题思路

  • 利用multimap（多重映射）对于一组键、值对，查找有没有对应值为键，键为值得的映射，有则删除，没有的话把当前 的键、值对加入multimap。最后检查是否为空

  • 网上还有一种虽然简单优雅但是有漏洞的解法，初始赋值\(ans[i]=i\)输入一组\(a,b\)，\(swap(ans[a],ans[b])\)， 最后检查是否复合原状态（一一匹配的话两次反转复原），不过这个解法没有考虑到三方交换的情况（即\(swap(a,b),swap(b,c),swap(c,a)\)） 其实这是不满足题意的，但也会判YES。所以说有漏洞。

解题代码

  • multimap 
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    #include <cstdio>
    #include <cstring>
    #include <iostream>
    #include <iomanip>
    #include <cmath> 
    #include <set>
    #include <vector>
    #include <string>
    #include <algorithm>
    #include <map>
    #include <sstream>
    #include <bits/stdc++.h>
    #define rep(i,a,n) for(int i=a;i<n;++i)
    #define per(i,a,n) for(int i=n-a;i>=a;--i)
    #define cl(x,a) memset(x,a,sizeof(x))
    #define all(x) x.begin(),x.end()
    #define pb push_back
    #define np next_permutation
    #define mp make_pair
    #define INF 0x3f3f3f3f
    #define eps 1e-8
    #define K 1001
    #define fi first
    #define se second
    using namespace std;
    const int maxn=1e5+5;
    typedef vector<int> vi;
    typedef multimap <int,int>::const_iterator cit;
    int main(){
    	ios::sync_with_stdio(false);
    	int n,a,b;
    	while(cin>>n && n){
    		multimap <int,int> mmp;
    		
    		rep(i,0,n){
    			cin>>a>>b;
    			typedef pair<cit,cit> Range;
    			Range range=mmp.equal_range(b);
    			int flag=0;
    			cit j=range.first;
    			for(;j!=range.second;++j){
    				if(j->second==a){
    					flag=1;
    					break;
    				}
    			}
    			if(flag) mmp.erase(j);
    			else mmp.insert(mp(a,b));

    		}
    		if(mmp.size()==0) cout<<"YES"<<endl;
    		else cout<<"NO"<<endl;
    	}
    }

  • 朴素法（有漏洞）

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    #include <cstdio>
    #include <cstring>
    #include <iostream>
    #include <iomanip>
    #include <cmath> 
    #include <set>
    #include <vector>
    #include <string>
    #include <algorithm>
    #include <map>
    #include <sstream>
    #include <bits/stdc++.h>
    #define rep(i,a,n) for(int i=a;i<n;++i)
    #define per(i,a,n) for(int i=n-a;i>=a;--i)
    #define cl(x,a) memset(x,a,sizeof(x))
    #define all(x) x.begin(),x.end()
    #define pb push_back
    #define np next_permutation
    #define mp make_pair
    #define INF 0x3f3f3f3f
    #define eps 1e-8
    #define K 1001
    #define fi first
    #define se second
    using namespace std;
    const int maxn=5e5+5;
    int ans[maxn];
    int main(){
    	ios::sync_with_stdio(false);
    	int n;
    	while(cin>>n && n){
    		int flag=0;
    		rep(i,1,n+1) ans[i]=i;
    		rep(i,1,n+1) {int a,b; cin>>a>>b; swap(ans[a],ans[b]);}
    		rep(i,1,n+1) {if(ans[i]!=i) {flag=1;break;}}
    		if(flag) cout<<"NO"<<endl;
    		else cout<<"YES"<<endl;
    	}
    }

收获与反思

  • 交换复原思想值得学习