暑假第二十四测

 

题解：

第一题：二分+贪心；二分距离上限，两端的人能从两端取就从两端取，这样可以为中间的做贡献；

#include<bits/stdc++.h>
using namespace std; const int M = 10005; int a[M], b[M], pos[M], x, n, m; bool id[M]; #define ll long long inline int ab(int a, int b){ if(a > b)return a - b; return b - a; } bool check(ll d){ memset(id, 0, sizeof(id)); int lf = 1, rg = m, i; for(i = 1; a[i] <= x && i <= n; i++){ int j; for(j = lf; j <= m; j++){ if(ab(a[i], b[j]) + pos[j] <= d){ id[j] = 1;lf = j + 1;break; } } if(j == m + 1)return 0; } for(int z = n; z >= i; z--){ int j; for(j = rg; j >= 1; j--){ if(id[j])continue; if(ab(a[z], b[j]) + pos[j] <= d){ id[j] = 1;rg = j - 1;break; } } if(!j)return 0; } return 1; } int tot; int main(){ freopen("keys.in","r",stdin); freopen("keys.out","w",stdout); int Z = 0, W = 0; scanf("%d%d%d", &n, &m, &x); for(int i = 1; i <= n; i++) scanf("%d", &a[i]), Z = max(Z, ab(x, a[i])); for(int i = 1; i <= m; i++) scanf("%d", &b[i]), Z = max(Z, ab(b[i], x)); sort(a + 1, a + 1 + n); sort(b + 1, b + 1 + m); for(int i = 1; i <= m; i++)pos[i] = ab(b[i], x); ll rg; if(1LL*(Z + W + b[m] - a[1]) > 2e9)rg = 2e9; else rg = Z + W + b[m] - a[1]; ll lf = 1; int ans; while(lf <= rg){ ll mid = (lf + rg) >> 1; if(check(mid))ans = mid, rg = mid - 1; else lf = mid + 1; } printf("%d\n", ans); }

 

第二题：线段树，我们发现数的先后相对顺序是不变的，所以每次查询序列中最小值，并删除；知道上次的位置，我们优先取他右边小的（如果和左边相同），同一区间的优先选左边；我写了两个小时的第二题，结果少打了一个等号；

#include<bits/stdc++.h>
using namespace std; const int M = 1e5 + 10; #define inf 1e9 + 7
#define ll long long
int n, x, a[M], pos[M]; struct cd{ int val, id; bool operator < (const cd &a)const{ if(a.val == val)return a.id > id; return a.val < val; } }q[M]; struct Node{ Node *ls, *rs; int sum, v, vin; inline void up(){ sum = ls->sum + rs->sum; if(ls->v <= rs->v)vin = ls->vin; else vin = rs->vin; v = min(ls->v, rs->v); } }pool[M << 2], *tail = pool, *root; Node * build(int l = 1, int r = n){ Node *nd = ++tail; if(l == r) nd->sum = 1, nd->v = a[l], nd->vin = l; else { int mid = (l + r) >> 1; nd->ls = build(l, mid); nd->rs = build(mid + 1, r); nd->up(); } return nd; } #define Ls nd->ls, l, mid
#define Rs nd->rs, mid + 1, r

int query1(int L, int R, Node * nd = root, int l = 1, int r = n){ if(L <= l && r <= R) return nd->sum; else { int mid = (l + r) >> 1; int ans = 0; if(L <= mid)ans += query1(L, R, Ls); if(R > mid)ans += query1(L, R, Rs); return ans; } } int query2(int L, int R, Node * nd = root, int l = 1, int r = n){ if(L <= l && r <= R) return nd->vin; else { int mid = (l + r) >> 1; int ans1 = 0, ans2 = 0; if(L <= mid)ans1 = query2(L, R, Ls); if(R > mid)ans2 = query2(L, R, Rs); if(a[ans1] <= a[ans2])return ans1; else return ans2; } } void add(int pos, Node * nd = root, int l = 1, int r = n){ if(l == r) nd->sum--, nd->v = inf, nd->vin = 0; else { int mid = (l + r) >> 1; if(pos <= mid)add(pos, Ls); else add(pos, Rs); nd->up(); } } int main(){ freopen("cards.in","r",stdin); freopen("cards.out","w",stdout); scanf("%d", &n); a[0] = inf; for(int i = 1; i <= n; i++){ scanf("%d", &a[i]); } root = build(); int lst = query2(1, n); ll sum = query1(1, lst); add(lst); for(int i = 2; i <= n; i++){ int pos1 = query2(lst, n); int pos2 = query2(1, lst); if(a[pos1] <= a[pos2]){ sum += 1LL*query1(lst, pos1); lst = pos1; add(pos1); } else { sum += 1LL*query1(1, pos2) + query1(lst, n); lst = pos2; add(pos2); } //printf("%I64d %d %d\n", sum, a[pos1], a[pos2]);
 } printf("%I64d\n", sum); }

 

第三题：整除分块

#include<bits/stdc++.h>
using namespace std;
const int M = 105;
#define ll long long
int n;
ll k, a[M];
vector <ll> vec;

bool check(ll d){
    ll ans = 0;
    for(int i = 1; i <= n; i++){
        ll x = (a[i] + d - 1) / d;
        ans += d * x - a[i];
    }
    return ans <= k;
}
void split(ll a){
    vec.push_back(a);
    for(ll d = a; d > 0; ){
        ll k = (a + d - 1) / d;
        ll res = (a + k - 1) / k;
        vec.push_back(res);
        d = res - 1;
    }
}

int main(){
    freopen("bamboo.in","r",stdin);
    freopen("bamboo.out","w",stdout);
    scanf("%d%I64d", &n, &k);
    ll uni = 0;
    for(int i = 1; i <= n; i++){
        scanf("%I64d", &a[i]);
        split(a[i]);
    }
    sort(vec.begin(), vec.end());
    vec.erase( unique(vec.begin(), vec.end()), vec.end());
    vec.push_back( 10000000000000ll );
    int tot = vec.size();
    for(int i = 0; i < tot; i++){
        ll lf = vec[i], rg = vec[i + 1] - 1, ans = 0;
        while(lf <= rg){
            ll mid = (lf + rg) >> 1;
            if(check(mid))ans = mid, lf = mid + 1;
            else rg = mid - 1;
        }    
        uni = max(uni, ans);
    }
    
    
    printf("%I64d\n", uni);
}