USACO 1.4 Wormholes 虫洞

xiaoxiao2021-03-01  15

题目描述


农夫约翰爱好在周末进行高能物理实验的结果却适得其反,导致N个虫洞在农场上(2<=N<=12,n是偶数),每个在农场二维地图的一个不同点。

根据他的计算,约翰知道他的虫洞将形成 N/2 连接配对。例如,如果A和B的虫洞连接成一对,进入虫洞A的任何对象体将从虫洞B出去,朝着同一个方向,而且进入虫洞B的任何对象将同样从虫洞A出去,朝着相同的方向前进。这可能发生相当令人不快的后果。

例如,假设有两个成对的虫洞A(1,1) 和 B(3,1),贝茜从(2,1)开始朝着 +x 方向(右)的位置移动。贝茜将进入虫洞 B(在(3,1)),从A出去(在(1,1)),然后再次进入B,困在一个无限循环中!

| . . . . | A > B . 贝茜会穿过B,A, + . . . . 然后再次穿过B

 农夫约翰知道他的农场里每个虫洞的确切位置。他知道贝茜总是向 +x 方向走进来,虽然他不记得贝茜的当前位置。请帮助农夫约翰计算不同的虫洞配对(情况),使贝茜可能被困在一个无限循环中,如果她从不幸的位置开始。

 

样例输入&输出


 sample input

4 0 0 1 0 1 1 0 1

 sample output

2

 

分析&反思


 dfs + 模拟检验,都有需要提高的地方

刚开始想到了一个简单剪枝,想到了dfs配对,想到了向大配对去重, 想到了从虫洞出发检查。

想不到dfs的代码实现,想不到partner数组 ,想不到right数组记录右边的点直接跳。

 

dfs很久没写了,基本的几点:

1. 终点状态,ans++,return ans。

2. 退出后partner还原为零。

 

ps:right是一个string类的函数,属于关键字, 不可用于命名。补充:

CString a,b;  a = "123456789";

 b = a.Left(4);   //值为:1234  b = a.Mid(3);    //值为:456789  b = a.Mid(2, 4); //值为:3456       //4为长度   b = a.Right(4);  //值为:6789

 

代码


 

#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> using namespace std; int n; int x[20], y[20], partner[20], right1[20]; int check() { int pos, start; for(int i = 1; i <= n; i++) { pos = start = i; for(int cnt = 0; cnt < n; cnt++) { pos = partner[right1[pos]]; if(pos == start) return 1; if(!pos) break; } } return 0; } int solve () { int i ,j, ans = 0; //int ans = 0 for(i = 1; i <= n; i++) if(!partner[i]) break; if(i == n+1) if(check()) return ++ans; // i在最后一个循环变成n+1,终点状态 // 向大的匹配,去重,想到了,如同分苹果,dfs常用去重 for(j = i+1; j <= n; j++) if(!partner[j]) { partner[i] = j; partner[j] = i; ans += solve(); // +=!!! partner[i] = partner[j] = 0; } return ans; } int main () { freopen("wormhole.in", "r", stdin); freopen("wormhole.out", "w", stdout); cin >> n; for(int i = 1; i <= n; i++) cin >> x[i] >> y[i]; // 记录每个点右边的点,直接跳; for(int i = 1; i <= n; i++) for(int j = 1; j <= n; j++) if(y[i] == y[j] && x[i] < x[j]) // 必须j在i的右边,顺便去掉ij相同的情况 if(!right1[i] || x[right1[i]]-x[i] > x[j]-x[i]) right1[i] = j; cout << solve() << endl; return 0; }

备注


solve () 里的 i 用的很巧妙。

很多还要重新pick up啊!

转载请注明原文地址: https://www.6miu.com/read-4050066.html

最新回复(0)