Zory的n0ip模拟赛题解

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

在这里必须吐槽一下组题人和出题人的语文水平……愣是把这场打成了语文场……

「CEOI2019」Cubeword (D1T3)

[LOJ 3164]

[CF 1192C]

居然这个题是完全机翻的……怪不得难以理解……

题意简述

给定 $n$ 个互不相同的有意义的单词( $1\le n\le 10^5$ )，每个单词都是一个长度在 $[3,10]$ 间的字符串，单词中包含小写的a到z，大写的A到Z，数字0到9。

然后，你选定正方体的棱长 $a$ ，建立一个有 $a^3$ 单位的立方体。你要在这个大正方体的 $12$ 条边上的所有单位正方体上填上一个字母（这里字母的定义是小写的a到z，大写的A到Z，数字0到9）。边上的所有单位立方体填上字母后，每条边都必须是一个有意义的长度为 $a$ 的单词。每条边可以双向阅读，即只要从一个方向读起来是有意义的单词即可。

例如上图就是 $a=6$ 时，只填了 $3$ 条边时的情况。此时已填的三条边分别可以看出单词SUBMIT(或TIMBUS)、ACCEPT(或TPECCA)、TURING(或GNIRUT)。

如果一个立方体可以通过旋转或镜像变成另一个立方体，则认为这两个立方体是不同的。

主要思路

以 $S$ 表示字符集。考虑如何处理长度为 $len$ 的单词。

当一个顶点所在的三条棱的另一端的顶点都已经确定填什么字母时，显然这三条棱的填法种类是固定的。这里使用 $f(i_1,i_2,i_3)$ 来描述。显然处理单个 $f(i_1,i_2,i_3)$ 的复杂度是 $O(|S|)$ 。

枚举正方体四个互不相邻的顶点该位置填什么字母。设这四个顶点分别填 $i_1,i_2,i_3,i_4$ ，则此时整个正方体满足要求的方案数是 $f(i_1,i_2,i_3)\times f(i_2,i_3,i_4) \times f(i_3,i_4,i_1) \times f(i_4,i_1,i_2)$ 。则最终的答案就是
$$\sum\limits_{i_1\in S}\sum\limits_{i_2\in S}\sum\limits_{i_3\in S}\sum\limits_{i_4\in S} f(i_1,i_2,i_3)\times f(i_2,i_3,i_4) \times f(i_3,i_4,i_1) \times f(i_4,i_1,i_2)$$

此时总时间复杂度是 $O(8 \times |S|^4)$ ，据说会被卡常。

考虑处理答案时可以钦定 $i_1\le i_2\le i_3\le i_4$ ，处理 $f(i_1,i_2,i_3)$ 时可以钦定 $i_1\le i_2\le i_3$ 。如此常数减小，完全可过。

注意最后求答案时需要处理 $i_1,i_2,i_3,i_4$ 的出现次数。

参考代码

字符串正反去重处理使用了hash。
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
#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 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))
    #define fir first
    #define sec second
    #define pq priority_queue
    #define MP make_pair
    typedef long long LL;
    typedef double DB;
    typedef pair<int,int> PII;
    #define Templ(T) template<typename T>
    inline int read(){
        Rint ans=0,f=1;reg char c=getchar();
        while(!isdigit(c)){ f^=(c=='-'); c=getchar(); }
        for(;isdigit(c);c=getchar()) ans=ans*10+c-'0'; return f?ans:-ans;
    }
    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 using_mod
    const int mod = 0x3B800001 , N = 100010;
    #ifdef using_mod
    inline void inc(int &x,const int &y){ x+=y; if(x>=mod) x-=mod; }
    inline int ksm(int x,LL y){ int res=1; for(;y;y>>=1,x=1ll*x*x%mod) if(y&1) res=1ll*res*x%mod; return res;}
    #endif
    Templ(_Tp) inline _Tp gcd(_Tp x,_Tp y){ return y?gcd(y,x%y):x; }
    #define FILE(s) freopen(s".in","r",stdin),freopen(s".out","w",stdout)
    #define PBTXDY
}
using namespace my_std;

template <typename Tp> inline Tp mul_(Tp t){ return t; }
template <typename Tp,typename... Args> inline Tp mul_(Tp t, Args ...args){ return 1ll * t * mul_(args...) % mod; }

const LL mod1 = 0x3B800001 , mod2 = 0x3BE00001;
const int board[2][2][2] = { { {24 , 12} , {12 , 4} } , { {12 , 6} , {4 , 1} } };

int n , cnt[62][62] , tot[62][62][62] , ans;
char str[N][13] , len[N] , rev[N];
map<PII,int> map_;
inline int chg_chr(char csp){
    if(isdigit(csp)) return csp - '0';
    if('a' <= csp && csp <= 'z') return csp - 'a' + 10;
    return csp - 'A' + 36;
}

inline void add_str(int x){
    reg LL tme1 = 0,tme2 = 0;
    FOR(i,0,len[x] - 1) (tme1 = tme1 * 233 + str[x][i]) %= mod1 , (tme2 = tme2 * 233 + str[x][i]) %= mod2;
    reg PII pr = MP(int(tme1),int(tme2));
    if(map_[pr]) return;
    map_[pr] = 1;
    cnt[chg_chr(str[x][0])][chg_chr(str[x][len[x] - 1])] ++;
    if(!rev[x]){
        tme1 = 0 , tme2 = 0;
        ROF(i,len[x] - 1,0) (tme1 = tme1 * 233 + str[x][i]) %= mod1 , (tme2 = tme2 * 233 + str[x][i]) %= mod2;
        pr = MP(int(tme1),int(tme2));
        map_[pr] = 1;
        cnt[chg_chr(str[x][len[x] - 1])][chg_chr(str[x][0])] ++;
    }
    return;
}

inline void work_len(int now_len){
    MEM(cnt , 0) , MEM(tot , 0) , map_.clear();
    FOR(i,1,n) if(len[i] == now_len) add_str(i);
    FOR(i1,0,61) FOR(i2,i1,61) FOR(i3,i2,61) FOR(i4,0,61){
        inc(tot[i1][i2][i3] , mul_(cnt[i1][i4],cnt[i2][i4],cnt[i3][i4]) );
    }
    Rint pre;
    FOR(i1,0,61) FOR(i2,i1,61) FOR(i3,i2,61) FOR(i4,i3,61){
        pre = mul_(tot[i1][i2][i3] , tot[i1][i2][i4] , tot[i1][i3][i4] , tot[i2][i3][i4]);
        inc(ans , 1ll * pre * board[i1 == i2][i2 == i3][i3 == i4] % mod);
    }
}

int main(){
    n = read();
    FOR(i,1,n){
        scanf("%s",str[i]);
        len[i] = strlen(str[i]);
        rev[i] = 1;
        FOR(j,0,len[i] - 1) if(str[i][j] != str[i][len[i] - 1 - j]){ rev[i] = 0; break; }
    }
    FOR(now_len,3,10) work_len(now_len);
    return printf("%d\n",ans),0;
}

「LOJ 6364」烂柯

[LOJ 6364]

居然是原创题，然而还是很难懂……

题意简述

给定一棵 $n$ 个节点的树，其中 $m$ 个节点上有柿子。在这棵树上进行博弈。双方轮流操作，每次选择一个有柿子的节点，将上面至少一个柿子移动到相邻节点，或如果这个节点是叶子节点且与开始给定的一个节点 $k$ 的距离是奇数，将上面至少一个柿子删除。每个柿子都不能移动到该柿子曾经位于的节点上。最后不能操作的人就输了。

给出树的形态和开始 $m$ 个节点上柿子的位置及个数，求双方最优策略下先手胜负。

有 $case$ 组数据， $case \le 10,\ n,a_i \le 100,\ m\le 18$ 。

主要思路

数据出得如此小，简直考验选手心理。

考虑以 $k$ 为根，能删除柿子的节点是深度为奇数的叶子（深度从 $0$ 开始）。这样，在节点上删柿子可以看作在该节点下挂了一个虚节点，将柿子移动到了该节点。所以当不能移动柿子时，柿子深度均为偶数。

发现每个柿子会被移动次数的奇偶性与深度的奇偶性相同，而游戏显然不能无限进行，因此该游戏和普通阶梯博弈等价。只需将所有距离 $k$ 为奇数的节点的柿子数量异或起来（记为 $cnt$ ）， $cnt > 0$ 就是先手必胜， $cnt = 0$ 就是后手必胜。

代码难度小，不放代码了。

「CF 567F」Mausoleum

[CF 567F]

Zory说这是签到题，然而本人场上没想出来……

题意简述

一个长为 $2n$ 的数列，其中 $1,2,\dots,n$ 各出现两次，并且是单峰的（先一段不降再一段不升，长度可以为 $0$ ）。并且给出了 $k$ 个限制，要求第 $x_i$ 个位置的数必须 $\mathtt{sign_i}$ 第 $y_i$ 个位置上的数，其中 $\mathtt{sign_i}$ 是等于、大于、小于、大于等于、小于等于中的一种。

求该数列的可能种数。 $n \le 35, k\le 100$ 。

主要思路

考虑 $f(l,r)$ 表示 $[l,r]$ 中的位置还没有填数并且峰顶在 $[l,r]$ 中时的方案总数，初始时 $f(0,2n + 1) = 0$ ，我们要求的答案是 $\sum\limits_{i=1}^{2n-1}f(i,i + 1)$ （因为剩下两个 $n$ 只能填在空缺的两个位置）。

$f(l,r)$ 可以转移到 $f(l+1,r+1),f(l+2,r),f(l,r-2)$ ，注意限制，具体实现见代码，大概就是每个位置开一个 $\text{vector}$ 存一下这个位置要等于哪些位置、小于等于哪些位置、小于哪些位置，然后转移时暴力判断。

参考代码

细节有点多：
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
#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 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))
    #define fir first
    #define sec second
    #define pq priority_queue
    #define MP make_pair
    typedef long long LL;
    typedef double DB;
    typedef pair<int,int> PII;
    #define Templ(T) template<typename T>
    inline int read(){
        int ans=0,f=1;char c=getchar();
        while(!isdigit(c)){ f^=(c=='-'); c=getchar(); }
        for(;isdigit(c);c=getchar()) ans=(ans<<1)+(ans<<3)+(c^48); return f?ans:-ans;
    }
    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 using_mod
    const int mod = 998244353, N = 120;
    #ifdef using_mod
    inline void inc(int &x,const int &y){ x+=y; if(x>=mod) x-=mod; }
    inline int ksm(int x,LL y){ int res=1; for(;y;y>>=1,x=1ll*x*x%mod) if(y&1) res=1ll*res*x%mod; return res;}
    #endif
    Templ(_Tp) inline _Tp gcd(_Tp x,_Tp y){ return y?gcd(y,x%y):x; }
    #define FILE(s) freopen(s".in","r",stdin),freopen(s".out","w",stdout)
    #define PBTXDY
}
using namespace my_std;

int n, k;
LL f[N][N], ans;
vector<PII> lim[N];
inline int read_sign(){
    reg char scoi[5];
    scanf("%s",scoi);
    if(scoi[0] == '=') return 0;
    if(scoi[1] == '=') return scoi[0] == '<' ? -1 : 1;
    return scoi[0] == '<' ? -2 : 2;
}
// < <=  =  >= >
//-2 -1  0  1  2
inline int check_lim(int l, int r, int x, int y){
    Rint xx = (x - 1 > l) ? x - 1 : y + 2 , yy = (y + 1 < r) ? y + 1 : x - 2;
    Rint opt, pos;
    for(auto tmp : lim[xx]){
        opt = tmp.fir, pos = tmp.sec;
        if(opt == 0 && pos != xx && pos != yy) return 0;
        if(opt == -1 && (l + 1 > pos || pos > r - 1)) return 0;
        if(opt == -2 && (x > pos || pos > y)) return 0;
    }
    for(auto tmp : lim[yy]){
        opt = tmp.fir, pos = tmp.sec;
        if(opt == 0 && pos != xx && pos != yy) return 0;
        if(opt == -1 && (l + 1 > pos || pos > r - 1)) return 0;
        if(opt == -2 && (x > pos || pos > y)) return 0;
    }
    return 1;
}
int main(){
    n = read(), k = read();
    Rint xx, yy, opt;
    FOR(i, 1, k){
        xx = read(), opt = read_sign(), yy = read();
        lim[xx].push_back(MP(opt, yy)), lim[yy].push_back(MP(-opt, xx));
    }
    f[0][n << 1 | 1] = 1;
    ROF(i, n, 1) for(Rint l = 0, r; l <= ((n - i) << 1); ++l){//i : n -> 1 ; l <= 2 * (n - i) ; r - l = 1 + 2 * i
        r = (i << 1 | 1) + l;
        if(!f[l][r]) continue;
        if(i == 1){
            if(check_lim(l, r, l + 2, r - 2)) ans += f[l][r];
            continue;
        }
        if(check_lim(l, r, l + 2, r - 2)) f[l + 1][r - 1] += f[l][r];
        if(check_lim(l, r, l + 3, r - 1)) f[l + 2][r] += f[l][r];
        if(check_lim(l, r, l + 1, r - 3)) f[l][r - 2] += f[l][r];
    }
    printf("%I64d\n",ans);
    return 0;
}

「HDU 5181」numbers

[HDU 5181]

实在是搞不懂为什么一个意义简明的题面可以被解释得如此难懂，导致本人在考试结束前 1h 才看懂题面。

题意简述

你手上有个栈，你要将 $1,2,\dots,n$ 依次入栈，然后有 $m$ 个限制，限制 $A_i$ 必须早于 $B_i$ 出栈，其余出栈顺序不限。求有多少种合法的进出栈序列。 $case$ 组数据， $case \le 5,n \le 300,m \le 90000$ 。

主要思路

我们添加一个数 $0$ ，让 $0$ 在所有数进栈之前进栈，所有数出栈之后出栈。这样进出栈序列可以写成一棵以 $0$ 为根的树，dfs 序为 $0,1,2,\dots,n$ ，每个元素 $x$ 将在自己子树内（除自己）的所有元素进栈前进栈，出栈后出栈。

如果没有限制，显然我们可以设 $dp(x,k)$ 为考虑 $[x,n]$ 的进出栈顺序， $x$ 的子树大小为 $k$ 的种数。枚举 $x$ 除最右子树外其他子树大小和 $t$，则有 $dp(x,k) = \sum\limits_{t=1}^{k-1}dp(x,t)\times dp(x+t,k-t)$ 。

考虑限制 $(A_i,B_i)$ 在这棵数上的意义。

  • 如果 $A_i=B_i$ ，显然直接无解。
  • 如果 $A_i<B_i$ ， $A_i$ 的子树内不能包含 $B_i$ ，即 $A_i$ 的子树大小最大是 $\operatorname{Maxsiz}(A_i)=B_i - A_i$ 。
  • 如果 $A_i>B_i$ ， $B_i$ 的子树内必须包含 $A_i$ ，即 $B_i$ 的子树大小最小是 $\operatorname{Minsiz}(B_i)=A_i - B_i + 1$ 。

仍设 $dp(x,k)$ ，此时 $k\in [\operatorname{Minsiz}(x),\operatorname{Maxsiz}(x)]$ 时才有意义。

由于某个点在挂到别的点上时，子树大小并不改变，所以可以仍如上述方法做 dp ，在处理完 $dp(x,k)$ 后再把无意义的位置设为 $0$ 即可。

复杂度 $O(n^3)$ ，完全可过。

参考代码

都9102年了HDU还是不支持万能头……
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
//#include<bits/stdc++.h>
#include <cstdio>
#include <cstring>
#include <algorithm>
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 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))
    #define fir first
    #define sec second
    #define pq priority_queue
    #define MP make_pair
    typedef long long LL;
    typedef double DB;
    typedef pair<int,int> PII;
    #define Templ(T) template<typename T>
    inline int read(){
        int ans=0,f=1;char c=getchar();
        while(!isdigit(c)){ f^=(c=='-'); c=getchar(); }
        for(;isdigit(c);c=getchar()) ans=(ans<<1)+(ans<<3)+(c^48); return f?ans:-ans;
    }
    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 using_mod
    const int mod = 1000000007, N = 310;
    #ifdef using_mod
    inline void inc(int &x,const int &y){ x+=y; if(x>=mod) x-=mod; }
    inline int ksm(int x,LL y){ int res=1; for(;y;y>>=1,x=1ll*x*x%mod) if(y&1) res=1ll*res*x%mod; return res;}
    #endif
    Templ(_Tp) inline _Tp gcd(_Tp x,_Tp y){ return y?gcd(y,x%y):x; }
    #define FILE(s) freopen(s".in","r",stdin),freopen(s".out","w",stdout)
    #define PBTXDY
}
using namespace my_std;

int n, m, f[N][N], Mins[N], Maxs[N]/*Min_siz, Max_siz*/;

inline void hdu5181(){
    n = read(), m = read();
    Rint flag = 1, xx, yy;
    FOR(i, 0, n) Mins[i] = 0, Maxs[i] = n + 1;
    FOR(i, 1, m){
        xx = read(), yy = read();
        if(xx == yy) flag = 0;
        else (xx < yy) ? chkmin(Maxs[xx], yy - xx) : chkmax(Mins[yy], xx - yy + 1);
    }
    if(!flag) return void(puts("0"));
    ROF(x, n, 0){
        FOR(siz, 1, n + 1) f[x][siz] = 0;
        f[x][1] = 1;
        FOR(siz, 2, n - x + 1) FOR(t, 1, siz - 1) inc(f[x][siz], 1ll * f[x][t] * f[x + t][siz - t] % mod);
        FOR(siz, 1, Mins[x] - 1) f[x][siz] = 0;
        FOR(siz, Maxs[x] + 1, n + 1) f[x][siz] = 0;
    }
    printf("%lld\n", f[0][n + 1]);
}

int main(){
    Rint esac = read();
    while(esac--) hdu5181();
    return 0;
}