背景

给时代以枚举，给人生以打表；给当下以骗分，给未来以暴搜……

某比赛。

近期丁老师正在读《三体》，发现这本书内容很精彩，看书的过程中也会出现很多奇奇怪怪的信奥思路，所以这次比赛就专门出了一套《三体》系列的信奥题目，让同学们能在紧张的比赛中带来些许乐趣，也希望能让同学们通过比赛除了有信奥的学习以外也能有一些其他的收获，比如万一你就喜欢上了这本书呢^_^

hhh

《三体》真是太好看了。顺便就做了这四题。

---

1.三体之太阳无解之谜

原文链接。额……我好像不小心把原文删掉了。

不就是分支语句嘛，Mod都发过的（《Mod笔谈》if分支）。

题目

略。

题解

不用想了，一眼if分支。上代码：

#include <iostream>
using namespace std;
int a, b, c;
int main()
{
    while(cin >> a >> b >> c)
    {
        if (a + b < c || a + c < b || b + c < a)cout << "Chaotic Era\n";
        else if (a + b == c || a + c == b || b + c == a)cout << "Tri-Solar Syzygy\n";
        else cout << "Triangle\n";
    }
    return 0;
}

70 Wrong Answer

好吧，我刚才什么都没说。

再仔细看一下题目：

对于所有数据均为int范围内的正整数。

好吧，一看到这句话就知道是坑人的了，数据都在int范围内，那int+int谁还知道在不在int范围内呢？

三体之太阳无解之谜题解

---

2. 三体之水滴进攻

题目

略。

题解

首先，看这张图：

这很容易想到差分。于是有了下面的代码：

#include <iostream>
using namespace std;

int n, m, a[10000007], ans;

int main()
{
    cin >> n >> m;
    for (int i = 1; i <= m; i++)
    {
        int l, r;
        cin >> l >> r;
        a[l]++;
        a[r + 1]--;
    }
    for (int i = 1; i <= n; i++)
    {
        a[i] += a[i - 1];
        if (a[i] == 0)ans++;
    }
    cout << ans;
    return 0;
}

但是……数据范围里 $N≤10^{17}$ ！！！这当然 RE 。

还是看到上面的图。虽然它输入了四个区间，但是打叉的只有两个区间。这里就需要合并区间了。按照上面的图，首先就要按照开始时间来排序，这很容易发现。每一个区间都和下一个区间比较，如果有重叠，就把 $ans$ 加上重叠的总区间，然后 $i$ 要加加。

但是这里有一个问题。如果有多个重叠的区间呢？上面的代码只能计算相邻的区间，而且每次计算完都 i++ 很容易错。这里可以用两个变量计算当前的重叠的区间。首先，如果 当前计算的区间与当前重叠区间重叠，就扩大重叠区间。要注意可能不会扩大 when 当前计算区间被当前重叠区间覆盖。否则就新开一个区间，记得用 $ans$ 加上当前重叠区间的长度。

还要注意的是，最后要加上最后一个重叠区间。代码：

三体之水滴进攻题解

---

3. 三体之三体密匙

题目

略。

题解

要知道这点就很简单了：答案就是 $n$ 的二进制的三进制。

说得简单亿点就是：将 $n$ 转化为二进制，如果当前位为 1 ，就需要加；反之则不用加。加的这个数就是 $3^k$ 。

按照上面的思路就好了。代码：

三体之三体密匙题解

---

4. 三体之智子封印三角矩阵

题目

略。

题解

别看题目这么长。看到 排列 （而且 $n≤7$ ）就什么都知道了： DFS 。

我本来想的是排列整个图形的。这只需要检查 $a_{ij}$ 是否上面两项之差。但想想好像不行，我不知道怎么排列二维。

但是发现这个图片：

它的第一行标红了。这给了我启发：只需要排列第一行，而剩下的可以推导。

所以就这样了。检查也很简单，只需要检查是否有 $1$ ~ $\frac{n(n+1)}{2}$ 中所有数就好了。

结果提交之后竟然超时了？？？好吧，放到 DEV-C++ 里调试一下。输入：

6

结果挂机了半天，什么都每输出。而题目是要输出 -1 的。输入 $7$ 也是。然后就脑洞大开，加上以下代码就 AC 了：

if (n >= 6)
{
  cout << -1;
  return 0;
}

我真天才。 代码：

三体之智子封印三角矩阵题解