NEERC 2015 选做

发表于 | 更新于 | 分类于 | 阅读次数：

集训队作业开冲。
2015-2016 ACM-ICPC Northeastern European Regional Contest (NEERC 15)

  • B - Binary vs Decimal
  • C - Cactus Jubilee
  • D - Distance on Triangulation
  • H - Hypercube
  • I - Iceberg Orders
  • J - Jump
  • K - King’s Inspection
  • L - Landscape Improved

B - Binary vs Decimal

题意简述

求第 $n$ 小的正整数 $A$ 满足：

  • $A$ 中仅含0,1。
  • 设 $A$ 的二进制表示为 $B$，则 $A$ 为 $B$ 的后缀。

$n\le 10000$。

主要思路

我会暴力判断！
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
def check(i):
    x = int(bin(i)[2:])
    xbs = str(bin(x)[2:])
    x = str(x)
    y = xbs[-len(x):]
    if x == y: return True
    return False

fin = open("binary.in", "r")
rd = int(fin.read())
fin.close()

Q = [0, 1]
lim = 1

while len(Q) <= rd:
    lim *= 2
    P = []
    for x in Q:
        y = x + lim
        if check(y):
            P.append(y)
    Q += P

# for x in Q:
#     print(x, end = ', ')

fout = open("binary.out", "w")
fout.write(bin(Q[rd])[2:])
fout.close()

然而显然这样是过不去的。
打了个表，好像也没啥性质。

后来发现如果 $A$ 合法，则 $A$ 的任意一个后缀都合法。
于是写个高精 bfs 就好了。

参考代码

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
#include <bits/stdc++.h>
namespace my_std {
using namespace std;
#define reg register
#define Rint register int
#define FOR(i, a, b) for (register int i = (a), ed_##i = (b); i <= ed_##i; ++i)
#define ROF(i, a, b) for (register int i = (a), ed_##i = (b); i >= ed_##i; --i)
#define Templ(T) template <typename T>
Templ(_Tp) inline int chkmin(_Tp &x, _Tp y) { return x > y ? x = y, 1 : 0; }
Templ(_Tp) inline int chkmax(_Tp &x, _Tp y) { return x < y ? x = y, 1 : 0; }
} // namespace my_std
using namespace my_std;

typedef unsigned long long u64;
typedef unsigned int u32;

#define BM 4
struct BigNum{
    u64 a[BM];
    inline void reset(){ FOR(i, 0, BM - 1) a[i] = 0; }
    inline void set(){ FOR(i, 0, BM - 1) a[i] = ~0ull; }
    inline BigNum(){ reset(); }
    inline void reset(const int &x){ a[x >> 6] &= ~(1ull << (x & 63)); }
    inline void set(const int &x){ a[x >> 6] |= 1ull << (x & 63); }
    inline bool test(const int &x)const{ return (a[x >> 6] >> (x & 63)) & 1; }
    inline BigNum operator <<(const int &x)const{//x must be in [0, 64)
        reg BigNum res;
        reg u64 t = 0;
        FOR(i, 0, BM - 1){
            res.a[i] = (a[i] << x) | t;
            t = a[i] >> (64 - x);
        }
        return res;
    }
    inline BigNum operator +(const BigNum &rhs)const{
        reg BigNum res;
        reg bool t = 0;
        FOR(i, 0, BM - 1){
            if(t){
                res.a[i] = a[i] + rhs.a[i] + 1;
                if(a[i] < ~0ull - rhs.a[i]) t = 0;
                else t = 1;
            }else{
                res.a[i] = a[i] + rhs.a[i];
                if(a[i] <= ~0ull - rhs.a[i]) t = 0;
                else t = 1;
            }
        }
        return res;
    }
}m10[256], Q[16384], P[16384];
int qt = 1;

inline void print(const BigNum &x){
    Rint t = 255;
    for(; !x.test(t); --t);
    for(; ~t; --t) putchar(int(x.test(t)) ^ 48);
    putchar(10);
}
inline bool check(const BigNum &x, const BigNum &y){
    Rint t = 255;
    for(; !x.test(t); --t);
    for(; ~t; --t) if(x.test(t) ^ y.test(t)) return 0;
    return 1;
}

int main() {
    freopen("binary.in", "r", stdin);
    freopen("binary.out", "w", stdout);
    
    m10[0].set(0);
    FOR(i, 1, 255) m10[i] = (m10[i - 1] << 3) + (m10[i - 1] << 1);

    int n;
    scanf("%d", &n);

    Q[1].set(0);
    P[1].set(0);

    Rint lim = 0;
    while(qt <= n){
        ++lim;
        FOR(i, 0, qt){
            reg BigNum x = Q[i], y = P[i];
            x.set(lim);
            y = y + m10[lim];
            if(check(x, y)){
                Q[++qt] = x;
                P[qt] = y;
            }
        }
    }

    print(Q[n]);
    // FOR(i, 1, n) print(Q[i]);
    return 0;
}

H - Hypercube

题意简述

给三位空间上 $8$ 个单位正方体，判断它们能否折叠成一个四维超立方体。

主要思路

被教育了一个非常 nb 的做法。
四维无法想象，故先考虑把 $6$ 个小正方体折成三维立方体。

那么折成的小立方体，从某一面开始，无论沿着哪个方向走 $2$ 步就能走到其对面，再走 $2$ 步就能走回来。
考虑到实际上只有两个方向，那么不妨考虑一个面 $c$（其对面记为 $-c$）与两个映射 $f_{x, y}$，$f_i(c)$ 意为在方向 $i$ 上走一步走到的面。
那么我们有 $f_x^2(c) = f_y^2(c) = -c$。
考虑在平面上也只有两个方向，故对于两个面 $c, d$，钦定 $c$ 是折起来后的哪一面，按照 $c\to d$ 经过的路径不断映射就能得到 $d$ 是哪一面。
对于所有 $(c, d)$ 计算出 $d$ 是哪一面，当有一组 $(c, d)$ 对应的面相同，则可充分说明无解。
其必要性不难证明。

那么关于这两个映射如何设。
可以构造如下的映射，其中元组的前两维代表到该面的方向，最后一维代表是在哪一面。即两个元素相等只需最后一维相等即可。

$$
f_x(A, B, C) = (-C, B, A)\\
f_y(A, B, C) = (A, -C, B)
$$

那么回到四维的情况，就类似地需要有三个方向的映射。

$$
f_x(A, B, C, D) = (-D, B, C, A)\\
f_y(A, B, C, D) = (A, -D, C, B)\\
f_z(A, B, C, D) = (A, B, -D, C)
$$

即可。

参考代码

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
#include <bits/stdc++.h>
namespace my_std {
using namespace std;
#define reg register
#define Rint register int
#define FOR(i, a, b) for (register int i = (a), ed_##i = (b); i <= ed_##i; ++i)
#define ROF(i, a, b) for (register int i = (a), ed_##i = (b); i >= ed_##i; --i)
typedef int I;
} // namespace my_std
using namespace my_std;

#define N 10
FILE *fo;

I n, m, k;
char s[N][N][N];

inline void init(){
    freopen("hypercube.in", "r", stdin);
    fo = fopen("hypercube.out", "w");
    scanf("%d%d%d", &n, &m, &k);
    FOR(i, 1, k) FOR(j, 1, m){
        scanf("%s", s[i][j] + 1);
    }
}

map<I, bool> vis;
void dfs(I x, I y, I z, I A, I B, I C, I D){
    s[x][y][z] = 32;
    if(!vis.count(D)) vis[D] = 1;
    if(s[x + 1][y][z] == 0x78) dfs(x + 1, y, z, -D, B, C, A);
    if(s[x - 1][y][z] == 0x78) dfs(x - 1, y, z, D, B, C, -A);
    if(s[x][y + 1][z] == 0x78) dfs(x, y + 1, z, A, -D, C, B);
    if(s[x][y - 1][z] == 0x78) dfs(x, y - 1, z, A, D, C, -B);
    if(s[x][y][z + 1] == 0x78) dfs(x, y, z + 1, A, B, -D, C);
    if(s[x][y][z - 1] == 0x78) dfs(x, y, z - 1, A, B, D, -C);
}

I main() {
    init();
    FOR(i, 1, k) FOR(j, 1, m) FOR(o, 1, n)
        if(s[i][j][o] == 0x78) dfs(i, j, o, 1, 2, 3, 4);
    return fputs((int)vis.size() == 8 ? "Yes" : "No", fo), fclose(fo), 0;
}

顺带一提，这个 sb 开始写了个极为复杂的实现，然后又被教育了，，，

J - Jump

题意简述

交互题，猜01串 $S$，$|S| = n$ 为偶数。
每次可以猜一个串 $T$，若 $S,T$ 的 $n$ 位全都相等则结束。
否则，若两串恰好有 $n/2$ 位相等，返回 $n/2$；否则返回 $0$。
请在 $n + 500$ 次内猜出 $S$，$n\le 1000$。

主要思路

随机一个串使得恰有 $n/2$ 位相等，据说大概 $\sqrt{n}$ 次左右就能得到一个。
然后对于相邻两位 $i, i + 1$，将他们均取反，查一次，可以知道 $s_i\omega s_{i+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
27
28
import random

n = int(input())

def check(s):
    print(*s, sep = '')
    x = int(input())
    if x == n: exit()
    else: return x == n//2

while True:
    s = random.choices([0, 1], k = n)
    if check(s): break

d = []
s[0] ^= 1
for i in range(1, n):
    s[i] ^= 1
    d.append(check(s) ^ s[i] ^ s[0])
    s[i] ^= 1
s[0] ^= 1

s = [0]
for i in d:
    s.append(i)

check(s)
check([i ^ 1 for i in s])

K - King’s Inspection

题意简述

有向图保证 $m\le n + 20, n\le 10^5$，求一条哈密顿回路，需判断无解。

主要思路

首先对于一些只有一条入边 $(v, u)$ 的点 $u$，很明显我们可以知道回路中只能 $v\to u$。
那么最后就可以压成 $O(m - n)$ 条链，这些链必须从链头走向链尾。
那么枚举一下这些链之间的顺序就好了。
复杂度是多少啊（/yun）

参考代码

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
#include <bits/stdc++.h>
namespace my_std {
using namespace std;
#define reg register
#define Rint register int
#define FOR(i, a, b) for (register int i = (a), ed_##i = (b); i <= ed_##i; ++i)
#define ROF(i, a, b) for (register int i = (a), ed_##i = (b); i >= ed_##i; --i)
#define Templ(T) template <typename T>
Templ(_Tp) inline int chkmin(_Tp &x, _Tp y) { return x > y ? x = y, 1 : 0; }
Templ(_Tp) inline int chkmax(_Tp &x, _Tp y) { return x < y ? x = y, 1 : 0; }
typedef vector<int> VI;
#define pb emplace_back
} // namespace my_std
using namespace my_std;

#define MMR (1 << 23)
struct INPUT{
    FILE *F;
    char buf[MMR], *s, *t;
    INPUT(): F(fopen("king.in", "r")){
        t = (s = buf) + fread(buf, 1, MMR, F);
        fclose(F);
    }
    Templ(_Tp) inline INPUT& operator >>(_Tp &x){
        x = 0;
        reg char c(*s++);
        while(c < 48) c = *s++;
        while(c > 47) x = x * 10 + c - 48, c = *s++;
        return *this;
    }
}fin;
FILE *fout(fopen("king.out", "w"));
#define EX() fclose(fout), exit(0);


#define N 100010
int n, m;
int suf[N], pre[N], vis[N];
int col[N], cc;
VI fr[N];

inline bool fail(){
    fputs("There is no route, Karl!", fout);
    EX();
    return 1;
}
inline void travel(){
    Rint u = 1;
    do{
        fprintf(fout, "%d ", u);
        u = suf[u];
    }while(u != 1);
    fprintf(fout, "%d\n", u);
    EX();
}

//small graph
namespace SG{
int hd[N], tl[N];
#define M 30
int suf[M], pre[M];
int vis[M];
VI e[M];
inline void check(){
    memset(vis, 0, sizeof(int) * M);
    Rint u = 1;
    for(; !vis[u]; u = suf[u]) vis[u] = 1;
    FOR(i, 1, cc) if(!vis[i]) return;
    FOR(i, 1, cc){
        ::suf[tl[i]] = hd[suf[i]];
    }
    travel();
}
void dfs(const int &u){
    if(u > cc) return check();
    for(Rint v: e[u]) if(!pre[v]){
        suf[u] = v, pre[v] = u;
        dfs(u + 1);
        suf[u] = 0, pre[v] = 0;
    }
}
void solve(){
    FOR(u, 1, n) if(!::pre[u]){
        for(Rint v: fr[u]) if(!::suf[v]){
            e[col[v]].pb(col[u]);
        }
    }
    dfs(1);
}
#undef M
}

void dfs(const int &u){
    col[u] = cc;
    vis[u] = 1;
    if(suf[u] && !vis[suf[u]]) dfs(suf[u]);
    else SG::tl[cc] = u;
}

int main() {
    fin >> n >> m;
    Rint u, v;
    FOR(i, 1, m){
        fin >> u >> v;
        fr[v].pb(u);
    }
    FOR(u, 1, n){
        if(fr[u].size() == 1){
            Rint v = fr[u][0];
            suf[v] && fail();
            suf[v] = u;
            pre[u] = v;
        }else fr[u].empty() && fail();
    }
    FOR(u, 1, n) if(!pre[u]){
        SG::hd[++cc] = u;
        dfs(u);
    }
    if(!vis[1]){
        ++cc;
        dfs(1);
        FOR(i, 1, n) col[i] != cc && fail();
        travel();
    }
    FOR(u, 2, n) !vis[u] && fail();
    SG::solve();
    fail();
    return 0;
}

L - Landscape Improved

题意简述

二维搭积木，第 $i$ 列上已经搭了 $h_i$ 块。共 $n$ 个位置。
现在你手上有 $W$ 块积木，手上的积木能搭在某个位置当且仅当该位置左下、正下、右下三个位置都已经有积木。
求最高的一列能搭多高。
$n\le 10^5, h_i\le 10^9, W\le 10^{18}$。

1
2
3
4
5
      .  
 #   ..#
##  ##.#
### ####
########

以上是一个 $n=8,W=4$ 的样例，其中以#表示原先有的积木，.表示后来放上去的积木。

主要思路

枚举一下第 $p$ 列最高，然后二分一下高度 $lim$。

那么大概就是什么找到最大的 $i<p$ 使得 $h_i + p - i \ge lim$，然后求一下区间 $(i, p)$ 的和。
对于左边也类似。
这个显然可以转成什么 $O(n)$ 次区间加减一。
求那个东西就把 $log n$ 个线段树上的区间捞下来，然后找到第一个最大值不小于 $lim$ 的区间，再套个线段树上二分啥的就好了。

参考代码

写完之后发现不优美，实际上有许多更优美的做法（例如直接来个 ST表和树状数组）。
虽然复杂度都是 $O(n\log^2 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
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
#include <bits/stdc++.h>
namespace my_std {
using namespace std;
#define reg register
#define Rint register int
#define FOR(i, a, b) for (register int i = (a), ed_##i = (b); i <= ed_##i; ++i)
#define ROF(i, a, b) for (register int i = (a), ed_##i = (b); i >= ed_##i; --i)
#define Templ(T) template <typename T>
Templ(_Tp) inline int chkmin(_Tp &x, _Tp y) { return x > y ? x = y, 1 : 0; }
Templ(_Tp) inline int chkmax(_Tp &x, _Tp y) { return x < y ? x = y, 1 : 0; }
typedef long long i64;
} // namespace my_std
using namespace my_std;

#define MMR (1 << 23)
struct INPUT{
    FILE *F;
    char buf[MMR], *s, *t;
    INPUT(): F(fopen("landscape.in", "r")){
        t = (s = buf) + fread(buf, 1, MMR, F);
        fclose(F);
    }
    Templ(_Tp) inline INPUT& operator >>(_Tp &x){
        x = 0;
        reg char c(*s++);
        while(c < 48) c = *s++;
        while(c > 47) x = x * 10 + c - 48, c = *s++;
        return *this;
    }
}fin;
struct OUTPUT{
    FILE *F;
    char buf[MMR], *s;
    OUTPUT(): F(fopen("landscape.out", "w")){ s = buf; }
    inline OUTPUT& operator <<(int x){
        static int tmp[10];
        Rint *top = tmp;
        do{
            *++top = (x % 10) ^ 48, x /= 10;
        }while(x);
        while(top != tmp) *s++ = *top--;
        *s++ = 10;
        return *this;
    }
    ~OUTPUT(){
        fwrite(buf, 1, s - buf, F);
        fclose(F);
    }
}fout;

#define N 100010
int n, a[N];
i64 K;

namespace DS{
#define lc ((t) << 1)
#define rc ((t) << 1 | 1)
#define mid ((l + r) >> 1)
typedef const int CI;
typedef const i64 CI64;
int m[N << 2], d[N << 2];
int L[N << 2], R[N << 2];
i64 s[N << 2];
inline void push_up(CI &t){
    s[t] = s[lc] + s[rc];
    m[t] = max(m[lc], m[rc]);
}
inline void push_down(CI &t, CI &len){
    if(d[t] != 0){
        CI tag = d[t];
        d[t] = 0;
        s[lc] += ((len + 1ll) >> 1) * tag;
        s[rc] += ((i64)len >> 1) * tag;
        m[lc] += tag;
        m[rc] += tag;
        d[lc] += tag;
        d[rc] += tag;
    }
}
void build(CI &t, CI &l, CI &r){
    L[t] = l, R[t] = r;
    if(l == r){
        s[t] = a[l] + l - 1;
        m[t] = a[l] + l - 1;
        d[t] = 0;
        return;
    }
    build(lc, l, mid), build(rc, mid + 1, r);
    push_up(t);
}
void update(CI &t, CI &L, CI &R, CI &v){
    CI l = DS::L[t], r = DS::R[t];
    if(L <= l && r <= R){
        s[t] += (i64)(r - l + 1) * v;
        m[t] += v;
        d[t] += v;
        return;
    }
    push_down(t, r - l + 1);
    if(L <= mid) update(lc, L, R, v);
    if(R > mid) update(rc, L, R, v);
    push_up(t);
}
int sk[64], *st;
void get_L(CI &t, CI &x){
    CI l = DS::L[t], r = DS::R[t];
    if(r < x){
        *++st = t;
        return;
    }
    if(l == r) return;
    push_down(t, r - l + 1);
    get_L(lc, x);
    if(mid + 1 < x) get_L(rc, x);
}
void get_R(CI &t, CI &x){
    CI l = DS::L[t], r = DS::R[t];
    if(l > x){
        *++st = t;
        return;
    }
    push_down(t, r - l + 1);
    get_R(rc, x);
    if(mid > x) get_R(lc, x);
}
i64 qry_L(CI &t, CI &v){
    CI l = DS::L[t], r = DS::R[t];
    if(m[t] < v) return (i64)(r - l + 1) * v - s[t];
    if(l == r) return 0;
    push_down(t, r - l + 1);
    if(m[lc] >= v) return qry_L(lc, v);
    return (i64)((r - l + 2) >> 1) * v - s[lc] + qry_L(rc, v);
}
i64 qry_R(CI &t, CI &v){
    CI l = DS::L[t], r = DS::R[t];
    if(m[t] < v) return (i64)(r - l + 1) * v - s[t];
    if(l == r) return 0;
    push_down(t, r - l + 1);
    if(m[rc] >= v) return qry_R(rc, v);
    return qry_R(lc, v) + (i64)((r - l + 1) >> 1) * v - s[rc];
}
inline i64 query(CI &x, CI &v){
    reg i64 res = v - a[x];
    {
        st = sk;
        get_L(1, x);
        bool f = 0;
        for(Rint *i(st); i != sk; --i){
            if(m[*i] >= v){
                res += qry_R(*i, v);
                f = 1;
                break;
            }
            else res += (R[*i] - L[*i] + 1ll) * v - s[*i];
        }
        if(!f) return -1;
    }
    {
        st = sk;
        get_R(1, x);
        bool f = 0;
        for(Rint *i(st); i != sk; --i){
            if(m[*i] >= v){
                res += qry_L(*i, v);
                f = 1;
                break;
            }
            else res += (R[*i] - L[*i] + 1ll) * v - s[*i];
        }
        if(!f) return -1;
    }
    return res;
}
#undef lc
#undef rc
#undef mid
}

#define inf 0x3f3f3f3f

int main() {
    fin >> n >> K;
    FOR(i, 1, n) fin >> a[i];
    DS::build(1, 1, n);
    Rint ans = max(a[1], a[n]);
    FOR(i, 2, n - 1){
        chkmax(ans, a[i]);
        DS::update(1, 1, i - 1, 1);
        DS::update(1, i, n, -1);
        Rint l = a[i], r = inf, mid;
        reg i64 tmp;
        while(l < r){
            mid = (l + r + 1) >> 1;
            tmp = DS::query(i, mid);
            if(tmp == -1 || tmp > K) r = mid - 1;
            else l = mid;
        }
        chkmax(ans, l);
    }
    fout << ans;
    return 0;
}