[BNU弱校联萌]厉兵秣马

比赛链接：http://acm.bnu.edu.cn/v3/contest_show.php?cid=6868

一如既往地水…两题……

A.求两组点不相交的匹配方案。。二分图匹配问题，KM算法求最小匹配，取权值相反数即可。

  1 #include <algorithm>
  2 #include <iostream>
  3 #include <iomanip>
  4 #include <cstring>
  5 #include <climits>
  6 #include <complex>
  7 #include <fstream>
  8 #include <cassert>
  9 #include <cstdio>
 10 #include <bitset>
 11 #include <vector>
 12 #include <deque>
 13 #include <queue>
 14 #include <stack>
 15 #include <ctime>
 16 #include <set>
 17 #include <map>
 18 #include <cmath>
 19 
 20 using namespace std;
 21 
 22 const int INF = 0x3f3f3f3f;
 23 const int maxn = 110;
 24 int n;
 25 int ans[maxn];
 26 int Left[maxn];
 27 bool S[maxn],T[maxn];
 28 double px[maxn<<1];
 29 double py[maxn<<1];
 30 double Lx[maxn],Ly[maxn];
 31 double dis[maxn][maxn];
 32 
 33 
 34 bool match(int i)
 35 {
 36     S[i]=true;
 37     for(int j=1;j<=n;j++)if(abs(Lx[i]+Ly[j]-dis[i][j])<1e-5&&!T[j])
 38     {
 39         T[j]=true;
 40         if(Left[j]==0||match(Left[j]))
 41         {
 42             Left[j]=i;
 43             return true;
 44         }
 45     }
 46     return false;
 47 }
 48 void update(){
 49     double a=INF;
 50     for(int i=1;i<=n;i++)if(S[i])
 51         for(int j=1;j<=n;j++)if(!T[j])
 52             a=min(a,Lx[i]+Ly[j]-dis[i][j]);
 53     for(int i=1;i<=n;i++){
 54         if(S[i])Lx[i]-=a;
 55         if(T[i])Ly[i]+=a;
 56     }
 57 }
 58 void KM()
 59 {
 60     for(int i=1;i<=n;i++){
 61         Left[i]=Lx[i]=Ly[i]=0;
 62         for(int j=1;j<=n;j++)
 63         {
 64             Lx[i]=max(Lx[i],dis[i][j]);
 65         }
 66     }
 67     for(int i=1;i<=n;i++) 
 68     {
 69         while(1) 
 70         {
 71             memset(S,0,sizeof(S));
 72             memset(T,0,sizeof(T));
 73             if(match(i)) break;
 74             else update();
 75         }
 76     }
 77 }
 78 
 79 inline double dist(double x1, double y1, double x2, double y2) {
 80     return sqrt(((x1-x2)*(x1-x2))+((y1-y2)*(y1-y2)));
 81 }
 82 
 83 int main() {
 84     // freopen("in", "r", stdin);
 85     double x, y;
 86     while(~scanf("%d", &n)) {
 87         memset(ans, 0, sizeof(ans));
 88         memset(px, 0, sizeof(px));
 89         memset(py, 0, sizeof(py));
 90         for(int i = 1; i <= 2*n; i++) {
 91             scanf("%lf %lf", &px[i], &py[i]);
 92         }
 93         for(int i = 1; i <= n; i++) {
 94             for(int j = 1; j <= n; j++) {
 95                 dis[i][j] = -dist(px[i], py[i], px[j+n], py[j+n]);
 96             }
 97         }
 98         KM();
 99         for(int i = 1; i <= n; i++) {
100             ans[Left[i]] = i;
101         }
102         for(int i = 1; i <= n; i++) {
103             printf("%d
", ans[i]);
104         }
105     }
106 }

B.方案：一层两列，一列是当前计数到的字母，另一列是所有的字母顺序排列。例：

 1 5
 2 5 5 2
 3 aaaaa
 4 abcde
 5 
 6 bbbbb
 7 abcde
 8 
 9 ccccc
10 abcde
11 
12 ddddd
13 abcde
14 
15 eeeee
16 abcde

代码：

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstdlib>
 4 #include <cstring>
 5 #include <iomanip>
 6 #include <cmath>
 7 #include <map>
 8 #include <vector>
 9 #include <string>
10 #include <queue>
11 #include <set>
12 #include <algorithm>
13 
14 using namespace std;
15 
16 int n;
17 
18 void output1(int cnt, int n) {
19     if(cnt >= 26) {
20         for(int i = 0; i < n; i++) {
21             printf("%c", cnt - 26 + 'A');
22         }
23     }
24     else {
25         for(int i = 0; i < n; i++) {
26             printf("%c", cnt + 'a');
27         }
28     }
29 }
30 
31 void output2(int n) {
32     if(n > 26) {
33         for(int i = 0; i < 26; i++) {
34             printf("%c", i + 'a');
35         }
36         for(int i = 0; i < n-26; i++) {
37             printf("%c", i + 'A');
38         }
39     }
40     else {
41         for(int i = 0; i < n; i++) {
42             printf("%c", i + 'a');
43         }
44     }
45     printf("
");
46 }
47 
48 int main() {
49     // freopen("in", "r", stdin);
50     freopen("out", "w", stdout);
51     while(~scanf("%d", &n)) {
52         printf("%d %d %d
", n, n, 2);
53         for(int i = 0; i < n; i++) {
54             output1(i, n);
55             printf("
");
56             output2(n);
57             printf("
");
58         }
59     }
60 }