Luogu

分析

前置工作

首先，神秘问题指的是染色问题。

观察代码，Floyd Warshall 是严格 $\mathcal{O}(V^3)$ 的 Floyd，Optimized Bellman Ford 是上界 $\mathcal{O}(QVM)$ 的奇怪的 Bellman Ford，Modified Dijkstra 就是堆优化的 Dijkstra。

Gamble1 一定不会 TLE，Gamble 2 一定会 TLE，Recursive Bactracking 是个爆搜。

Point 1

Floyd 最多能跑 $\sqrt[3]{1000000} = 100$ 个点的数据。于是构造 $101$ 个点、没有边的图，再随便搞一个询问，总共是$1+101+1+2=105$ 个数。

Point 2

好像不太好搞。

因为要放 Floyd 过去，所以搞 $100$ 个点。

考虑用负权边卡 Optimized Bellman Ford。每个点向外随机连一些负权边就行了，好像怎么样搞都能过。

Point 3

把 Point 1 复制过来就行了。

Point 4

Modified Dijkstra 在负权图上完全可以卡成指数级。

我们可以用这样的图形卡它：

这样子 Modified Dijkstra 会被骗到 $2$ 来，然后往下走了一会之后发现走 $1\to 2$ 更优，于是它就被卡了。

多搞几个这样的图形套起来就好了。

Point 5

因为有 Modified Dijkstra 的存在，我们不能像 Point 2 那样乱造负权边了。

不妨让每一个询问都从 $0$ 到 $1$。于是可以从 $0$ 到 $1$ 连一条边权任意的边，剩下的 $298$ 个点每个点连出一个负权自环，然后再让几个点搞一堆重边就能卡掉 Optimized Bellman Ford 了。

Point 6

想法和 Point 4 是一样的，然而 $T$ 比 Point 4 小了 $14$，需要适当的调下参。

Point 7

去掉 $n$ 和 $m$ 后，还剩下$3002$个数，对应$1501$条边。

众所周知，爆搜随便怎么卡，所以随机生成一个$1501$条边的图就能过了。

Point 8

我们要把爆搜放过去。

考虑造一个二分图，然后只在异色点间连边，这样子就跑得飞快了。

代码

Point 1

int main() {
    freopen("1.txt","w",stdout);
    puts("101");
    for (re int i=1;i<=101;++i) puts("0");
    puts("1"); puts("1 2");
    return 0;
}

Point 2

int main() {
    freopen("2.txt","w",stdout);
    puts("100");
    for (re int i=0;i<20;++i) {
        printf("11");
        for (re int j=1;j<=11;++j)
            printf(" %d %d",rand()%100,-1);
        putchar('\n');
    }
    for (re int i=0;i<80;++i) {
        printf("10");
        for (re int j=1;j<=10;++j)
            printf(" %d %d",rand()%100,-1);
        putchar('\n');
    }
    puts("10");
    for (re int i=1;i<=10;++i) puts("0 99");
    return 0;
}

Point 3

int main() {
    freopen("3.txt","w",stdout);
    puts("101");
    for (re int i=1;i<=101;++i) puts("0");
    puts("1"); puts("1 2");
    return 0;
}

Point 4

int main() {
    freopen("4.txt","w",stdout);
    int pw=65536;
    puts("33");
    printf("2 1 %d 2 0\n",pw);
    for (re int i=1;i<32;++i) {
        if (i&1) printf("1 %d %d\n",i+1,-pw*2),pw/=2;
        else printf("2 %d %d %d 0\n",i+1,pw,i+2);
    }
    puts("0");
    puts("6");
    for (re int i=1;i<=6;++i) puts("0 32");
    return 0;
}

Point 5

int main() {
    freopen("5.txt","w",stdout);
    puts("300");
    puts("1 1 1"); puts("0");
    for (re int i=2;i<300;++i) {
        if (i<=5) {
            printf("11 %d -1",i);
            for (re int j=1;j<=10;++j) printf(" %d -1",i);
            putchar('\n');
        }
        else printf("1 %d -1\n",i);
    }
    puts("10");
    for (re int i=1;i<=10;++i) puts("0 1");
    return 0;
}

Point 6

我做Point 4的时候顺便把Point 6一起写了，所以两个点的代码是一样的。

int main() {
    freopen("6.txt","w",stdout);
    int pw=65536;
    puts("33");
    printf("2 1 %d 2 0\n",pw);
    for (re int i=1;i<32;++i) {
        if (i&1) printf("1 %d %d\n",i+1,-pw*2),pw/=2;
        else printf("2 %d %d %d 0\n",i+1,pw,i+2);
    }
    puts("0");
    puts("6");
    for (re int i=1;i<=6;++i) puts("0 32");
    return 0;
}

Point 7

int G[75][75];

int main() {
    freopen("7.txt","w",stdout);
    puts("71 1501");
    for (re int i=1;i<=1501;++i) {
        int u=rand()%71,v=rand()%71;
        while (G[u][v]||u==v) u=rand()%71,v=rand()%71;
        G[u][v]=G[v][u]=1; printf("%d %d\n",u,v);
    }
    return 0;
}

Point 8

int c[1000],cnt=0;

int main() {
    freopen("8.txt","w",stdout);
    puts("100 1501");
    for (re int i=0;i<100;++i) c[i]=rand()&1;
    for (re int i=0;i<100;++i)
        for (re int j=i+1;j<100;++j) {
            if (c[i]==c[j]) continue;
            printf("%d %d\n",i,j);
            ++cnt; if (cnt==1501) return 0;
        }
    return 0;
}