题解 | 2023 年牛客多校第三场 D 题 Ama no Jaku

World Fragments I

https://ac.nowcoder.com/acm/contest/57357/A

题意:给定一 n×nn\times n 的 01 矩阵,每次可以翻转一行或一列,执行若干次操作。若将操作完成后的矩阵的每一行从做到右视为一个二进制数 {r}i=1n\{r\}_{i=1}^n,每一列从上到下视为 {c}i=1n\{c\}_{i=1}^n,要求 min(ri)max(ci)\min(r_i) \ge \max(c_i),问是否可以实现,可以实现求最小操作次数。1n3001 \le n \le 300

解法:假设第一行有一个 11,则 max(ci)2n1\max(c_i) \ge 2^{n-1},此时 min(ri)2n1\min(r_i) \ge 2^{n-1},即第一列每个数字都是 11,则此时 max(ci)=2n1\max(c_i)=2^n-1,则要求整个矩阵都是 11。因而全 11 矩阵是合理的。

如果第一行全 00,则 min(ri)=0\min(r_i)=0,则 max(ci)=0\max(c_i)=0,整个矩阵全 00

因而整个矩阵必须所有数字都相同。

考虑维护方程 {ci}\{c_i\}{rj}\{r_j\}。如果最后是全 00,如果当前 ai,j=1a_{i,j}=1,则 cirjc_i \ne r_j,反之相等。因而维护一个 01 种类并查集即可。

#include <bits/stdc++.h>
using namespace std;
const int N = 2000;
char a[N + 5][N + 5];
// [1, n] row0; [n+1,2n] row1
// [2*n+1,3*n] col0
int father[4 * N + 5], n;
int getfather(int x)
{
    return father[x] == x ? x : father[x] = getfather(father[x]);
}
int getid(int id, int flag, int col)
{
    int ans = id;
    if (flag)
        ans += 2 * n;
    if (col)
        ans += n;
    return ans;
}
void merge(int x, int y)
{
    x = getfather(x);
    y = getfather(y);
    if (x != y)
        father[x] = y;
}
bool check(int x, int y)
{
    return getfather(x) == getfather(y);
}
int solve(int op)
{
    int m = n * 2;
    for (int i = 1; i <= 2 * m; i++)
        father[i] = i;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
            if (a[i][j] == ('1' ^ op))
            {
                merge(getid(i, 0, 0), getid(j, 1, 1));
                merge(getid(i, 0, 1), getid(j, 1, 0));
            }
            else
            {
                merge(getid(i, 0, 0), getid(j, 1, 0));
                merge(getid(i, 0, 1), getid(j, 1, 1));
            }
    for (int i = 1; i <= n; i++)
        if (check(i, i + n))
            return -1;
    for (int i = 1; i <= n; i++)
        if (check(i + 2 * n, i + 3 * n))
            return -1;
    map<int, int> siz;
    for (int i = 1; i <= n; i++)
        siz[getfather(i)]++;
    for (int i = 2 * n + 1; i <= 3 * n; i++)
        siz[getfather(i)]++;
    int ans = 2 * n;
    for (auto [x, y] : siz)
        ans = min(ans, y);
    return min(ans, 2 * n - ans);
}
int main()
{
    scanf("%d", &n);
    for (int i = 1; i <= n; i++)
        scanf("%s", a[i] + 1);
    if (solve(0) == -1)
    {
        printf("-1");
        return 0;
    }
    printf("%d", min(solve(0), solve(1)));
    return 0;
}
全部评论
终于看到和我一样做法的
点赞 回复 分享
发布于 2023-08-01 11:28 北京

相关推荐

少糖去冰的小师弟很沉稳:一群cs公司lz摇奶茶都不止这点钱,md3k***
点赞 评论 收藏
分享
FieldMatching:看成了猪头顾问,不好意思
点赞 评论 收藏
分享
(黑话警告⚠️:hc=岗位数量,&nbsp;mt=导师,&nbsp;ld=直属领导,&nbsp;cr=代码审查)25年1月,我加入了字节某前端团队,并期望能在这里待到秋招并尝试转正。然而,就在上周,ld&nbsp;找我1v1,告诉我,我的能力和团队预期不太匹配,并和我劝退。晴天霹雳吗?肯定是有的。那一刻,脑子里嗡嗡作响,各种情绪翻涌。但冷静下来想想,这几个月,自己在能掌控的范围内,确实有不少地方做得不尽如人意。所以,我想把这段不算成功的经历复盘一下,希望能给同样在努力转正的你提个醒,避开我踩过的坑。一、ld&nbsp;的要求要注意刚进组时,ld就和我聊过转正的事。我当时发问:“咱们这儿有hc&nbsp;吗?”&nbsp;ld没直接回答,只是说:“看能力,能力到了...
牛客上的彭于晏:过来人告诉你,入职后要做的第一件事儿不是说主动找活儿做,你要先学会融入团队,摸清ld的性格,投其所好。然后才是展示你的能力,能力上可以说技术或者业务,以业务能力为主,技术能力为辅。优先保证自己对业务需求的开发保证质量效率,然后再谈技术的问题,不要你觉得啥啥啥不行就想着整体优化了(发现校招生最喜欢干这事儿),我工作快5年了发现搞这种的最后都没啥好的结果,产出没有还引入新的bug,校招或者实习的水平看到的问题别人看不到嘛?为什么别人不去搞?浪费时间还没收益的事儿不要去做,技术上的能力体现在对于一个新需求,在不符合现在业务发展的架构设计上,你能拿出好的技术方案同时能考虑到后续业务发展逐渐将技术架构引入合理的架构,这是一个漫长的过程而不是一次性的
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客企业服务