B.Mine Sweeper II

思路：

很巧的思维题，虽然很容易想到直接构造一个图，但如果没得出这么几个性质的话就感觉无从下手。首先对于一个图来说，他的和与把这个图取反（.变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;
}

D.Walker

思路：

可以分三种情况讨论：

1. 其中一人走完全程（一人速度远大于另一人时该方案用时最短）
2. 两人相向而行
3. 在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;
}