首页 > 其他分享 >abc--277--F

abc--277--F

时间:2022-12-22 15:22:33浏览次数:61  
标签:ch -- int abc 277 using getchar

F - Sorting a Matrix

技巧

1 对于每一列,可以直接sort,然后判断谁在谁的前面,但是多个这样的关系要怎么判断是否矛盾??
也就是判断前后关系是否矛盾,对吧,使用topsort,就可以确定谁在谁的前面。
2 对于多个相同的点,比如 1 1 1 2 2 2如果直接建图,需要建立9条边,也就是左边相数m1*右边相等数m2
这里可以采用一个中间点的方式,这样子是m1+m2
这样可以保证边的数量很小
3 怎么确定那种谁和谁之间建立边,怎么样代码优雅一点,设立一个pre,然后每次对pre进行更新

代码

//设立一个超级起源地,来代替多个点
#include <bits/stdc++.h>
using namespace std;
const int M=1e6+5;
using pii=pair<int,int>;
#define fi first
#define se second

inline int read(){
    int x=0,f=1;
    char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
    return x*f;
}

vector<int>g[M<<1];
vector<pii>f;
int in[M<<1];

int n,m,tot;

bool topsort() {
    queue<int>q;
    for(int i=1;i<=tot;i++)
        if(in[i]==0)q.push(i);
    while(!q.empty()) {
        int now=q.front();
        q.pop();
        for(auto to:g[now])
            if(--in[to]==0)q.push(to);
    }
    for(int i=1;i<=m;i++)
        if(in[i])return 0;
    return 1;
}

int main() {
    n=read(),m=read();
    tot=m;
    for(int i=1;i<=n;i++) {
        vector<pii>v;
        for(int j=1;j<=m;j++) {
            int x=read();
            if(x)v.push_back({x,j});
        }
        sort(v.begin(),v.end());
        int pre=0;
        //这个处理很奇妙呀
        for(int j=1;j<v.size();j++) {
            if(v[j-1].fi<v[j].fi) {
                ++tot;
                for(int k=pre;k<j;k++) {
                    g[v[k].se].push_back(tot);
                    in[tot]++;
                }
                pre=j;
            }
            if(pre!=0) {
                g[tot].push_back(v[j].se);
                in[v[j].se]++;
            }
        }
        if(v.size())f.push_back({v.front().fi,v.back().fi});
    }
    if(topsort()==0)return cout<<"No\n",0;
    sort(f.begin(),f.end());
    for(int i=1;i<f.size();i++)
        if(f[i].fi<f[i-1].se)return cout<<"No\n",0;
    cout<<"Yes\n";
    return 0;
}

标签:ch,--,int,abc,277,using,getchar
From: https://www.cnblogs.com/basicecho/p/16998802.html

相关文章

  • 用python写一个获取git log也就是changeLog的小工具
    一、前提:每次发版后,都是人工去整理gitlog进行发版说明,结合项目需要,决定写个小工具获取gitlog,主要实现的功能点有以下几点:1、获取gitcommit时的记录。2、在commit中......
  • 初级程序员需了解工具
    VSCode编辑器地址文档git项目管理地址文档markdown文档格式(GitHubFlavoredMarkdownSpec)文档linux操作系统(RockyLinux)地址文档DB......
  • Docker学习笔记十四:Docker安装Grafana
    介绍是一个开源的度量分析和可视化工具,可以通过将采集的数据分析、查询,然后进行可视化的展示,并能实现报警。参考官网地址:https://grafana.com/docs/grafana/latest/inst......
  • 大四上 | 计算机综合课设答辩经验帖
    被问了如下问题:我们的OS中是否有idle进程。背景:如果所有进程都被kill掉了,那么os就会陷入死循环。即使再发生需要响应的事情,比如希望再创建个进程或者异常处理......
  • 使用errorPage属性指明出错后跳转的错误页面
    在Test.jsp中,page指令的errorPage属性指明了出错后跳转到"/ErrorPage/error.jsp",error.jsp页面代码如下:1<%@pagelanguage="java"import="java.util.*"pageEncoding......
  • page指令的import属性
    在Jsp页面中,Jsp引擎会自动导入下面的包java.lang.*javax.servlet.*javax.servlet.jsp.*javax.servlet.http.*可以在一条page指令的import属性中引入多个类或......
  • 基础教程-try.except-命令行输入-字符串格式化
    tryexpecttry块允许您测试代码块以查找错误。except块允许您处理错误。finally块允许您执行代码,无论try和except块的结果如何。多个异常elsefinally定义多......
  • Oracle函数入坑指南
     一、oracle函数概述Oracle 提供一系列用于执行特定操作的函数SQL函数带有一个或多个参数并返回一个值以下是SQL函数的分类: 二、单行函数单行函数对于从表中......
  • Go-18 Golang结构体struct详解
    packagemainimport"fmt"//Golang中的结构体详解typenewIntint//自定义类型typemyInt=int//类型别名typezsIntinttypepersonstruct{ namestr......
  • 使用page指令的的isErrorPage属性显式声明页面为错误页面
    如果某一个jsp页面是作为系统的错误处理页面,那么建议将page指令的isErrorPage属性(默认为false)设置为"true"来显式声明这个Jsp页面是一个错误处理页面。例如:将error.jsp......