AtCoder Regular Contest 106 解题报告

arc106_c Solutions

AtCoder Regular Contest 106 的第三题,构造。

题目链接:C – Solutions

题意翻译

  • 一个经典的问题:\( N ( 1 \leq N \leq 10 ^ 5 ) \) 条线段,每条线段覆盖了 \( \left[ L _ i , R _ i \right] ( 1 \leq L _ i < R _ i \leq 10 ^ 9 ) \),选出互不相交的线段,问最多选出多少条。
  • 现在有两种解法:
    1. 将区间按左端点排序,然后扫一遍,能选则选;
    2. 将区间按右端点排序,然后扫一遍,能选则选。
  • 请你构造一种方案,使得第一种算法的答案减去第二种算法的答案的差为 \( M ( – N \leq M \leq N ) \),若无解,输出 \( – 1 \)。

题解

显然第二种做法是正解,进而如果 \( M < 0 \),则无解。

考虑到无论如何,两种算法都至少会选出一个区间,那么我们不妨构造方案使得:第一种算法结果为 \( 1 \),第二种算法的答案为 \( M + 1 \)。

这种方案的构造十分简单:
\[ \left[ \left[ \left[ \left[ ()()\cdots()() \right] \right] \right] \right] \]

#include <bits/stdc++.h>
using namespace std;
#define reg register
typedef long long ll;
#define getchar() (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 100000, stdin), p1 == p2) ? EOF : *p1++)
static char buf[100000], *p1 = buf, *p2 = buf;
inline int read(void)
{
    reg bool f = false;
    reg char ch = getchar();
    reg int res = 0;
    while (!isdigit(ch))
        f |= (ch == '-'), ch = getchar();
    while (isdigit(ch))
        res = 10 * res + ch - '0', ch = getchar();
    return f ? -res : res;
}

int n, m;

int main(void)
{
    n = read(), m = read();
    if (n == 1 && m == 0)
        puts("1 2");
    else if (m > n - 2 || m < 0)
        puts("-1");
    else if (!m)
        for (reg int i = 1; i <= n; ++i)
            printf("%d %d\n", i, i + n);
    else
    {
        const int Delta = 3e5;
        for (reg int i = 1; i <= m + 1; ++i)
            printf("%d %d\n", i * 2 - 1 + Delta, i * 2 + Delta);
        for (reg int i = m + 2, l = 0, r = (m + 1) * 2 + 1; i <= n; ++i, --l, ++r)
            printf("%d %d\n", Delta + l, Delta + r);
    }
    return 0;
}
Pages: 1 2 3 4 5 6 7 8