Hile_Meow's Blog

2021CCPC东北四省赛

2021-10-19 分类 组队训练 作者 Hile_Meow ~10.08K 字

都1202年了竟然有比赛会出模板题（主要是没带模板，战犯++

A. Matrix

一开始的思路是计算前$n$个数分布在恰好$k$行的方案数，然后考虑了容斥、斯特林数等一堆东西，发现又重又漏。

写完H，在Awei写C的时候突然反应过来，对于每个数在一行作为最小值的情况计算贡献完全没问题且公式简洁，遂ac。

当一道被a穿的题想不出来时，及时转换思路防止钻牛角尖。

（笑死，思路想歪，2h签不出到）

Solution

$n\times(n^2-n)!\times\sum_{i=1}^{i=n}{n^2-i\choose n-1}$

B. Cypher

五页的题面三个字：大模拟。但其实听队友一说好像难度$90\%$都在读题上，属于是出题人不怀好意了（

题意建议自己读，体验一下（）

Code
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
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 55+7;
const int MOD = 1e9+7;
int n,p,q,d[N],b[N];
string s[N],t[N],r,all="ABCDEFGHIJKLMNOPQRSTUVWXYZ";
map<char,char> mp,mr;
void rotate(int i,int k){
    s[i]=s[i].substr(k,26)+s[i].substr(0,k);
    t[i]=t[i].substr(k,26)+t[i].substr(0,k);
}
char query(char c){
    for(int i=1;i<=n;i++){
        b[i]++;
        rotate(i,1);
        if(b[i]%26==0&&i<=n){
            continue;
        }else break;
    }
    int id=mp[c]-'A';
    for(int i=1;i<=n;i++){
        id=t[i][id];
        id=s[i].find(id);
    }
    id=all[id];
    id=r.find(id);
    for(int i=n;i>=1;i--){
        id=s[i][id];
        id=t[i].find(id);
    }
    return mp[id+'A'];
}
int main(){
    ios::sync_with_stdio(false);
    int T=1;
    cin>>T;
    while(T--){
        cin>>p;
        for(int i=0;i<26;i++){
            mp[i+'A']=i+'A';
        }
        for(int i=1;i<=p;i++){
            string tmp;
            cin>>tmp;
            mp[tmp[0]]=tmp[1];
            mp[tmp[1]]=tmp[0];
        }
        cin>>n;
        for(int i=1;i<=n;i++){
            cin>>s[i];
            t[i]=all;
        }
        for(int i=1;i<=n;i++){
            cin>>d[i];
            b[i]=d[i];
            rotate(i,d[i]);
        }
        cin>>r;
        for(int i=0;i<26;i++){
            mr['A'+i]=r[i];
        }
        cin>>q;
        while(q--){
            string tmp;
            cin>>tmp;
            for(auto i:tmp){
                cout<<query(i);
            }
            cout<<"\n";
        }
    }
}

C. Vertex Deletion

D. Lowbit

Solution

属于是势能线段树裸题了，势能函数$f(x)$为将$x$变为$2^k$的操作次数，显然$\max\{f(x)\}=log_2(x)$，所以可以维护一个标记来表示区间内的数都为$2$的幂次，当一个区间被标记时，$1$操作就变成了区间乘二。复杂度$O(n\log^2 n)$。

Code
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
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e5+7;
const int MOD=998244353;
int n,m,a[N];
vector<int> b[N];
ll lowbit(ll x){
    return x&-x;
}
struct SegmentTree{
    #define lson o<<1,l,mid
    #define rson o<<1|1,mid+1,r
    ll val[N<<2];
    int tag[N<<2],all[N<<2];
    void build(int o,int l,int r){
        tag[o]=1,all[o]=0;
        if(l==r){
            val[o]=a[l],all[o]=!b[l].size();
            return;
        }
        int mid=l+r>>1;
        build(lson);
        build(rson);
        all[o]=all[o<<1]+all[o<<1|1];
        val[o]=(val[o<<1]+val[o<<1|1])%MOD;
    }
    void pd(int o,int k){
        tag[o]=1LL*tag[o]*k%MOD;
        val[o]=1LL*val[o]*k%MOD;
    }
    void pushdown(int o){
        pd(o<<1,tag[o]);
        pd(o<<1|1,tag[o]);
        tag[o]=1;
    }
    void update(int o,int l,int r,int L,int R){
        if(L<=l&&r<=R){
            if(all[o]==r-l+1){
                pd(o,2);
                return;
            }
            if(l==r&&!all[o]){
                val[o]=(val[o]+b[l].back())%MOD;
                b[l].pop_back();
                if(!b[l].size())all[o]=1;
                return;
            }
        }
        pushdown(o);
        int mid=l+r>>1;
        if(L<=mid)update(lson,L,R);
        if(R>mid)update(rson,L,R);
        all[o]=all[o<<1]+all[o<<1|1];
        val[o]=(val[o<<1]+val[o<<1|1])%MOD;
    }
    ll query(int o,int l,int r,int L,int R,ll res=0){
        if(L<=l&&r<=R){
            return val[o];
        }
        pushdown(o);
        int mid=l+r>>1;
        if(L<=mid)(res+=query(lson,L,R))%=MOD;
        if(R>mid)(res+=query(rson,L,R))%=MOD;
        return res;
    }
}S;
int main(){
    ios::sync_with_stdio(false);
    int T;
    cin>>T;
    while(T--){
        cin>>n;
        for(int i=1;i<=n;i++){
            cin>>a[i];
            b[i].clear();
            ll tmp=a[i];
            while(__builtin_popcount(tmp)!=1){
                b[i].push_back((lowbit(tmp))%MOD);
                tmp+=lowbit(tmp);
            }
            reverse(b[i].begin(),b[i].end());
        }
        S.build(1,1,n);
        cin>>m;
        while(m--){
            int op,l,r;
            cin>>op>>l>>r;
            if(op==1){
                S.update(1,1,n,l,r);
            }else{
                cout<<S.query(1,1,n,l,r)<<"\n";
            }
        }
    }
}

E. Easy Math Problem

签到。Hile_Meow病发，wa一发才过。

F. Permutation

G. Ball

计数。考虑满足$n,m,k$的状态最终一定是两段，前一段连续，后一段和前一段不连续（长度可能为0）。

假设第一段长度为$x$，令$f_{i,j}$表示扔$i$个球填满$j$个区域的方案数，$g_{i,j}$表示扔$i$个球填不满$j$个区域的方案数，则此时答案为$f_{k+x,x}\times g_{m-k-x,n-x-1}\times {m\choose k+x}$，

考虑枚举所有可能的$x$，则答案为上式之和，接下来计算$f$和$g$。

可以看看ZAwei的博客，里面的转移很简单，这里提供一种相对麻烦但是没有思维难度的计算方法：

考虑$f_{i,j}$的转移有两种：

  • 在已经填满$j$个区域的基础上再扔一个球
  • 扔第$i$个球时恰好填满$j$个区域

第一种转移就是$f_{i-1,j}\times j$，

第二种转移考虑枚举最后一个填的位置$x$，结果为$f_{i-j+x-1,j}\times f_{j-x,j-x}\times{i-1\choose j-x}\times(j-x+1)$，

复杂度$O(mn^2)$。

Code
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
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 500+7;
const int MOD = 998244353;
int f[N<<1][N],g[N<<1][N],C[N<<2][N<<2];
ll solve(int n,int m,int k){
    ll ans=0;
    if(!k)return g[m][n];
    for(int i=1;i<=min(n,m-k);i++){
        if(i<n){
            ans=(ans+1LL*f[i+k][i]*g[m-i-k][n-i-1]%MOD*C[m][i+k]%MOD)%MOD;
        }else if(n+k==m){
            ans=(ans+f[m][n])%MOD;
        }
    }
    return ans;
}
int main(){
    C[0][0]=1;
    for(int i=1;i<=2000;i++){
        C[i][0]=1;
        for(int j=1;j<=i;j++){
            C[i][j]=(C[i-1][j-1]+C[i-1][j])%MOD;
        }
    }
    f[0][0]=g[0][0]=1;
    for(int i=1;i<=1000;i++){
        for(int j=1;j<=min(i,500);j++){
            for(int k=1;k<=j;k++){
                f[i][j]=(f[i][j]+1LL*f[i-j+k-1][k-1]*f[j-k][j-k]%MOD*C[i-1][j-k]%MOD*(j-k+1)%MOD)%MOD;
            }
            f[i][j]=(f[i][j]+1LL*f[i-1][j]*j%MOD)%MOD;
        }
    }
    for(int j=1;j<=500;j++){
        g[0][j]=1;
        for(int i=1;i<=j;i++){
            for(int k=0;k<=i;k++){
                g[i][j]=(g[i][j]+1LL*g[i-k][j-1]*C[i][k]%MOD)%MOD;
            }
        }
    }
    ios::sync_with_stdio(false);
    int T;
    cin>>T;
    while(T--){
        int n,m,k;
        cin>>n>>m>>k;
        cout<<solve(n,m,k)<<"\n";
    }
}

H. Loneliness

给出一个$n\times n$的矩阵，你的分数初始为$1$。当分数为$x$时，往上下左右分别会变成$x/2,x\times2,x+2,x-2$（往上时$x$必须为偶数），给出一个$k$，要求输出从$(1,1)$到$(n,n)$的一条路径（可重复经过$(n,n)$在内的点）使得在终点时分数恰好为$k$。

Solution

构造。考虑$n=100$，有足够的空间去构造答案，所以不妨倒过来想$k$是怎么构造出来的（考虑二进制），可以发现能根据$k$找到一个点$P(x,y)$满足在$P$点的答案为$0$，只往右或往下就能在$(n,n)$恰好得到$k$。由于$k\le 10^{16}<2^{60}$，$P$肯定在矩阵中。

然后考虑上下左右移动就是对于$2$的加减乘除：假设初始为偶数$x$，则$x$依次右上左下移动会得到$x+2,x/2+1,x/2-1,x-2$，也就是说$x$可以这么转一圈然后原地减$2$。

问题解决了，首先二进制分解$k$求出$P$点。第一步往下移动到$(2,1)$，当前答案为$2$，通过转圈操作使答案保持为$0$，逐步右移到和$P$同纵坐标，然后就一路往下到$P$，再构造$k$就好了。题目要求操作数小于$1000$，每次转圈消耗$4$步，从$(1,1)$到$(100,100)$需要$198$步，构造的答案显然小于$1000$。

（这种构造题建议给出充足的时间让不上机的队友玩，玩着玩着就出了）

Code

赛中代码有点丑，不放了。

I. Takeaway

签到。Boboge秒了。

J. Transform

求三维点绕三维向量旋转某角度之后的结果。

Solution

Rodriguez Formula板子题。

向量$v$绕单位向量$u$旋转$\theta$后的$v’$为

$v’=v\cos\theta+u(u·v)(1-\cos\theta)+(u\times v)\sin\theta$

（其中 $·$ 为三维点乘，$\times$为三维叉乘）

Solution
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
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 2e5+7;
const int MOD = 1e9+7;
const double PI = acos(-1.0);
typedef struct Point {
    double x,y,z;
    Point(double x=0,double y=0,double z=0):x(x),y(y),z(z){}
    double len(){return sqrt(x*x+y*y+z*z);}
    double operator*(const Point &b) const{return x*b.x+y*b.y+z*b.z;}
    Point operator + (const Point &t) {return Point(x+t.x,y+t.y,z+t.z);}
    Point operator ^ (const Point &t) {return Point(y*t.z-t.y*z,t.x*z-x*t.z,x*t.y-t.x*y);}
    Point operator * (double t) {return Point(x*t,y*t,z*t);}
    void read(){
        scanf("%lf%lf%lf",&x,&y,&z);
    }
} Vector;
double Length(Point a){
    return sqrt(a*a);
}
Vector Rotate(Vector u,Vector v,double r){
    double len=Length(u);
    u=u*(1.0/len);
    return v*cos(r)+u*(u*v)*(1.0-cos(r))+(u^v)*sin(r);
}
int main(){
    int T=1;
    scanf("%d",&T);
    while(T--){
        Point a,b;
        double r;
        a.read(),b.read();
        scanf("%lf",&r);
        r=r*PI/180.0;
        Vector P=Rotate(a,b,r);
        Vector Q=Rotate(a,b,-r);
        if(P.z>Q.z)swap(P,Q);
        printf("%.9f %.9f %.9f\n",Q.x,Q.y,Q.z);
    }
}

K. City

签到。Boboge秒了。

L. k-th Smallest Common Substring

M. Master of Shuangpin

签到。Boboge秒了。

本作品采用 知识共享署名-相同方式共享 4.0 国际许可协议 进行许可
最后编辑：2021-11-03