一道有意思的题答构造题。题目是要你卡掉一个算法,给另一个算法过。前 6 个点是最短路的三种解法,后面 2 个点是一个染色问题。
最短路部分
一些需要了解的东西:
-
FloydWarshall 就是 \(O(V^3)\),和边无关。
-
ModifiedDijkstra 堆优化的 Dijkstra,正权图里 \(O(Q*\log V*E)\),负权图可以卡。
-
OptimizedBellmanFord \(O(QVE)\),随机图跑的快。
然后就可以开始了。
一、卡掉 Floyd (Task1,3)
最简单的部分,可以直接令 \(V=101,E=0\),Floyd 正好炸开。此时 \(T=105\),正好满足限制。
cout << "101" << endl;
for (int i=1;i<=101;i++) cout << "0" << endl;
cout << "1\n1 101\n";
二、卡掉 BellmanFord (Task2,5)
从这里本题正式开始。BellmanFord 可以用负环卡掉,或者是用自环和重边等。
-
给 Floyd 过(Task 2)
即为 \(n\le100\)。卡掉 BellmanFord 我造了几组自环和重边,一条从 \(99\) 到 \(1\) 的大长链,然后调了半天,终于把这个点卡了。
cout << "100" << endl; int tot=1100; for (int i=0;i<100;i++) { if (i!=0); else { cout << "1 0 13\n"; continue; } int u=min(tot,30)/2; cout << u+5 << " "; for (int j=1;j<=u;j++) cout << i << " " << rand()<<" "; if (tot>30) tot-=30; else tot=0; cout << i-1 << " " <<rand()-rand()<<" "; cout << i-1 << " " <<rand()-rand()<<" "; cout << i-1 << " " <<rand()-rand()<<" "; cout << i-1 << " " <<rand()-rand()<<" "; cout << i-1 << " " <<rand()-rand()<<" "; cout << endl; } cout << "10" << endl; for (int i=1;i<=10;i++) cout << "99 0\n";
-
给 Dijkstra 过(Task 5)
考虑负环。由于题目要求起点开始无负环,所以可以将起点终点从用偶数点连,奇数点做负数自环。稍微卡一下就行了。
cout << "300" << endl; for (int i=0;i<300;i++) { if (i%2==0) { if (i==298) { cout << "0" << endl; continue; } cout << "1 " << i+2 << " 1 " << endl; } else { if (i>80) cout << "1 " << i << " -1 " << endl; else cout << "2 " << i << " -1 " << i << " -1 "<< endl; } } cout << "10" << endl; for (int i=1;i<=10;i++) cout << "0 298\n";
三、卡掉 Dijkstra (Task4,6)
这里是最难的。我们知道 Dijkstra 在负权图上可能被卡掉。那么怎么卡呢?我去看了题解,这里给出一种构造方法。
每个三角形是前一个三角形边权 \(2\) 倍。构造若干个这样的三角形结构,这样傻傻的 dij 会已知沿着 \(0\) 的边走到 \(0\),然后往回走,这样就是指数级的。
然后给出 Task 4 的代码,Task 6 几乎一样,减少一下询问数即可。
cout << "33" << endl;
int tot=1;
for (int i=0;i<33;i++)
{
if (i==0)
{
cout << "0\n";
continue;
}
if (i%2==0)
{
printf("2 %d %d %d %d\n",i-2,0,i-1,2*tot);
}
else printf("1 %d %d\n",i-1,-4*tot);
if (i%2==0)
{
tot*=2;
}
}
cout << "10" << endl;
for (int i=1;i<=10;i++) cout << "32 0\n";
最短路部分到此结束。
染色问题部分
先观察三个代码。
-
RecursiveBacktracking 爆搜。
-
Gamble1 永远不会 TLE。
-
Gamble2 永远都会 TLE。
所以两个问题就是要你卡掉爆搜和给爆搜过。这部分不难。
结合 \(T\),你会发现边数是固定为 \(1501\) 的。
一、卡掉 RecursiveBacktracking (Task7)
众所周知,爆搜随便卡。然后搞个随机图就可以了。这个代码好像不用给吧。
二、给 RecursiveBacktracking 过 (Task8)
因为边数固定,点数又不能小,考虑答案 \(X=2\)。然后这就是一个二分图,直接构造一个二分图就可以过了。这个代码好像也不用给吧。
本题综合考察了对三个最短路的理解和掌握和图论知识,是个不错又奇怪的题。
我的做题记录: