UOJ Logo absi2011的博客

博客

提价答案题新坑 UOJ 270

2017-11-10 19:28:04 By absi2011

看起来是一个挺有趣的题,来玩一玩......

http://uoj.ac/problem/270

目前完成进度 : Accepted

Task 1:

如果是不是1或者0的东西,直接Reject掉

如果是0,走到1号点,如果是1,走到2号点

如果最后在2号点则Accept,在1号点则Reject

#include<set>
#include<map>
#include<list>
#include<queue>
#include<stack>
#include<string>
#include<math.h>
#include<time.h>
#include<vector>
#include<bitset>
#include<memory>
#include<utility>
#include<fstream>
#include<stdio.h>
#include<sstream>
#include<iostream>
#include<stdlib.h>
#include<string.h>
#include<algorithm>
using namespace std;
int main()
{
    freopen("1.out","w",stdout);
    int n=2;
    printf("%d\n",n);
    int i;
    printf("1 ");
    for (i=0;i<128;i++)
    {
        if ((i!='0')&&(i!='1')) printf("-1 ");
        if (i=='0') printf("1 ");
        if (i=='1') printf("2 ");
    }
    printf("-1\n");
    printf("1 ");
    for (i=0;i<128;i++)
    {
        if ((i!='0')&&(i!='1')) printf("-1 ");
        if (i=='0') printf("1 ");
        if (i=='1') printf("2 ");
    }
    printf("0\n");
    return 0;
}

Task 2:

一个AC自动机的样子

如果可以的话,这一题就当练习AC自动机也可以

不过我觉得这题为什么可以用一个特别劣的算法,反正不会TLE对吧,写起来多简单

#include<set>
#include<map>
#include<list>
#include<queue>
#include<stack>
#include<string>
#include<math.h>
#include<time.h>
#include<vector>
#include<bitset>
#include<memory>
#include<utility>
#include<fstream>
#include<stdio.h>
#include<sstream>
#include<iostream>
#include<stdlib.h>
#include<string.h>
#include<algorithm>
using namespace std;
string c;
int main()
{
    freopen("2.out","w",stdout);
    c="aaaaaaaaaaaabaaaaaabaaaaaaaaaaaaaabaaabaaabaaaaaaaaaabaaaaaaaaabaabaaaaaaaaaaaaabaaaaaaaaaaaaaaaaaaaorz";
    int n=c.size();
    printf("%d\n",n);
    int i;
    for (i=0;i<n;i++)
    {
        printf("1 ");
        int j;
        for (j=0;j<128;j++)
        {
            int k;
            for (k=i;k>=0;k--)
            {
                int l;
                for (l=0;l<k;l++)
                {
                    if (c[l]!=c[i-k+l]) break;
                }
                if ((l==k)&&(c[k]==j)) break;
            }
            if (k!=n-1)
            {
                printf("%d ",k+2);
            }
            else
            {
                printf("%d ",0);
            }
        }
        printf("-1\n");
    }
    return 0;
}

Task 3 & 4

第一眼看上去,显然要求复杂度O(n)的

那么,我的反应是,每次找一对括号,删掉它们,直到最后...

后来仔细一想,不对啊......这样不可以啊.....会T的

后来想到,括号有一种判定姿势

假设n个括号,每碰到一个左括号,计数器+1 碰到右括号计数器-1

然后 这样还是不行 因为一共300个点

我就想到了.....

如果计数器超过范围 一次+16/-16 会怎么样

后来又发现 如果)()()()(....这样的数据我会炸

所以我决定 如果超过范围 一次+16 如果超过32 一次-16 这样保证每次+/-16以后,至少运行16个括号,才会进行下一次操作

然后我发现16可能会T,顺手改成了64

代码:

#include<set>
#include<map>
#include<list>
#include<queue>
#include<stack>
#include<string>
#include<math.h>
#include<time.h>
#include<vector>
#include<bitset>
#include<memory>
#include<utility>
#include<fstream>
#include<stdio.h>
#include<sstream>
#include<iostream>
#include<stdlib.h>
#include<string.h>
#include<algorithm>
using namespace std;
int main()
{
    freopen("3.out","w",stdout);
    int n=138;
    printf("%d\n",n);
    int i;
    for (i=1;i<=128;i++)
    {
        printf("1 ");
        int j;
        for (j=0;j<128;j++)
        {
            if (j=='(')
            {
                printf("%d ",i+1);
            }
            else if (j==')')
            {
                if (i==1)
                {
                    printf("130 ");
                }
                else
                {
                    printf("%d ",i-1);
                }
            }
            else if (j>=9)
            {
                printf("-1 ");
            }
            else if (j%2==1)
            {
                if (i==128)
                {
                    printf("%d ",130+j);
                }
                else
                {
                    printf("%d ",i+1);
                }
            }
            else
            {
                if (i==1)
                {
                    printf("%d ",130+j);
                }
                else
                {
                    printf("%d ",i-1);
                }
            }
        }
        if (i==1)
        {
            printf("0\n");
        }
        else
        {
            printf("-1\n");
        }
    }
    printf("2 %d 65\n",1);
    printf("2 %d 64\n",2);
    printf("2 %d 65\n",3);
    printf("2 %d 64\n",4);
    printf("2 %d 65\n",5);
    printf("2 %d 64\n",6);
    printf("2 %d 65\n",7);
    printf("2 %d 64\n",8);
    printf("2 %d 65\n",9);
    printf("2 %d -1\n",10);
    return 0;
}

Task 5

基本同Task 1

三个节点,表示%3 = 0/1/2

没了

#include<set>
#include<map>
#include<list>
#include<queue>
#include<stack>
#include<string>
#include<math.h>
#include<time.h>
#include<vector>
#include<bitset>
#include<memory>
#include<utility>
#include<fstream>
#include<stdio.h>
#include<sstream>
#include<iostream>
#include<stdlib.h>
#include<string.h>
#include<algorithm>
using namespace std;
int main()
{
    freopen("5.out","w",stdout);
    int n=3;
    printf("%d\n",n);
    int i;
    printf("1 ");
    for (i=0;i<128;i++)
    {
        if ((i!='0')&&(i!='1')) printf("-1 ");
        if (i=='0') printf("1 ");
        if (i=='1') printf("2 ");
    }
    printf("0\n");
    printf("1 ");
    for (i=0;i<128;i++)
    {
        if ((i!='0')&&(i!='1')) printf("-1 ");
        if (i=='0') printf("3 ");
        if (i=='1') printf("1 ");
    }
    printf("-1\n");
    printf("1 ");
    for (i=0;i<128;i++)
    {
        if ((i!='0')&&(i!='1')) printf("-1 ");
        if (i=='0') printf("2 ");
        if (i=='1') printf("3 ");
    }
    printf("-1\n");
    return 0;
}

Task 6~7

考虑到Fib语言,也就是说

假设我们把a当成1

b当成2

那么我们可以将2和1合并为3

所以 bab = 212 = 32 = 4

发现是一个数,返回Accepted

如果很不巧,发现最后剩的是多个数,那只能Reject掉了

比如

$bababbaba$ = $212122121$ = $33233$ = $3433$ = $353$

判定它爆炸就行了

#include<set>
#include<map>
#include<list>
#include<queue>
#include<stack>
#include<string>
#include<math.h>
#include<time.h>
#include<vector>
#include<bitset>
#include<memory>
#include<utility>
#include<fstream>
#include<stdio.h>
#include<sstream>
#include<iostream>
#include<stdlib.h>
#include<string.h>
#include<algorithm>
using namespace std;
int main()
{
    freopen("7.out","w",stdout);
    int ii;
    printf("%d\n",281);
    for (ii=0;ii<40;ii++)
    {
        printf("2 127 %d\n",ii*7+2);     //1 
        int i;
        printf("1 ");
        for (i=0;i<128;i++)             //2
        {
            if (i>=32)
            {
                if (i==127)
                {
                    printf("%d ",(ii+1)*7+1);
                }
                else if ((i!='a')&&(i!='b'))
                {
                    printf("-1 ");
                    continue;
                }
                else if (i=='a')
                {
                    printf("%d ",ii*7+7);
                }
                else if (i=='b')
                {
                    printf("%d ",ii*7+3);
                }
            }
            else
            {
                if (i==ii)
                {
                    printf("%d ",ii*7+7);
                }
                else if (i==ii+1)
                {
                    printf("%d ",ii*7+3);
                }
                else
                {
                    printf("-1 ");
                }
            }
        }
        printf("-1\n");
        printf("1 ");
        for (i=0;i<128;i++)             //3
        {
            if (i>=32)
            {
                if (i==127)
                {
                    printf("%d ",ii*7+6);
                }
                else if ((i!='a')&&(i!='b'))
                {
                    printf("-1 ");
                    continue;
                }
                else if (i=='a')
                {
                    printf("%d ",ii*7+5);
                }
                else if (i=='b')
                {
                    printf("%d ",ii*7+4);
                }
            }
            else
            {
                if (i==ii)
                {
                    printf("%d ",ii*7+5);
                }
                else if (i==ii+1)
                {
                    printf("%d ",ii*7+4);
                }
                else
                {
                    printf("-1 ");
                }
            }
        }
        printf("-1\n");
        printf("2 %d %d\n",ii+1,ii*7+3); //4
        printf("2 %d %d\n",ii+2,ii*7+2); //5
        printf("2 %d %d\n",ii+1,(ii+1)*7+1); //6
        printf("1 ");
        for (i=0;i<128;i++)             //7
        {
            if (i==127)
            {
                printf("%d ",ii*7+7);
                continue;
            }
            printf("-1 ");
            continue;
        }
        printf("0\n");
    }
    printf("2 0 -1\n");
    return 0;
}

Task 10

时间复杂度 $O(n)$

空间复杂度 $O(2n)$

第x个点,表示连续x个i

或者说i比e的数量多x个,目前还是合法,但是缺a的

第x+101个点,表示连续x个i

后面已经有a的

那么 如果遇到i

那么x转移到x+1,当然x+101直接-1掉

遇到e x直接-1掉 x+101 转移到x-1

遇到a x转移到x+101 x+101就-1掉(因为不允许aaaa这种东西)

#include<set>
#include<map>
#include<list>
#include<queue>
#include<stack>
#include<string>
#include<math.h>
#include<time.h>
#include<vector>
#include<bitset>
#include<memory>
#include<utility>
#include<fstream>
#include<stdio.h>
#include<sstream>
#include<iostream>
#include<stdlib.h>
#include<string.h>
#include<algorithm>
using namespace std;
int main()
{
    freopen("10.out","w",stdout);
    printf("202\n");
    int i;
    for (i=1;i<=101;i++)
    {
        printf("1 ");
        int j;
        for (j=0;j<128;j++)
        {
            if (j=='i')
            {
                printf("%d ",i+1);
            }
            else if (j=='a')
            {
                printf("%d ",i+101);
            }
            else if (j=='e')
            {
                printf("%d ",-1);
            }
            else
            {
                printf("-1 ");
            }
        }
        printf("-1\n");
    }
    for (i=1;i<=101;i++)
    {
        printf("1 ");
        int j;
        for (j=0;j<128;j++)
        {
            if (j=='i')
            {
                printf("-1 ");
            }
            else if (j=='a')
            {
                printf("-1 ");
            }
            else if (j=='e')
            {
                if (i!=1)
                {
                    printf("%d ",i-1);
                }
                else
                {
                    printf("-1 ");
                }
            }
            else
            {
                printf("-1 ");
            }
        }
        printf("0\n");
    }
    return 0;
}

Task 8~9

果然是和括号匹配相关的

首先,先判定是否合法

一个不合法的部分,我们认为:

(以下部分,$+$代表$+$和$*$ , $1$代表$0$和$1$)

$($,$+$后面,需要跟$1$或者$($

$1$,$)$后面,需要跟$+$或者$)$

然后如果合法,那么直接再跑一次Task 4就行了

代码后半段基本是try_3_4.cpp的

#include<set>
#include<map>
#include<list>
#include<queue>
#include<stack>
#include<string>
#include<math.h>
#include<time.h>
#include<vector>
#include<bitset>
#include<memory>
#include<utility>
#include<fstream>
#include<stdio.h>
#include<sstream>
#include<iostream>
#include<stdlib.h>
#include<string.h>
#include<algorithm>
using namespace std;
int main()
{
    freopen("9.out","w",stdout);
    printf("143\n");
    printf("2 127 3\n");        //1
    int i;
    printf("1 ");
    for (i=0;i<128;i++)         //2
    {
        if (i==127)
        {
            printf("6 ");
        }
        else if (i=='+')
        {
            printf("3 ");
        }
        else if (i=='*')
        {
            printf("3 ");
        }
        else if (i=='(')
        {
            printf("-1 ");
        }
        else if (i==')')
        {
            printf("4 ");
        }
        else if (i=='0')
        {
            printf("-1 ");
        }
        else if (i=='1')
        {
            printf("-1 ");
        }
        else
        {
            printf("-1 ");
        }
    }
    printf("-1\n");
    printf("1 ");
    for (i=0;i<128;i++)         //3
    {
        if (i==127)
        {
            printf("-1 ");
        }
        else if (i=='+')
        {
            printf("-1 ");
        }
        else if (i=='*')
        {
            printf("-1 ");
        }
        else if (i=='(')
        {
            printf("5 ");
        }
        else if (i==')')
        {
            printf("-1 ");
        }
        else if (i=='0')
        {
            printf("2 ");
        }
        else if (i=='1')
        {
            printf("2 ");
        }
        else
        {
            printf("-1 ");
        }
    }
    printf("-1\n");
    printf("2 %d 2\n",')');          //4
    printf("2 %d 3\n",'(');          //5
    for (i=1;i<=128;i++)
    {
        printf("1 ");
        int j;
        for (j=0;j<128;j++)
        {
            if (j=='(')
            {
                printf("%d ",i+1+5);
            }
            else if (j==')')
            {
                if (i==1)
                {
                    printf("135 ");
                }
                else
                {
                    printf("%d ",i-1+5);
                }
            }
            else if (j>=9)
            {
                printf("-1 ");
            }
            else if (j%2==1)
            {
                if (i==128)
                {
                    printf("%d ",135+j);
                }
                else
                {
                    printf("%d ",i+1+5);
                }
            }
            else
            {
                if (i==1)
                {
                    printf("%d ",135+j);
                }
                else
                {
                    printf("%d ",i-1+5);
                }
            }
        }
        if (i==1)
        {
            printf("0\n");
        }
        else
        {
            printf("-1\n");
        }
    }
    printf("2 %d 70\n",1);
    printf("2 %d 69\n",2);
    printf("2 %d 70\n",3);
    printf("2 %d 69\n",4);
    printf("2 %d 70\n",5);
    printf("2 %d 69\n",6);
    printf("2 %d 70\n",7);
    printf("2 %d 69\n",8);
    printf("2 %d 70\n",9);
    printf("2 %d -1\n",10);
    return 0;
}

评论

WrongAnswer
输出文件好占版面啊……
skyline
标题上是不是有个错别字啊

发表评论

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

Server time: 2024-04-25 16:13:37