出题人 APIO2013

WZH2026-07-112026-07-27

[APIO2013] 出题人

难得我会写的构造。

题目链接： [APIO2013] 出题人。

题目描述：

当今世界上各类程序设计竞赛层出不穷。而设计一场好比赛绝非易事，比如给题目设计测试数据就是一项挑战。一组好的测试数据需要对不同的程序有区分度：满足所有要求的程序自然应该得到满分，而那些貌似正确的程序则会在某些特殊数据上出错。

在本题中，你在比赛中的角色反转啦！作为一名久经百战的程序员，你将帮助 Happy Programmer Contest 的命题委员会设计这次比赛的测试数据。本次比赛命题委员会选择了两个图论问题，分为 $8$ 个子任务。委员会写了一些貌似可以解决这些子任务的代码。在给任务设计数据的时候，命题委员会期望其中的一些源程序能够得到满分，而另外的一些则只能得到 $0$ 分或者少许的部分分。现在你将会获得这些源程序（C, C++, Pascal 版本）。对于每个子任务，你需要去产生一组数据 $X$ 使得它能将该任务给定的 $2$ 种源程序 $A$ 和 $B$ 区分开来。更具体地说，生成的数据必须满足如下两个条件:

输入 $X$ 对于源程序 $A$ 一定不会出现超出时间限制（TLE）的问题。

输入 $X$ 一定会导致源程序 $B$ 产生超出时间限制的问题。

此外,命题委员喜欢较小规模的测试数据，希望测试数据最好能够包含不超过 $T$ 个整数。

本题中只关心源程序 $A$ 和 $B$ 是否超时，不关心是否结果正确。

命题委员会选择了单源最短路（SSSP）以及一个被称之为神秘问题（Mystery）的两个图论问题来作为比赛的题目。我们将命题委员会完成的伪代码列在了附录中，而具体的 C、C++ 和 Pascal 源程序被我们放在了下发的文件当中。

子任务

参见下表。表中每一行描述了一个子任务。其中前六个子任务与单源最短路相关，子任务 7,8 与神秘问题相关。每个任务所占分数见下表。

对于每个子任务，你的程序给出的输入 $X$ 需要能够将源程序 $A$ 和 $B$ 区分开来，这有这样你才能够得到相应的分数。具体说来，你的分数将由输入 $X$ 中数的个数决定。假设 $X$ 中包含了 $F$ 个整数，子任务的满分为 $S,T$ 是该任务的目标大小，则该测试点的分数将由下式给出:

$S \times \min\{T / F, 1\}$

也就是说，如果你的测试数据 $X$ 中含有不超过 $T$ 个整数，则你将得到该任务的全部得分。

你需要把你的 $8$ 个测试数据命名为 1.txt ~ 8.txt。对于每个子任务 $X$ ，评测系统将根据如下步骤来确定你将会得到多少分:

如果未提交数据，则不得分；

若数据不满足输入格式要求，则不得分；

对源程序 $A$ 运行输入，若发生超时现象，则不得分；

对源程序 $B$ 运行输入，若发生超时现象，则按照前文所述的公式给出该测试点的分数。

题目提供的所有源代码均会维护一个计数器来统计程序的操作次数。在源程序的运行过程中，当该计数器超过了 $10^6$ 次时，那么我们认为程序运行超时。

问题 1：单源最短路（SSSP）

给定一个带权有向图 $G$ ，以及 $G$ 中的两个节点 $s$ 与 $t$ ，令 $p(s, t)$ 为 $G$ 中从 $s$ 至 $t$ 的最短路长度。如果 $s$ 与 $t$ 不连通，则认为 $p(s, t)=10^9$ 。在本题中，输入为图 $G$ 以及 $Q$ 个询问 $(s_1, t_1), (s_2, t_2), \dots, (s_Q, t_Q)$ 。输出则是对这 $Q$ 个询问的相应输出 $p(s_1, t_1), p(s_2 , t_2), \cdots, p(s_Q, t_Q)$ 。

问题 2：神秘问题

给定一个包含 $V$ 个节点 $E$ 条边的无向图 $G$ ，要求将所有的节点进行编号（编号范围为 $[0, X-1]$ ），使得所有直接相连的节点均有不同的编号。找出符合题意的最小的 $X$ 。

输入格式

问题 1

输入数据包含两部分，其中第一部分使用邻接表来描述带权有向图 $G$ 。第二部分则描述对 $G$ 的最短路径的查询。

数据第一部分的第一行包含一个整数 $V$ ，表示 $G$ 中点的个数，所有点的编号为 $0, 1, \cdots, V - 1$ 。

接下来 $V$ 行，每行描述一个点的所有边。行中的第一个整数 $n_i$ 描述了节点 $i$ 的出边数量，接下来有 $n_i$ 个整数对 $(j, w)$ 表示有一条从 $i$ 到 $j$ ，边权为 $w$ 的边。

数据第二部分的第一行包含一个整数 $Q$ ，表示询问的组数。

接下来 $Q$ 行，第 $k$ 行包含两个整数 $s_k, t_k$ ，为该询问对应的起点与终点位置。

同一行中任意两个相邻的整数均需要至少一个空格将他们分开。除此之外，数据还需满足如下条件:

$0 < V \leq 300$ ， $n_i$ 是一个非负整数， $0 \leq j < V$ ， $\lvert w \rvert < 10^6$ ， $0 \leq \sum\limits_{i = 0}^{V-1} n_i \leq 5000$ ， $0 < Q \leq 10$ ， $0 \leq s_k < V, 0 \leq t_k < V$ ；

图中没有负权圈。

问题 2

输入数据的第一行包含两个整数 $V$ 和 $E$ 。

接下来 $E$ 行,每行两个整数 $a, b$ ，表示 $a$ 与 $b$ 在 $G$ 中直接相连。此外,输入数据应满足如下限制条件:

$70 < V < 1000$ ， $1500 < E < 10^6$ ；

对于所有的边 $(a, b)$ ，有 $a \neq b, 0 \leq a < V, 0 \leq b < V$ ，不会重复描述一条边。

伪代码：

接下来是我们提供的所有程序的伪代码；变量 counter 近似描述出了程序的运行时间。评测时将会使用这些伪代码的 C++ 版本来进行评测。

FloydWarshall
1
2
3
4
5
6
7
8
9
// pre-condition: the graph is stored in an adjacency matrix M
counter = 0
for k = 0 to V-1
    for i = 0 to V-1
        for j = 0 to V-1
            increase counter by 1;
            M[i][j] = min(M[i][j], M[i][k] + M[k][j]);
for each query p(s,t)
    output M[s][t];
OptimizedBellmanFord
1
2
3
4
5
6
7
8
9
10
11
12
13
14
// pre-condition: the graph is stored in an adjacency list L
counter = 0
for each query p(s,t);
    dist[s] = 0; // s is the source vertex
    loop V-1 times
        change = false;
        for each edge (u,v) in L
            increase counter by 1;
            if dist[u] + weight(u,v) < dist[v]
                dist[v] = dist[u] + weight(u,v);
                change = true;
        if change is false // this is the ’optimized’ Bellman Ford
            break from the outermost loop;
    output dist[t];
ModifiedDijkstra
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
// pre-condition: the graph is stored in an adjacency list L
counter = 0;
for each query p(s,t)
    dist[s] = 0;
    pq.push(pair(0, s)); // pq is a priority queue
    while pq is not empty
        increase counter by 1;
        (d, u) = the top element of pq;
        remove the top element from pq;
        if (d == dist[u])
            for each edge (u,v) in L
                if (dist[u] + weight(u,v) ) < dist[v]
                    dist[v] = dist[u] + weight(u,v);
                    insert pair (dist[v], v) into the pq;
    output dist[t];
Gamble1
1
2
3
Sets X = V;
labels vertex i in [0..V-1] with i;
Sets counter = 0; // will never get TLE
Gamble2
1
2
3
Sets X = V;
labels vertex i in [0..V-1] with i;
Sets counter = 1000001; // force this to get TLE
RecursiveBacktracking
1
2
3
4
5
This algorithm tries X from 2 to V one by one and stops at the first valid X.  
For each X, the backtracking routine label vertex 0 with 0, then for each vertex u that has been > assigned a label, the backtracking routine tries to assign 
the smallest possible label up to label X-1 to its neighbor v, and backtracks if necessary.  
// Please check RecursiveBacktracking.cpp/pas to see 
// the exact lines where the iteration counter is increased by 1

代码：

FloydWarshall

#include <algorithm>
#include <cstdio>
using namespace std;

int i, j, k, V, n, w, M[300][300], counter, Q, s, t;

int main() {
  scanf("%d", &V);
  for (i = 0; i < V; i++)
    for (j = i+1; j < V; j++)
      M[i][j] = M[j][i] = 1000000000;
  for (i = 0; i < V; i++)
    M[i][i] = 0;

  for (i = 0; i < V; i++) {
    scanf("%d", &n);
    while (n--) {
      scanf("%d %d", &j, &w);
      M[i][j] = min(M[i][j], w);
    }
  }

  counter = 0;
  for (k = 0; k < V; k++)
    for (i = 0; i < V; i++)
      for (j = 0; j < V; j++) {
        counter++;
        if (counter > 1000000) {
          printf("TLE because iteration counter > 1000000\n");
          return 1;
        }
        M[i][j] = min(M[i][j], M[i][k] + M[k][j]);
      }

  scanf("%d", &Q);
  while (Q--) {
    scanf("%d %d", &s, &t);
    printf("%d\n", M[s][t]);
  }

  printf("The value of counter is: %d\n", counter);
  return 0;
}

ModifiedDijkstra

#include <algorithm>
#include <cstdio>
#include <iostream>
#include <vector>
#include <queue>
using namespace std;

typedef pair<int, int> IntPair;
typedef vector<IntPair> VectorIntPair;

#define INF 1000000000

int i, j, V, n, w, counter, Q, s, t, d, u;
vector<VectorIntPair> AdjList;

// scroll down to line 92 for the
// short C++ implementation (with STL priority_queue)










































































int main() {
  scanf("%d", &V);
  AdjList.assign(V, VectorIntPair());
  for (i = 0; i < V; i++) {
    scanf("%d", &n);
    while (n--) {
      scanf("%d %d", &j, &w);
      AdjList[i].push_back(IntPair(j, w));

    }
  }

  counter = 0;
  scanf("%d", &Q);
  while (Q--) {
    scanf("%d %d", &s, &t);

    vector<int> dist(V, INF);
    dist[s] = 0;
    priority_queue< IntPair, vector<IntPair>, greater<IntPair> > pq;
    pq.push(IntPair(0, s));
    while (!pq.empty()) {
      counter++;
      if (counter > 1000000) {
        printf("TLE because iteration counter > 1000000\n");
        return 1;
      }

      IntPair front = pq.top(); pq.pop();
      d = front.first; u = front.second;
      if (d == dist[u]) {
        for (j = 0; j < (int)AdjList[u].size(); j++) {
          IntPair v = AdjList[u][j];
          if (dist[u] + v.second < dist[v.first]) {
            dist[v.first] = dist[u] + v.second;
            pq.push(IntPair(dist[v.first], v.first));
          }
        }
      }
    }

    printf("%d\n", dist[t]);
  }

  printf("The value of counter is: %d\n", counter);
  return 0;
}

OptimizedBellmanFord

#include <algorithm>
#include <cstdio>
#include <iostream>
#include <vector>
using namespace std;

typedef pair<int, int> IntPair;
typedef vector<IntPair> VectorIntPair;

#define INF 1000000000

int i, j, u, V, n, w, Q, counter, s, t;
vector<VectorIntPair> AdjList;
bool change;

int main() {
  scanf("%d", &V);
  AdjList.assign(V, VectorIntPair());
  for (i = 0; i < V; i++) {
    scanf("%d", &n);
    while (n--) {
      scanf("%d %d", &j, &w);
      AdjList[i].push_back(IntPair(j, w));


    }
  }

  counter = 0;
  scanf("%d", &Q);
  while (Q--) {
    scanf("%d %d", &s, &t);
    vector<int> dist(V, INF);
    dist[s] = 0;

    for (i = 0; i < V-1; i++) {
      change = false;
      for (u = 0; u < V; u++)
        for (j = 0; j < (int)AdjList[u].size(); j++) {
          counter++;
          if (counter > 1000000) {
            printf("TLE because iteration counter > 1000000\n");
            return 1;
          }

          IntPair v = AdjList[u][j];
          
          if (dist[u] + v.second < dist[v.first]) {
            dist[v.first] = dist[u] + v.second;
            change = true;
          }
        }

      if (!change) // the optimized BellmanFord
        break;
    }

    printf("%d\n", dist[t]);
  }

  printf("The value of counter is: %d\n", counter);
  return 0;
}

Gamble1

#include <cstdio>
using namespace std;

int i, a, b, V, E;

int main() {
  scanf("%d %d", &V, &E);
  for (i = 0; i < E; i++)
    scanf("%d %d", &a, &b);

  printf("%d\n", V);
  printf("%d", 0);
  for (i = 1; i < V; i++)
    printf(" %d", i);
  printf("\n");

  printf("The value of counter is: %d\n", 0);
  return 0; // will never get TLE
}

Gamble2

#include <cstdio>
using namespace std;

int i, a, b, V, E;

int main() {
  scanf("%d %d", &V, &E);
  for (i = 0; i < E; i++)
    scanf("%d %d", &a, &b);

  printf("%d\n", V);
  printf("%d", 0);
  for (i = 1; i < V; i++)
    printf(" %d", i);
  printf("\n");

  printf("TLE because iteration counter > 1000000\n");
  return 1; // this is TLE
}

RecursiveBacktracking

#include <algorithm>
#include <cstdio>
#include <vector>
using namespace std;

typedef vector<int> vi;

#define INF 1000000000

int i, a, b, V, E, counter, X;
vector<vi> AdjList;
vi cur, ans;
bool found;

void backtrack(int u, int label) {
  if (found) return;



  counter++;
  cur[u] = label; // assign label to u
  if (u == V - 1) { // done
    found = true;
    ans.assign(V, 0);
    for (int j = 0; j < V; j++)
      ans[j] = cur[j];
    return;
  }

  // explore neighbors
  vi ok(X, 1);

  for (int j = 0; j < (int)AdjList[u+1].size(); j++) {
    counter++;
    if (counter > 1000000)
      return;

    int v = AdjList[u+1][j];
    if (cur[v] != -1)
      ok[cur[v]] = false;
  }

  for (int j = 0; j < X; j++)
    if (ok[j])
      backtrack(u+1, j);
}

int main() {
  scanf("%d %d", &V, &E);
  AdjList.assign(V, vi());
  for (i = 0; i < E; i++) {
    scanf("%d %d", &a, &b);
    AdjList[a].push_back(b);
    AdjList[b].push_back(a);
  }

  found = false;
  counter = 0;
  for (X = 2; X <= V; X++) {
    cur.assign(V, -1);
    backtrack(0, 0);
    if (found)
      break;

    if (counter > 1000000) {
      printf("TLE\n");
      return 1;
    }
  }

  printf("%d\n", X);
  printf("%d", ans[0]);
  for (i = 1; i < V; i++)
    printf(" %d", ans[i]);
  printf("\n");

  printf("The value of counter is: %d\n", counter);
  return 0;
}

Test 1: Dijkstra -> Floyd

Floyd 算法复杂度恒定 $O(V^3)$ ,所以我们可以构造一个 $0$ 个边的 $100$ 个点的图，这样我们就可以在 $F=104$ 个数字内卡掉 Floyd 。

代码：

#include <bits/stdc++.h>
using namespace std;
int main(){
    freopen("1.txt","w",stdout);
    int n=101;
    cout<<n<<"\n";
    for(int i=1;i<=n;i++){
        cout<<0<<"\n";
    }
    cout<<1<<"\n"<<"1 2"<<"\n";
    return 0;
}

Test 2: Floyd -> Bellman

Floyd 算法复杂度恒定 $O(V^3)$ ，所以只要 $V\le 100$ ， Floyd 就能过。

Bellman 算法复杂度 $O(VE)$ ，想要卡到上界可以通过让 Bellman 每轮只更新一条边的贡献，即恶意操控边的顺序。

这样就可以卡掉 Bellman 了。

代码：

#include<bits/stdc++.h>
using namespace std;
#define pii  pair<int,int> 
#define mk make_pair
#define pb push_back
signed main(){
	freopen("2.txt","w",stdout);
	int tot=(2222-22-294-5)/2;
	int n=100;
	cout<<n<<"\n";
	cout<<"0\n";
	for(int i=1;i<n;++i){
//	  cout<<"1 ";
//	  cout<<i-1<<" 1\n";
	  vector<pii>v;
	  v.pb(mk(i-1,1));
	  for(int j=0;j<n&&tot;++j){
		if(j==i-1||j==i)continue;
		v.pb(mk(j,666));
		--tot;
	  }
	  cout<<v.size()<<"\n";
	  for(pii p:v)cout<<p.first<<" "<<p.second<<" ";
	  cout<<"\n";
	}
	cout<<"10\n";
	for(int i=1;i<=10;++i)cout<<n-1<<" 0"<<"\n";
	return 0;
}

Test 3: Bellman -> Floyd

跟 Test 1 一样。

Test 4: Floyd -> Dijkstra

观察 Dijkstra 的代码，发现出题人给定的~~不要 $&.%…#@#~~ 代码中忽略了 priority_queue 的复杂度！

也就是说，在正权图中， Dijkstra 的复杂度为 $O(V)$ 。

那么为了卡掉 Dijkstra ，只能通过引入负权来解决。

首先，在负权图中的 Dijkstra 相当于一个启发式搜索，换句话说，也就是贪心。

贪心最大的问题是目光短浅，只考虑当下。也就是说，我可以通过引入负权图来使得当下不优秀的选择在以后会变成更优的选择，并来优化之前的最优选择。

把这个东西的结构写出来长这样：

1
2
3

1 0 0
1 2 1
2 0 -2

这是一个三角的结构，可以发现如果在 $0$ 号节点会导致 $k$ 次计数，那么整个结构就会有至少 $2k$ 次计数。

那么把这个结构嵌套在一起 $k$ 次， Dijkstra 就会被卡到 $O(2^k)$ ！

我一开始这样想，发现这样做边权的增长也是 $O(2^k)$ 的，当时我没有想到有多测，并且这个结构的常数极大。事实上边权迭代到 $32768$ 就已经可以了。

文件：

32
1 31 1
2 0 0 2 1
1 0 -2
2 1 0 4 2
1 1 -4
2 3 0 6 4
1 3 -8
2 5 0 8 8
1 5 -16
2 7 0 10 16
1 7 -32
2 9 0 12 32
1 9 -64
2 11 0 14 64
1 11 -128
2 13 0 16 128
1 13 -256
2 15 0 18 256
1 15 -512
2 17 0 20 512
1 17 -1024
2 19 0 22 1024
1 19 -2048
2 21 0 24 2048
1 21 -4096
2 23 0 26 4096
1 23 -8192
2 25 0 28 8192
1 25 -16384
2 27 0 30 16384
1 27 -32768
0

10
29 0
29 0
29 0
29 0
29 0
29 0
29 0
29 0
29 0
29 0

这样做有 $F=146$ ，可以通过。

Test 5: Dijkstra -> Bellman

同 Test 2 。

Test 6: Bellman -> Dijkstra

如果你看了 Test4 的 counter 计数，就会发现 counter>1300000 ，那么砍掉两次询问后有 counter>1040000 且 $F=142$ ，可以通过。

Test 7: MustAccepted -> Search

这个和后面的 Test 8 都太水了，甚至不如 Test 2&5 ，结果分数还这么高。

这里的 Gamble1 是一个一定不超时的程序，而 Search 是一个暴力程序，思想是暴力枚举 $X$ 然后枚举所有可能的染色方案。

容易发现要卡掉 Search 只需要让 $X$ 比较大就行，因为每枚举一个 $X$ 就要遍历所有可能性。

那么完全图是一个很好的选择。

通过计算可以得到 $K_{55}$ 有 $1485$ 条边，剩下的边随便设置也能卡掉 Search 。

代码：

#include <bits/stdc++.h>
using namespace std;
const int N=110;
int main(){
  freopen("7.txt","w",stdout);
  cout<<"71 1501\n";
  int cnt=0;
  for(int i=0;i<55;i++)for(int j=0;j<55;j++){
    if(i>=j)continue;
    cnt++;
    cout<<i<<' '<<j<<"\n";
  }
  for(int i=55;i<71&&cnt<1501;i++)for(int j=55;j<71&&cnt<1501;j++){
    if(i>=j)continue;
    cnt++;
    cout<<i<<' '<<j<<"\n";
  }
    return 0;
}

Test 8: Search -> MustUnaccepted

这里的 Gamble2 是一个一定超时的程序，所以这里我们只需要让 Search 通过就行。

通过 Test 7 的分析，我们发现答案 $X$ 的大小和搜索时间有关。

那么这里只需要让 $X$ 最小就行。

$X$ 最小显然为 $2$ ，此时为一个二分图。

那么只需要构造一个左边 $V_1$ 右边 $V_2$ 个的满足 $V_1+V_2>70$ 的二分图就行。

我这里选择完全二分图，刚好 $1501=19\times 79$ ，那么只需要将左边 $19$ 个点和 $79$ 个右侧的点连边就行。

代码：

#include <bits/stdc++.h>
using namespace std;
const int N=110;
int main(){
  freopen("8.txt","w",stdout);
  cout<<"98 1501\n";
    for(int i=0;i<19;i++){
        for(int j=19;j<98;j++){
            cout<<i<<' '<<j<<"\n";
        }
    }
    return 0;
}

“为什么要攀登？因为山就在那里。”