Codeforces Round 449 (Div. 2) 题解

2017/12/13

我又菜了。

居然是珂学 Round 。

A. Scarborough Fair

签到题。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
using namespace std;

int N, M;
string s;

int main() {
    cin >> N >> M;
    cin >> s;
    
    for(int i=1;i<=M;i++) {
        int l, r; char c1, c2;
        cin >> l >> r >> c1 >> c2;
        
        for(int j=l;j<=r;j++) {
            if(s[j-1] == c1) s[j-1] = c2;
        }
    }
    
    cout << s << endl;
}

B. Chtholly’s request

猜结论型签到。

 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
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cmath>
using namespace std;
typedef long long LL;

LL K, P;

LL pha(int x) {
    int c = log10(x) + 1;
    LL r = x;
    
    for(int i=0;i<c;i++) {
        r = r * 10 + (x % 10);
        x /= 10;
    }
    
    return r;
}

int main() {
    scanf("%lld %lld", &K, &P);
    
    LL cnt = 0;
    for(int i=1;i<=K;i++) {
        cnt = (cnt + pha(i)) % P;
    }
    
    printf("%lld\n", cnt);
}

C. Nephren gives a riddle

记搜签到。

 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
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <string>
using namespace std;
typedef long long LL;

string s1 = "What are you doing at the end of the world? Are you busy? Will you save us?";
string s2_1 = "What are you doing while sending \"";
string s2_2 = "\"? Are you busy? Will you send \"";
string s2_3 = "\"?";
string s2 = s2_1 + s2_2 + s2_3;
int Q, N; LL K;

const int SIZ = 1E5 + 1007;
LL cnt[SIZ]; int p;

char res = '.';
LL pos = 0;
void query(int N) {
    if(res != '.' || pos > K) return;
    if(N <= p && pos + cnt[N] <= K) { pos += cnt[N]; return; }
    
    if(N == 0) {
        res = s1[K - pos];
        pos += s1.size();
        return;
    } else {
        if(pos <= K && pos + s2_1.size() > K) {
            res = s2_1[K - pos];
            pos += s2_1.size();
            return;
        } else { pos += s2_1.size(); query(N-1); }
        
        if(pos <= K && pos + s2_2.size() > K) {
            res = s2_2[K - pos];
            pos += s2_2.size();
            return;
        } else { pos += s2_2.size(); query(N-1); }
        
        if(pos <= K && pos + s2_3.size() > K) {
            res = s2_3[K - pos];
            pos += s2_3.size();
            return;
        } else { pos += s2_3.size(); return; }
    }
}

int main() {
    scanf("%d", &Q);
    
    cnt[0] = s1.size();
    for(p=1;p<SIZ;p++) {
        cnt[p] = s2.size() + (cnt[p-1]<<1);
        if(cnt[p] >= 1e18) break;
    }
    
    while(Q--) {
        scanf("%d %lld", &N, &K); K-=1;
        res = '.', pos = 0;
        query(N);
        printf("%c", res);
    } puts("");
}

D. Ithea Plays With Chtholly

注意到交互轮数大于 N * C / 2,即对于每个位置可以被更新 C / 2 次。

判断数是否大于 C / 2,如果大于从右边找第一个比它小或者为空的位置,反之从左侧找第一个比它大的替换掉。

 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
#include <cstdio>
#include <cstdlib>
#include <algorithm>
using namespace std;

int N, M, C;

int seq[2007];

int insert_l(int p) {
    for(int i=1;i<=N;i++) {
        if(!seq[i] || seq[i] > p)
            return (seq[i] = p), i;
    }
}

int insert_r(int p) {
    for(int i=N;i>=1;i--) {
        if(!seq[i] || seq[i] < p)
            return (seq[i] = p), i;
    }
}

bool check() {
    for(int i=1;i<=N;i++) {
        if(!seq[i]) return 0;
    }
    
    return 1;
}

int main() {
    scanf("%d %d %d", &N, &M, &C);
    
    int mid = (C+1)>>1;
    int p;
    while(M--) {
        scanf("%d", &p);
        
        int pos = -1;
        if(p <= mid) pos = insert_l(p);
        else pos = insert_r(p);
        printf("%d\n", pos);
        fflush(stdout);
        
        if(check()) break;
    }
}

E. Willem, Chtholly and Seniorious

这个题就非常强……

表面上看起来是数据结构题,但实际上因为数据随机所以说分线段维护不会炸。

好像我不会分析这个均摊复杂度……

  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
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <set>
#include <vector>
using namespace std;
const int SIZ = 1e5 + 1007;

typedef long long LL;
int N, M, VMax; LL Seed;

int rnd() {
    int ret = Seed;
    Seed = (Seed * 7 + 13) % 1000000007;
    return ret;
}

struct seg { // [l, r]
    int l, r; LL val;

    friend bool operator<(const seg &a, const seg &b) {
        return a.l < b.l;
    }
};

bool cmp_val(const seg &a, const seg &b) {
    return a.val < b.val;
}

set<seg> S;
int Seq[SIZ];

void init() {
    int prev = Seq[1], prep = 1, _ = N+1;
    for(int i=1;i<=_;i++) {
        if(Seq[i] != prev) {
            S.insert(seg{prep, i-1, prev});
            prev = Seq[i];
            prep = i;
        }
    }
}

typedef set<seg>::iterator It;
void q_add(int l, int r, int x) {
    It st = S.upper_bound(seg{l, 0, 0}); --st;
    It nd = S.upper_bound(seg{r, 0, 0});
    
    vector<seg> buf;

    for(It i=st;i!=nd;++i) {
        if(i->l > r) break;
        buf.push_back(*i);
    }
    
    S.erase(st, nd);
    
    if(buf[0].l < l) {
        S.insert(seg{buf[0].l, l-1, buf[0].val});
        buf[0].l = l;
    }
    
    int _ = buf.size() - 1;
    if(buf[_].r > r) {
        S.insert(seg{r+1, buf[_].r, buf[_].val});
        buf[_].r = r;
    }
    
    for(seg &s : buf) {
        s.val += x;
        S.insert(s);
    }
}

void q_change(int l, int r, int x) {
    It st = S.upper_bound(seg{l, 0, 0}); --st;
    It nd = S.upper_bound(seg{r, 0, 0});
    
    vector<seg> buf;

    for(It i=st;i!=nd;++i) {
        if(i->l > r) break;
        buf.push_back(*i);
    }
    
    S.erase(st, nd);
    
    if(buf[0].l < l && buf[0].val != x) {
        S.insert(seg{buf[0].l, l-1, buf[0].val});
        buf[0].l = l;
    }
    
    int _ = buf.size() - 1;
    if(buf[_].r > r && buf[_].val != x) {
        S.insert(seg{r+1, buf[_].r, buf[_].val});
        buf[_].r = r;
    }
    
    S.insert(seg{buf[0].l, buf[_].r, x});
}

void q_kth(int l, int r, int x) {
    It st = S.upper_bound(seg{l, 0, 0}); --st;
    It nd = S.upper_bound(seg{r, 0, 0});
    
    vector<seg> buf;

    for(It i=st;i!=nd;++i) {
        if(i->l > r) break;
        buf.push_back(*i);
    }
    
    if(buf[0].l < l) {
        buf[0].l = l;
    }
    
    int _ = buf.size() - 1;
    if(buf[_].r > r) {
        buf[_].r = r;
    }
    
    sort(buf.begin(), buf.end(), cmp_val);
    
    LL cnt = 0; LL ans = -1;
    for(seg &s : buf) {
        cnt += (s.r - s.l + 1);
        if(cnt >= x) { ans = s.val; break; }
    }
    
    printf("%lld\n", ans);
}

LL qpow(LL a, LL b, LL mod) {
    LL ret = 1;
    a = a % mod;
    while(b) {
        if(b & 1) ret = (ret * a) % mod;
        a = (a * a) % mod;
        b >>= 1;
    }
    return ret;
}

void q_sum(int l, int r, int x, int y) {
    It st = S.upper_bound(seg{l, 0, 0}); --st;
    It nd = S.upper_bound(seg{r, 0, 0});
    
    vector<seg> buf;

    for(It i=st;i!=nd;++i) {
        if(i->l > r) break;
        buf.push_back(*i);
    }
    
    if(buf[0].l < l) {
        buf[0].l = l;
    }
    
    int _ = buf.size() - 1;
    if(buf[_].r > r) {
        buf[_].r = r;
    }
    
    LL ans = 0;
    for(seg &s : buf) {
        ans = (ans + (s.r - s.l + 1) * qpow(s.val, x, y)) % y;
    }
    
    printf("%d\n", int(ans));
}

int main() {
    scanf("%d %d %lld %d", &N, &M, &Seed, &VMax);
    
    for(int i=1;i<=N;i++) {
        Seq[i] = (rnd() % VMax) + 1;
    }
    
    init();
    
    for(int i=1;i<=M;i++) {
        int op = (rnd() % 4) + 1;
        int l = (rnd() % N) + 1;
        int r = (rnd() % N) + 1;
        
        if(l > r) swap(l, r);
        
        int x = -1, y = -1;
        
        if(op == 3)
            x = (rnd() % (r - l + 1)) + 1;
        else
            x = (rnd() % VMax) + 1;
        
        if(op == 4)
            y = (rnd() % VMax) + 1;
        
        switch(op) {
            case 1: q_add(l, r, x); break;
            case 2: q_change(l, r, x); break;
            case 3: q_kth(l, r, x); break;
            case 4: q_sum(l, r, x, y); break;
        }
    }
}