题解：UVA10730 Antiarithmetic?

UVA10730

题意简述

给定整数 $n$，并给出 $0$ 至 $n-1$ 的一个排列 $p$（下标从 $0$ 开始），判断这个排列是否满足：对于任意的 $0 \le i < j < k < n$，不存在 $(p_i,p_j,p_k)$ 构成等差数列。如果满足，则称这个序列为 “antiarithmetic” 的。

解题思路

首先，经过尝试，如果暴力枚举 $i,j,k$ 并判断任意三项是否构成等差数列，结果会超时。

于是尝试枚举中间项 $p_j$ 和公差 $d$，并判断 $p_j-d$ 和 $p_j+d$ 两项是否在数列 $p$ 中。如果存在，则记 $p_j-d$，$p_j$ 和 $p_j+d$ 这三项的下标分别为 $i,j,k$，并判断 $i,j,k$ 是否是单调的，即 $i<j<k$ 或 $i>j>k$ 即可。如果找到了符合条件的三项，则说明这不是 “antiarithmetic” 序列。

代码

#include<bits/stdc++.h>
using namespace std;

inline int read()
{
	char c=getchar();int x=0,f=1;
	for(;!isdigit(c);c=getchar())if(c=='-')f=-1;
	for(;isdigit(c);c=getchar())x=x*10+c-48;
	return x*f;
}

#define r(a) (a)=read()

int n,x,MAX,MIN,p1,p2,p3; //p1,p2,p3分别为三个数的下标
int pos[10005]; //pos[i]表示数i在序列中的位置（下标）
bool chk; //标记判断结果

signed main()
{
	while (cin>>n)
	{
		getchar(); //读冒号
		if (n==0) return 0; 
		memset(pos,0,sizeof pos); //初始化pos数组
		MAX=-1; MIN=1e8; chk=1;
		MAX=n-1;
		MIN=0;
		for (int i=1;i<=n;i++)
		{
			r(x);
			pos[x]=i; //标记x的下标
		}
		for (int i=MIN;i<=MAX;i++)
		{
			for (int d=1;d<=min(i-MIN,MAX-i);d++) //d为公差
			{
				if (pos[i]&&pos[i-d]&&pos[i+d]) //三个数都在p中
				{
					p1=pos[i-d];
					p2=pos[i];
					p3=pos[i+d];
					if ((p1<p2&&p2<p3)||(p1>p2&&p2>p3)) //判断下标是否是单调的
					{
						chk=0;
						goto END; //直接结束
					}
				}
			}
		}
		goto END;
		END: //输出
		printf(chk?"yes\n":"no\n");
	}
}