NEERC 2013 选做

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

2013-2014 ACM-ICPC Northeastern European Regional Contest (NEERC 13)

  • A - ASCII Puzzle
  • C - Cactus Automorphisms
  • D - Dictionary
  • E - Easy Geometry
  • G - Green Energy
  • H - Hack Protection
  • I - Interactive Interception
  • K - Kabaleo Lite

C - Cactus Automorphisms

题意简述

给一棵仙人掌（$n\le 5\times 10^4$），求其自同构的数量。
图的自同构是一个从 $V$ 到 $V$ 的一一映射 $m$，满足对于任意边 $\{u, v\}\in E$，均有 $\{m(u), m(v)\}\in E$。

主要思路

考虑树怎么做：显然重心置换之后还是重心，所以令重心为根（有两个就新建一个虚根），然后树哈希。

如何推广到仙人掌？直接建圆方树，那么对原图置换之后相当于对圆方树进行置换。此时圆点不能变成方点，所以有两个重心的时候，只取一个为根。

由于方点的儿子是有序的，所以方点只支持 reverse 儿子序列；但如果方点是根那么就是循环移位加翻转，一共 $2\times cnt(cir)$ 种。

D - Dictionary

题意简述

给 $n$ 个单词 $a_i$，你需要构造一棵 Trie，使得每个单词都能表示为某个节点到其子树内某个节点的这段路径，并且 Trie 上的节点最少。$n\le 50$，单词长度都不超过 $10$。

主要思路

首先至多要 $\sum|a_i|$ 个点。

考虑把一个单词 $a$ 的一个前缀接在另一个单词 $b$ 的一个子串上，那么就能节省这个前缀的长度。

于是就转化为在一个有向完全图上求一棵最大的树形图。这个树形图上的边全都可以省。

朱刘算法冲冲冲。

顺带一提这个题要方案于是写起来很垃圾。实际上因为数据很小，随便写都能过，感觉也还好。

参考代码

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
#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 pair<int, int> PII;
typedef vector<int> VI;
#define SZ(x) ((int)(x).size())
#define pb push_back
#define fr first
#define sc second
#define MP make_pair
#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;

const bool __file__ = [&](){
    freopen("dictionary.in", "r", stdin);
    freopen("dictionary.out", "w", stdout);
    return true;
}();

#define N 55
#define NN 550
inline bool is_sub(const string &x, const string &y){
    if(SZ(x) > SZ(y)) return 0;
    FOR(i, 0, SZ(x) - 1) if(x[i] != y[i]) return 0;
    return 1;
}
inline int get_wgh(const string &x, const string &y){
    int res = 0;
    FOR(i, 0, SZ(x) - 1) FOR(j, 1, SZ(x) - i){
        if(is_sub(x.substr(i, j), y)) chkmax(res, j);
    }
    return res;
}

struct Edge{
    int from, wgh;
    inline Edge(): from(0), wgh(0){}
    inline Edge(int _f, int _w): from(_f), wgh(_w){}
};
struct Vertice{
    vector<Edge> in;
    int pre, wgh;
    inline Vertice(): pre(-1){}
};

void MDST(vector<Vertice> &P){
    const int n = SZ(P) - 1;
    // printf(": %d\n", n);
    P[0].pre = -1;
    FOR(i, 1, n){
        P[i].pre = P[i].wgh = -0x3f3f3f3f;
        for(Edge e: P[i].in) if(chkmax(P[i].wgh, e.wgh)){
            P[i].pre = e.from;
        }
    }
    // FOR(i, 1, n) printf("%d%c", P[i].pre, " \n"[i == ed_i]);
    // FOR(i, 1, n) printf("%d%c", P[i].wgh, " \n"[i == ed_i]);
    vector<int> vis(n + 1, 0);
    VI cir;
    FOR(i, 1, n) if(!vis[i]){
        stack<int> sk;
        vis[i] = 2, sk.push(i);
        int x = P[i].pre;
        while(x != -1 && !vis[x]) vis[x] = 2, sk.push(x), x = P[x].pre;
        // printf("-- %d %d\n", i, x);
        if(vis[x] == 2){
            FOR(j, 1, n) vis[j] = 0;
            int j;
            while((j = sk.top()) != x) cir.pb(j), vis[j] = 1, sk.pop();
            cir.pb(j), vis[j] = 1;
            break;
        }
        while(!sk.empty()) vis[sk.top()] = 1, sk.pop();
    }
    if(cir.empty()){
        // puts("No Cir!");
        return;
    }
    // FOR(i, 1, n) printf("%d%c", vis[i], " \n"[i == ed_i]);

    VI id(n + 1);
    int sz = 0;
    id[0] = 0;
    FOR(i, 1, n) if(!vis[i]) id[i] = ++sz;
    ++sz;
    for(int i: cir) id[i] = sz;
    vector<Vertice> Q(sz + 1);
    FOR(i, 1, n) if(vis[i]){
        for(Edge e: P[i].in) if(!vis[e.from])
            Q[sz].in.pb(Edge(id[e.from], e.wgh - P[i].wgh));
    }else{
        for(Edge e: P[i].in)
            Q[id[i]].in.pb(Edge(id[e.from], e.wgh));
    }
    MDST(Q);

    VI rd(sz + 1);
    rd[0] = 0;
    FOR(i, 1, n) if(!vis[i]) rd[id[i]] = i;
    FOR(i, 1, n) if(!vis[i]){
        if(Q[id[i]].pre == sz){
            for(Edge e: P[i].in) if(vis[e.from] &&
                e.wgh == Q[id[i]].wgh){
                P[i].pre = e.from;
                P[i].wgh = e.wgh;
                break;
            }
        }else{
            P[i].pre = rd[Q[id[i]].pre];
            P[i].wgh = Q[id[i]].wgh;
        }
    }
    [&](){ for(int i: cir){
        for(Edge e: P[i].in) if(e.from == rd[Q[sz].pre] &&
            e.wgh == P[i].wgh + Q[sz].wgh){
            P[i].wgh = e.wgh;
            P[i].pre = e.from;
            return;
        }
    } }();
    // FOR(i, 1, n) printf("%d%c", P[i].pre, " \n"[i == ed_i]);
    // FOR(i, 1, n) printf("%d%c", P[i].wgh, " \n"[i == ed_i]);
    // puts("-----");
    return;
}

int n;
string key[N];
int e[N][N];
int ans = 1;
int vis[N];
int G[NN][26];
int hd[N], cc;
char fc[NN];
int fth[NN];

int main() {
    cin >> n;
    FOR(i, 1, n) cin >> key[i], ans += SZ(key[i]);
    vector<Vertice> P(n + 1);
    FOR(i, 1, n) FOR(j, 1, n) if(i != j){
        e[i][j] = get_wgh(key[i], key[j]);
        // printf("%d %d %d\n", i, j, e[i][j]);
        P[j].in.pb(Edge(i, e[i][j]));
    }
    FOR(i, 1, n) P[i].in.pb(Edge(0, -0x3f3f3f));
    MDST(P);
    // printf("%d\n", ans);
    FOR(i, 1, n) if(P[i].pre > 0) ans -= P[i].wgh;
    printf("%d\n", ans);

    function<void(int)> dfs = [&](const int &u){
        const int fa = P[u].pre, len = P[u].wgh;
        if(!fa){
            int t = hd[u] = ++cc;
            for(char c: key[u]) t = (G[t][c - 'a'] = ++cc);
            return;
        }
        if(!hd[fa]) dfs(fa);
        const string x = key[fa], y = key[u];
        int t = hd[fa];
        int s = len == 0 ? SZ(x) : [&](){
            FOR(i, 0, SZ(x) - len)
                if(is_sub(x.substr(i, len), y)){
                return i;
            }
            return SZ(x);
        }();
        FOR(i, 0, s - 1) t = G[t][x[i] - 'a'];
        hd[u] = t;
        FOR(i, s, s + len - 1) t = G[t][x[i] - 'a'];
        assert(SZ(y) == len || G[t][y[len] - 'a'] == 0);
        FOR(i, len, SZ(y) - 1) t = G[t][y[i] - 'a'] = ++cc;
    };
    FOR(i, 1, n) if(!hd[i]) dfs(i);

    FOR(i, 1, cc){
        int j;
        FOR(c, 0, 25) if((j = G[i][c]))
            fc[j] = c + 'a', fth[j] = i;
    }
    FOR(i, 1, cc){
        if(fth[i]) printf("%d %c\n", fth[i], fc[i]);
        else printf("0\n");
    }
    return 0;
}

H - Hack Protection

题意简述

给个序列，求有多少个区间异或和等于按位与的值。$n\le 10^5,W<2^{31}$。

主要思路

从左到右枚举右端点，注意到右端点往左 AND 只有 $O(\log W)$ 种不同的值。
再 XOR 前缀和一下。
于是相当于求 $O(n\log W)$ 个区间中某个数的数量。
随便 $O(n\log W\log 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
#include <bits/stdc++.h>
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 long long i64;
typedef vector<int> VI;
typedef pair<int, int> PII;
#define MP(a, b) make_pair(a, b)
#define pb push_back
#define fr first
#define sc second

#define MMR (1 << 22)
struct INPUT{
    FILE *F;
    char buf[MMR], *s, *t;
    INPUT(): F(fopen("hack.in", "r")){
        t = (s = buf) + fread(buf, 1, MMR, F);
        fclose(F);
    }
    inline INPUT& operator >>(int &x){
        x = 0;
        reg char c(*s++);
        while(!isdigit(c)) c = *s++;
        while(isdigit(c)) x = x * 10 + c - 48, c = *s++;
        return *this;
    }
}fin;

#define N 100010
int n;
int a[N], s[N];
VI ps[N];

map<int, int> mp;
inline int md(const int &x){
    if(mp.count(x)) return mp[x];
    return mp[x] = mp.size() + 1;
}

inline int count(const int &l, const int &r, const int &x){
    if(!mp[x]) return 0;
    VI &f = ps[md(x)];
    return lower_bound(f.begin(), f.end(), r) - lower_bound(f.begin(), f.end(), l);
}

i64 ans;
int main() {
    fin >> n;
    ps[md(0)].pb(0);
    FOR(i, 1, n){
        fin >> a[i];
        s[i] = a[i] ^ s[i - 1];
        if(i != n) ps[md(s[i])].pb(i);
    }
    // for(PII x: mp) ps[x.sc].pb(n + 1);
    // FOR(i, 0, n - 1) printf("%d%c", s[i], " \n"[i == ed_i]);
    vector<PII> B;
    FOR(i, 1, n){
        const int v = a[i];
        vector<PII> C;
        for(PII x: B){
            if(C.empty() || (x.sc & v) != C.back().sc)
                C.pb(MP(x.fr, x.sc & v));
        }
        ++ans;
        int r = i;
        ROF(j, (int)C.size() - 1, 0){
            ans += count(C[j].fr - 1, r - 1, C[j].sc ^ s[i]);
            // printf("count(%d, %d, %d): %d\n",
            //     C[j].fr - 1, r - 1, C[j].sc ^ s[i],
            //     count(C[j].fr - 1, r - 1, C[j].sc ^ s[i]));
            r = C[j].fr;
        }
        // for(PII x: C)
        //     printf("%d %d\n", x.fr, x.sc);
        // puts("-----");
        if(C.empty() || (a[i] != C.back().sc))
            C.pb(MP(i, v));
        B = C;
    }
    FILE *fo(fopen("hack.out", "w"));
    fprintf(fo, "%lld\n", ans);
    fclose(fo);
    return 0;
}

I - Interactive Interception

题意简述

交互题。有一辆小车，开始在 $[0, p]$ 中的一个整点，小车有一个向右的整数的速度 $q\in [0, v]$，当然你是不知道的。
每次你可以问小车在不在 $[L, R]$ 里，问完小车会向右移动 $q$。请用至多 $100$ 次询问求出小车某一时刻的位置。$p,v\le 10^5$。

主要思路

可能的情况在二维平面的矩形里，一次询问相当于用一条定斜率的直线去切它。由于座标范围比较小，可以直接存储每个横坐标对应哪些纵坐标还可能是答案，然后询问的时候二分询问点，使得把剩下的点切成尽可能均匀的两部分。

然后感觉挺宽的，跑不满。

参考代码

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
#include <bits/stdc++.h>
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; }

#define N 100
inline bool query(const int &l, const int &r){
    printf("check %d %d\n", l, r), fflush(stdout);
    static char s[8];
    scanf("%s", s);
    return *s == 'Y';
}

int lp, rp, lv, rv;
int l[N], r[N];
int main() {
    scanf("%d%d", &rp, &rv);
    int t = 0, dp;
    while(lp < rp){
        dp = (lp + rp) >> 1;
        if(query(lp, dp)) rp = dp;
        else lp = dp + 1;
        FOR(i, 0, t - 1){
            chkmin(rv, (rp - l[i]) / (t - i));
            chkmax(lv, (lp - r[i]) / (t - i));
        }
        l[t] = lp, r[t] = rp;
        lp += lv, rp += rv;
        ++t;
    }
    printf("answer %d\n", lp);
    return 0;
}

K - Kabaleo Lite

题意简述

桌上有 $n$ 堆筹码，堆顶颜色分别为 $b_i$；$p$ 个玩家，你是第一个，每人手上分别有一个颜色为 $l_i$ 的筹码。所有玩家依次将自己的筹码放到某堆的堆顶，最后统计占据最多筹码堆堆顶的颜色，称其为胜利颜色。
你有一个目标颜色 $h$，并希望自己的目标颜色无论如何为胜利颜色。问你能够把自己手上的筹码放到哪些堆上，使得满足条件。
颜色数 $c, n, p\le 10^6$。

主要思路

显然最坏情况是所有人都来把覆盖你的颜色的筹码。于是就是个大讨论。

我感觉写得也非常不清真。总之过了就行。

参考代码

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
#include <bits/stdc++.h>
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 FORit(templ, arr, i, a, b) for (register templ *i = (arr) + (a), *ed_##i = (arr) + (b) + 1; i != ed_##i; ++i)
#define ROFit(templ, arr, i, a, b) for (register templ *i = (arr) + (a), *ed_##i = (arr) + (b) - 1; i != ed_##i; --i)
#define GO(x, p, e, i, v) for (register int i = p[x].head, v; i; i = e[i].link)
#define MEM(x, v) memset(x, v, sizeof(x))
typedef long long i64;
typedef pair<int, int> PII;
typedef vector<int> VI;
#define pb push_back
#define fr first
#define sc second
#define pq priority_queue
#define MP make_pair
#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; }

#define MMR (1 << 24)
struct INPUT{
    FILE *F;
    char buf[MMR], *s, *t;
    INPUT(): F(fopen("kabaleo.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(!isdigit(c)) c = *s++;
        while(isdigit(c)) x = x * 10 + c - 48, c = *s++;
        return *this;
    }
}fin;
struct OUTPUT{
    FILE *F;
    char buf[MMR], *s;
    OUTPUT(): F(fopen("kabaleo.out", "w")){ s = buf; }
    inline OUTPUT& operator <<(int x){
        static int tmp[23];
        Rint *top = tmp;
        if(x < 0) x = -x, *s++ = '-';
        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 1000010
using I = int[N];
int n, m, C, H;
I a, c, f, q;

inline int gg(){
    return fout << 0, 0;
}
inline bool all_H(){
    FOR(i, 1, n) if(a[i] != H) return 0;
    return 1;
}

int main() {
    fin >> n >> m >> C >> H;
    FOR(i, 1, n) fin >> a[i], ++f[a[i]];
    FOR(i, 1, m) fin >> c[i];
    if(n == 1){
        c[m] == H ? fout << 1 << 1 : fout << 0;
        return 0;
    }
    if(all_H()){
        --f[H], ++f[c[1]];
        FOR(i, 2, m){
            if(!f[H]) return gg();
            --f[H], ++f[c[i]];
        }
        FOR(i, 1, C) if(i != H && f[i] >= f[H]) return gg();
        fout << n;
        FOR(i, 1, n) fout << i;
        return 0;
    }
    ++f[c[1]];
    FOR(i, 2, m){
        if(!f[H]) return gg();
        --f[H], ++f[c[i]];
    }
    int smF = -1, onH = 1;
    FOR(i, 1, C) if(i != H){
        if(f[i] == f[H]){
            if(smF != -1) return gg();
            smF = i;
        }
        else if(f[i] > f[H]) return gg();
        else if(f[i] == f[H] - 1) onH = 0;
    }
    if(smF == -1){
        FOR(i, 1, C){
            if(i != H || onH) q[i] = 1;
        }
    }
    else q[smF] = 1;
    Rint cnt = 0;
    FOR(i, 1, n) if(q[a[i]]) ++cnt;
    fout << cnt;
    FOR(i, 1, n) if(q[a[i]]) fout << i;
    return 0;
}