2021牛客暑期多校训练营6

F.Hamburger Steak

题意

给n个汉堡，m个锅，每个锅只能同时做一个汉堡，做第i个汉堡需要(a_i)的时间，并且每个汉堡最多只能被两个锅做，问在尽可能减少平均每口锅做汉堡的时间的条件下，每个汉堡的方案。

思路

一看，一想，wtf，好难啊，想了半天，在看，emmm，wc，~~签到题~~
每个汉堡无论被几个锅做，都是(a_i)那么最大的时间就是(max(a_i , sum / m + (sum % m != 0)))
然后直接写就行了。。

code:


int a[N];
void solve(){
    int n,m;
    sc("%lld%lld", &n, &m);
    int sum = 0, maxn = 0;
    for(int i = 1;i <= n;i ++) {
        scanf("%lld", &a[i]);
        sum += a[i];
        maxn = max(maxn,a[i]);
    }
    int sz = max(maxn, sum / m + (sum % m != 0));
    int now = sz;
    int cnt = 1;
    for(int i = 1;i <= n;i ++) {
        if(now >= a[i]) {
            pr("1 %d %lld %lld
", cnt, sz - now, sz - now + a[i]);
            now -= a[i];
            if(!now) now = sz,cnt ++;
        }else {
            pr("2 %d %lld %lld %d %lld %lld
", cnt + 1, 0, a[i] - now, cnt, sz - now, sz);
            now = sz - (a[i] - now);
            cnt ++;
//             if(!now) now += sz, cnt ++;
        }
    }
}

H.Hopping Rabbit

题意

一个二维坐标轴，兔子每次跳的距离是d，并且只向上下左右跳，你需要找到兔子的起始坐标，让他怎么跳都跳不到给出的陷阱中，陷阱为一个矩阵((x_i,y_i o x_j,y_j))(左下角到右上角)。

思路

扫描线，把空间上所有大小为d * d的矩形合并起来，然后扫一遍，看看有没有空的就行

code :

struct node {
    int l,r;
};
// sum维护区间最小值
int sum[N << 2], laz[N << 2];
 
void update(int u,int l,int r,int L,int R,int v) {
    if(L > r || l > R) return;
    if(L <= l && R >= r) {
        sum[u] += v;
        laz[u] += v;
        return;
    }
    int mid = l + r >> 1;
    if(L <= mid) update(u << 1, l, mid, L, R, v);
    if(R > mid) update(u << 1 | 1, mid + 1, r, L, R, v);
    sum[u] = min(sum[u << 1], sum[u << 1 | 1]) + laz[u];
    return;
}
 
int query(int u,int l,int r) {
    if(l == r) return l;
    int mid = l + r >> 1;
    if(laz[u] + sum[u << 1] == sum[u]) {
        return query(u << 1,l,mid);
    }else {
        return query(u << 1 | 1,mid + 1,r);
    }
}
 
vector<node> st[N], ed[N];
 
void solve(){
    int n,d;
    cin >> n >> d;
    bool flag = true;
    for(int i = 1;i <= n;i ++) {
        int x1,x2,y1,y2;
        cin >> x1 >> y1 >> x2 >> y2;
		// 精度问题
        x1 += d * INF,y1 += d * INF, y2 += d * INF, x2 += d * INF;
        vector<node> a,b;
        if(x2 - x1 >= d && y2 - y1 >= d) {
            flag = 0;
        }
        if(x2 - x1 >= d) {
            a.pb({0,d - 1});
        }else if((x2 - 1) % d >= x1 % d) {
            a.pb({x1 % d, (x2 - 1) % d});
        }else {
            a.pb({0,(x2 - 1) % d});
            a.pb({x1 % d, d - 1});
        }
 
        if(y2 - y1 >= d) {
            b.pb({0,d-1});
        }else if((y2 - 1) % d >= y1 % d) {
            b.pb({y1 % d, (y2 - 1) % d});
        }else {
            b.pb({0,(y2 - 1) % d});
            b.pb({y1 % d, d - 1});
        }
 
        for(auto sa : a) {
            for(auto sb : b) {
                st[sa.l].pb(sb);
                ed[sa.r + 1].pb(sb);
            }
        }
    }
    if(!flag) {
        cout << "NO" << endl;
        return;
    }
    for(int i = 0;i < d;i ++) {
        // 维护差分
        for(auto a : st[i]) {
            update(1,0,d-1,a.l,a.r,1);
        }
        for(auto b : ed[i]) {
            update(1,0,d-1,b.l,b.r,-1);
        }
        if(sum[1] == 0) {
            cout << "YES" << endl;
            cout << i << ' ' << query(1,0,d-1) << endl;
            return;
        }
    }
    cout << "NO" << endl;
}

I. Intervals on the Ring

题意

给你一个n,m，序列长度为n且(n,1)为相邻的，(1,3)表示(1,2,3), (3,1)表示(3,4,5,1), 并且给出m个区间，让你构造一个k个区间，令这k个区间的交集为给出的m个区间的并集。

思路

构造题，考场没想到简单的做法，所以写了贼长
就是类似：
110011001100110011
连续1表示需要交集的部分，那么就这样构造, (5,2), (9,5),(13,10),(17,14)记录每一个连续的l,r即可,(r_i o l_{i-1})即可，最后特判最后一个和第一个是否相连即可。

code:

int a[N];
 
vpi ans;
void solve(){
    int n,m;
    cin >> n >> m;
    int l,r;
    ans.clear();
    for(int i = 1;i <= 2 * n;i ++) a[i] = 0;
    fep(i,1,m) { // 构建差分数组
        cin >> l >> r;
        if(l <= r) {
            a[l] ++, a[r + 1] --;
        }else {
            a[l] ++, a[r + n + 1] --;
        }
    }
    if(m == 1) {
        cout << "1" << endl << l << ' ' << r << endl;
        return;
    }
    for(int i = 1;i <= 2 * n;i ++) {
        a[i] += a[i - 1];
    }
    // 建立双指针
    l = 1,r = 0;
    while(l <= n && !a[l] && !a[l + n]) l ++;
    r = l;
    while(r <= n && (a[r] || a[r + n])) r ++;
    if(r > n) {
        cout << "1" << endl << l << ' ' << n << endl;
        return;
    }
    int now = r;
    r --;
    ans.pb({l,r});
    while(now <= n && (!a[now] && !a[now + n])) now ++;
    while(now <= n) {
        int i = now;
        while(i <= n && (a[i] || a[i + n])) i ++;
        ans.push_back({now,i - 1});
        now = i;
        while(now <= n && (!a[now] && !a[now + n])) now ++;
    }
    if(ans.size() == 1) {
        cout << "1" << endl;
        cout << ans[0].first << ' ' << ans[0].second << endl;
    }else {
        if((a[n] || a[n + n]) && (a[1] || a[1 + n])) {
            cout << ans.size() - 1 << endl;
            for(int i = 1;i < ans.size();i ++) {
                cout << ans[i].first << ' ' << ans[i - 1].second << endl;
            }
        }else {
            cout << ans.size() << endl;
            for(int i = 1;i < ans.size();i ++) {
                cout << ans[i].first << ' ' << ans[i - 1].second << endl;
            }
            cout << ans[0].first << ' ' << ans[ans.size() - 1].second << endl;
        }
    }
}

J.Defend Your Country

题意

给出一个无向连通图，每个点的权值为(w_i),那么当一个连通块中的点数为奇数个那么整个联通块的价值是-1*权值和，否则是+1 *权值和，让你通过删边来最大化整个图中的价值

思路

如果当前整个图的点都是偶数个，那么答案直接是(sum_{1}^{n} w_i)

若为奇数个那么一定是将整个图变成偶+1奇+偶最优，那么令中间的奇数点最小即可。

那么首先，这个奇数点是割点，然后它去的边必须也是偶数的

code:

int n,m;
ll w[N];
int h[N], e[M], ne[M], idx;
int dfn[N],low[N],times;
int sz[N];

ll res = 1e9 + 7;

void add(int a,int b) {
    e[idx] = b,ne[idx] = h[a], h[a] = idx ++;
}

void tarjan(int u,int fa = -1) {
    dfn[u] = low[u] = ++ times;
    sz[u] = 1;
    bool ok = 1;
    for(int i = h[u];~i;i = ne[i]) {
        int j = e[i];
        if(j == fa) continue;
        if(!dfn[j]) {
            tarjan(j,u);
            low[u] = min(low[u],low[j]);
            if(u == 1) {
                // 根节点是割点的情况
                if(i != h[u] && sz[j] % 2) ok = 0;
            }
            else if(dfn[u] <= low[j] && sz[j] % 2) { // 割点
                ok = 0;
            }
            sz[u] += sz[j];
        }else low[u] = min(low[u], dfn[j]);
    }
    if(ok) res = min(res, w[u]);
}


void solve(){
    n = rd(), m = rd();
    ll sum = 0;
    fep(i,1,n) w[i] = rd(), sum += w[i];
    idx = times = 0;
    res = 1e9 + 7;
    for(int i = 1;i <= n;i ++) {
        h[i] = -1;
        dfn[i] = 0;
        sz[i] = 0;
    }
    fep(i,1,m) {
        int a = rd(),b = rd();
        add(a,b);
        add(b,a);
    }
    if(n % 2 == 0) {
        cout << sum << endl;
        return;
    }
    // 寻找割点，令整个图分割成(偶奇偶)即可
    tarjan(1);

    ll ans = max(-sum, sum - 2 * res);
    pr("%lld
", ans);
}