看起来是一个挺有趣的题,来玩一玩......
目前完成进度 : 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;
}
鄂公网安备 42010202000505 号