APIO2013 TASKSAUTHOR

题目

简要题意

给你一些代码,每个数据要求构造一组数据,使其中一个代码AC,另一个代码TLE。

每个代码内部有一个计数器counter,如果counter>1000000则认为TLE,否则认为AC

互相伤害真开心

题解

Subtask1

用Dijkstra干Floyd。

由于Floyd 计数器的值为n3n^3,和询问和边数无关,所以直接101个点0条边1组询问就可以了(因为询问次数>=1)

数字个数为105(1+101+1+2)

Subtask2

用Floyd干BellmanFord。

注意到它的BellmanFord会在已经得到从源点到所有点的答案后结束。

计数器的值就为 (原点到所有点的最短路长度的最大值×\timesE)

那么我们就让最短路长度=v-1。

但是它的更新是按照点从0..v-1对每个点的出边进行松弛。

如果这条最短路从0到v-1就会一遍松弛结束。

所以这条最短路就得反着来。

先连n-1条边权为-1的边:n-1 到 n-2 到n-3...到0.

然后当总边数是E的时候counter就是(V1)E(V-1)E

由于有总数字个数限制,所以得控制好点数和边数使得恰好卡掉BellmanFord。

显然k组一样的询问会让counter乘k,那就放10组数据。(最多10组)

每组的查询显然是n-1到0的最短路。

当n=98的时候1051条边恰好2222个数字也能卡掉BellmanFord并且让Floyd过。

数据生成器:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
vector<pair<int,int> > e[128];

int main(){

freopen("tasksauthor2.out","w",stdout);

int n=98;

printf("%d\n",n);

for(int i=n-1;i;--i)e[i].push_back(make_pair(i-1,-1));

for(int i=1;i<=954;++i)e[rand()%n].push_back(make_pair(rand()%n,rand()%1000000));

for(int i=0;i<n;++i){

printf("%d",e[i].size());

for(auto x:e[i])printf(" %d %d",x.first,x.second);

putchar('\n');

}

printf("%d\n",10);

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

return 0;

}

Subtask3

用BellmanFord干Floyd,直接用Subtask1的数据即可。

Subtask4

用Floyd干Dijkstra。

Dijkstra每次取出优先队列队首时counter+1。

可以有负边!

第一想法:用负权环让它在圈内打转。

但是要求不能有负权环。

还有另一个办法:让一个点重复被更新多次。

由于Dijkstra是贪心,我们可以让它先沿一个错误的路径瞎走,然后再用一个“初步看上去不是更优秀的”路径再更新一遍。

类似于

图片挂了

把这样的4个点叫做一组。

然后就会根据贪心,先从1走到2,自然的走到4,从4开始继续更新,然后后面的更新完了再从1到3 ,走到4,再更新

然后4号再去作为1得到另一组。以此类推。

然后越往前的组,负边要指数级增加 类似于5,10 10,20 20,40这样。

然后如果46个点这样就能卡掉Dijkstra了。

但是有188个数字只能拿到14分。

发现点2是没用的 。

稍加修改:

图片挂了

然后3继续作为后面一组的1。

负边依然是从后往前指数级增加。

一共33个点刚好干掉。

Subtask5

用Dijkstra干BellmanFord。

由于数字个数不多,所以可以通过增加点数的方法卡。

点数300,边数340就卡掉了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
vector<pair<int,int> > e[355];

int main(){

freopen("tasksauthor5.out","w",stdout);

int n=300;

printf("%d\n",n);

for(int i=n-1;i;--i)e[i].push_back(make_pair(i-1,-1));

for(int i=1;i<=40;++i)e[0].push_back(make_pair(rand()%n,rand()%1000000));

for(int i=0;i<n;++i){

printf("%d",e[i].size());

for(auto x:e[i])printf(" %d %d",x.first,x.second);

putchar('\n');

}

printf("%d\n",10);

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

return 0;

}

Subtask6

用BellmanFord卡Dijkstra。

和Subtask4一样,只是限制更紧了。

发现Dijkstra在第六组询问的时候就挂了,就把询问次数改成6。

(第四组也可以改)

4和6:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
#define x first
#define y second

typedef pair<int,int> pii;
vector<pii> e[66];
int main(){
freopen("tasksauthor4.out","w",stdout);
int n=33,k=-1;
for(int i=n-3;i>=0;i-=2){
e[i].push_back(make_pair(i+1,k));
e[i].push_back(make_pair(i+2,2*k));
e[i+1].push_back(make_pair(i+2,2*k));

k=k*2;
}
printf("%d\n",n);
for(int i=0;i<n;++i){
printf("%d",e[i].size());
for(auto x:e[i])printf(" %d %d",x.x,x.y);
putchar('\n');
}
int m=6;
printf("%d\n",m);
for(int i=1;i<=m;++i)printf("%d %d\n",0,n-1);
return 0;
}

Subtask7

问题2。

边数至少1501,点数至少71,至多999。

限制3004,也就是点数随便,边数只能1501。

用恒过器干这个算法,也就是让它TLE。

直接随机一组数据即可如果你随机的数据能不TLE那么恭喜你中奖了

Subtask8

限制还是3004。

用这个算法干恒挂器,也就是让它不TLE。

大力随机多组数据就可以了 如果随机出来的那么恭喜你中奖了

观察代码:

答案从2到v用DFS判断是否可行,可行就结束。

所以需要尽量减少它DFS的次数。

答案是2需要是链或偶环,1501条边显然不可能。

那就让答案是3并且可以很显然的找到答案且让答案2很快的判断是不可行的。

999个点,如果每个点的颜色为1 2 3 1 2 3 1 2 3 1 2 3...。

那么可以先连出一条链1-2-3-4-5-6-7-8-9-...-999,然后再1-3-5-7-9-...-999 2-4-6-8-10-...-998,然后把多余的边从后往前删去即可。

这样答案是3就很轻松的找到,答案是2在第3个点的时候就gg了。

1
2
3
4
5
6
7
8
9
10
from random import *
import sys
sys.stdout=open("my.out","w")
v=999
e=1501
print(v,e)
for i in range(v-1):
print(i,i+1)
for i in range(503):
print(i,i+2)

并不顺利地获得100分!

文章目录
  1. 1. 简要题意
  2. 2. 题解
    1. 2.1. Subtask1
    2. 2.2. Subtask2
    3. 2.3. Subtask3
    4. 2.4. Subtask4
    5. 2.5. Subtask5
    6. 2.6. Subtask6
    7. 2.7. Subtask7
    8. 2.8. Subtask8
|

博客使用Disqus作为评论系统