A

大的加1,第二的在中间

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
signed main() {
    IOS;
    int tmp[3][2] = {{1, 2}, {1, 3}, {2, 3}};
    vector<int> v(4, 0);
    for (int i = 0; i < 3; i++) {
        int op;
        char x;
        cin >> x;
        if (x == '<') {
            op = 1;
        } else {
            op = 0;
        }
        v[tmp[i][op]]++;
    }
    for (int i = 1; i <= 3; i++) {
        //cout << v[i] << endl;
        if (v[i] == 1)
        {
            char ans = 'A' + i - 1;
            cout << ans << endl;
            return 0;
        }
    }
    return 0;
}

B

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
signed main() {
    IOS;
    int n, m;
    cin >> n >> m;
    vector<int> v(n + 1, 0);
    while (m--) {
        int x;
        char y;
        cin >> x >> y;
        if (v[x] == 0 && y == 'M') {
            cout << "Yes" << endl;
            v[x] = 1;
        } else {
            cout << "No" << endl;
        }
    }

    return 0;
}

C

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
map<PII, int> m;
int dis[20][20];
signed main()
{
    IOS;
    int n;
    cin >> n;
    int m1;
    cin >> m1;
    vector<int> tmp(n + 1);
    for (int i = 1; i <= n; i++)
    {
        tmp[i] = i;
    }
    vector<PII> oc1(m1 + 1);
    for (int i = 1; i <= m1; i++)
    {
        int u, v;
        cin >> u >> v;
        if (u > v)
        {
            swap(u, v);
        }
        oc1[i] = {u, v};
    }
    int m2;
    cin >> m2;
    vector<PII> oc2(m2 + 1);
    for (int i = 1; i <= m2; i++)
    {
        int u, v;
        cin >> u >> v;
        if (u > v)
        {
            swap(u, v);
        }
        oc2[i] = {u, v};
    }
    for (int i = 1; i < n; i++)
    {
        for (int j = i + 1; j <= n; j++)
        {
            cin >> dis[i][j];
        }
    }
    int res = 1e9;
    do
    {
        m.clear();
        for (int i = 1; i <= m1; i++)
        {
            int u, v;
            u = tmp[oc1[i].first], v = tmp[oc1[i].second];
            if (u > v)
            {
                swap(u, v);
            }
            m[{u, v}]++;
        }
        for (int i = 1; i <= m2; i++)
        {
            int u, v;
            u = oc2[i].first, v = oc2[i].second;
            if (u > v)
            {
                swap(u, v);
            }
            m[{u, v}]--;
        }
        int ans = 0;
        for (auto [x, y] : m)
        {
            if (y == 0)
            {
                continue;
            }
            ans += dis[x.first][x.second];
        }
        res = min(res, ans);
    } while (next_permutation(tmp.begin() + 1, tmp.end()));
    cout << res << endl;
    return 0;
}

D

直接离散化

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
signed main() {
    IOS;
    int n;
    cin >> n;
    vector<int> ind;
    vector<int> a(n), w(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
        ind.emplace_back(a[i]);
    }
    for (int i = 0; i < n; i++) {
        cin >> w[i];
        //ind.emplace_back(w[i]);
    }
    int q;
    cin >> q;
    vector<int> l(q), r(q);
    for (int i = 0; i < q; i++) {
        cin >> l[i] >> r[i];
        ind.emplace_back(l[i]);
        ind.emplace_back(r[i]);
    }
    sort(ind.begin(), ind.end());
    ind.erase(unique(ind.begin(), ind.end()), ind.end());
    int len = ind.size();
    vector<int> ans(len, 0);
    for (int i = 0; i < n; i++) {
        int idx = lower_bound(ind.begin(), ind.end(), a[i]) - ind.begin();
        ans[idx] += w[i];
    }
    for (int i = 1; i < len; i++)
    {
        ans[i] += ans[i - 1];
        //cout << ans[i] << ' ';
    }
    //cout << endl;
    for (int i = 0; i < q; i++)
    {
        int h = lower_bound(ind.begin(), ind.end(), l[i]) - ind.begin(), t = lower_bound(ind.begin(), ind.end(), r[i]) - ind.begin();
        if (h != 0) cout << ans[t] - ans[h - 1] << endl;
        else
            cout << ans[t] << endl;
    }
        return 0;
}

E

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
const int N = 2e5 + 10;
typedef long long ll;

int n, pre[N];

signed main() {
    IOS;
     cin >> n;
    ll ans = 0;
    for (int i = 1; i <= n; i ++ ){
        int x;
        cin >> x;
        ans += 1ll * (i - pre[x]) * (n - i + 1);
        pre[x] = i;
    }
    cout << ans;
    return 0;
}

F

对于i-人的坐标Xi，考虑定义为Xi=Xi′+i的整数Xi′

然后写线段树再说

懒得写了，抄了一份

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
const int N = 2e5 + 10;
typedef long long ll;

ll n, q, x[N];

struct info{
    ll sum, sz;
    info(){sum = 0; sz = 1;}
    info(ll sum, ll sz):sum(sum), sz(sz){}
};

struct tag{
    ll d;
    tag(){d = -1;}
    tag(ll d):d(d){}
};

info operator+(const info &l, const info &r){
    return {l.sum + r.sum, l.sz + r.sz};
}

info operator+(const info &v, const tag &t){ // 区间修改
    return {v.sz * t.d, v.sz};
}

tag operator+(const tag &t1, const tag &t2){ //懒标记和并
    return {t2.d};
}

struct Node{
    tag t;
    info val;
} seg[N * 4];

void settag(int id, tag t){
    seg[id].val = seg[id].val + t;
    seg[id].t = seg[id].t + t;
}

void pushdown(int id){ // 每一步都需要标记下传
    if (seg[id].t.d != -1){ // 标记非空
        settag(id * 2, seg[id].t);
        settag(id * 2 + 1, seg[id].t);
        //初始化标记
        seg[id].t.d = -1;
    }
}

void update(int id){
    seg[id].val = seg[id * 2].val + seg[id * 2 + 1].val;
}

void build(int id, int l, int r){
    if (l == r){
        seg[id].val = info(x[l], 1);
        seg[id].t = tag(-1);
    }
    else{
        int mid = (l + r) / 2;
        build(id * 2, l, mid);
        build(id * 2 + 1, mid + 1, r);
        update(id);
    }
}

info query(int id, int l, int r, int ql, int qr){
    if (l == ql && r == qr){
        return seg[id].val;
    }
    int mid = (l + r) / 2;
    pushdown(id);
    if (qr <= mid)
        return query(id * 2, l, mid, ql, qr);
    else if (ql > mid)
        return query(id * 2 + 1, mid + 1, r, ql, qr);
    else
        return query(id * 2, l, mid, ql, mid) +
               query(id * 2 + 1, mid + 1, r, mid + 1, qr);
}

void modify(int id, int l, int r, int ql, int qr, tag t){
    if (l == ql && r == qr)
    {
        settag(id, t);
        return;
    }
    int mid = (l + r) / 2;
    pushdown(id);
    if (qr <= mid)
        modify(id * 2, l, mid, ql, qr, t);
    else if (ql > mid)
        modify(id * 2 + 1, mid + 1, r, ql, qr, t);
    else
    {
        modify(id * 2, l, mid, ql, mid, t);
        modify(id * 2 + 1, mid + 1, r, mid + 1, qr, t);
    }
    update(id);
}

void solve() {
    cin >> n;
    for (int i = 1; i <= n; i ++ ) cin >> x[i], x[i] -= i;
    build(1, 1, n);
    cin >> q;
    ll ans = 0;
    while (q -- ){
        ll t, g;
        cin >> t >> g; g -= t;
        //讨论方向
        ll xt = query(1, 1, n, t, t).sum;
        if (xt <= g){ // 向右  //[xt, g]
            int l = t, r = n;
            while (l < r){
                int mid = (l + r + 1) / 2;
                if (query(1, 1, n, mid, mid).sum <= g) l = mid;
                else r = mid - 1;
            }
            ans += g * (r - t + 1) - query(1, 1, n, t, r).sum;
            modify(1, 1, n, t, r, tag(g));
        }else{ //向左  //[g, xt]
            int l = 1, r = t;
            while (l < r){
                int mid = (l + r) / 2;
                if (query(1, 1, n, mid, mid).sum >= g) r = mid;
                else l = mid + 1;
            }
            ans += query(1, 1, n, l, t).sum - g * (t - l + 1);
            modify(1, 1, n, l, t, tag(g));
        }
    }
    cout << ans;
}

signed main() {
    IOS;
    int t = 1;
//    cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}

END