Noip2016 D1T1 题解

#include<iostream>
#include<cstdio>
using namespace std;
const int L=100000+30; 
int wa=0;
struct rose{
  int a;//chao xiang
  char b[13];//name
  struct rose *right=NULL;
  struct rose *left=NULL;
} ;
struct rose tree[L];
void chao(int a,int i,int n)
{
  if (i<n)
    {
    if (a==1)
      {
    tree[i].right=&tree[i-1];
    tree[i].left=&tree[i+1];
      }
    if (a==0)
      {
        tree[i].left=&tree[i-1];
    tree[i].right=&tree[i+1];
      }
   }
  //继续建表
  if (i==n)
   {
    if (a==1)
      {
    tree[i].right=&tree[i-1];
    tree[i].left=&tree[1];
      }
    if (a==0)
      {
    tree[i].left=&tree[i-1];
    tree[i].right=&tree[1];
      }
    if (tree[1].a==1)
      {tree[1].right=&tree[i];tree[1].left=&tree[2];}
    if (tree[1].a==0)
      {tree[1].left=&tree[i];tree[1].right=&tree[2];}
   }
  //建表完毕
}

void cinrose(int n)
 {
   int i=1;
   for (;;)
     {
       scanf("%d %s",&tree[i].a,tree[i].b);//读入
  if (i==1){i++; continue;}//第一个节点，忽略
  else chao(tree[i].a,i,n);//建立链表
  if (i==n) break;//end
       i++;
     }
 }
void shuren(int m)
{
  int i=1,x=0,y=0,k=99;
  struct rose *s=&tree[1];
  // char name=tree[s].name;
  for(;;)
    {
      scanf("%d %d",&x,&y);
  if (x==0) {k=s->a;s=s->left;y--;
   while(y>0){if (s->a!=k) s=s->right;else s=s->left;y--;}}
  if (x==1) {k=s->a;s=s->right;y--;
    while(y>0) {if (s->a!=k) s=s->left;else s=s->right;y--;}}
  if (i==m) break;//end
  i++;
    }
  cout<<s->b<<endl;
}

int main()
{
  int n=0,m=0;
  cin>>n>>m;
  wa=n;
  cinrose(n);
  shuren(m);
  return 0;
}

这是段还可以的代码，用链表来模拟，但是会超时，大数据会被卡时间复杂度，只有很低的65分. 所以我尝试了进一步思考，改了一下模拟的方式，使时间复杂度得以降低，在数据规模大的时候这一优势将较之与前一种实现方式体现出明显的差异。 AC code:

#include <iostream>
#include <cstdio>
using namespace std;
const long long int L=1000000+10;
struct round{long long int a;char b[16];} tree[L];
void builta(long long int n)
{long long int i=1;for(;;){scanf("%d %s",&tree[i].a,tree[i].b);if (i==n) break;i++;}}

void founda(long long int n,long long int m)
{long long int i=1,x=0,y=0,p=1;for(;;){scanf("%d %d",&x,&y);
{
if(x==0){if(tree[p].a==0)p=p-y<=0?n+p-y:p-y;else if(tree[p].a==1)p=p+y>n?p+y-n:p+y;}
if(x==1){if(tree[p].a==1)p=p-y<=0?n+p-y:p-y;else if(tree[p].a==0)p=p+y>n?p+y-n:p+y;}}
 if(i==m)break;i++;}printf("%s",tree[p].b);}

int main()
{
  long long int n,m;
  cin>>n>>m;
  builta(n);
  founda(n,m);

  return 0;
}