Codeforces 975 div2
A. Max Plus Size
点击查看代码
void solve() {
int n;cin>>n;
int imax1=0,imax2=0;
for(int i=1;i<=n;i++) {
int x;
cin>>x;
if(i%2)
imax1=max(imax1,x);
else
imax2=max(imax2,x);
}
if(!n%2) cout<<max(imax1,imax2)+n/2<<endl;
else cout<<max(imax1+(n+1)/2,imax2+n/2)<<endl;
}
B. All Pairs Segments
每个线段内部的点的答案都是一样的，在处理一下线段两边边界的点。被包含次数就是左边*右边。用map记录答案即可。此题为贡献法，每个线段对点的贡献。
点击查看代码
const int maxn=2e6+5;
int h[maxn];
void solve() {
int n,q;
cin >> n >> q;
int a[n];
for ( int i = 1; i <= n; i++ ) cin >> a[i];
map<int,int> cnt;
for ( int i = 1; i < n; i++ ){
cnt[(n - i) + (i - 1) * (n - i + 1)]++;
if ( a[i + 1] - a[i] > 1 ){
cnt[i * (n - i)] += (a[i + 1] - a[i] - 1);
}
}
cnt[n - 1]++;
while ( q-- ){
int k;
cin >> k;
cout << cnt[k] << " ";
}
cout << endl;
}
C. Cards Partition
找最大容量，数一定，那么要尽可能小。观察到众数数量mx为最小可能组数，无法改变。则改变容量，确定最大容量。遍历大小，在每组大小确定的情况下，此时的组数是最小的可以保证合法的组数，而我们只需要判断 mx*i<=sum+k即可。
点击查看代码
const int maxn=2e6+5;
int a[maxn];
int n,k,sum,mx;
void solve(){
cin >> n >> k;
mx = 0, sum = 0;
for ( int i = 1; i <= n; i++ ){
cin >> a[i];
mx = max(mx, a[i]);
sum += a[i];
}
int ans = 0;
for ( int i = 1; i <= n; i++ ){
if ( k < (sum + k) % i ) continue;
if ( mx * i <= sum + k ){
ans = max(ans, i);
}
}
cout << ans << endl;
}