UOJ #56. 【WC2014】非确定机
分类:
IT文章
•
2022-09-03 09:51:12
题意大意：给出一个输出文件，求输入。
1.满足所求的输入文件是一张图，n个点，m条边，所用算法是k（k在给出的输出文件中给出了）
2.算法是图论算法？!k基本上→两位数组成，若十位数相同，说明基本算法可能是相同的。
3.给出一个可执行文件，可以在终端中运行自己造出的数据，从而猜测算法。
4.你所给出的图不能有重边，但可以有自环，边权<=2*10^4
5.p是在给出的输出文件中给定的一个参数，这个参数由你所造出的图由某种计算方式所决定的。
先挖坑。。。感觉是一个很有意思的构造+XJB乱搞题，假设是WC的话，我能搞2个半个小时提答，那么。。。。。
闷声滚大粗
Notice:这题直接看题解没意思，还是要先做题。。。
(1)喜闻乐见的01矩阵，再加上样例的那个例子，就是A(i,j)表示是否有i向j连边的意思。
![]()
1 #include<iostream>
2 #include<cstdio>
3 #include<algorithm>
4 #include<vector>
5 #include<cstdlib>
6 #include<cmath>
7 #include<cstring>
8 using namespace std;
9 #define maxn 10010
10 #define llg long long
11 #define yyj(a) freopen(a".in","r",stdin),freopen(a".out","w",stdout);
12 llg n,m;
13 int main()
14 {
15 yyj("nm1");
16 cin>>n;
17 llg tot=0;
18 for (llg i=1;i<=n;i++)
19 for (llg j=1;j<=n;j++)
20 {
21 llg x;
22 //tot++;
23 cin>>x;
24 if (x) tot++;
25 if (x) cout<<i<<" "<<j<<" 1"<<endl;
26 }
27 cout<<tot;
28 return 0;
29 }
View Code
(2)算法编号k=10，新的图论算法，随便自己造个图用给出的程序试一试发现就是以1为原点的单源最短路，p就是边的数目。
考虑如何构造：
1.显然一号点向每个点连一条所要求的权值的边就满足了最短路的条件，但是边数只有n-1条，即p'!=p,可以get 4分。
2.按照上面的做法打完拿了程序一测正确性发现GG，我之前没看到边权<=2*10^4，好吧，按照所要求的最短路长度排序，按照从小到达的顺序处理，如果小于2*10^4直接和一号点相连，不然找到之前的处理过的点，而且当前点要求的权值减去处理过的点的权值小于等于2*10^4中权值最小的那一个连边，考虑到p的限制，在已经处理过的最小权值的可连边的点之后的点再向待处理的点连出的边将不对答案产生影响。
![]()
1 #include<iostream>
2 #include<cstdio>
3 #include<algorithm>
4 #include<vector>
5 #include<cstdlib>
6 #include<cmath>
7 #include<cstring>
8 using namespace std;
9 #define maxn 10010
10 #define llg long long
11 #define yyj(a) freopen(a".in","r",stdin),freopen(a".out","w",stdout);
12 llg n,m,p,k;
13 bool d[maxn][maxn];
14
15 struct node
16 {
17 llg p,val;
18 }a[maxn];
19 bool cmp(const node&a,const node&b) {return a.val<b.val;}
20 int main()
21 {
22 yyj("nm2");
23 cin>>n>>k>>p;
24 for (llg i=1;i<=n;i++)
25 {
26 a[i].p=i;
27 cin>>a[i].val;
28 }
29 sort(a+1,a+n+1,cmp);
30 p-=n;
31 p++;
32 for (llg i=2;i<=n;i++)
33 {
34 llg j;
35 for (j=1;j<i;j++)
36 if (a[i].val-a[j].val<=20000)
37 {
38 cout<<a[j].p<<" "<<a[i].p<<" "<<a[i].val-a[j].val<<endl;
39 break;
40 }
41 j++;
42 while (p>0 && j<i)
43 {
44 p--;
45 cout<<a[j].p<<" "<<a[i].p<<" "<<20000<<endl;
46 j++;
47 }
48 }
49 return 0;
50 }
View Code
(3)算法编号k=11，嗯，类似于最短路，但是这个点还是要多试试，一开始我认为是求到每个点的不同路径的最短路的数目，我靠不会构啊，再去试了几组数据之后发现：
所求为所有点之间的最短路，但是和边权没有关系，即边权默认为1，p为边数。
沉思。。。。。没办法了打一个暴力，想到优化显然矩阵中为1点的相当于所对应的(x,y)一定连了一条边。再一看有400个1。p也是400，在想想这很显然啊，连出了所有为1的边之后答案就确定了。
![]()
1 #include<iostream>
2 #include<cstdio>
3 #include<algorithm>
4 #include<vector>
5 #include<cstdlib>
6 #include<cmath>
7 #include<cstring>
8 using namespace std;
9 #define maxn 10010
10 #define llg long long
11 #define yyj(a) freopen(a".in","r",stdin),freopen(a".out","w",stdout);
12 llg n,m,p,k;
13 bool d[maxn][maxn];
14
15 struct node
16 {
17 llg p,val;
18 }a[maxn];
19 bool cmp(const node&a,const node&b) {return a.val<b.val;}
20 int main()
21 {
22 yyj("nm3");
23 cin>>n>>k>>p;
24 cout<<n<<" "<<p<<" "<<k<<endl;
25 for (llg i=1;i<=n;i++)
26 {
27 for (llg j=1;j<=n;j++)
28 {
29 llg x;
30 cin>>x;
31 if (x==1) cout<<i<<" "<<j<<" 2333"<<endl;
32 }
33 }
34 return 0;
35 }
View Code
(4)算法编号k=12，最短路。。。似乎是次短路欸，但是第一个点居然有权值，这会在一开始迷惑住我们，但是多试几次就会发现点1的次短路是经过点1的最短环的长度，那么我们考虑构造一个装置增长每个点的路径的长度，这样就类似于第k=10的算法了。
![]()
1 #include<iostream>
2 #include<cstdio>
3 #include<algorithm>
4 #include<vector>
5 #include<cstdlib>
6 #include<cmath>
7 #include<cstring>
8 using namespace std;
9 #define maxn 10010
10 #define llg long long
11 #define yyj(a) freopen(a".in","r",stdin),freopen(a".out","w",stdout);
12 int d[10202],v[10202],q[10202];
13 int i,j,k,n=10000,m=0,P=379;
14 int main()
15 {
16 yyj("nm4");
17 scanf("%*d %*d %*d");
18 for (i=1;i<=n;i++){scanf("%d",&d[i]);if (d[i]==112374) P=i;}
19 for (i=2;i<=n;i++)
20 if (i != P) d[i]-=18000;
21 int tmp=d[1];
22 j=1; d[1]=0;
23 for (int x=1; x<=6; x++)
24 {
25 k=j; q[j]=1;
26 for (i=1;i<=10000;i++)
27 if (i!=P && d[i]>d[j] && d[i]<=d[j]+20000)
28 {
29 if (d[i] > d[k]) k=i;
30 printf("%d %d %d
",j,i,d[i]-d[j]),m++;
31 if (j==1) v[i]=1;
32 }
33 j=k;
34 }
35 d[1]=tmp;
36 for (i=1;i<=n;i++)
37 if (d[i]<d[1] && d[i]>d[1]-10000) break;
38 printf("%d %d %d
",i,1,d[1]-d[i]);
39 printf("%d %d %d
",1,P,d[P]-d[1]);
40 m += 2;
41 for (i=1;i<=n;i++)if (v[i]) printf("%d %d %d
",P,i,d[i]+18000-d[P]+d[1]),m++;
42 for (i=1;i<=n;i++)
43 if (!q[i])
44 for (j=1; j<=n; j++)
45 if (d[i]+2000>d[j])
46 {
47 printf("%d %d %d
",i,j,20000);
48 m++;
49 if (m==20000) return 0;
50 }
51 return 0;
52 }
View Code
(5)算法编号k=20，新的算法，既然是2.0那么应该是送分的，造几组数据之后发现答案输出了n个数，每一个数都小于n，并且有很多是相同的。考虑一下，这不就是强连通分量么，每一个数字表示他这个点所属于的这个强连通分量的最小点的编号，p是强连通分量的数目，给出的输出中也只有p个不同的数字。那就很好做了，既然和边数没有关系，把属于同一个强连通分量的点拉出来连成一个环就可以了。
![]()
1 #include<iostream>
2 #include<cstdio>
3 #include<algorithm>
4 #include<vector>
5 #include<cstdlib>
6 #include<cmath>
7 #include<cstring>
8 using namespace std;
9 #define maxn 10010
10 #define llg long long
11 #define yyj(a) freopen(a".in","r",stdin),freopen(a".out","w",stdout);
12 llg n,m,k,p,tot,c[maxn];
13
14 vector<llg>a[maxn];
15
16 int main()
17 {
18 yyj("nm5");
19 cin>>n>>k>>p;
20 for (llg i=1;i<=n;i++) cin>>c[i];
21 for (llg i=1;i<=n;i++) a[c[i]].push_back(i);
22 for (llg x=1;x<=n;x++)
23 {
24 llg w=a[x].size();
25 for (llg i=1;i<w;i++)
26 {
27 tot++;
28 cout<<a[x][i]<<" "<<a[x][i-1]<<" 2333"<<endl;
29 }
30 if (w>=2)
31 {
32 cout<<a[x][0]<<" "<<a[x][w-1]<<" 2333"<<endl;
33 tot++;
34 }
35 }
36 cout<<tot;
37 return 0;
38 }
View Code
(6))算法编号k=21，这个p是个什么鬼，试了试发现之和图的构型有关和权值无关，那么n=8，管他是什么，爆搜就可以了。（考你会不会用终端）
![]()
1 8 8 21
2 8 5 1
3 5 8 1
4 5 4 1
5 4 5 1
6 7 1 1
7 1 7 1
8 8 4 1
9 4 8 1
View Code
(7)算法编号k=22，又和上面是一个节奏，这次n更大了，GG。。1分走人（挖坑）
![]()
1 20 0 22
2 2333
View Code
(8)算法编号k=30，以为是个水的，但看了数据真是一脸懵逼，搞了好久才发现求的是这个图的匹配数量(一般图最大匹配),没什么技术含量，p=61*100，下面那一行给的是匹配数，那么构一个前面61个点，后面100个点(及所有点)的图出来即可。(一共一百个点）
![]()
1 #include<iostream>
2 #include<cstdio>
3 #include<algorithm>
4 #include<vector>
5 #include<cstdlib>
6 #include<cmath>
7 #include<cstring>
8 using namespace std;
9 #define maxn 10010
10 #define llg long long
11 #define yyj(a) freopen(a".in","r",stdin),freopen(a".out","w",stdout);
12 llg n,m,k,p;
13 int main()
14 {
15 yyj("nm8");
16 cin>>n>>k>>p;
17 cout<<n<<" "<<p<<" "<<k<<endl;
18 for (llg i=1;i<=61;i++)
19 for (llg j=1;j<=100;j++)
20 {
21 cout<<i<<" "<<j<<" 2333"<<endl;
22 }
23 return 0;
24 }
View Code
(9)算法编号k=31，把一个点拆成了两个点之后（最小路径覆盖的那种拆分），然后二分图匹配之后对应i位置输出的是匹配到右边的第j个。可是方案不止一种.
以上口胡，求的是字典序最小的排列,使得(i,)有边。尝试发现是字典序最小的。
![]()
1 #include<iostream>
2 #include<cstdio>
3 #include<algorithm>
4 #include<vector>
5 #include<cstdlib>
6 #include<cmath>
7 #include<cstring>
8 using namespace std;
9 #define llg long long
10 #define maxn 2010
11 #define yyj(a) freopen(a".in","r",stdin),freopen(a".out","w",stdout);
12 llg n,m,p,f[maxn],k[maxn][maxn];
13 int main()
14 {
15 yyj("nm9");
16 scanf("%lld %*d %lld", &n, &m);
17 for (llg i=1;i<=n;i++) scanf("%lld",&f[i]);
18 for (llg i=1;i<=n; i++)
19 {
20 for (llg j=1;j<i;j++) printf("%lld %lld 1
",i,f[j]), k[i][f[j]]=1;
21 for (llg j=f[i];j<=100; j++) if (!k[i][j]) printf("%lld %lld 1
", i, j);
22 }
23 return 0;
24 }
View Code
(10)算法k=13，不要问我是怎么奇妙的get到了这个点的意思(大概是spfa选手的缘故？），似乎就是对于这个图的spfa增广队列的顺序，而且这个顺序还是错的(同级增广编号小的点在前）。。。。MDZZ不会啊，拿下1分走人。 挖坑，会了再补。
