Codeforces gym 103990

C – Correct

prob.:

ICPC赛制规则，九点开始的场，有个队只交了一发且直接AC，给出提交时间，问罚时

code：

#include
using namespace std;

signed main() {
    int hh, mm;
    cin >> hh >> mm;
    cout << (hh - 9 ) * 60 + mm;
}

F – Finalists

prob.:

一共6个地区，给出final队伍名额分配规则，给出相应的数据，问t被分到的名额

code：

#include

using namespace std;

struct node {
    string name;
    double val;
};

vector<node> vec;

signed main() {
    ios::sync_with_stdio(false);
    int n;
    cin >> n;
    for(int i = 0; i < 6; ++ i) {
        string s;
        cin >> s;
        double a, b, c, d, e;
        cin >> a >> b >> c >> d >> e;
        double tmp = a * 0.56 + b * 0.24 + c * 0.14 + d * 0.06 + e * 0.3;
        vec.push_back({s, tmp});
    }
    sort(vec.begin(), vec.end(), [&](node a, node b){
        return a.val> b.val;
    });
    int ans = n /6;
    n=n%6;
    for(int i = 0; i < n; ++ i) {
        if(vec[i].name == "t") ans ++;
    }
    cout << ans << endl;
}

H – Heximal （没写

prob.:

给一个n位的十进制数，问转化成六进制之后的位数

n 5e5

ideas：

我看榜都过穿了，但怎么想都不好写，一看题解是python，打扰了

D – Distance and Tree

prob.:

定义树上两个点的距离是这两个点的路径的长度

一个正向的问题是，给出n个点的树，n个点在二维平面上，平面上没有树边交叉，规定一个根，计算出根到每个点的距离

现在有根到每个点的距离数组，和n个点的位置（在一个大圆上平均分布），要求构造树边使得边不交叉且满足距离数组

ideas：

根到根的距离为0，判断找出唯一的根

对距离排序，贪心地将每个点连到相邻的距离恰好小1的点上

code：

#include

using namespace std;

const int N = 1e6 + 10;
const int inf = 0x3f3f3f3f;
int d[N];

vector<int> g[N];
set<int> vec;

set<int> st;

signed main() {
    ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);

    int n;
    cin >> n;

    vector<pair<int, int> > res;

    int rt = -1;
    for (int i = 1; i  n; ++i) {
        cin >> d[i];
        g[d[i]].push_back(i);
        vec.insert( d[i]);
        if (d[i] == 0) {
            if (rt == -1) rt = i;
            else {
                cout << -1;
                return 0;
            }
        }
    }

    st.insert(rt);
    int L = rt, R = rt;

    for (auto dist : vec) {
        if (dist == 0) continue;
        for(auto x : g[dist]) {
            bool flag = false;
            if (x > R || x < L) {
                if (d[L] == dist - 1) {
                    res.push_back({L, x});
                    flag = true;
                } else if (d[R] == dist - 1) {
                    res.push_back({R, x});
                    flag = true;
                }
                if (!flag) {
                    cout << -1;
                    return 0;
                }
            }
            else {
                auto it = st.lower_bound(x);
                it--;
                if (d[*it] == dist - 1) {
                    res.push_back({*it, x});
                    flag = true;
                }
                else {
                    it = st.upper_bound(x);
                    if (d[*it] == dist - 1) {
                        res.push_back({*it, x});
                        flag = true;
                    }
                }

                if (!flag) {
                    cout << -1;
                    return 0;
                }
            }

        }

        for(auto x: g[dist]) {
            L= min(L, x);
            R= max(R, x);
            st.insert(x);
        }

    }

    for(auto [u, v] : res) {
        cout << u << " "<< v << "\n";
    }
}

G – Geekflix

prob.:

有n个视频，编号1到n，呈循环，每个视频有两个属性a和b

刚开始在1号，有三种操作，1.移动到编号-1的位置，2.移动到编号+1的位置，3.播放当前视频

第k次播放i号视频可以获得的价值为m a x ( 0 , a i − ( k − 1 ) × b i ) max(0, a_i – (k -1)\times b_i)m a x (0 ,a i ​−(k −1 )×b i ​)

求m次操作能获得的最大价值

n 200 m 1000 a, b 5000

ideas：

破环成链，枚举左右到达的端点（需要判断1号点是不是在区间内

把移动的操作数计算上，然后贪心地看视频

O ( n 2 m l o g m ) O(n^2 m logm)O (n 2 m l o g m )

复杂度有点悬的样子但跑不满

code:

#include

using namespace std;

typedef long long ll;
const int N = 1e3 + 10;
const int inf = 0x3f3f3f3f;

int a[N], b[N];

signed main() {
    ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);

    int n, m;
    cin >> n >> m;
    for (int i = 0; i < n; ++i) cin >> a[i], a[i + n] = a[i];
    for (int i = 0; i < n; ++i) cin >> b[i], b[i + n] = b[i];

    auto in = [&](int l, int r) {
        if(l  0 && 0  r) return true;
        if(l  n && n  r) return true;
        return false;
    };

    auto dis = [&](int l, int r) {
        int res =0;
        if(l == 0) return (r - l + 1);
        res = min(n - l , r - n) + (r- l + 1);
        return res;
    };

    auto calc = [&](int pos, int k) {
        return max(0, a[pos] - (k - 1) * b[pos]);
    };

    int ans = 0;
    for(int l = 0; l < 2 * n; ++ l) {
        for(int r = l; r <2 * n; ++ r ) {
            if(!in(l, r) || (r - l + 1) > n) continue;
            int time = m  - dis(l, r)+ 1;
            priority_queue<pair<int, pair<int, int>>> que;
            for(int i = l; i  r; ++ i) {
                que.push({calc(i, 1), {i, 1}});
            }
            int res = 0;
            for(int i = 0; i < time; ++ i) {
                res += que.top().first;
                int pos = que.top().second.first;
                int k=que.top().second.second;
                que.pop();
                que.push({calc(pos, k + 1), {pos, k + 1}});
            }
            ans = max(res, ans);
        }
    }

    cout << ans << endl;
}

B – Balanced Seesaw Array

prob：

n个数的序列，定义一种特殊的子序列[l, r]满足条件为，∃ k ∈ [ l , r ] , s t . ∑ i ( i − k ) × a i = 0 \exist k \in[l, r], st. \sum_{i} (i – k)\times a_i = 0 ∃k ∈[l ,r ],s t .∑i ​(i −k )×a i ​=0

三种操作1. 区间赋值 2.区间加 3.询问区间是否为特殊的子序列

n 1e5 q 1e6 保证ll够用

ideas：

拆一下式子，∑ i ( i − k ) × a i = 0 = ∑ i a i × i − k × ∑ i a i \sum_{i} (i – k)\times a_i = 0 = \sum_i a_i \times i – k \times \sum_i a_i ∑i ​(i −k )×a i ​=0 =∑i ​a i ​×i −k ×∑i ​a i ​

维护区间a i a_i a i ​的和和a i × i a_i\times i a i ​×i的和就可以O(1)判断k是否在区间内

需要注意的是如果两个和都是0的时候k可以任意取值，这时候也满足条件

线段树维护 1.区间赋值 2.区间加 3.区间和 4.区间a i × i a_i\times i a i ​×i 的和

线段树两个lazytag，区间赋值和区间加，其中区间赋值的优先级大于区间加

细节看代码吧（其中asum表示a i a_i a i ​的和，iisum表示a i × i a_i\times i a i ​×i 的和，其他命名应该都挺好懂（大概

代码能力太差，在MASHUPS WA了一整页，我真的栓Q

code：

#include

using namespace std;

typedef long long ll;

const ll N = 1e6 + 10;
const ll inf = 0x3f3f3f3f3f3f3f3f;

ll a[N];

struct node {
    ll l, r;
    ll asum, iisum;
    ll changeTag, addTag;
};

node tr[N << 2];

void pushup(ll u) {
    tr[u].asum = tr[u << 1].asum + tr[u << 1 | 1].asum;
    tr[u].iisum = tr[u << 1].iisum + tr[u << 1 | 1].iisum;
}

void pushdown(ll u) {
    auto &rt = tr[u], &left = tr[u << 1], &right = tr[u << 1 | 1];

    if (rt.changeTag != inf) {
        left.asum = rt.changeTag * (left.r - left.l + 1);
        left.iisum = (left.l + left.r) * (left.r - left.l + 1) / 2 * rt.changeTag;
        left.changeTag = rt.changeTag, left.addTag = 0;

        right.asum = rt.changeTag * (right.r - right.l + 1);
        right.iisum = (right.l + right.r) * (right.r - right.l + 1) / 2 * rt.changeTag;
        right.changeTag = rt.changeTag, right.addTag = 0;

        rt.changeTag = inf;
    }
    if (rt.addTag != 0) {
        left.asum += rt.addTag * (left.r - left.l + 1);
        left.iisum += (left.l + left.r) * (left.r - left.l + 1) / 2 * rt.addTag;
        left.addTag += rt.addTag;

        right.asum += rt.addTag * (right.r - right.l + 1);
        right.iisum += (right.l + right.r) * (right.r - right.l + 1) / 2 * rt.addTag;
        right.addTag += rt.addTag;

        rt.addTag = 0;
    }
}

void build(ll u, ll l, ll r) {
    if (l > r) return;
    if (l == r) {
        tr[u] = {l, r, a[l], a[l] * l, inf, 0};
        return;
    }
    tr[u] = {l, r, 0, 0, inf, 0};
    ll mid = (l + r) >> 1;
    build(u << 1, l, mid), build(u << 1 | 1, mid + 1, r);
    pushup(u);
}

void modify(ll u, ll l, ll r, ll change, ll add) {
    if (l > r) return;
    if (tr[u].l >= l && tr[u].r  r) {
        if (change != inf) {
            tr[u].asum = (tr[u].r - tr[u].l + 1) * change;
            tr[u].iisum = (tr[u].l + tr[u].r) * (tr[u].r - tr[u].l + 1) / 2 * change;
            tr[u].changeTag = change;
            tr[u].addTag = 0;
        }
        if (add != 0) {
            tr[u].asum += (tr[u].r - tr[u].l + 1) * add;
            tr[u].iisum += (tr[u].l + tr[u].r) * (tr[u].r - tr[u].l + 1) / 2 * add;
            tr[u].addTag += add;
        }
        return;
    }

    pushdown(u);
    ll mid = (tr[u].l + tr[u].r) >> 1;
    if (l  mid) modify(u << 1, l, r, change, add);
    if (r > mid) modify(u << 1 | 1, l, r, change, add);
    pushup(u);
}

ll queryAsum(ll u, ll l, ll r) {
    if (l > r) return 0;
    if (tr[u].l >= l && tr[u].r  r) return tr[u].asum;
    pushdown(u);
    ll mid = (tr[u].l + tr[u].r) >> 1;
    ll ans = 0;
    if (l  mid) ans = ans + queryAsum(u << 1, l, r);
    if (r > mid) ans = ans + queryAsum(u << 1 | 1, l, r);
    return ans;
}

ll queryIisum(ll u, ll l, ll r) {
    if (l > r) return 0;
    if (tr[u].l >= l && tr[u].r  r) return tr[u].iisum;
    pushdown(u);
    ll mid = (tr[u].l + tr[u].r) >> 1;
    ll ans = 0;
    if (l  mid) ans = ans + queryIisum(u << 1, l, r);
    if (r > mid) ans = ans + queryIisum(u << 1 | 1, l, r);
    return ans;
}

signed main() {
    ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);

    ll n, q;
    cin >> n >> q;
    for (ll i = 1; i  n; ++i) cin >> a[i];
    build(1, 1, n);
    for (int cas = 1; cas  q; ++cas) {
        ll op, l, r;
        cin >> op >> l >> r;
        if (l > r) swap(l, r);
        if (op == 1) {
            ll x;
            cin >> x;
            modify(1, l, r, inf, x);
        } else if (op == 2) {
            ll x;
            cin >> x;
            modify(1, l, r, x, 0);
        } else if (op == 3) {
            ll asum = queryAsum(1, l, r);
            ll iisum = queryIisum(1, l, r);
            bool flag = false;
            if (asum == 0 && iisum == 0) flag = true;
            else if (asum && iisum % asum == 0) {
                ll d = iisum / asum;
                if (l  d && d  r) flag = true;
            }
            if (flag) {
                cout << "Yes\n";
            } else {
                cout << "No\n";
            }
        }
    }
    return 0;
}

Original: https://blog.csdn.net/qq_39602052/article/details/127823889
Author: juraws
Title: Codeforces gym 103990