哈哈 我是最先使用XOJ的人之一

膜拜zrt ing

首先是XOJ神奇的界面

还没有建设完的OJ是这个样子的

一共有5道题

这次小测有3道题 是T2T3T4

首先是骑士精神

（BZOJ1085）

上来一个裸搜 因为数据范围有梯度。。所以 混30分吧。。

然后就怎么改都改不对。。

改了快一个小时 发现ohc 题看错了 是12个黑 12个白 我当成了14个黑10个白

无语。。。

限制了一下搜索深度，比赛的时候限制了10层。后来发现 oh 限制11层还能多对一个点。。。。 这份代码是比赛后提交的。

//By: Sirius_Ren#include 
     
      #include 
      
       #include 
       
        using namespace std;char a[10][10];int cases,jyi,jyj,ans,b[10][10];int xx[10]={
    0,1,1,-1,-1,2,2,-2,-2},yy[10]={
    0,2,-2,2,-2,1,-1,1,-1};inline bool check(int t){    if(a[3][3]!=-1)return 0;    for(int i=1;i<=5;i++)        for(int j=i;j<=5;j++)            if(a[i][j]!=b[i][j])return 0;    return 1;}void dfs(int x,int y,int t){    if(t>=11)return;    if(check(t))ans=min(ans,t);    for(int i=1;i<=8;i++){        int jyx=x+xx[i],jyy=y+yy[i];        if(jyx>0&&jyx<=5&&jyy>0&&jyy<=5){            swap(a[x][y],a[jyx][jyy]);            dfs(jyx,jyy,t+1);            swap(a[x][y],a[jyx][jyy]);        }    }}int main(){    scanf("%d",&cases);    for(int i=1;i<=5;i++)        for(int j=i+1;j<=5;j++)b[i][j]=1;    b[1][1]=b[2][2]=1;b[3][3]=-1;    while(cases--)    {        ans=0x3ffffff;        for(int i=1;i<=5;i++){            for(int j=1;j<=5;j++){                cin>>a[i][j];                if(a[i][j]=='1')a[i][j]=1;                else if(a[i][j]=='0')a[i][j]=0;                else if(a[i][j]=='*'){a[i][j]=-1;jyi=i;jyj=j;}            }        }        dfs(jyi,jyj,0);        if(ans>15)printf("-1\n");        else printf("%d\n",ans);    }}
       
      
     

详细结果:

Case#1: Time Limit Exceeded time: 1024ms mem: 30764kb

Case#2: Presentation Error time: 124ms mem: 30764kb

Case#3: Presentation Error time: 348ms mem: 30764kb

Case#4: Presentation Error time: 324ms mem: 30764kb

Case#5: Presentation Error time: 476ms mem: 30764kb

Case#6: Wrong Answer time: 480ms mem: 30764kb

Case#7: Wrong Answer time: 556ms mem: 30764kb

Case#8: Wrong Answer time: 760ms mem: 30764kb

Case#9: Wrong Answer time: 776ms mem: 30764kb

Case#10: Wrong Answer time: 920ms mem: 30764kb

score: 40

PE的原因好像是章末回车 这个不重要。。

晚上回家以后改了改 加了个剪枝 A此题。

//By: Sirius_Ren#include 
     
      #include 
      
       #include 
       
        using namespace std;char a[10][10];int cases,jyi,jyj,b[10][10],cnt,flag,xx[10]={
    0,1,1,-1,-1,2,2,-2,-2},yy[10]={
    0,2,-2,2,-2,1,-1,1,-1};bool check(int t){    if(a[3][3]!=-1)return 0;    for(int i=1;i<=5;i++)        for(int j=i;j<=5;j++)            if(a[i][j]!=b[i][j])return 0;    return 1;}bool hong (int t){    int Q=0;    for(int i=1;i<=5;i++)        for(int j=1;j<=5;j++)            if(a[i][j]!=b[i][j]){Q++;if(Q+t>cnt)return 0;}    return 1;}void dfs(int x,int y,int t){    if(t==cnt){
    if(check(t))flag=1;return;}    if(flag)return;    for(int i=1;i<=8;i++){        int jyx=x+xx[i],jyy=y+yy[i];        if(jyx>0&&jyx<=5&&jyy>0&&jyy<=5){            swap(a[x][y],a[jyx][jyy]);            if(hong(t))dfs(jyx,jyy,t+1);            swap(a[x][y],a[jyx][jyy]);        }    }}int main(){    scanf("%d",&cases);    for(int i=1;i<=5;i++)        for(int j=i+1;j<=5;j++)b[i][j]=1;    b[1][1]=b[2][2]=1;b[3][3]=-1;    while(cases--){        for(int i=1;i<=5;i++)            for(int j=1;j<=5;j++){                cin>>a[i][j];                if(a[i][j]=='1')a[i][j]=1;                else if(a[i][j]=='0')a[i][j]=0;                else if(a[i][j]=='*'){a[i][j]=-1;jyi=i;jyj=j;}            }        for(cnt=1;!flag&&cnt<=15;cnt++)            dfs(jyi,jyj,0);        if(!flag)printf("-1\n");        else printf("%d\n",cnt-1),flag=0;    }}
       
      
     

据cxc说 这就叫ID-DFS （不就是加了个可行性剪枝&限制搜索深度嘛） 不管那么多了 他说是那就是吧

第二题是魔术师（BZOJ 3714）

呃呃根本想不到要用Kruskal 比赛的时候写了个区间DP 写挂了 （不挂就鬼了）

#include 
     
      #include 
      
       using namespace std;int tot=1,ans=0,f[8000005],n,jy;struct node{
    int x,y,wei;}d[8000005];bool cmp(node x,node y){
    return x.wei
      
     

这是晚上回家写得

第三题

写了个数组模拟

ZRT的评测机太快 一开始AC了 然后他就把Time limit从1000ms改到了500ms 80分也相当高了

刚才写了一下正解。 用set 20行之内就能搞定

插入的数的fa只能是上一个比它大的数或者是上一个比它小的数 （要看时间先后）

//By: Sirius_Ren#include 
     
      #include 
      
       using namespace std;int n,a[100005];set
       
        
          >s;int main(){    scanf("%d%d",&n,&a[1]);    s.insert(make_pair(a[1],1));    for(int i=2;i<=n;i++){        scanf("%d",&a[i]);        set
         
          
            >::iterator it=s.upper_bound(make_pair(a[i],0)),it2=it--; if(it2==s.begin()) printf("%d ",*it2); else if(it->second>it2->second) printf("%d ",*it); else printf("%d ",*it2); s.insert(make_pair(a[i],i)); }}
          
         
        
       
      
     

代码长度短的惊人

比赛结果 （暴力出奇迹）

Orz gzz Orz lty