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;
}
1
2
3
4
5
6
7
8

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;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

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";
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90

G - Geekflix

prob.:

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

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

第k次播放i号视频可以获得的价值为$max(0,a_i-(k-1)\times b_i)$

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

n 200 m 1000 a, b 5000

ideas：

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

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

$O(n^{2}mlogm)$

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

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;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58

B - Balanced Seesaw Array

prob：

n个数的序列，定义一种特殊的子序列[l, r]满足条件为，$\exists k\in [l,r],st.{\sum }_i(i-k)\times a_i=0$

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

n 1e5 q 1e6 保证ll够用

ideas：

拆一下式子，${\sum }_i(i-k)\times a_i=0={\sum }_i{a}_i\times i-k\times {\sum }_i{a}_i$

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

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

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

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

细节看代码吧（其中asum表示$a_i$的和，iisum表示$a_i\times 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; // sum of ai, sum of i * ai
    ll changeTag, addTag; // the priority of 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;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146