思路:
很巧的思维题,虽然很容易想到直接构造一个图,但如果没得出这么几个性质的话就感觉无从下手。首先对于一个图来说,他的和与把这个图取反(.变X,X变.)得到的和是相等的,所以我们就可以比较图B与图A不相等的元素的个数是多少,如果图B与图A不相等的元素个数不超过nm/2,那么图B就可以改变不超过nm/2个元素变成图A。否则,如果图B与图A不相等的元素个数超过nm/2了,那图B和图A取反后的图不相等的元素个数就一定小于等于nm/2,那么我们直接输出图A取反后的结果就可以了。所以题目中要求没有方案时输出-1为干扰项。
#include <iostream> #include <cstring> #include <cstdio> #include <algorithm> #include <cmath> #include <queue> #include <stack> #include <set> #include <vector> #include <map> #include <unordered_set> #include <unordered_map> #define x first #define y second #define IOS ios::sync_with_stdio(false);cin.tie(0); using namespace std; typedef long long LL; typedef pair<int, int> PII; const int N = 1010, M = 200010, MOD = 1000000007, INF = 0x3f3f3f3f; char ga[N][N], gb[N][N]; int main() { IOS; int n, m; cin >> n >> m; for (int i = 1; i <= n; i ++ ) for (int j = 1; j <= m; j ++ ) cin >> ga[i][j]; for (int i = 1; i <= n; i ++ ) for (int j = 1; j <= m; j ++ ) cin >> gb[i][j]; int cnt = 0; for (int i = 1; i <= n; i ++ ) for (int j = 1; j <= m; j ++ ) if(ga[i][j] != gb[i][j]) cnt++; if(cnt <= n) { for (int i = 1; i <= n; i ++ ) { for (int j = 1; j <= m; j ++ ) cout << ga[i][j] << ' '; cout << endl; } return 0; } else { for (int i = 1; i <= n; i ++ ) for (int j = 1; j <= m; j ++ ) if(ga[i][j] == '.') ga[i][j] == 'X'; else ga[i][j] == '.'; for (int i = 1; i <= n; i ++ ) { for (int j = 1; j <= m; j ++ ) cout << g[i][j] << ' '; cout << endl; } return 0; } cout << -1 << endl; return 0; }
思路:
可以分三种情况讨论:
- 其中一人走完全程(一人速度远大于另一人时该方案用时最短)
- 两人相向而行
- 在p1到p2找到一点
mid
,使mid
左右两端路程分别由两人自己走完,通过二分法多次选取mid
点,尽可能使两人所用时间相等
这个题不知道为什么二分循环条件r-l<1e-8不行,得循环100次
#include <iostream> #include <cstring> #include <cstdio> #include <algorithm> #include <cmath> #include <queue> #include <stack> #include <set> #include <vector> #include <map> #include <unordered_set> #include <unordered_map> #define x first #define y second #define IOS ios::sync_with_stdio(false);cin.tie(0); using namespace std; typedef long long LL; typedef pair<int, int> PII; const int N = 1010, M = 200010, MOD = 1000000007, INF = 0x3f3f3f3f; double cal(double n, double p, double v) { return (min(p, n - p) + n) / v; } int main() { IOS; int T; cin >> T; while(T -- ) { double n, p1, v1, p2, v2; cin >> n >> p1 >> v1 >> p2 >> v2; if(p1 > p2) { swap(p1, p2); swap(v1, v2);//别忘了交换速度 } double res1 = min(cal(n, p1, v1), cal(n, p2, v2));//一人走全程 double res2 = max((n - p1) / v1, p2 / v2);//两人相对走 double res = min(res1, res2); double l = p1, r = p2; double t1 = 0, t2 = 0; for(int i = 1; i <= 100; i ++)//精度 { double mid = (l + r) / 2; t1 = cal(mid, p1, v1); t2 = cal(n - mid, n - p2, v2); if(t1 >= t2) r = mid;//左边比右边花的时间多,所以左边变短点 else l = mid; } double res3 = max(t1, t2); printf("%.10lf\n", min(res, res3)); } return 0; }