专栏文章

题解：CF1586I Omkar and Mosaic

____Dice___
CF1586I题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@min5p30r
此快照首次捕获于
2025/12/01 20:59
3 个月前
此快照最后确认于
2025/12/01 20:59
3 个月前
查看原文
*3500，挺好玩的一道题。
我们首先画一些情况，容易发现，假设左下角的那个位置是 xx，与 xx 相反的数是 yy，那么可以发现：
CPP
..xx
.y.x
x.y.
xx..
1. nn 是奇数的情况无解。
画一个图就可以知道。
n=3n=3 举例：
CPP
.xx
x.x
xx.
至此，我们可以发现 nn 一定是偶数。
然后我们接着尝试，从右下角再来一下。
CPP
pp....xx
p.q..y.x
.q.px.y.
..pyqx..
..xqyp..
.y.xp.q.
x.y..q.p
xx....pp
好像还是没有什么规律。。。
但是，我们再来想一下，考虑：
CPP
pp....xx
p.q..y.x
.q.px.y.
..pyqx..
..xqyp..
.y.xp.q!
x.y..q#p
xx...?pp
考虑 ? 和 # 这两个位置，发现其必须不相等。
因为如果相等，则可以得出 (8,7)(8,7) 这个 pp 就不符合题意了。
同理，!≠\neq#。
∴\therefore!==?。
我在模拟赛的时候发现了这一点，然后进一步观察得出，所有长度为奇数的斜线一定满足此条件。
然后我就以为获得了正解，直接写了，成功没过样例。。。。
这说明我们还需要再进行观察。
还是考虑上面这个例子：
CPP
pp....xx
p.q..y.x
.q.px.y.
..pyqx..
..xqyp..
.y.xp.q.
x.y..q.p
xx..*?pp
容易发现，
∵p≠q\because p\neq q,
∴\therefore*==?。
于是我们把 * 对应的那条线画出来。
? 的相反为 &。
CPP
pp....xx
p.q..y.x
#q.px.y.
?.pyqx..
.&xqyp..
.y?xp.q?
x.y&.q&p
xx..??pp
由上可知 #==?。
接着补全图形。
CPP
pp??..xx
p&q.&y.x
?q.px?y.
?.pyqx&.
.&xqyp.?
.y?xp.q?
x.y&.q&p
xx..??pp
惊奇的发现竟然构成了一个环。
然后再画几个例子发现所有的连续的两个位置（例如 (n,2k)(n,2k) 和 (n,2k+1)(n,2k+1)）都满足这个性质。
一共是 n2\frac n 2 个环。
又画了几个发现这个结论确实是对的。
于是魔改一下赛时代码即可。
代码十分潦草。
CPP
#include <bits/stdc++.h>
// #define int long long
#define hh(i, a, b) for (int i = (a); i <= (b); ++i)
#define lob(i, n) for (int i = (n); ~i; --i)
#define rep(i, n) for (int i = 1; i <= (n); ++i)
#define re0(i, n) for (int i = 0; i <= (n); ++i)
#define reb(i, n) for (int i = 0; i < (n); ++i)
#define FILEIN(s) freopen(s ".in", "r", stdin)
#define FILE(s) freopen(s ".in", "r", stdin), freopen(s ".out", "w", stdout)
#define mem(a, b) memset(a, b, sizeof a)
#define pii pair<int, int>
#define X first
#define Y second
#define pb push_back
#define pf pop_front
using namespace std;
const int N = 2000 + 7;
void cmax(int &a, int b)
{
    if (a < b)
        a = b;
}
double Time()
{
    return 1. * clock() / CLOCKS_PER_SEC;
}
int a[N][N], n;
string s[N];
bool ok(int x, int y)
{
    if (x == 2 || y == 2)
        return 1;
    return x == y;
}
void lol(int &x, int y)
{
    if (y == 2)
        return;
    x = y;
}
// int ru(int x,int y){
//     int now=2;
//     int ncol=0,rcl=0;int tx=x,ty=y;
// while(x&&y<=n){
//     if(!ok(now,a[x][y]))return 0;
//     lol(now,a[x][y]);
//     if(now!=2)ncol=rcl^now;
//     --x;++y;rcl^=1;
//     if(now!=2)now^=1;
// }
//     if(now==2)return 2;
//     x=tx;y=ty;
//     while(x&&y<=n){
//         a[x][y]=ncol;ncol^=1;
//         --x;++y;
//     }
//     return (now==2)+1;
// }
// int lu(int x,int y){
// int now=2;
// int ncol=0,rcl=0;int tx=x,ty=y;
//     while(x&&y){
//         if(!ok(now,a[x][y]))return 0;
//         lol(now,a[x][y]);
//         if(now!=2)ncol=rcl^now;
//         --x;--y;rcl^=1;
//         if(now!=2)now^=1;
//     }
//     if(now==2)return 2;
//     x=tx;y=ty;
// while(x&&y){
//     a[x][y]=ncol;ncol^=1;
//     --x;--y;
// }
//     return (now==2)+1;
// }
int dx[] = {-1, -1, 1, 1}, dy[] = {1, -1, -1, 1};
bool check(int x, int y, int dir)
{
    return (y == n && dir == 0) || (x == 1 && dir == 1) || (y == 1 && dir == 2);
}
void ggg(int &x, int &y, int &dir)
{
    if (dir == 0)
        return --x, ++dir, void();
    if (dir == 1)
        return --y, ++dir, void();
    if (dir == 2)
        ++x, ++dir;
}
int Go(int x, int y)
{
    int tx = n, ty = y - 1;

    int now = 2, dir = 0;
    int ncol = 0, rcl = 0;
    int xx = x, yy = y;
    bool hp;
    while (1)
    {
        hp = 0;
        // if (check(x, y, dir))
        // {
        //     if (now != 2)
        //         now ^= 1;
        //     rcl ^= 1;
        // }
        // cout << "! " << x << ' ' << y << ' ' << now << '\n';
        if (!ok(now, a[x][y]))
            return 0;
        lol(now, a[x][y]);
        if (now != 2)
            ncol = rcl ^ now;
        if (x == tx && y == ty)
            break;
        if (check(x, y, dir))
            ggg(x, y, dir), hp = 1;
        else
            x += dx[dir], y += dy[dir];
        if (!hp)
        {
            rcl ^= 1;
            if (now != 2)
                now ^= 1;
        }
    }
    // cout << "SHIT\n";
    if (now == 2)
        return 2;
    x = xx;
    y = yy;
    dir = 0;
    while (x && y)
    {
        a[x][y] = ncol;
        ncol ^= 1;
        if (x == tx && y == ty)
            break;
        if (check(x, y, dir))
            ggg(x, y, dir), ncol ^= 1, a[x][y] = ncol;
        else
            x += dx[dir], y += dy[dir];
    }
    return 1;
}
void print()
{
    cout << "\n";

    rep(i, n) rep(j, n)
    {
        // if(a[i][j]==2)a[i][j]=1;
        cout << a[i][j] << " \n"[j == n];
    }
}
int solve()
{
    cin >> n;
    rep(i, n) cin >> s[i], s[i] = ' ' + s[i];
    if (n & 1)
        return cout << "NONE\n", 0;
    rep(i, n) rep(j, n)
    {
        if (s[i][j] == '.')
            a[i][j] = 2;
        else
            a[i][j] = (s[i][j] == 'G');
    }
    // for(int i=1;i<=n;i+=2){
    //     if(!ok(a[i+1][1],a[i][1]))return cout<<"0\n",0;
    //     lol(a[i+1][1],a[i][1]);
    //     if(!ok(a[1][i+1],a[1][i]))return cout<<"0\n",0;
    //     lol(a[1][i+1],a[1][i]);
    // }
    // for(int i=n;i>=1;i-=2){
    //     if(!ok(a[i][n],a[i-1][n]))return cout<<"0\n",0;
    //     lol(a[i-1][n],a[i][n]);
    //     if(!ok(a[n][i-1],a[n][i]))return cout<<"0\n",0;
    //     lol(a[n][i-1],a[n][i]);
    // }
    // for(int i=2;i<=n;i+=2){
    //     if(!ok(a[1][i-1],a[1][i]))return cout<<"0\n",0;
    //     lol(a[1][i-1],a[1][i]);
    // }
    // for(int i=1;i<=n;i+=2){
    //     if(!ok(a[i+1][n],a[i][n]))return cout<<"0\n",0;
    //     lol(a[i+1][n],a[i][n]);
    // }
    // for(int i=n;i>=1;i-=2){
    //     if(!ok(a[i][1],a[i-1][1]))return cout<<"0\n",0;
    //     lol(a[i-1][n],a[i][n]);
    // }
    // for(int i=1;i<=n;i+=2){
    //     if(!ok(a[n][i+1],a[n][i]))return cout<<"0\n",0;
    //     lol(a[n][i+1],a[n][i]);
    // }
    // // cout<<"123213\n";
    // // print();
    int fk = 1;
    // for(int i=n-1;i>=1;i-=2){
    //     int op=ru(i,1);
    //     if(op==2)fk=2;//,cout<<"! "<<i<<'\n';
    //     if(op==0)return cout<<"0\n",0;
    // }
    // // cout<<"NERD "<<fk<<'\n';
    // for(int i=2;i<=n;i+=2){
    //     int op=ru(n,i);
    //     if(op==2)fk=2;
    //     if(op==0)return cout<<"0\n",0;
    // }
    // for(int i=1;i<=n;i+=2){
    //     int op=lu(i,n);
    //     if(op==2)fk=2;
    //     if(op==0)return cout<<"0\n",0;
    // }
    // for(int i=n-1;i>=1;i-=2){
    //     int op=lu(n,i);
    //     if(op==2)fk=2;
    //     if(op==0)return cout<<"0\n",0;
    // }
    // print();
    for (int i = 2; i <= n; i += 2)
    {
        int op = Go(n, i);
        if (op == 0)
            return cout << "NONE\n", 0;
        if (op == 2)
            fk = 2;
    }
    if (fk == 2)
        cout << "MULTIPLE\n";
    else
    {
        cout << "UNIQUE\n";
        rep(i, n) rep(j, n)
        {
            if (a[i][j] == 2)
                a[i][j] = 1;
            cout << (a[i][j] ? 'G' : 'S');
            if (j == n)
                cout << "\n";
        }
    }
    return 0;
}
main()
{
    // FILE("");
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int T = 1;
    // cin >> T;
    while (T--)
        solve();
    // cout << Time() << "\n";
    return 0;
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...