1 条题解

  • 0
    @ 2026-1-12 22:29:27

    #include <bits/stdc++.h>
    using std::cin;
    using std::cout;
    
    const int N = 1024;
    typedef std::pair <int, int> pr;
    typedef std::bitset <N> bitset;
    const pr failed = pr(INT_MIN, INT_MIN);
    
    inline int min(const int x, const int y) {return x < y ? x : y;}
    inline void up(int &x, const int y) {x < y ? x = y : 0;}
    inline void down(int &x, const int y) {x > y ? x = y : 0;}
    
    struct graph {
    	bitset g[N];
    	int ar, ac, rightmost;
    
    	friend std::istream & operator >> (std::istream &in, graph &B) {
    		int i, j, r, c, min = N; bool ok = false; static char s[N];
    		in >> r >> c, B.rightmost = B.ar = B.ac = 0;
    		for (i = 0; i < N; ++i) B.g[i].reset();
    		for (i = 0; r; --r, ++i)
    			if (in >> s, ok || std::count(s, s + c, '*')) {
    				for (j = 0; j < c; ++j)
    					if (!(s[j] & 4)) B.g[i].set(j), up(B.rightmost, j);
    				down(min, B.g[i]._Find_first()), ok = true;
    			} else --i, ++B.ar;
    		if (ok) for (B.ac = min, i = 0; i < N; ++i) B.g[i] >>= min;
    		return in;
    	}
    
    	inline int significant() const {return g->_Find_first();}
    
    	inline bool empty() const {return g->none();}
    } G1, G2, G3, G;
    
    bitset R[N];
    
    pr check(const graph &G1, const graph &G2, const graph &goal) {
    	int i, j, d, c1 = G1.significant(), c2 = G2.significant(); pr ret;
    	if (c1 <= c2) {
    		if (d = c2 - c1, G1.rightmost + d >= N) return failed;
    		memcpy(R, G2.g, sizeof R);
    		for (i = 0; i < N; ++i) R[i] ^= G1.g[i] << d;
    	} else {
    		if (d = c1 - c2, G2.rightmost + d >= N) return failed;
    		memcpy(R, G1.g, sizeof R);
    		for (i = 0; i < N; ++i) R[i] ^= G2.g[i] << d;
    		d = 0;
    	}
    	for (i = 0; i < N && R[i].none(); ++i);
    	if (i == N) return goal.empty() ? pr(0, 0) : failed;
    	ret = pr(i, R[i]._Find_first() - goal.significant());
    	if (ret.second < 0) return failed;
    	for (j = 0; i < N; ++i, ++j) {
    		if ((int)R[i]._Find_first() < ret.second) return failed;
    		if (R[i] >> ret.second != goal.g[j]) return failed;
    	}
    	for (; j < N; ++j) if (goal.g[j].any()) return failed;
    	return ret.second -= d, ret;
    }
    
    int main() {
    	int offset_r, offset_c; pr r;
    	std::ios::sync_with_stdio(false), cin.tie(NULL);
    	cin >> G1 >> G2 >> G3, offset_r = G1.ar - G2.ar, offset_c = G1.ac - G2.ac,
    	r = check(G1, G2, G3);
    	if (r != failed) return cout << "YES\n" << G1.significant() - G2.significant() + offset_c << ' ' << offset_r << '\n', 0;
    	if (!G3.empty()) {
    		r = check(G1, G3, G2);
    		if (r != failed) return cout << "YES\n" << r.second + offset_c << ' ' << r.first + offset_r << '\n', 0;
    		r = check(G2, G3, G1);
    		if (r != failed) return cout << "YES\n" << -r.second + offset_c << ' ' << -r.first + offset_r << '\n', 0;
    	}
    	return cout << "NO\n", 0;
    }
    
    • 1

    信息

    ID
    6516
    时间
    2000ms
    内存
    512MiB
    难度
    10
    标签
    递交数
    2
    已通过
    2
    上传者