初三奥赛模拟测试1

\(T1\) 回文 \(0pts\)

• 设 \(f_{x_{1},y_{1},x_{2},y_{2}}\) 表示从 \((1,1)\) 到 \((x_{1},y_{1})\) 结束的回文路径条数，其中 \((x_{1},y_{1})\) 关于最终形成的回文串的回文中心的对称点为 \((x_{2},y_{2})\) 。状态转移方程为 \(f_{x_{1},y_{1},x_{2},y_{2}}= \begin{cases} f_{x_{1}-1,y_{1},x_{2},y_{2}+1}+f_{x_{1}-1,y_{1},x_{2}+1,y_{2}}+f_{x_{1},y_{1}-1,x_{2},y_{2}+1}+f_{x_{1},y_{1}-1,x_{2}+1,y_{2}} & A_{x_{1},y_{1}}=A_{x_{2},y_{2}} \\ 0 & A_{x_{1},y_{1}} \ne A_{x_{2},y_{2}} \end{cases}\)

  • 因为合法的路径一定满足 \(x_{1}+y_{1}+x_{2}+y_{2}=n+m+2\) ，故可以省去 \(y_{2}\) 这一维。

• 在对角线（非严格意义）统计答案即可。

  点击查看代码

  const ll p=993244853;//注意模数不是998244353
  int f[510][510][510];
  char c[510][510];
  int main()
  {
      int n,m,i,j,x1,x2,y1,y2,ans=0;
      cin>>n>>m;
      for(i=1;i<=n;i++)
      {
          for(j=1;j<=m;j++)
          {
              cin>>c[i][j];
          }
      }
      f[1][1][n]=(c[1][1]==c[n][m]);
      for(x1=1;x1<=n;x1++)
      {
          for(y1=1;y1<=m;y1++)
          {
              for(x2=min(n,n+m+2-x1-y1),y2=n+m+2-x1-y1-x2;x2>=x1&&y2<=m;x2--,y2++)
              {
                  if(y2>=1&&c[x1][y1]==c[x2][y2])
                  {
                      f[x1][y1][x2]=(f[x1][y1][x2]+f[x1-1][y1][x2])%p;
                      f[x1][y1][x2]=(f[x1][y1][x2]+f[x1-1][y1][x2+1])%p;
                      f[x1][y1][x2]=(f[x1][y1][x2]+f[x1][y1-1][x2])%p;
                      f[x1][y1][x2]=(f[x1][y1][x2]+f[x1][y1-1][x2+1])%p;
                  }
              }
          }
      }
      for(x1=1;x1<=n;x1++)
      {
          for(y1=1;y1<=m;y1++)
          {
              x2=x1;
              y2=y1;
              if(x1+y1+x2+y2==n+m+2)
              {
                  ans=(ans+f[x1][y1][x2])%p;
              }
              x2=x1+1;
              y2=y1;
              if(x1+y1+x2+y2==n+m+2)
              {
                  ans=(ans+f[x1][y1][x2])%p;
              }
              x2=x1;
              y2=y1+1;
              if(x1+y1+x2+y2==n+m+2)
              {
                  ans=(ans+f[x1][y1][x2])%p;
              }
          }
      }
      cout<<ans<<endl;
      return 0;
  }
  

\(T2\) 快速排序 \(0pts\)

struct number
{
	bool isnan;
	int value;
};
bool operator < (const number& x, const number& y)
{
	if(x.isnan || y.isnan)
		return false;
	return x.value < y.value;
}
number tmp[1 << 20];
void qsort(number* _begin, number* _end)
{
	if(_begin + 1 >= _end)
		return;
	number a = *_begin, *s = _begin, *t = tmp;
	for(number* p = _begin + 1; p < _end; p++)
	{
		if(*p < a)*s = *p, s++;
		else *t = *p, t++;
	}
	*s = a, s++;
	for(t--; t >= tmp; t--) *(s + (t - tmp)) = *t;
	qsort(_begin, s - 1);
	qsort(s, _end);
}

• 部分分

  • \(12pts\) ：因输入中不包含 nan ，故直接排序即可。

• 正解

  • 因当 left.isnan=1 时，有 (A[i]<left)=0，故 L+1 到 R 的数都不会被放到 left 前；否则将 L+1 到 R 中小于 left.value 的数从小到大放到 left 前面。
  • multiset 大法好，注意迭代器失效问题。
  点击查看代码

  int b[600000];
  string a[600000];
  multiset<int>vis;
  int main()
  {
      int t,n,i,j,k;
      cin>>t;
      for(i=1;i<=t;i++)
      {
          cin>>n;
          for(j=1;j<=n;j++)
          {
              cin>>a[j];
              if(a[j]!="nan")
              {
                  b[j]=0;
                  for(k=0;k<a[j].size();k++)
                  {
                      b[j]=b[j]*10+a[j][k]-'0';
                  }
                  vis.insert(b[j]);
              }
          }
          for(j=1;j<=n;j++)
          {
              if(a[j]=="nan")
              {
                  cout<<"nan"<<" ";
              }
              else
              {
                  if(vis.find(b[j])!=vis.end())				
                  {
                      while(*vis.begin()<b[j])
                      {
                          cout<<*vis.begin()<<" ";
                          vis.erase(vis.begin());
                      }
                      cout<<b[j]<<" ";
                      vis.erase(vis.find(b[j]));
                  }
              }
          }
          cout<<endl;
      }
      return 0;
  }
  

\(T3\) 混乱邪恶 \(0pts\)

\(T4\) 校门外歪脖树上的鸽子 \(0pts\)

总结

• \(T1\)
  • 模数建议复制题面，注意不要打错。
• \(T2\)
  • 要搞清算法的本质。
  • 要提高读伪代码能力。