Codeforces Global Round 30
A
长 \(n\) 的数组 \(a\)，每可以选一个 \(x\) 满足 \(\operatorname{min}(a_i,a_{i+1})\le x \le \operatorname{max}(a_i,a_{i+1})\)，然后去掉 \(a_i,a_{i+1}\) 并将其替换为 \(x\)。给定数 \(k\)，问能否若干次操作让 \(a\) 数组只剩数字 \(k\)？
我们发现这个 \(=\) 是很好的性质。为了让 \(k\) 的空间尽可能大，又想到保留最大最小值。于是可以这样构造：找到最大值，把它周围的全部和他操作，\(x\) 就钦定为这个最大值。最小值也同理，把附近所有都换掉。最后只剩最大最小值，当 \(k\) 在此范围内时就输出 YES，否则 NO。
点击查看代码
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define For(i,l,r) for(int i=l;i<=r;i++)
int n;
const int N=110;
ll a[N],x,mn,mx;
void solve(){ mn=1e18;mx=-1e18;cin>>n;For(i,1,n){cin>>a[i];mn=min(mn,a[i]);mx=max(mx,a[i]);}cin>>x;if(mn<=x&&x<=mx){cout<<"YES\n";}else cout<<"NO\n";}
int main(){ ios::sync_with_stdio(0); cin.tie(0);cout.tie(0); int T; cin>>T; while(T--)solve(); return 0;
}
B
给定 \(a_1<a_2<\cdots<a_{n-1}<a_n\)，选一对 \(a_i<a_j\) 满足 \(a_j \ mod \ a_i\) 为偶数。\(n\le 10^5\)。
分讨，条件转化为 \(a_j-k\times a_i\) 为偶数，\(k\) 为商。如果存在两个偶数的话，显然成立。如果只有一个偶数，可以拿这个偶数试所有的奇数，可以就输出。最后只留下奇数匹配奇数的问题。
排序，现在有奇数序列 \(b_1,b_2,\cdots,b_m\)。注意到：如果 \(b_2<2\times b_1\)，\(b_2\ mod\ b_1=b_2-b_1=偶数\)。也就是假如存在一段 \(b\) 序列满足相邻两数都不会凑出正确答案，那么是指数级增长的，项数最多 \(\log V\)。
因此暴力枚举一对数，实际复杂度是 \(O(n\log V)\) 的。
点击查看代码
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define For(i,l,r) for(int i=l;i<=r;i++)
int n;
const int N=1e5+10;
ll a[N];
ll even[N],c0;
ll odd[N],c1;
void solve(){ cin>>n;c0=c1=0;For(i,1,n){cin>>a[i];if(a[i]%2==0)even[++c0]=a[i];else odd[++c1]=a[i];}if(c0>=2){cout<<min(even[1],even[2])<<" "<<max(even[1],even[2])<<"\n";return;}if(c0==1){For(i,1,c1){ll mx=max(odd[i],even[1]);ll mn=min(odd[i],even[1]);if((mx%mn)%2==0){cout<<mn<<" "<<mx<<"\n";return;}}}sort(odd+1,odd+c1+1);For(i,1,c1){For(j,i+1,c1){if((odd[j]%odd[i])%2==0){cout<<odd[i]<<" "<<odd[j]<<"\n";return;}}}cout<<"-1\n";
}
int main(){ ios::sync_with_stdio(0); cin.tie(0);cout.tie(0); int T; cin>>T; while(T--)solve(); return 0;
}
C
你现在身处地牢，面对着 \(m\) 个怪物和 \(n\) 把剑。
\(i\) 把剑的伤害是 \(a_i\)，\(i\) 只怪物的生命值是 \(b_i\) 。用伤害为 \(x\) 的剑杀死 \(i\) 的怪物后，这把剑就会消失。然后，如果 \(c_i>0\) ，你将获得一把伤害为 \(\operatorname{max}(x,c_i)\) 的新剑。否则，你将一无所获。
现在你想知道最多可以杀死多少只怪物。注意，每只怪物你最多只能杀死一次。\(n,m\le 2\times 10^5,a,b,c\le 10^9\)。