UOJ Logo absi2011的博客

博客

[UOJ 56非确定机 题解]直播玩提价答案题[Done]

2016-05-22 21:03:55 By absi2011

http://uoj.ac/problem/56

我们分别考虑10个点

点1:

考虑到和样例一样..手打了一个输出..

点3:

其实好像是在求两点的距离..把所有的1全部输出即可..

try_3.cpp
#include<set>
#include<map>
#include<list>
#include<queue>
#include<stack>
#include<math.h>
#include<string>
#include<time.h>
#include<bitset>
#include<vector>
#include<memory>
#include<utility>
#include<stdio.h>
#include<sstream>
#include<fstream>
#include<iostream>
#include<stdlib.h>
#include<string.h>
#include<algorithm>
using namespace std;
int main()
{
    freopen("nm3.in","r",stdin);
    freopen("nm3.out","w",stdout);
    int n,k,p;
    scanf("%d%d%d",&n,&k,&p);
    int i;
    for (i=0;i<n;i++)
    {
        int j;
        for (j=0;j<n;j++)
        {
            int x;
            scanf("%d",&x);
            if (x==1)
            {
                printf("%d %d 1\n",i+1,j+1);
            }
        }
    }
}

点2:

一个最短路..排序下就好..再加一堆废边..

try_2.cpp
#include<set>
#include<map>
#include<list>
#include<queue>
#include<stack>
#include<math.h>
#include<string>
#include<time.h>
#include<bitset>
#include<vector>
#include<memory>
#include<utility>
#include<stdio.h>
#include<sstream>
#include<fstream>
#include<iostream>
#include<stdlib.h>
#include<string.h>
#include<algorithm>
using namespace std;
pair<int,int> temp[100005];
int main()
{
    freopen("nm2.in","r",stdin);
    freopen("nm2.out","w",stdout);
    int n,k,p;
    scanf("%d%d%d",&n,&k,&p);
    printf("%d %d %d\n",n,2*n,k);
    int i;
    for (i=0;i<n;i++)
    {
        int x;
        scanf("%d",&x);
        temp[i].first=x;
        temp[i].second=i;
    }
    sort(temp+1,temp+n);
    for (i=1;i<n;i++)
    {
        printf("%d %d %d\n",temp[i-1].second+1,temp[i].second+1,temp[i].first-temp[i-1].first);
    }
    for (i=0;i<n;i++)
    {
        printf("%d %d 20000\n",i+1,i+1);
    }
    printf("%d %d 20000\n",2333,3333);
}

点5:

不是很理解到底是在做什么

但是还是发现了一些有趣的事情..

比如....

好像在输出强联通分量里的最小顶点唉..

直接乱构造一发,最后手工改下m就是了

try_5.cpp
#include<set>
#include<map>
#include<list>
#include<queue>
#include<stack>
#include<math.h>
#include<string>
#include<time.h>
#include<bitset>
#include<vector>
#include<memory>
#include<utility>
#include<stdio.h>
#include<sstream>
#include<fstream>
#include<iostream>
#include<stdlib.h>
#include<string.h>
#include<algorithm>
using namespace std;
pair<int,int> temp[100005];
int main()
{
    freopen("nm5.in","r",stdin);
    freopen("nm5.out","w",stdout);
    int n,m,k;
    scanf("%d%d%d",&n,&k,&m);
    printf("%d %d %d\n",n,m,k);
    int i;
    for (i=1;i<=n;i++)
    {
        int x;
        scanf("%d",&x);
        if (x==i) continue;
        printf("%d %d %d\n",x,i,1);
        printf("%d %d %d\n",i,x,1);
    }
    return 0;
}

点8:

实在是莫名其妙的输出,61

以及整个的边数是6100....实在不明所以

乱测了几个小数据

还是没懂怎么玩

然后就凭着$"大胆猜想,不用证明"$的想法,写了这个程序,然后AC了

try_8.cpp
#include<set>
#include<map>
#include<list>
#include<queue>
#include<stack>
#include<string>
#include<time.h>
#include<math.h>
#include<memory>
#include<vector>
#include<bitset>
#include<fstream>
#include<stdio.h>
#include<utility>
#include<sstream>
#include<string.h>
#include<iostream>
#include<stdlib.h>
#include<algorithm>
using namespace std;
int main()
{
    freopen("nm8.out","w",stdout);
    int n,m,k;
    printf("%d %d %d\n",100,6100,30);
    int i;
    for (i=1;i<=61;i++)
    {
        int j;
        for (j=1;j<=100;j++)
        {
            printf("%d %d %d\n",i,j,1);
        }
    }
}

点4:

和2号点一样,一大堆权值

经过多次小数据实验,可以发现是到达某个点的次短路的权值

看起来就要构造数据..构造了个边为n左右的数据,然后用了一堆废边就过了..

try_4.cpp
#include<set>
#include<map>
#include<list>
#include<queue>
#include<stack>
#include<string>
#include<time.h>
#include<math.h>
#include<memory>
#include<vector>
#include<bitset>
#include<fstream>
#include<stdio.h>
#include<utility>
#include<sstream>
#include<string.h>
#include<iostream>
#include<stdlib.h>
#include<algorithm>
using namespace std;
pair<int,int> x[100005];
int main()
{
    freopen("nm4.in","r",stdin);
    freopen("nm4.out","w",stdout);
    int n,m,k;
    scanf("%d%d%d",&n,&k,&m);
    printf("%d %d %d\n",n,n+n,k);
    int i;
    for (i=0;i<n;i++)
    {
        scanf("%d",&x[i].first);
        x[i].second=i;
        //printf("%d ",x[i]);
    }
    sort(x+1,x+n);
    printf("%d %d %d\n",1,x[1].second+1,x[1].first-20000);
    printf("%d %d %d\n",x[1].second+1,x[1].second+1,20000);
    for (i=2;i<n;i++)
    {
        printf("%d %d %d\n",x[i-1].second+1,x[i].second+1,x[i].first-x[i-1].first);
        printf("%d %d %d\n",x[i].second+1,x[i].second+1,20000);
    }
    printf("%d %d %d\n",x[n-1].second+1,1,x[0].first+20000-x[n-1].first);
    printf("%d %d %d\n",x[n-1].second+1,x[n-2].second+1,20000);
    return 0;
}

点9:

这个点的做法可以好好试试..

input: 100 31 7653

外加一个1~100的排列

我试了几组小数据,发现是输出所有a-->b中b的最小值

写了一发很果断得到m=5050,这样可以拿..4分..

并不满意啊..这样显然是无可救药的

无意间发现自己写错了,竟然求的又是a-->b中的最大值

搞什么名堂!

弄了个贪心,如果点的编号>50就输出1~x不然输出x~100

结果...很果断的爆了,Wrong Answer

仔细观察,发现输出是这样的

100 31 7549
5 1 49 2 3 15 4 13 6 7 42 36 18 10 8 44 41 9 11 12 20 14 16 17 19 21 22 24 23 25 26 39 27 47 28 33 29 30 31 32 34 35 37 38 40 43 45 46 48 51 54 55 56 57 58 62 63 65 66 61 60 67 69 70 71 73 74 68 75 77 78 82 84 85 88 79 76 89 86 59 90 92 52 93 94 72 64 95 96 81 53 83 97 98 80 50 99 100 91 87

我们来对比下原来的

100 31 5050
5 51 49 88 70 15 99 13 71 66 42 36 18 10 78 44 41 90 3 6 20 94 57 58 12 84 67 24 23 54 55 39 73 47 96 33 92 82 1 75 98 19 56 14 93 27 4 25 28 43 48 74 8 65 69 62 63 7 100 61 60 31 29 95 77 85 32 68 26 17 89 30 16 97 45 79 76 35 86 59 38 22 52 9 34 72 64 21 11 81 53 83 46 2 80 50 40 37 91 87

可以发现51-->1 88-->2 ....

我由此认定:求字典序最小的排列,使得(i,$x_i$)有边

果断写了个程序,Accepted

try_9.cpp
#include<set>
#include<map>
#include<list>
#include<queue>
#include<stack>
#include<string>
#include<time.h>
#include<math.h>
#include<memory>
#include<vector>
#include<bitset>
#include<fstream>
#include<stdio.h>
#include<utility>
#include<sstream>
#include<string.h>
#include<iostream>
#include<stdlib.h>
#include<algorithm>
using namespace std;
int x[105];
int main()
{
    freopen("nm9.in","r",stdin);
    freopen("nm9.out","w",stdout);
    int n,m,k;
    scanf("%d%d%d",&n,&k,&m);
    printf("%d %d %d\n",100,7653,31);
    int i;
    for (i=1;i<=100;i++)
    {
        scanf("%d",&x[i]);
        int j;
        for (j=x[i];j<=100;j++)
        {
            printf("%d %d %d\n",i,j,1);
        }
        for (j=1;j<i;j++)
        {
            if (x[j]<x[i])
            {
                printf("%d %d %d\n",i,x[j],1);
            }
        }
    }
}

点10(Unsolved):

似乎输出的是bfs序..不明白到底怎么才能做到诡异的把数字输出好几遍..

打开了.js的文件,不知道里面是啥

似乎是被加密的源代码..看不懂..

打开了.mem文件也没用= =看不懂..不过里面有这么一段不知道啥意思...

 L A M P M AM PM J a n u a r y F e b r u a r y M a r c h A p r i l J u n e J u l y A u g u s t S e p t e m b e r O c t o b e r N o v e m b e r D e c e m b e r J a n F e b M a r A p r M a y J u n J u l A u g S e p O c t N o v D e c January February March April May June July August September October November December Jan Feb Mar Apr Jun Jul Aug Sep Oct Nov Dec S u n d a y M o n d a y T u e s d a y W e d n e s d a y T h u r s d a y F r i d a y S a t u r d a y S u n M o n T u e W e d T h u F r i S a t Sunday Monday Tuesday Wednesday Thursday Friday Saturday Sun Mon Tue Wed Thu Fri Sat

我决定放弃破解源代码的想法

就在我对第10个点放弃希望的时候,出来了这么个东西..

test.txt
4 4 13
1 2 1
1 3 2
2 4 0
4 3 0

enter
4 13 5
1 2 3 4 3

居然是权值相关的..有点报警啊

经过尝试,发现只要1 3的权值比4 3的权值大2即可再出现一次3....

这又是什么含义呢..

另外第6,7个点真的是不看权值的么..

再次发现,只要1 3的权值比2 4的权值+4 3的权值大2.....

猜想:这个2是3-1得到的

结果当然很残酷..

4 4 13
1 2 1
1 4 300
2 3 1
3 4 297

输出是

4 13 5
1 2 4 3 4

这说明..这个2和3-1无关..那么..就可能跟长度有关..

我来试一发..

实际上,这似乎是个bellman-ford的访问顺序..

似乎不是这样的?那么我们可以把所有权值都+1再尝试一次?

既然是bellman-ford的话..那么可以开始神一般的乱构造了...

看这个序列,似乎并不好构造的样子...

大概看的出来..这个图好像有点卡spfa的倾向

点6:

然而我会暴力....

虽然不知道内部怎么操作的反正能暴力的出来就是..

try_6.cpp
#include<set>
#include<map>
#include<list>
#include<queue>
#include<stack>
#include<math.h>
#include<string>
#include<time.h>
#include<bitset>
#include<vector>
#include<memory>
#include<utility>
#include<stdio.h>
#include<sstream>
#include<fstream>
#include<iostream>
#include<stdlib.h>
#include<string.h>
#include<algorithm>
using namespace std;
vector<int> v[25];
bool visit[25];
ofstream fout;
int n,m,k;
void dfs(int x)
{
    if (x==0)
    {
        static int count=0;
        count++;
        printf("%d\n",count);
        //return;
        fout.open("nm6.out");
        fout<<n<<" "<<m<<" "<<k<<'\n';
        int i;
        for (i=1;i<=8;i++)
        {
            if (!visit[i]) continue;
            int j;
            int last=i;
            for (j=0;j<v[i].size();j++)
            {
                fout<<last<<" "<<v[i][j]<<" "<<k<<'\n';
                last=v[i][j];
            }
            fout<<last<<" "<<i<<" "<<k<<'\n';
        }
        fout.close();
        system("prog_win32 nm6.out >enter");
        ifstream fin;
        fin.open("enter");
        string x;
        fin>>x;
        fin>>x;
        fin>>x;
        fin>>x;
        if (x=="232615585") exit(0);
        return;
    }
    if (v[x].size()==0)
    {
        int i;
        visit[x]=false;
        for (i=1;i<x;i++)
        {
            v[i].push_back(x);
            dfs(x-1);
            v[i].pop_back();
        }
    }
    visit[x]=true;
    dfs(x-1);
}
int main()
{
    freopen("nm6.in","r",stdin);
    scanf("%d%d%d",&n,&k,&m);
    dfs(n);
    system("pause");
}

点7:

不知道怎么hash的,用try_6的大暴力跑一遍比较小的数据来找找规律

我把n=5的表打了出来..

对比一下n=4的表..

1 5 4 3 2 1
0

1 5 4 3 1
2 2
60

1 5 4 1
2 3 2
80

1 5 4 2 1
3 3
40

1 5 4 1
2 2
3 3
100

1 5 3 1
2 4 2
65

1 5 1
2 4 3 2
85

1 5 1
2 4 2
3 3
105

1 5 2 1
3 4 3
50

1 5 1
2 2
3 4 3
110

1 5 3 2 1
4 4
15

1 5 3 1
2 2
4 4
75

1 5 1
2 3 2
4 4
95

1 5 2 1
3 3
4 4
55

1 5 1
2 2
3 3
4 4
115

1 4 3 1
2 5 2
61

1 4 1
2 5 3 2
81

1 4 1
2 5 2
3 3
101

1 3 1
2 5 4 2
66

1 1
2 5 4 3 2
86

1 1
2 5 4 2
3 3
106

1 1
2 5 2
3 4 3
111

1 3 1
2 5 2
4 4
76

1 1
2 5 3 2
4 4
96

1 1
2 5 2
3 3
4 4
116

1 4 2 1
3 5 3
42

1 4 1
2 2
3 5 3
102

1 1
2 4 2
3 5 3
107

1 2 1
3 5 4 3
52

1 1
2 2
3 5 4 3
112

1 2 1
3 5 3
4 4
57

1 1
2 2
3 5 3
4 4
117

1 3 2 1
4 5 4
18

1 3 1
2 2
4 5 4
78

1 1
2 3 2
4 5 4
98

1 2 1
3 3
4 5 4
58

1 1
2 2
3 3
4 5 4
118

1 4 3 2 1
5 5
4

1 4 3 1
2 2
5 5
64

1 4 1
2 3 2
5 5
84

1 4 2 1
3 3
5 5
44

1 4 1
2 2
3 3
5 5
104

1 3 1
2 4 2
5 5
69

1 1
2 4 3 2
5 5
89

1 1
2 4 2
3 3
5 5
109

1 2 1
3 4 3
5 5
54

1 1
2 2
3 4 3
5 5
114

1 3 2 1
4 4
5 5
19

1 3 1
2 2
4 4
5 5
79

1 1
2 3 2
4 4
5 5
99

1 2 1
3 3
4 4
5 5
59

1 1
2 2
3 3
4 4
5 5
119

请按任意键继续. . .
1 4 3 2 1
0

1 4 3 1
2 2
12

1 4 1
2 3 2
16

1 4 2 1
3 3
8

1 4 1
2 2
3 3
20

1 3 1
2 4 2
13

1 1
2 4 3 2
17

1 1
2 4 2
3 3
21

1 2 1
3 4 3
10

1 1
2 2
3 4 3
22

1 3 2 1
4 4
3

1 3 1
2 2
4 4
15

1 1
2 3 2
4 4
19

1 2 1
3 3
4 4
11

1 1
2 2
3 3
4 4
23

似乎是有什么规律,仔细观察,发现如果5和1在一起,那么答案就是4的答案*5!

而如果是5和2在一起,那么就是*5+1...以此类推..

所以.....

就可以解出来了

try_7.cpp
#include<set>
#include<map>
#include<list>
#include<queue>
#include<stack>
#include<math.h>
#include<string>
#include<time.h>
#include<bitset>
#include<vector>
#include<memory>
#include<utility>
#include<stdio.h>
#include<sstream>
#include<fstream>
#include<iostream>
#include<stdlib.h>
#include<string.h>
#include<algorithm>
using namespace std;
int last[25];
int n,k,m;
int main()
{
    freopen("nm7.in","r",stdin);
    freopen("nm7.out","w",stdout);
    scanf("%d%d%d",&n,&k,&m);
    long long val;
    cin>>val;
    int i;
    for (i=n;i>=0;i--)
    {
        last[i]=i;
    }
    printf("%d %d %d\n",n,m,k);
    for (i=n;i>=1;i--)
    {
        int k=val%i;
        k++;
        printf("%d %d %d\n",i,last[k],k);
        last[k]=i;
        val/=i;
    }
}

点10:

基于上面的分析,可以发现这是个bellman-ford的序列

我们要构造个图使得这个图跑出这样的序列

观察输出,我们发现里面有好几个转折点

第一个就是在5上面

然后在37左右还有一个

我就造了个程序把转折点全给抓出来

然后..强行建点边,强制它走这些新建边即可

try_10.cpp
#include<set>
#include<map>
#include<list>
#include<queue>
#include<stack>
#include<math.h>
#include<string>
#include<time.h>
#include<bitset>
#include<vector>
#include<memory>
#include<utility>
#include<stdio.h>
#include<sstream>
#include<fstream>
#include<iostream>
#include<stdlib.h>
#include<string.h>
#include<algorithm>
using namespace std;
bool visit[505][505];
int x[6005];
int sp_point[6005];
int dist[6005];
int main()
{
    freopen("nm10.in","r",stdin);
    freopen("nm10.out","w",stdout);
    int n,m,k;
    scanf("%d%d%d",&n,&k,&m);
    int i;
    /*
    for (i=0;i<m;i++)
    {
        scanf("%d",&x);
        if (x>=300)
        {
            printf("%d ",x);
        }
    }
    return 0;*/
    printf("%d %d %d\n",n,537,k);
    printf("1 2 1\n");
    printf("1 3 10000\n");
    for (i=0;i<m;i++)
    {
        scanf("%d",&x[i]);
    }
    static int front=1,rail=3;
    for (;front<rail;)
    {
        if (rail>=m) break;
        int t=x[rail];
        if ((x[front]==499)||(x[front]==500))
        {
            front++;
        }
        if (t==x[front]-1)
        {
            if (!visit[x[front]][t]) printf("%d %d %d\n",x[front],t,1);
            sp_point[x[front]]=-1;
            visit[x[front]][t]=true;
            rail++;
            continue;
        }
        if (t==x[front]+1)
        {
            if (!visit[x[front]][t]) printf("%d %d %d\n",x[front],t,1);
            sp_point[x[front]]=1;
            visit[x[front]][t]=true;
            rail++;
            continue;
        }
        if (t==x[front]+2)
        {
            front++;
            rail++;
        }
        else
        {
            //printf("Error: %d %d %d (Loc : %d & %d) \n",x[front],t,1,front,rail);
            rail++;
        }
    }
    dist[2]=2;
    dist[3]=10001;
    for (i=2;i<=498;i++)
    {
        int x=10000;
        if (sp_point[i+2])
        {
            x=1;
        }
        printf("%d %d %d\n",i,i+2,x);
        dist[i+2]=dist[i]+x+1;
    }
}

完结撒花~

评论

zhouzixuan
%%%
WrongAnswer
强。至今没A的路过（话说我当时做第6个点的时候也是在程序里暴搜调checker- -搜了好久搜出来了）

发表评论

可以用@mike来提到mike这个用户，mike会被高亮显示。如果你真的想打“@”这个字符，请用“@@”。

Server time: 2024-04-26 12:02:54