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;
}

[弃疗]直播玩提价答案题

2016-06-07 23:01:09 By absi2011

发现交互题不会做了..

还是提交答案题靠谱..

http://uoj.ac/problem/116

首先先手写个checker..

#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 a[1<<23];
stringstream s;
ofstream fout;
int * get(int check_tag=0)
{
    static int operating[15];
    static int now=0;
    int x;
    char oper;
    s>>oper;
    s>>x;
    if (oper=='@')
    {
        if (check_tag)
        {
            printf("RuntimeError : Inputing/Equalling a constant\n");
            exit(0);
        }
        fout<<x<<" ";
        if (now==15) now=0;
        operating[now++]=x;
        return &operating[now-1];
    }
    else if (oper=='$')
    {
        if (x>=(1<<23))
        {
            printf("RuntimeError : Trying to visit a[%d]\n",x);
            exit(0);
        }
        else
        {
            fout<<"a["<<x<<"] ";
            return a+x;
        }
    }
    else
    {
        if (x>=(1<<23))
        {
            printf("RuntimeError : Trying to visit a[a[%d]]\n",x);
            exit(0);
        }
        else if (a[x]>=(1<<23))
        {
            printf("RuntimeError : Trying to visit a[a[%d]] (a[%d])\n",x,a[x]);
            exit(0);
        }
        else
        {
            fout<<"a[a["<<x<<"]] ";
            return a+a[x];
        }
    }
}
string line[100005];
char t[100005];
int main()
{
    ifstream fin;
    fin.open("lock1.in");
    fout.open("log.txt");
    int now=0;
    int n=1;
    for (;;)
    {
        fin.get(t,100000);
        if (t[0]=='\0') break;
        line[n++]=t;
        fin.get();
    }
    now=1;
    for (;;)
    {
        string oper;
        if (now==-1)
        {
            printf("\n\n\n");
            printf("Program Exit successfully");
            exit(1);
        }
        if ((now<-1)||(now>=n)||(now==0))
        {
            printf("RuntimeError : Trying to get %d-line",now);
            exit(0);
        }
        s.clear();
        s<<line[now];
        s>>oper;
        fout<<now<<endl;
        if (oper=="=")
        {
            int * t1=get(1);
            fout<<"=";
            int * t2=get();
            (*t1)=(*t2);
            fout<<" Value = "<<(*t2);
        }
        else if (oper=="geti")
        {
            int * t1=get(1);
            fout<<".input(int)";
            if (scanf("%d",t1)!=1)
            {
                printf("RuntimeErorr: Reading Failed (%%d)");
                exit(0);
            }
        }
        else if (oper=="getc")
        {
            int * t1=get(1);
            char tx;
            fout<<".input(char)";
            if (scanf("%c",&tx)!=1)
            {
                printf("RuntimeErorr: Reading Failed (%%c)");
                exit(0);
            }
            (*t1)=tx;
        }
        else if (oper=="puti")
        {
            int * t1=get();
            fout<<".print(int)";
            printf("%d",(*t1));
        }
        else if (oper=="putc")
        {
            int * t1=get();
            fout<<".print(char)";
            printf("%c",(*t1));
        }
        else if (oper=="if")
        {
            int * t1=get();
            int * t2=get();
            fout<<"Goto "<<(*t2)<<"?";
            if ((*t1)!=0) now=(*t2)-1;
            if ((*t1)!=0) fout<<" Yes";
        }
        else if (oper=="+")
        {
            int * t1=get();
            fout<<"+";
            int * t2=get();
            fout<<"-->";
            int * t3=get(1);
            (*t3)=(*t1)+(*t2);
            fout<<" Value = "<<(*t3);
        }
        else if (oper=="-")
        {
            int * t1=get();
            fout<<"-";
            int * t2=get();
            fout<<"-->";
            int * t3=get(1);
            (*t3)=(*t1)-(*t2);
            fout<<" Value = "<<(*t3);
        }
        else if (oper=="==")
        {
            int * t1=get();
            fout<<"==";
            int * t2=get();
            fout<<"-->";
            int * t3=get(1);
            (*t3)=((*t1)==(*t2));
            fout<<" Value = "<<(*t3);
        }
        else if (oper=="*")
        {
            int * t1=get();
            fout<<"*";
            int * t2=get();
            fout<<"-->";
            int * t3=get(1);
            (*t3)=(*t1)*(*t2);
            fout<<" Value = "<<(*t3);
        }
        else if (oper=="/")
        {
            int * t1=get();
            fout<<"/";
            int * t2=get();
            fout<<"-->";
            int * t3=get(1);
            if ((*t2)==0)
            {
                printf("RuntimeErorr : %d / 0 = ?",(*t1));
            }
            (*t3)=(*t1)/(*t2);
            fout<<" Value = "<<(*t3);
        }
        else if (oper=="<")
        {
            int * t1=get();
            fout<<"/";
            int * t2=get();
            fout<<"-->";
            int * t3=get(1);
            (*t3)=(*t1)<(*t2);
            fout<<" Value = "<<(*t3);
        }
        now++;
        fout<<endl;
    }
    return 0;
}

Test 1

写好checker就可以做题啦!

第一个输入点数字进去发现都会Too yaung..

始终在思考是yaung故意拼错还是什么...然后发现可能故意可能出题人手滑了..

反正..根据log.txt,大概发现是你输入的东西和23333333比较,如果一样就输出8个ok...

好的..过了

Test 2

第二个点好像是让你输入10个数字

输入第一个是1,发现输出了ko.....

输入了个0就给ok了...

我输入了10个0就全ok了....

果然是checker写错了我就知道不会那么简单..

改过以后看下log..


a[5] +0 -->a[0]  Value = 8388605
a[a[0]] =0  Value = 0
1 2314 Goto 2314? Yes
a[5] +0 -->a[0]  Value = 8388605
a[a[4]] =a[0]  Value = 8388605
a[4] -1 -->a[4]  Value = 8388593
a[4] +1 -->a[4]  Value = 8388594
a[1] =a[a[4]]  Value = 8388605
a[a[1]] /10 -->a[0]  Value = 1
a[0] 2294 Goto 2294? Yes
a[0] .input(int)
a[a[4]] =a[0]  Value = 0
a[4] -1 -->a[4]  Value = 8388593
a[5] +0 -->a[0]  Value = 8388605
a[a[0]] +-10 -->a[0]  Value = -10
a[0] +a[5] -->a[0]  Value = 8388595
a[4] +1 -->a[4]  Value = 8388594
a[1] =a[a[4]]  Value = 0
a[1] ==a[a[0]] -->a[0]  Value = 0 ( *t1 = 0 && *t2 = 7)
a[0] 2308 Goto 2308?
107 
111 
10 
1 2311 Goto 2311? Yes
a[5] +0 -->a[0]  Value = 8388605
a[a[0]] +1 -->a[a[0]]  Value = 1
a[a[0]] -1 -->a[0]  Value = 0
a[5] +0 -->a[0]  Value = 8388605
a[a[4]] =a[0]  Value = 8388605
a[4] -1 -->a[4]  Value = 8388593
a[4] +1 -->a[4]  Value = 8388594
a[1] =a[a[4]]  Value = 8388605
a[a[1]] /10 -->a[0]  Value = 1
a[0] 2294 Goto 2294? Yes
a[0] .input(int)
a[a[4]] =a[0]  Value = 0
a[4] -1 -->a[4]  Value = 8388593
a[5] +0 -->a[0]  Value = 8388605
a[a[0]] +-10 -->a[0]  Value = -9
a[0] +a[5] -->a[0]  Value = 8388596
a[4] +1 -->a[4]  Value = 8388594
a[1] =a[a[4]]  Value = 0
a[1] ==a[a[0]] -->a[0]  Value = 0 ( *t1 = 0 && *t2 = 47)
a[0] 2308 Goto 2308?
107 
111 
10 
1 2311 Goto 2311? Yes
a[5] +0 -->a[0]  Value = 8388605
a[a[0]] +1 -->a[a[0]]  Value = 2
a[a[0]] -1 -->a[0]  Value = 1
a[5] +0 -->a[0]  Value = 8388605
a[a[4]] =a[0]  Value = 8388605
a[4] -1 -->a[4]  Value = 8388593
a[4] +1 -->a[4]  Value = 8388594
a[1] =a[a[4]]  Value = 8388605
a[a[1]] /10 -->a[0]  Value = 1
a[0] 2294 Goto 2294? Yes
a[0] .input(int)
a[a[4]] =a[0]  Value = 0
a[4] -1 -->a[4]  Value = 8388593
a[5] +0 -->a[0]  Value = 8388605
a[a[0]] +-10 -->a[0]  Value = -8
a[0] +a[5] -->a[0]  Value = 8388597
a[4] +1 -->a[4]  Value = 8388594
a[1] =a[a[4]]  Value = 0
a[1] ==a[a[0]] -->a[0]  Value = 0 ( *t1 = 0 && *t2 = 1965)
a[0] 2308 Goto 2308?
107 
111 
10 
1 2311 Goto 2311? Yes
a[5] +0 -->a[0]  Value = 8388605
a[a[0]] +1 -->a[a[0]]  Value = 3
a[a[0]] -1 -->a[0]  Value = 2
a[5] +0 -->a[0]  Value = 8388605
a[a[4]] =a[0]  Value = 8388605
a[4] -1 -->a[4]  Value = 8388593
a[4] +1 -->a[4]  Value = 8388594
a[1] =a[a[4]]  Value = 8388605
a[a[1]] /10 -->a[0]  Value = 1
a[0] 2294 Goto 2294? Yes
a[0] .input(int)
a[a[4]] =a[0]  Value = 0
a[4] -1 -->a[4]  Value = 8388593
a[5] +0 -->a[0]  Value = 8388605
a[a[0]] +-10 -->a[0]  Value = -7
a[0] +a[5] -->a[0]  Value = 8388598
a[4] +1 -->a[4]  Value = 8388594
a[1] =a[a[4]]  Value = 0
a[1] ==a[a[0]] -->a[0]  Value = 0 ( *t1 = 0 && *t2 = 1915)
a[0] 2308 Goto 2308?
107 
111 
10 
1 2311 Goto 2311? Yes
a[5] +0 -->a[0]  Value = 8388605
a[a[0]] +1 -->a[a[0]]  Value = 4
a[a[0]] -1 -->a[0]  Value = 3
a[5] +0 -->a[0]  Value = 8388605
a[a[4]] =a[0]  Value = 8388605
a[4] -1 -->a[4]  Value = 8388593
a[4] +1 -->a[4]  Value = 8388594
a[1] =a[a[4]]  Value = 8388605
a[a[1]] /10 -->a[0]  Value = 1
a[0] 2294 Goto 2294? Yes
a[0] .input(int)
a[a[4]] =a[0]  Value = 0
a[4] -1 -->a[4]  Value = 8388593
a[5] +0 -->a[0]  Value = 8388605
a[a[0]] +-10 -->a[0]  Value = -6
a[0] +a[5] -->a[0]  Value = 8388599
a[4] +1 -->a[4]  Value = 8388594
a[1] =a[a[4]]  Value = 0
a[1] ==a[a[0]] -->a[0]  Value = 0 ( *t1 = 0 && *t2 = -2551)
a[0] 2308 Goto 2308?
107 
111 
10 
1 2311 Goto 2311? Yes
a[5] +0 -->a[0]  Value = 8388605
a[a[0]] +1 -->a[a[0]]  Value = 5
a[a[0]] -1 -->a[0]  Value = 4
a[5] +0 -->a[0]  Value = 8388605
a[a[4]] =a[0]  Value = 8388605
a[4] -1 -->a[4]  Value = 8388593
a[4] +1 -->a[4]  Value = 8388594
a[1] =a[a[4]]  Value = 8388605
a[a[1]] /10 -->a[0]  Value = 1
a[0] 2294 Goto 2294? Yes
a[0] .input(int)
a[a[4]] =a[0]  Value = 0
a[4] -1 -->a[4]  Value = 8388593
a[5] +0 -->a[0]  Value = 8388605
a[a[0]] +-10 -->a[0]  Value = -5
a[0] +a[5] -->a[0]  Value = 8388600
a[4] +1 -->a[4]  Value = 8388594
a[1] =a[a[4]]  Value = 0
a[1] ==a[a[0]] -->a[0]  Value = 0 ( *t1 = 0 && *t2 = -1646938625)
a[0] 2308 Goto 2308?
107 
111 
10 
1 2311 Goto 2311? Yes
a[5] +0 -->a[0]  Value = 8388605
a[a[0]] +1 -->a[a[0]]  Value = 6
a[a[0]] -1 -->a[0]  Value = 5
a[5] +0 -->a[0]  Value = 8388605
a[a[4]] =a[0]  Value = 8388605
a[4] -1 -->a[4]  Value = 8388593
a[4] +1 -->a[4]  Value = 8388594
a[1] =a[a[4]]  Value = 8388605
a[a[1]] /10 -->a[0]  Value = 1
a[0] 2294 Goto 2294? Yes
a[0] .input(int)
a[a[4]] =a[0]  Value = 0
a[4] -1 -->a[4]  Value = 8388593
a[5] +0 -->a[0]  Value = 8388605
a[a[0]] +-10 -->a[0]  Value = -4
a[0] +a[5] -->a[0]  Value = 8388601
a[4] +1 -->a[4]  Value = 8388594
a[1] =a[a[4]]  Value = 0
a[1] ==a[a[0]] -->a[0]  Value = 0 ( *t1 = 0 && *t2 = -322)
a[0] 2308 Goto 2308?
107 
111 
10 
1 2311 Goto 2311? Yes
a[5] +0 -->a[0]  Value = 8388605
a[a[0]] +1 -->a[a[0]]  Value = 7
a[a[0]] -1 -->a[0]  Value = 6
a[5] +0 -->a[0]  Value = 8388605
a[a[4]] =a[0]  Value = 8388605
a[4] -1 -->a[4]  Value = 8388593
a[4] +1 -->a[4]  Value = 8388594
a[1] =a[a[4]]  Value = 8388605
a[a[1]] /10 -->a[0]  Value = 1
a[0] 2294 Goto 2294? Yes
a[0] .input(int)
a[a[4]] =a[0]  Value = 0
a[4] -1 -->a[4]  Value = 8388593
a[5] +0 -->a[0]  Value = 8388605
a[a[0]] +-10 -->a[0]  Value = -3
a[0] +a[5] -->a[0]  Value = 8388602
a[4] +1 -->a[4]  Value = 8388594
a[1] =a[a[4]]  Value = 0
a[1] ==a[a[0]] -->a[0]  Value = 0 ( *t1 = 0 && *t2 = -167542220)
a[0] 2308 Goto 2308?
107 
111 
10 
1 2311 Goto 2311? Yes
a[5] +0 -->a[0]  Value = 8388605
a[a[0]] +1 -->a[a[0]]  Value = 8
a[a[0]] -1 -->a[0]  Value = 7
a[5] +0 -->a[0]  Value = 8388605
a[a[4]] =a[0]  Value = 8388605
a[4] -1 -->a[4]  Value = 8388593
a[4] +1 -->a[4]  Value = 8388594
a[1] =a[a[4]]  Value = 8388605
a[a[1]] /10 -->a[0]  Value = 1
a[0] 2294 Goto 2294? Yes
a[0] .input(int)
a[a[4]] =a[0]  Value = 0
a[4] -1 -->a[4]  Value = 8388593
a[5] +0 -->a[0]  Value = 8388605
a[a[0]] +-10 -->a[0]  Value = -2
a[0] +a[5] -->a[0]  Value = 8388603
a[4] +1 -->a[4]  Value = 8388594
a[1] =a[a[4]]  Value = 0
a[1] ==a[a[0]] -->a[0]  Value = 0 ( *t1 = 0 && *t2 = 4346926)
a[0] 2308 Goto 2308?
107 
111 
10 
1 2311 Goto 2311? Yes
a[5] +0 -->a[0]  Value = 8388605
a[a[0]] +1 -->a[a[0]]  Value = 9
a[a[0]] -1 -->a[0]  Value = 8
a[5] +0 -->a[0]  Value = 8388605
a[a[4]] =a[0]  Value = 8388605
a[4] -1 -->a[4]  Value = 8388593
a[4] +1 -->a[4]  Value = 8388594
a[1] =a[a[4]]  Value = 8388605
a[a[1]] /10 -->a[0]  Value = 1
a[0] 2294 Goto 2294? Yes
a[0] .input(int)
a[a[4]] =a[0]  Value = 0
a[4] -1 -->a[4]  Value = 8388593
a[5] +0 -->a[0]  Value = 8388605
a[a[0]] +-10 -->a[0]  Value = -1
a[0] +a[5] -->a[0]  Value = 8388604
a[4] +1 -->a[4]  Value = 8388594
a[1] =a[a[4]]  Value = 0
a[1] ==a[a[0]] -->a[0]  Value = 0 ( *t1 = 0 && *t2 = 1531256182)
a[0] 2308 Goto 2308?
107 
111 
10 
1 2311 Goto 2311? Yes
a[5] +0 -->a[0]  Value = 8388605
a[a[0]] +1 -->a[a[0]]  Value = 10
a[a[0]] -1 -->a[0]  Value = 9
a[5] +0 -->a[0]  Value = 8388605
a[a[4]] =a[0]  Value = 8388605
a[4] -1 -->a[4]  Value = 8388593
a[4] +1 -->a[4]  Value = 8388594
a[1] =a[a[4]]  Value = 8388605
a[a[1]] /10 -->a[0]  Value = 0
a[0] 2294 Goto 2294?
a[0] =0  Value = 0
a[4] +11 -->a[4]  Value = 8388605
a[4] =a[5]  Value = 8388605
a[4] +1 -->a[4]  Value = 8388606
a[5] =a[a[4]]  Value = 0
a[4] +1 -->a[4]  Value = 8388607
1 a[a[4]] Goto -1? Yes

这不就出来了么...

Test 3

lock3醚一样的让你输入一大堆东西..不是很懂怎么弄..

感觉输入全部被无视掉了..因为它让我反复输入..

好吧是输入20个数字...

应该是几个子问题,每个子问题有个ok/fail

task1: 输入完20个数 奖励: 1个ok

task2: 积为0 奖励: 3个ok

task3: 和为0 奖励: 3个ok

task4: 所有数里面没有0 奖励: 3个ok

所有数字均为-2147483648即可

Test 4

随便输入点东西

给了3个ok,并且说输入的太短了

二分下长度,长了会给4个ok

长度对了给5个,并且输出了No!

我觉得我可以去试试..看log

log上的判定很容易的让我判定出来了东西..

我发现第一个是97 != 112 所以我就把输入的字符给改了下

第一个字符对了,第二个错了..

之后就一直改到对了为止..

前面pr我以为是print结果竟然是primary..

primaryshcool!

然后后面的词..p开头的..pupil..?

过了

Test 5

输入10个字符串

我输入一个以后ctrl-C看看log里面的东西...

log大法好

a[1] ==a[a[0]] -->a[0]  Value = 0 ( *t1 = 374 && *t2 = 25)
a[1] ==a[a[0]] -->a[0]  Value = 0 ( *t1 = 374 && *t2 = 23)
a[1] ==a[a[0]] -->a[0]  Value = 0 ( *t1 = 374 && *t2 = 11)
a[1] ==a[a[0]] -->a[0]  Value = 0 ( *t1 = 274 && *t2 = 17)
a[1] ==a[a[0]] -->a[0]  Value = 0 ( *t1 = 274 && *t2 = 15)
a[1] ==a[a[0]] -->a[0]  Value = 0 ( *t1 = 318667 && *t2 = 14336)
a[1] ==a[a[0]] -->a[0]  Value = 0 ( *t1 = 7216519 && *t2 = 205973)
a[1] ==a[a[0]] -->a[0]  Value = 0 ( *t1 = 846609806 && *t2 = 43563464)
a[1] ==a[a[0]] -->a[0]  Value = 0 ( *t1 = 11227352 && *t2 = 506369272)
a[1] ==a[a[0]] -->a[0]  Value = 0 ( *t1 = 217741918 && *t2 = 214107364)

前几个就是..字符

后面的不知道怎么弄,不过..试试吧

374我输入的是ok

为啥ok = 374而ko = 274呢..

'o' = 111 'k' = 107 o : 14 k : 10 $10*26+14 = 274$

$14*26+10 = 374$

我觉得明确了..

我估计最后几个点我的答案绝对不是作者想要的2333

作者在取模..我又不是没事儿取模玩的人...

Test 6

lock6还是10个串?

突然感觉有checker就是好..log真心神器

这次是31进制的..execiting...

a[1] ==a[a[0]] -->a[0]  Value = 0 ( *t1 = 0 && *t2 = 15)
a[1] ==a[a[0]] -->a[0]  Value = 0 ( *t1 = 1 && *t2 = 13)
a[1] ==a[a[0]] -->a[0]  Value = 0 ( *t1 = 2 && *t2 = 394136050)
a[1] ==a[a[0]] -->a[0]  Value = 0 ( *t1 = 3 && *t2 = 951319991)
a[1] ==a[a[0]] -->a[0]  Value = 0 ( *t1 = 4 && *t2 = 973533818)
a[1] ==a[a[0]] -->a[0]  Value = 0 ( *t1 = 5 && *t2 = 796026279)
a[1] ==a[a[0]] -->a[0]  Value = 0 ( *t1 = 6 && *t2 = 254508514)
a[1] ==a[a[0]] -->a[0]  Value = 0 ( *t1 = 7 && *t2 = 740118828)
a[1] ==a[a[0]] -->a[0]  Value = 0 ( *t1 = 9 && *t2 = 929913515)
a[1] ==a[a[0]] -->a[0]  Value = 0 ( *t1 = 8 && *t2 = 208126208)

PS:t1是我输入的东西,所以会存在t1=9和t1=8反了的情况..我字母表背错啦

还有上面一句话莫名成链接了

然而...

Are you ready? Please enter 10 strings.
p
ok
n
ok
nxybfe
ok
bchdeeu
ok
bdaeyow
ok
|y~lgc
Expected a string consisting of a-z

就这么炸了..

...没办法咯..

这里是UOJ!取模的数字一定是998244353

去乖乖的加质数再取模吧

稍微改下5的程序即可..

lock6.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;
/*
t2 = 25) (z)
t2 = 23) (x)
t2 = 11) (l)
t2 = 17) (r)
t2 = 15) (p)
t2 = 14336)
t2 = 205973)
t2 = 43563464)
t2 = 506369272)
t2 = 214107364)
*/
const int modo=998244353;
int main()
{
    freopen("lock6.out","w",stdout);
    int n=10;
    int i;
    for (i=0;i<n;i++)
    {
        long long x;
        cin>>x;
        long long p=1;
        long long tx=x;
        for (;;)
        {
            p=1;
            for (;;)
            {
                p*=31;
                if (p>x) break;
            }
            tx=x;
            for (;;)
            {
                p/=31;
                if (p==0) break;
                int t=tx/p;
                tx-=t*p;
                if (t>=26) break;
            }
            if (p==0) break;
            x+=998244353;
        }
        p=1;
        for (;;)
        {
            p*=31;
            if (p>x) break;
        }
        for (;;)
        {
            p/=31;
            if (p==0) break;
            int t=x/p;
            x-=t*p;
            if (t>=26) break;
            printf("%c",t+'a');
        }
        printf("\n");
    }
}

Test 7

然后....

第7个点开始有TLE的迹象了?

a[1] ==a[a[0]] -->a[0]  Value = 0 ( *t1 = 1 && *t2 = 0)
a[1] ==a[a[0]] -->a[0]  Value = 0 ( *t1 = 499122177 && *t2 = 1)
a[1] ==a[a[0]] -->a[0]  Value = 0 ( *t1 = 332748118 && *t2 = 55555)
a[1] ==a[a[0]] -->a[0]  Value = 0 ( *t1 = 748683265 && *t2 = 66666666)
a[1] ==a[a[0]] -->a[0]  Value = 0 ( *t1 = 598946612 && *t2 = 234324325)
a[1] ==a[a[0]] -->a[0]  Value = 0 ( *t1 = 166374059 && *t2 = 643522257)
a[1] ==a[a[0]] -->a[0]  Value = 0 ( *t1 = 855638017 && *t2 = 865106053)
a[1] ==a[a[0]] -->a[0]  Value = 0 ( *t1 = 873463809 && *t2 = 179441119)
a[1] ==a[a[0]] -->a[0]  Value = 0 ( *t1 = 443664157 && *t2 = 864389574)
a[1] ==a[a[0]] -->a[0]  Value = 0 ( *t1 = 299473306 && *t2 = 407615848)

感觉自己QAQ......

这tm是啥

0 : 0

1 : 1

2 : 499122177 这是啥数字啊

好吧是逆元什么的..

所以..这怎么办呢....

暴力大法好了

很快我意识到这复杂度是吃不消的gg...

然而想到$A^{-1^{-1}} = A$....没了

lock7.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;
const int modo=998244353;
int power(int x,int y)
{
    if (y==0) return 1;
    int t=power(x,y/2);
    t=(long long)t*t%modo;
    if (y%2==1) t=(long long)t*x%modo;
    return t;
}
int a[15]={0,1,55555,66666666,234324325,643522257,865106053,179441119,864389574,407615848};
int main()
{
    freopen("lock7.out","w",stdout);
    int i;
    for (i=0;i<10;i++)
    {
        int t=power(a[i],modo-2);
        printf("%d\n",t);
    }
    return 0;
}

Test 8

又看到有77977这种进制的存在了...

不是很懂..输入的是数字

a[1] ==a[a[0]] -->a[0]  Value = 0 ( *t1 = 1 && *t2 = 0)
a[1] ==a[a[0]] -->a[0]  Value = 0 ( *t1 = 922932310 && *t2 = 1)
a[1] ==a[a[0]] -->a[0]  Value = 0 ( *t1 = 792803569 && *t2 = 55555)
a[1] ==a[a[0]] -->a[0]  Value = 0 ( *t1 = 194654562 && *t2 = 66666666)
a[1] ==a[a[0]] -->a[0]  Value = 0 ( *t1 = 911030197 && *t2 = 234324325)
a[1] ==a[a[0]] -->a[0]  Value = 0 ( *t1 = 591537984 && *t2 = 643522257)
a[1] ==a[a[0]] -->a[0]  Value = 0 ( *t1 = 170973641 && *t2 = 865106053)

不用看了肯定和上面的是同一组..数字..

现在的问题是.......前面那个*t1是什么鬼

输入x,则输出$x^{77977}$.....

取模的数字依旧...

然而这个我真的不会做啊.....

大概5s一个ok,一共100个ok大概要500s感觉不是很慌

#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;
const int modo=998244353;
int power(int x,int y)
{
    if (y==0) return 1;
    int t=power(x,y/2);
    t=(long long)t*t%modo;
    if (y%2==1) t=(long long)t*x%modo;
    return t;
}
int a[15]={0,1,55555,66666666,234324325,643522257,865106053,179441119,864389574,407615848};
int ans[15];
int main()
{
    freopen("lock8.out","w",stdout);
    int i;
    for (i=0;i<modo;i++)
    {
        int t=power(i,77977);
        int j;
        for (j=0;j<10;j++)
        {
            if (t==a[j]) ans[j]=i;
        }
        if (i%10000000==0) fprintf(stderr,"ok\n");
    }
    for (i=0;i<10;i++)
    {
        printf("%d\n",ans[i]);
    }
    return 0;
}

Test 9(UnAC)

目前看懂了它在对10取模..

有趣了

前面俩OK基本是送的..只要你输入了就有

如果输入的数字全是0会TLE...

后面暂时不太懂

感觉是10进制的数字!

你要输入一个高精度数字...然后要让它的某个属性=0

这个属性是啥我也不知道....

已知:

1,输入0会TLE

2,输入n位数,该属性最大为n

3,输入1似乎会被直接退掉..

看代码感觉..是个高精度..除法?

虽然底下的东西不是很懂..

但是很多地方有醚一样的*10...

而且乘出来的结果只有0和10两种..

难道是高精度减法模拟除法?返回余数有几位不是0,如果全是0就输出8个Yes

难道是A mod B problem?

目标:找出一个不是1和本身的因数!

81135286724930827243695738730846577445642314805943搜了下$2~2^{32}-1$竟然都不行....我有种要报警的想法了

接着搜看int范围内有没有吧.....

我相信..根据test 10的提示..

这个数一定是x^3的样子...

果断写了个立方根没开出来..

Test 10(UnAC)

随便输入俩不是1并且..大于等于0的数字,输出一个ok

后面的骗不出来了...

第10个点应该是输入两个数字

然后输出1个ok

然后进行一次运算如果符合一个条件则给3个ok

然后再进行一次运算..

虽然我不是很会分解质因数!

但是当我输入81135286724930827243695738730846577445642314805943 81135286724930827243695738730846577445642314805943的时候

他给了我4个ok!

里面似乎是..高精度乘法?不是很懂什么鬼情况...

两个数乘起来并不是里面的那个大数字..不是很懂..

换了一些数是过了的..

真心不明白到底是啥情况..

还有50位数到底怎么找质因数..

最终得分 : 86

(通过搜索$wolframalpha$得到100分)

我弃疗了..

主要是因为Test 9那个整数我实在是不会分解了..

去看题解了..

题解链接在这里..http://mxh1999.blog.163.com/blog/static/247319071201542853335300/

你们好可怕竟然不认真做题用$醚$一样的办法把它给爆了..

我是不想说什么..

我只能认真的做出1~8个点了..

后面的点实在是sxbk..不想说什么

竟然后面两个点$醛$是这么利用爆栈乱搞的我服...

认输认输..

PS:据说可以分解..

第9个点:

http://www.wolframalpha.com/input/?source=nav&i=the+Divisors+of+81135286724930827243695738730846577445642314805943

$8873721024639708188763151 * 9143321781205657319947993 = 81135286724930827243695738730846577445642314805943$

第10个点:

http://www.wolframalpha.com/input/?source=nav&i=the+Divisors+of+35442943893941093802986826887594209913195827438699

$5364013213705248146033063 * 6607542241578206359887773 = 35442943893941093802986826887594209913195827438699$

得出结论:vfk真良心出题人...

把答案长度压缩了下成功到达rank 1..虽然好像没啥意义..http://uoj.ac/submission/76216

直播玩交互题

2016-06-01 17:14:54 By absi2011

http://uoj.ac/problem/166

考虑到这个东西本地就能测正确性所以在哪里交都一样..

$A + 1$ problem

第一个点:

我觉得看懂题了的都能过..? http://uoj.ac/submission/74677

第2/3个点:

其实我果然题意读错了..不然一定是$8$分T_T

模拟高精度加法即可得 http://uoj.ac/submission/74678

第5个点:

我们可以把整个东西像线段树一样建出来..似乎我写的是树状数组

然后暴力像树状数组一样的查询...查询的复杂度为$O(\log n)$

这样的话..用的跳蚤的复杂度是$O(n \log n)$的,这样能过掉第5个点而不能过掉第4个点

PS:似乎常数大概是1/2,不然的话$17 * 100000 > 1.5*10^6 $而爆炸...

仔细算了下,大概复杂度是$O(2n + 1/2 n \log n)$的?

http://uoj.ac/submission/74739

第4个点:

当然我觉得,也可以再一遍处理把它处理出来,这样能过第4个点而不能过第五个点

要开始写分支了...

还是不算很难写的...

复杂度O(3n),t的复杂度是$O(2\log n)$

http://uoj.ac/submission/74740

所以

那下面就是A+B了

$A + B$ problem

显然暴力还能再过点分..然而不是很想写...毕竟写了也没意义...

感觉之前A+1 problem的办法直接搬过来的话,复杂度瞬间就成了$O(n^2)$的,这并不是我们想要的结果

而且之前枚举进位到的位置也是不可取的,因为..你每一位并不知道它要+1还是+2

而且每一位都算个进位复杂度也爆炸了吧..

思考一发,感觉可以分治

对于A和B,我们分前一半和后一半

我们假设前一半和后一半加好了,然后后一半是否有进位我们也知道了

如果有进位,不就是个A+1 problem了么..

然而这样有几个问题

1,一共有进行$\log n$次分治..每次的复杂度又是$\log n$似乎过不了什么点

2,我们不好判断那个进位的问题,就是如果进位是0我们按A+1 problem一算肯定要炸

我们来思考下怎么优化吧

感觉好无聊把小数据给过掉了..

    if (task_id==1) {
        C[0]=A[0]^1;
        bool c=A[0];
        int i;
        for (i=1;i<n;i++) {
            C[i]=A[i]^c;
            c=C[i]<A[i];
        }
    } else if (task_id==2) {
        C[0]=A[0]^B[0];
        bool c=A[0]&B[0];
        int i;
        for (i=1;i<n;i++) {
            C[i]=A[i]^B[i]^c;
            c=(A[i]&B[i])|((A[i]|B[i])&c);
        }
    } else if (task_id==3) {
        int c=0;
        int i,j;
        for (i=0;i<n;i++) {
            for (j=0;j<=i;j++) {
                c+=A[j]&B[i-j];
            }
            C[i]=c&1;
            c>>=1;
        }

刚才这一大段代码是grader里面的..感觉task_id==3就可以解了?

我发现我自己不会..感觉弃疗了如果哪次把这题过了后面的部分再接着更吧

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

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

关于O(n log^2 n)的后缀数组

2016-05-19 23:42:09 By absi2011
absi2011 Avatar