【题解】牛客2025年七夕节比赛-J

J 诡异的激光

$\hspace{15pt}$ 一道充满着随机的题目，这里给出一种随机的做法，如果想使用概率dp来做，那也是可以的。

$\hspace{15pt}$ 随机生成激光 $10-100$ 次，选择经过次数最少的位置即可。

<del>据ai证明，该做法的通过率大约在99%以上</del>

$\hspace{15pt}$ 对于数据出锅，加强后仍然很弱，在这里出题人深表歉意。

#include <bits/stdc++.h>
using namespace std;
using ll = long long; 
using i64 = long long; 
using loli = long long;
using ull = unsigned long long; 
mt19937_64 rnd(time(0));
constexpr int mod = 998244353;  
constexpr int inf = 0x3f3f3f3f; 
constexpr ll linf = 0x3f3f3f3f3f3f3f3f;

template<typename T>
istream& operator >> (istream& in, vector<T>& a) { 
    for (auto &i : a) { 
        cin >> i; 
    } 
    return in; 
}

template<typename T>
istream& operator << (istream& in, vector<T>& a) {
     for (int i = 1; i < a.size(); i++) { 
        cin >> a[i];
    } 
    return in; 
}

template<typename T> 
ostream& operator << (ostream& out, vector<T>& a) { 
    if (a.size() == 0) 
        return out; 
    for (auto& i : a) {
        out << i << ' ';  
    } 
    return (out << '\n');   
}

template<typename T> 
ostream& operator << (ostream& out, vector<vector<T>>& a) {  
    for (auto& i : a)  
        out << i; 
    return (out);  
}

auto main() -> signed {
    cin.tie(0), ios::sync_with_stdio(0);
    auto baka_loli_killer = [&]() -> int { 
        int n, m, k; cin >> n >> m >> k; 
        vector<pair<int, int>> p(k); 
        vector<vector<int>> a(n, vector<int>(m)); 
        for (auto& [x, y] : p) cin >> x >> y, x--, y--, a[x][y] = inf; 

        auto add = [&](int i, int j) { 
            auto& [x1, y1] = p[i]; 
            auto& [x2, y2] = p[j]; 
            vector<pair<int, int>> go; 
            int x = x1, y = y1; 
            while (x1 < x2) go.emplace_back(1, 0), x1++;
            while (x1 > x2) go.emplace_back(-1, 0), x1--;
            while (y1 < y2) go.emplace_back(0, 1), y1++;    
            while (y1 > y2) go.emplace_back(0, -1), y1--;
            shuffle(go.begin(), go.end(), rnd);
            a[x][y]++; 
            for (auto& [dx, dy] : go) { 
                x += dx, y += dy; 
                a[x][y]++; 
            }
        };

        vector<int> v(n); 
        iota(v.begin(), v.end(), 0); 
        for (int i = 0; i < 50; i++) { 
            shuffle(v.begin(), v.end(), rnd); 
            for (int i = 0; i < n / 2; i++) { 
                add(v[i], v[i + n / 2]); 
            }
        }

        int tarx = 0, tary = 0; 
        for (int i = 0; i < n; i++) { 
            for (int j = 0; j < m; j++) { 
                if (a[i][j] < a[tarx][tary]) tarx = i, tary = j; 
            }
        }
        // cerr << a << '\n'; 
        cout << tarx + 1 << ' ' << tary + 1 << '\n'; 
        return 0; 
    }; 

    int t; cin >> t; 
    while (t--) { 
        baka_loli_killer(); 
    }
    return 0;        
}