Educational Codeforces Round 180 (Rated for Div. 2) C. Coloring Game
C – Coloring Game思路：
不难看出，当 Alice 选完三个数 a b c（其中 a ≤ b ≤ c）后，Bob 能选的只有两种情况：
[*]选择 c，这样只用比较 a+b 和 c 的大小关系，其中 a+b 一定要大于c；
[*]选择数组最大值 a，这样只用比较 a+b+c 和 a 的大小关系，且前者要更大。
所以，排序后枚举外层 a_id 和内层 b_id：
[*]对于情况1：因为 a+b 的和一开始较小，后续逐渐变大，所以最大能选择的 c_id 一开始会较小，然后会随着 b_id 的变大而变大，该情况的“最大满足当前条件的 c_id”记为 k；
[*]对于情况2：因为 a+b 的和一开始较小，需要较大的 c 才能使得 a+b+c > a，因此满足条件的最小 c_id 一开始会较大，后续随着 a+b 的增大而变小，该情况的“最小满足当前条件的 c_id”记为 l。
那么，对于每对 (a_id, b_id)，可选的 c_id 数量即为 区间长度。利用 k、l 单调移动的特点，可用双指针在 O(n²) 内完成。
view code#include#define FAST ios::sync_with_stdio(false)#define abs(a) ((a)>=0?(a):-(a))#define sz(x) ((int)(x).size())#define all(x) (x).begin(),(x).end()#define mem(a,b) memset(a,b,sizeof(a))#define max(a,b) ((a)>(b)?(a):(b))#define min(a,b) ((a)0){if(b&1)res=res*a%MOD;a=a*a%MOD;b>>=1;}return res;}inline ll inv(ll x,ll p){return qpow(x,p-2,p);}inline ll Jos(ll n,ll k,ll s=1){ll res=0; rep(i,1,n+1) res=(res+k)%i; return (res+s)%n;}inline ll read(){ ll f=1,x=0; char ch=getchar(); while(ch>'9'||ch='0'&&ch
页:
[1]