​ 给我一样想这题要想很久的人的题解。

首先，有几个要确定的性质：

1.一个固定的结束人数 $m$，对应的开始人数一定是一个连续的整数区间 $[m, m + a[i] - 1]$。

2.对于下一轮的开始人数取值区间里的单个值 $x$，一定是从当前轮开始区间 $[x, x + a[i] - 1]$ 转移。

而 $x$ 的值是连续的区间，所以当前轮开始也一定是连续的区间。

3.由上两条可知，每轮开始也必为连续区间（指不会有分散的解）。手模样例印证。

4.假设 $l[i + 1]$ 和 $r[i + 1]$ 是下一轮的开始人数区间（包括第 $i$ 轮的结束人数区间）

如何由此求出当前轮的开始人数区间 $l[i]$ 和 $r[i]$ ？

我们知道，当前轮结束的数一定是 $a[i]$ 的倍数。

但 $l[i + 1]$ 和 $r[i + 1]$ 不保证这个范围内的每个数都是 $a[i]$ 的倍数。

因为 $l[i+1]$ 和 $r[i+1]$ 是由更后面的轮次（第 i+1 轮、第 i+2 轮、...、第 n 轮）约束出来的，它只保证从这个范围内的某个数出发，能完成后面所有轮次并最终剩下 2 人。

换句话说，我们要从 $l[i+1]$ 和 $r[i+1]$ 这个区间从取所有 $a[i]$ 的倍数做第 i 轮结束的值。

这些 $a[i]$ 倍数绝对不能跳出这个区间，不然不能满足后续约束，最后达成 2 人。

那么当前轮结束值最小的 $a[i]$ 倍数应该为多少呢？

$l[i] = (l[i + 1] + a[i] - 1) / a[i] * a[i]$

是 $l[i + 1]$ 的上取整 $a[i]$ 倍数。

那么当前轮结束值最大应该为多少呢？

$r[i] = r[i + 1] / a[i] * a[i]$

是 $r[i + 1]$ 的下取整 $a[i]$ 倍数。

现在我们得到 $l[i] =$ 第 i 轮结束值最小的 $a[i]$ 倍数，$r[i] =$ 第 i 轮结束值最大的 $a[i]$ 倍数。

注意，这里他俩现在还不是第 $i$ 轮的开始人数区间。

5.考虑到第 $i$ 轮最多淘汰 $a[i] - 1$ 人，所以想要得到第 $i$ 轮的开始人数最大值。

$r[i] += a[i] - 1$

第 $i$ 轮的开始人数最小值就是原来第 $i$ 轮的结束人数最小值啦（没有淘汰任何人）。

6.那什么情况下会无解？

即  $l[i+1]$ 和 $r[i+1]$ 区间内没有 $a[i]$ 的倍数的情况。

也就是：

if (l[i] > r[i]) {
	cout << "-1\n";
	return 0;
}

整体代码：

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

typedef unsigned long long LL;
const int N = 2e5 + 10;
LL a[N], l[N], r[N];

int main () {
	ios::sync_with_stdio(false);
	cin.tie(0);
	
	int n;
	cin >> n;
	for (int i = 1; i <= n; i ++) {
		cin >> a[i];
	}
	
	if (a[n] != 2) {
		cout << "-1\n";
		return 0;
	}
	
	l[n + 1] = r[n + 1] = 2;
	a[n + 1] = 1;
	for (int i = n; i >= 1; i --) {
		l[i] = (l[i + 1] + a[i] - 1) / a[i] * a[i];
		r[i] = r[i + 1] / a[i] * a[i];
		r[i] += a[i] - 1;
		if (l[i] > r[i]) {
			cout << "-1\n";
			return 0;
		}
	}
	
	cout << l[1] << " " << r[1] << "\n";
	
	return 0;
} 
​

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
long long n,a[N],l=2,r=2;
int main()
{
	cin>>n;
	for(int i=n;i>=1;i--)cin>>a[i];
	for(int i=1;i<=n;i++)
	{
		l=((l-1)/a[i]+1)*a[i];
		r=r/a[i]*a[i]+a[i]-1;
	}
	if(l>r) cout<<"-1\n",exit(0);
	cout<<l<<' '<<r;
	return 0;
}

实现思路差不多，

但这代码最后还要正推一遍验证,有点费时间...

#include<bits/stdc++.h>
using namespace std;
#define ll long long
ll n,a[100010],mi=2,mx=2,k,k1;
int main()
{
	scanf("%lld",&n);
	for(ll i=1;i<=n;i++)scanf("%lld",&a[i]);
	if(a[n]!=2){puts("-1");return 0;}
	for(ll i=n;i;i--)
	{
		if(mi/a[i]>mx/a[i]){puts("-1");return 0;}
		mi=ceil(mi*1.0/a[i])*a[i];
		mx=mx/a[i]*a[i]+a[i]-1;
	}
	k=mi,k1=mx;
	for(ll i=1;i<=n;i++)k=k/a[i]*a[i],k1=k1/a[i]*a[i];
	if(k!=2||k1!=2)puts("-1");
	else printf("%lld %lld\n",mi,mx);
	return 0;
}

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=2e5+10;
int a[N];
signed main()
{
	int n;cin>>n;
	for(int i=1;i<=n;i++)cin>>a[i];
	int mn=2,mx=2;
	for(int i=n;i>=1;i--)
	{
		int ml=ceil(1.0*mn/a[i])*a[i],mr=mx/a[i]*a[i];
		if(ml>mx||mr<mn||ml>mr)
		{
			cout<<-1;
			return 0;
		}
		mn=ml,mx=mr+a[i]-1;
	}
	cout<<mn<<' '<<mx<<'\n';
	return 0;
}

一道简单的递推，标的绿题，大概只有橙或黄（虽然有些细节卡了我好几次）。

已知最后还剩 $2$ 人，求初始人数，考虑逆向推。

由于最终的答案是一个 $[l,r]$ 区间，所以可以考虑求出经过每个 $a_i$ 前能取到的人数的区间 $[l,r]$，进行递推。

于是就抽离出了一个小的问题，已知经过 $a_i$ 后能取到的人数区间为 $[L,R]$，求经过 $a_i$ 前能取到的人数区间 $[l,r]$。

稍微思考一下，不难想出， $l = a_i \times p$ 以及 $r = a_i \times (q + 1) - 1$

考虑几种无解情况：

• $R < a_i$，这不用多说

• $[L,R]$ 被夹在 $a_i$ 的两个倍数之间，暂且叫它特殊情况吧，待会特判一下

除去这两种，容易算出：

$p = \left\lceil\dfrac{L}{a_i}\right\rceil$

$q = \left\lfloor\dfrac{R}{a_i}\right\rfloor$

• 对于特殊情况，根据上式算出 $p$，$q$ 后必有 $p > q$，舍去即可

上代码

#include <iostream>

using namespace std;

const int N = 100010;     
long long a[N],l[N],r[N];

int main()
{
	int n,i;
	cin>>n;
	for(i = n;i >= 1;i--) cin>>a[i]; //逆向存储方便递推 
	l[0] = r[0] = 2;
	for(i = 1;i <= n;i++)
	{
		if(r[i - 1] < a[i]) break;
		long long p = l[i - 1] / a[i] + (l[i - 1] % a[i] != 0?1:0),q = r[i - 1] / a[i];
		if(p > q) break;
		l[i] = p * a[i];
		r[i] = (q + 1) * a[i] - 1;
	}
	if(l[n] == 0) cout<<-1;
	else cout<<l[n]<<' '<<r[n];
	return 0;
}