首页 > 其他分享 >牛客多校第三场-D-Ama no Jaku

牛客多校第三场-D-Ama no Jaku

时间:2023-07-31 10:22:04浏览次数:38  
标签:cnt no Ama memset int dfn low sizeof 第三场

D-Ama no Jaku_2023牛客暑期多校训练营3 做法:2-sat 先贴个代码,晚点补上思路

#include<bits/stdc++.h>
using namespace std;
#define endl "\n"
typedef long long ll;

const int N=2e3+5;

char a[N][N];

std::vector<int>edge[N];

//bel数组记录某个点在哪个连通块里面
int dfn[N],low[N],ins[N],bel[N],sz[N],sum[N],idx,cnt,n;
stack<int>stk;

void dfs(int u){
    dfn[u]=low[u]=++idx;
    ins[u]=true;
    stk.push(u);
    for(auto v:edge[u]){
        if(!dfn[v]){
            dfs(v);
            low[u]=min(low[u],low[v]);
        }else{
            if(ins[v])low[u]=min(low[u],dfn[v]);
        }
    }
    if(dfn[u]==low[u]){
        cnt++;
        while(1){
            int v=stk.top();
            ins[v]=false;
            bel[v]=cnt;
            stk.pop();
            sum[cnt]++;
            if(v>2*n)sz[cnt]++;
            if(v==u)break;
        }
    }
}

int calc(int val){
    memset(dfn,0,sizeof(dfn));
    memset(low,0,sizeof(low));
    memset(bel,0,sizeof(bel));
    memset(sum,0,sizeof(sum));
    memset(sz,0,sizeof(sz));
    idx=cnt=0;
    for(int i=1;i<=4*n;i++)edge[i].clear();
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            if(a[i][j]-'0'==val){
                edge[i].push_back(j+n);
                edge[j+n].push_back(i);
                edge[i+2*n].push_back(j+3*n);
                edge[j+3*n].push_back(i+2*n);
            }else{
                edge[i].push_back(j+3*n);
                edge[j+3*n].push_back(i);
                edge[j+n].push_back(i+2*n);
                edge[i+2*n].push_back(j+n);
            }
        }
    }
    for(int i=1;i<=4*n;i++){
        if(!dfn[i])dfs(i);
    }
    for(int i=1;i<=2*n;i++){
        if(bel[i]==bel[i+2*n])return INT_MAX;
    }
    int ans=0;
    for(int i=1;i<=cnt;i++)ans+=min(sum[i]-sz[i],sz[i]);
    return ans;
}

int main(){
    ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    cin>>n;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            cin>>a[i][j];
        }
    }
    int ans=min(calc(0),calc(1));
    if(ans<INT_MAX)cout<<ans/2<<endl;
    else cout<<-1<<endl;
    return 0;
}
 

标签:cnt,no,Ama,memset,int,dfn,low,sizeof,第三场
From: https://www.cnblogs.com/zhujio/p/17592742.html

相关文章

  • 使用 pip 出现 Script file ‘C:\Anaconda3\Scripts\pip-script.py‘ is not prese
    某天在虚拟环境使用pip更新tf的时候莫名其妙出现Scriptfile'D:\Anaconda3\Scripts\pip-script.py'isnotpresent的错误,之前用的还好好的,但是突然就不能用了,初步猜测是依赖库发生的更新,可以使用如下方式解决:1、进入创建的环境:activateenv_name2、输入:pyt......
  • 初步体验 llama.cpp
    llama.cpp:PortofFacebook'sLLaMAmodelinC/C++github仓库:https://github.com/ggerganov/llama.cpp参考博文:High-SpeedInferencewithllama.cppandVicunaonCPU第1步,准备一台阿里云4核8G的服务器,操作系统用的是ubuntu22.04第2步,签出llama.cpp源码进行build......
  • npm下载依赖报错:npm does not support Node.js vxx.xx.x
    因为本地运行不同的项目需要的node.js版本不一样,所以经常需要用nvm来切换nodejs版本,有时候下载依赖就会出现问题。想下载依赖 运行npmi后报错,提示node和npm版本不对应:npmdoesnotsupportNode.jsv14.15.1...解决思路:1.考虑node版本和npm版本不兼容的问题,查看node......
  • Linux环境Arduino IDE中配置ATOM S3
    linux选择ubuntu发行版。硬件设备有多小呢:功能超级强大。之前的ROS1和ROS2案例已经全部移植完成并测试结束(三轮纯人力校验......
  • [SWPUCTF 2021 新生赛]no_wakeup
    [SWPUCTF2021新生赛]no_wakeup题目来源:nssctf题目类型:web涉及考点:PHP反序列化1.题目给了一个点击按钮,点进去看看:进去后就是代码审计了:<?phpheader("Content-type:text/html;charset=utf-8");error_reporting(0);show_source("class.php");classHaHaHa{p......
  • NOI 2023 游记
    Day-7坐了10h+高铁后到达成都!Day-6~Day-2赛前集训!还看了两场hdu多校的题,不过贡献几乎为\(0\)。第二场的计算几何题写了一个小时,调了一个小时没过然后下播了。赛后改了一车东西才过。成都的外卖怎么都这么辣!Day-1进校!感觉cdqz的环境和华二昆山的没法比,不过鉴于后者是国......
  • Intention-Aware Online POMDP Planning for Autonomous Driving in a Crowd
    一、论文信息发表日期:2015年发表机构:新加坡国立大学,计算机科学系二、论文内容1.解决问题:无人车在人员密集处的速度规划算法2.方法:前向仿真+强化学习概念   ①.路径规划和速度规划进行解耦,进行速度规划之前路径已确定。 ②.速度规划采取部分可观测马尔可夫决策过程,......
  • vivado生成Bitstream报错[Vivado 12-1345] Error(s) found during DRC. Bitgen not ru
    写了一个很简单的程序,2-4译码器。moduledecoder2to4(inputin1,in0,outputreg[3:0]out);always@(*)beginif({in1,in0}==2'b00)out=4'b1111;elseif({in1,in0}==2'b01)out=4......
  • 2023 联合省选-PKUSC2023-NOI2023游记
    在这段时间主要在学文化课,没怎么停课,天天暴力拼盘,所以索性合在一起。感觉非常意识流,和OI关系好像也不大。pig嫌我开始写的太短,我积极听取他人建议,加了一车流水账。联赛结束以后就退役了。因为即使NGOI也大概率会被卡“省线”,但还打算参加省选碰碰运气。遂在省选前两周申请一周半......
  • 基于中文金融知识的 LLaMA 系微调模型的智能问答系统:LLaMA大模型训练微调推理等详细教
    基于中文金融知识的LLaMA系微调模型的智能问答系统:LLaMA大模型训练微调推理等详细教学基于LLaMA系基模型经过中文金融知识指令精调/指令微调(Instruct-tuning)的微调模型。通过中文金融公开问答数据+爬取的金融问答数据构建指令数据集,并在此基础上对LLaMA系模型进行了指令......