首页 > 其他分享 >[COCI2012-2013#2] INFORMACIJE 题解

[COCI2012-2013#2] INFORMACIJE 题解

时间:2024-08-30 19:48:01浏览次数:10  
标签:二分 匹配 题解 位置 二元关系 COCI2012 区间 INFORMACIJE

前言

题目链接:洛谷

题意简述

你需要构造一个 \(1 \sim n\) 的排列 \(a\),满足 \(m\) 个条件,格式如下:

  • 1 x y v:\(\max \limits _ {i = l} ^ r a_i = v\)。

  • 2 x y v:\(\min \limits _ {i = l} ^ r a_i = v\)。

题目分析

首先这个最值很难受,考虑能不能转化成我们喜欢的二元关系。比如,当 \([l, r]\) 的最值为 \(v\) 时,说明 \(v\) 必须出现在这段区间内。再思考一下,对于最大值,为了保证这段区间的最大值是 \(v\),那么大于 \(v\) 的数就不能出现在这段区间内,最小值同理。把前者“必须出现”转化为补集的“不能出现”,这样我们处理出了对于每一个值 \(v\) 不能出现的位置。

有什么用呢?我在膜尼赛上用爆搜骗分。直接骗肯定不好看,这时候就需要一些常见的剪枝优化。对于限制类题目,我们把限制多的先搜索能节约不少时间。此外,寻找到一个没有确定的位置可以使用双向链表优化。预处理区间覆盖转化为差分。能够得到 \(86\) 分的好成绩

话说回来,这么搜肯定是错的,那还有什么做法呢?我们必须敏感地注意到位置和值的特殊二元关系。到了最后,每一个位置一定一一对应一个值,将“不能”反转得到若干“可能”的匹配关系,最后的对应一定这些可能匹配中的一种。

不妨继续抽象模型。有红黄两种颜色的小球各 \(n\) 个,我们知道了每一个红球可能和哪些黄球匹配,找到一种匹配方式,使得红黄球一一对应。这不就是二分图的裸题了吗?我们将可能得匹配方式看作是值向位置的连边,最终的答案就是位置对应的那个值。

注意到存在无解的情况,此时说明二分图不存在完美匹配,判断即可。

时间复杂度理论上来说可以优化到:\(\Theta(m \log n + n^{\frac{5}{2}})\),但是可能比不过常数小的 \(\Theta(nm + n ^ 3)\)?

代码

#include <cstdio>

#define isdigit(x) ('0' <= x && x <= '9')
inline void read(int &x) {
    x = 0; char ch = getchar();
    for (; !isdigit(ch); ch = getchar());
    for (;  isdigit(ch); ch = getchar()) x = (x << 3) + (x << 1) + (ch ^ 48);
}

const int N = 220;

int n, m, val[N], mi[N], mx[N], cant[N][N];
int to[N * N], nxt[N * N], head[N], tot;
int vis[N], timer, mark[N];

bool dfs(int now) {
    for (int i = head[now]; i; i = nxt[i]) {
        int to = ::to[i];
        if (vis[to] != timer) {
            vis[to] = timer;
            if (!mark[to] || dfs(mark[to])) {
                mark[to] = now;
                return true;
            }
        }
    }
    return false;
}

signed main() {
    read(n), read(m);
    for (int i = 1; i <= n; ++i) mx[i] = n;
    for (int i = 1, op, l, r, v; i <= m; ++i) {
        read(op), read(l), read(r), read(v);
        ++cant[v][1], --cant[v][l];
        ++cant[v][r + 1], --cant[v][n + 1];
        for (int j = l; j <= r; ++j) {
            if (op == 1)
                v < mx[j] && (mx[j] = v);
            else
                v > mi[j] && (mi[j] = v);
        }
    }
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= n; ++j) {
            cant[i][j] += cant[i][j - 1];
            if (mi[j] <= i && i <= mx[j] && !cant[i][j]) {
                to[++tot] = j;
                nxt[tot] = head[i];
                head[i] = tot;
            }
        }
    }
    for (int i = 1; i <= n; ++i) {
        ++timer;
        if (!dfs(i)) return puts("-1"), 0;
    }
    for (int i = 1; i <= n; ++i) printf("%d ", mark[i]);
    return 0;
}

总结 & 反思

说实话,都想到爆搜,想不到二分图匹配确实不应该,应该归根结底是二分图模型不熟悉了。

二分图是处理两种不同类型的物件之间的对应关系。对于本题,一个排列的构造,我们如果能找出值和下标的二元关系,就能建立二分图,跑匹配,最后输出匹配的方案。

标签:二分,匹配,题解,位置,二元关系,COCI2012,区间,INFORMACIJE
From: https://www.cnblogs.com/XuYueming/p/18389339

相关文章

  • Luogu P10997 Partition 题解 [ 蓝 ] [ 轮廓 dp ]
    Partition:一道dp神题,用到了以轮廓线的轨迹来做dp的技巧,和敲砖块这题的状态设计有点相似。观察首先观察样例,发现整张图可以看作是被两条线分隔开的。同时每个颜色的四个方向上又存在一大堆奇怪的性质,很容易发现这两条线一条是从左上到右下的线,另一条是从右下到左上的线。暴......
  • CF603E 题解
    题意给定一个\(n\)个结点的无向图,初始没有边。接下来有\(m\)个询问,每次向图中加入一条连接\((u,v)\)权值为\(w\)的边。每次加边后,查询是否存在一个边集\(E\),满足当图中只有\(E\)中的边时,所有点的度数均为奇数。同时你还要最小化\(\max\limits_{(u,v,w)\inE}......
  • 【Mysql】mysql count主键字段很慢超时 执行计划Select tables optimized away ,最终调
     背景: mysql表 主键字段count,速度很慢,耗时将近30s   从执行计划可以看出:explainSELECTCOUNT(rule_id)ASdataCountFROM`sku_safe_stock_rule`;   原理分析:SelecttablesoptimizedawaySELECT操作已经优化到不能再优化了(MySQL根本没有遍历......
  • CF891E Lust 题解
    题目链接点击打开链接题目解法会不了\(egf\)/ll我们把贡献变成\(\prod\limits_{j\neqi}a_j=\prod\limits_{j=1}^na_j-\prod\limits_{j=1}^n(a_i-[i=j])\)即答案为一开始的乘积\(-\)\(k\)次操作之后所有数乘积的期望因为有顺序,所以用\(egf\)的形式表示最后乘积的期......
  • UVA12421 (Jiandan) Mua (I) - Lexical Analyzer题解
    没什么废话、超级珂爱的大模拟。本蒟蒻写了2h才过。其实就是按题意模拟即可,不需要什么高深的算法。本人就是错在了符号中的“=”,因为如果是连续的两个等于号,只能输出“==”,而不能输出“=”“==”,然后本人就卡在这个地方卡了1.5h。代码量也不大,主要是毒瘤细节模拟题。......
  • P6192 【模板】最小斯坦纳树 题解
    Description给定一个包含\(n\)个结点和\(m\)条带权边的无向连通图\(G=(V,E)\)。再给定包含\(k\)个结点的点集\(S\),选出\(G\)的子图\(G'=(V',E')\),使得:\(S\subseteqV'\);\(G'\)为连通图;\(E'\)中所有边的权值和最小。你只需要求出\(E'\)中所有边的权值......
  • BZOJ 4403序列统计题解
    缅怀zxc......
  • CSP-J 2021 初赛试题解析(第三部分:完善程序(2))
    完善程序二完整程序代码#include<iostream>usingnamespacestd;structpoint{intx,y,id;};boolequals(pointa,pointb){returna.x==b.x&&a.y==b.y;}boolcmp(pointa,pointb){returna.x!=b.x?a.x<b.x:a.y<b.y;}......
  • AT_arc170_b 的题解
    (一)因为\(a_i\)较小,那么可以对每一个\(i\),求出它右边离他最近的值为\(j\)的位置。枚举左端点和中间那个数\(a_j\),那么可以求出最小的\(k\)。这样就求出了每个左端点可以取到的最小的\(k\),记为\(b_i\)再从右到左\(b_i=\min(b_i,b_{i+1})\)。(二)AC代码。#include<bi......
  • AGC041D Problem Scores 题解
    在分值不降的条件下,要使任意一个大小为\(k\)的子集\(S\)内题目的分值之和少于任意一个大小为\(k+1\)的子集\(T\)内题目的分值之和,容易发现只需要取\(S\)为后\(k\)道题目,\(T\)为前\(k+1\)道题目时满足限制即可。换而言之,只需要对满足\(a\)的每一段长为\(k+......