The 2023 CCPC Online Contest

https://codeforces.com/gym/104651

A. Almost Prefix Concatenation

题解

容易发现对于固定的起始位置 ii，符合almost prefix的结束位置一定是一段连续的区间。具体地，我们求出 lcp（最长公共前缀），然后往后移动一位，然后再求一次lcp，得到的就是最远的结束位置，记为 lcpilcp_i。

题目中要求平方和，我们可以先考虑方案数：可以倒着转移，记 fif_i 表示从 ii 到 ss结尾位置的子串的所有划分方案数，那么有 fi=∑j=i+1lcpi+1fjf_i=\sum\limits_{j=i+1}^{lcp_i+1}f_j。而 (n+1)2=n2+2×n+1(n+1)^2=n^2+2\times n+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
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
#include <bits/stdc++.h>
using namespace std;
const int N=1e6+5;
const int p=998244353;
typedef long long ll;
typedef unsigned long long ull;
const int M=2;
const ull B=233,mod[M]={1000000009,1000000901};
ull pw[M][N];
void init()
{
    for(int j=0;j<M;++j)
    {
        pw[j][0]=1;
        for(int i=1;i<N;++i)
            pw[j][i]=pw[j][i-1]*B%mod[j];
    }
}
// h[i]表示s_{0,1,...,i-1}的哈希值
void initHash(string &s,vector<vector<int>> &h)
{
    h.resize(M);
    for(int j=0;j<M;++j)
    {
        h[j].resize(s.size()+1);
        h[j][0]=0;
        for(int i=0;i<(int)s.size();++i)
            h[j][i+1]=(h[j][i]*B+s[i]-'a'+1)%mod[j];
    }
}
array<ull,M> subHash(vector<vector<int>> &h,int l,int r)
{
    array<ull,M> res;
    for(int i=0;i<M;++i)
        res[i]=(h[i][r]+mod[i]-h[i][l-1]*pw[i][r-l+1]%mod[i])%mod[i];
    return res;
}
string s,t;
vector<vector<int>> hs,ht;
int lcp[N];
ll f[N][3],diff[N][3];
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    init();
    cin>>s>>t;
    initHash(s,hs),initHash(t,ht);
    int n=(int)s.size(),m=(int)t.size();
    for(int i=1;i<=n;i++)
    {
        int ans=0,mid,l=1,r=min(m,n-i+1);
        while(l<=r)
        {
            mid=(l+r)>>1;
            if(subHash(hs,i,i+mid-1)==subHash(ht,1,mid))
            {
                ans=mid;
                l=mid+1;
            }
            else r=mid-1;
        }
        lcp[i]=ans;
        if(lcp[i]==min(n-i+1,m)) continue;
        ans=0,l=1,r=min(m,n-i+1)-lcp[i]-1;
        while(l<=r)
        {
            mid=(l+r)>>1;
            if(subHash(hs,i+lcp[i]+1,i+mid+lcp[i])==subHash(ht,1+lcp[i]+1,mid+lcp[i]+1))
            {
                ans=mid;
                l=mid+1;
            }
            else r=mid-1;
        }
        lcp[i]+=ans+1;
    }
    f[n+1][0]=1;
    for(int i=n;i;i--)
    {
        int l=i+1,r=i+lcp[i];
        f[i][0]=(f[l][0]-f[r+1][0]+p)%p;
        f[i][1]=((f[l][1]-f[r+1][1]+p)+(f[l][0]-f[r+1][0]+p))%p;
        f[i][2]=((f[l][2]-f[r+1][2]+p)+2*(f[l][1]-f[r+1][1]+p)+(f[l][0]-f[r+1][0]+p))%p;
        f[i][0]=(f[i][0]+f[i+1][0])%p;
        f[i][1]=(f[i][1]+f[i+1][1])%p;
        f[i][2]=(f[i][2]+f[i+1][2])%p;
    }
    cout<<(f[1][2]-f[2][2]+p)%p<<'\n';
    return 0;
}

D. Discrete Fourier Transform

题解

每个 FiF_i 对应复平面上的一个点，要求的是所有点到原点距离的最大值最小。当 fkf_k 变化时，每个点都在一条直线上运动，它们到原点的距离是一个关于 fkf_k 的下凸函数，它们的 max⁡\max 也是下凸函数。可以三分求解。

代码

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
#include <bits/stdc++.h>
using namespace std;
const int N=2005;
const double pi=acos(-1);
int n,k,f[N];
double a[N][2];
double len(double x,double y)
{
    return sqrt(x*x+y*y);
}
double cal(int m)
{
    double mx=0;
    for(int i=0;i<n;i++) mx=max(mx,len(a[i][0]+m*cos(2*pi*k*i/n),a[i][1]-m*sin(2*pi*k*i/n)));
    return mx;
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin>>n>>k;
    for(int i=0;i<n;i++) cin>>f[i];
    for(int i=0;i<n;i++)
        for(int j=0;j<n;j++)
            if(j!=k) 
            {
                a[i][0]+=f[j]*cos(2*pi*i*j/n);
                a[i][1]-=f[j]*sin(2*pi*i*j/n);
            }
    int l=-1e9,r=1e9;
    double lans,rans;
    while(l<r)
    {
        int lmid=l+(r-l)/3;
        int rmid=r-(r-l)/3;
        lans=cal(lmid),rans=cal(rmid);
        if(lans<=rans) r=rmid-1;
        else l=lmid+1;
    }
    cout<<fixed<<setprecision(12)<<min(lans,rans)<<'\n';
    return 0;
}

F. Flying Ship Story

题解

将每个商品看作二维平面上的点，令格子 (x,y)(x, y) 的权值 f(x,y)f(x, y) 表示与 (x,y)(x, y) 两维都不同的 商品的价值的最大值。一开始，所有点的权值都为 00。

按照价值从大到小依次考虑每个商品。假设现在考虑到商品 (a,b,w)(a, b, w)，它需要将除了直线 x=ax = a 以及直线 y=by = b 之外的所有权值为 00 的格子的权值都赋值为 ww。不难发现，如果这个商品没有修改到任意一个格子，那么这个商品是无用的，可以直接删除。否则，权值为 00 的格子 集合将缩小，只有以下几种可能的形态：全集、一个十字、一条横线、一条竖线、两个格子、 一个格子、空集。

不同状态之间的转移显然，并且根据商品无用论，我们最多只需要保存 44 个有用的商品。 每次加入新的商品时，将最多 55 个商品按价值从大到小排序，依次维护出权值为 00 的格子集合， 并剔除无用商品。对于每个询问，暴力检查至多 44 个商品即可。

代码

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
#include <bits/stdc++.h>
using namespace std;
#define y0 yy0
#define y1 yy1
int last,state,x0,y0,x1,y1,x2,y2;
struct node
{
    int x,y,w;
    bool operator<(const node& i)const{return w>i.w;}
};
vector<node> v;
bool add(int x,int y)
{
    if(state==0)
    {
        state=1;
        x0=x,y0=y;
        return 1;
    }
    if(state==1)
    {
        if(x!=x0&&y!=y0)
        {
            state=2;
            x1=x,y1=y0;
            x2=x0,y2=y;
            return 1;
        }
        if(y!=y0)
        {
            state=3;
            return 1;
        }
        if(x!=x0)
        {
            state=4;
            return 1;
        }
        return 0;
    }
    if(state==2)
    {
        if(x!=x1&&x!=x2&&y!=y1&&y!=y2)
        {
            state=6;
            return 1;
        }
        if(x!=x1&&y!=y1)
        {
            state=5;
            x0=x2,y0=y2;
            return 1;
        }
        if(x!=x2&&y!=y2)
        {
            state=5;
            x0=x1,y0=y1;
            return 1;
        }
        return 0;
    }
    if(state==3)
    {
        if(x!=x0)
        {
            state=5;
            y0=y;
            return 1;
        }
        return 0;
    }
    if(state==4)
    {
        if(y!=y0)
        {
            state=5;
            x0=x;
            return 1;
        }
        return 0;
    }
    if(state==5)
    {
        if(x!=x0&&y!=y0)
        {
            state=6;
            return 1;
        }
        return 0;
    }
    return 0;
}
void insert(int x,int y,int w)
{
    v.push_back({x,y,w});
    sort(v.begin(),v.end());
    state=0;
    vector<node> tmp;
    for(auto i:v) 
        if(add(i.x,i.y)) tmp.push_back(i);
    v=tmp;
}
int query(int x,int y)
{
    for(auto i:v)
        if(x!=i.x&&y!=i.y) 
        {
            return i.w;
        }
    return 0;
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int q;cin>>q;
    while(q--)
    {
        int op;cin>>op;
        if(op==1)
        {
            int x,y,w;cin>>x>>y>>w;
            x^=last,y^=last,w^=last;
            insert(x,y,w);
        }
        else 
        {
            int x,y;cin>>x>>y;
            x^=last,y^=last;
            last=query(x,y);
            cout<<last<<'\n';
        }
    }
    return 0;
}

G. GCD of Pattern Matching

题解

记 nn 为 PP 中不同的字符个数，则必有 n≤mn\leq m。当 m=2m=2 时，显然首位对应的字符为 11，另一种字符（如果有的话）为 00。

当 m>2m>2 时，我们先随意指定一种映射。我们希望枚举其它的映射方式，求出它们的 gcd⁡\gcd，但可能的映射太多了。可以利用 gcd⁡\gcd 的性质：gcd⁡(x,y)=gcd⁡(x,y−x)(∗)\gcd(x,y)=\gcd(x,y-x)(*)，所以考虑改变量即可。记当前考虑到的所有映射的 gcd⁡\gcd 为 gg。

  • 考虑交换两个字符对应的数字，记它们的权重为 xi,xjx_i,x_j，对应的数字为 yi,yjy_i,y_j，那么就有 g←gcd⁡(g,∣(yi−yj)×(xi−xj)∣)g\leftarrow \gcd(g,|(y_i-y_j)\times(x_i-x_j)|)。对于确定的两个字符，它们所有可能的交换的 gcd⁡\gcd 为 ∣xi−xj∣|x_i-x_j|。所以直接令 g←gcd⁡(g,∣xi−xj∣)g\leftarrow \gcd(g,|x_i-x_j|)。再利用性质 ∗*，只需要对所有的 ii 用 gcd⁡(g,∣xi−xP0∣)\gcd(g,|x_i-x_{P_0}|) 来更新即可。
  • 同时，也可能有空余的数字未被映射，可以将某个字符对应的数字改为它。记该字符的权重为 xix_i，对应的数字为 yiy_i，将它改为 yi′y_i'，那么就有 g←gcd⁡(g,xi×∣yi′−yi∣)g\leftarrow \gcd(g,x_i\times |y_i'-y_i|)。类似地，对所有的 ii 用 gcd⁡(g,xi)\gcd(g,x_i) 来更新即可。

代码

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;
ll mp[26],mp2[26];
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int t;cin>>t;
    while(t--)
    {
        int m;string P;
        cin>>m>>P;
        if(m==2)
        {
            ll ans=0;
            for(auto i:P)
            {
                ans<<=1;
                if(i==P[0]) ans++;
            }
            cout<<ans<<'\n';
        }
        else
        {
            memset(mp,-1,sizeof(mp)),memset(mp2,0,sizeof(mp2));
            int n=(int)P.size(),cnt=0;
            for(int i=0;i<n;i++)
            {
                if(mp[P[i]-'a']==-1) 
                {
                    mp[P[i]-'a']=(cnt<2?1-cnt:cnt);
                    cnt++;
                }
            }
            ll base=1,ans=0;
            for(int i=n-1;i>=0;i--,base*=m)
            {
                mp2[P[i]-'a']+=base;
                ans=ans+mp[P[i]-'a']*base;
            }
            for(int i=0;i<26;i++) 
                if(mp2[i]) ans=__gcd(ans,abs(mp2[i]-mp2[P[0]-'a']));
            if(cnt<m)
            {
                for(int i=0;i<26;i++) ans=__gcd(ans,mp2[i]);
            }
            cout<<ans<<'\n';
        }
    }
    return 0;
}

H. Hurricane

题意

题解

如果直接从每个点出发跑一次单源补图最短路，时间复杂度为 O(n(n+m))O(n(n + m))，不能接受。 观察到对于两个点 uu 和 vv，如果在补图上满足 degu+degv<ndeg_u + deg_v < n，那么一定有 dis(u,v)≤2dis(u, v) ≤ 2， 这是因为原图中存在至少一个点与 uu 和 vv 均相连。考虑从所有满足 2degu≥n2deg_u ≥ n 的 uu 出发跑一次 单源补图最短路，这样的 uu 只有 O(mn)≤O(m)O( m n ) ≤ O( \sqrt{m}) 个，其余所有点对之间的最短路长度都不超过 22，并且当且仅当两个点之间在补图有边直接相连时，两点之间的最短路长度为 22。

（补图最短路可能需要一个快一点的写法。）

代码

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
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e5+5;
int n,m,d[N],deg[N];
ll ans[N];
vector<int> g[N];
bool flag[N];
void bfs(int s)
{
    vector<int> res,tmp;
    for(int i=1;i<=n;i++) 
        if(i!=s) res.push_back(i);
    queue<int> q;
    d[s]=0;
    q.push(s);
    while(!q.empty())
    {
        int u=q.front();q.pop();
        for(auto i:res) flag[i]=0;
        for(auto i:g[u]) flag[i]=1;
        for(auto v:res)
            if(!flag[v])
            {
                d[v]=d[u]+1;
                if(v>s||deg[v]*2<n) ans[d[v]]++;
                q.push(v);
            }
            else tmp.push_back(v);
        res=tmp;
        tmp.clear();
    }
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin>>n>>m;
    for(int i=1;i<=m;i++)
    {
        int u,v;cin>>u>>v;
        deg[u]++,deg[v]++;
        g[u].push_back(v),g[v].push_back(u);
    }
    int cnt=0,cnt2=0;
    for(int i=1;i<=n;i++)
        if(deg[i]*2>=n) bfs(i);
        else 
        {
            cnt++;
            for(auto v:g[i])
                if(deg[v]*2<n&&v>i) cnt2++;
        }
    ans[1]+=1ll*cnt*(cnt-1)/2-cnt2;
    ans[2]+=cnt2;
    for(int i=1;i<n;i++) cout<<ans[i]<<" \n"[i==n-1];
    return 0;
}

J. Find the Gap

题解

对于一般情况，在最优情况下两个平面要么分别卡住两个点，要么一个卡住一个点、另一 个卡住三个点。预处理出 $O(n^2) $个点对之间的向量，然后枚举两个非共线的向量 A⃗,B⃗\vec{A},\vec{B}，叉乘得到平面的法向量 C⃗\vec{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
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
#include <bits/stdc++.h>
using namespace std;
double eps=1e-10;
double inf=1e18;
#define zero(x) (((x)>0?(x):-(x))<eps)
struct Point
{
    double x,y,z;
}p[55];
vector<Point> line;
bool operator<(Point a,Point b)
{
    if(!zero(a.x-b.x)) return a.x<b.x;
    if(!zero(a.y-b.y)) return a.y<b.y;
    return a.z<b.z;
}
Point operator*(Point a,double k) {return {a.x*k,a.y*k,a.z*k};}
Point operator/(Point a,double k) {return {a.x/k,a.y/k,a.z/k};}
Point operator-(Point a,Point b) {return {a.x-b.x,a.y-b.y,a.z-b.z};}
double len(Point a)
{
    return sqrt(a.x*a.x+a.y*a.y+a.z*a.z);
}
double dot(Point a,Point b)
{
    return a.x*b.x+a.y*b.y+a.z*b.z;
}
// a在b上的投影
Point proj(Point a,Point b)
{
    return b*dot(a,b);
}
Point cross(Point a,Point b)
{
    Point c;
    c.x=a.y*b.z-a.z*b.y;
    c.y=a.z*b.x-a.x*b.z;
    c.z=a.x*b.y-a.y*b.x;
    return c;
} 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;cin>>n;
    for(int i=1;i<=n;i++) cin>>p[i].x>>p[i].y>>p[i].z;
    for(int i=1;i<=n;i++)
        for(int j=i+1;j<=n;j++)
            line.push_back(p[i]-p[j]);
    double ans=inf;
    for(int i=0;i<(int)line.size();i++)
        for(int j=0;j<(int)line.size();j++)
            {
                Point v1=line[i],v2=line[j];
                if(zero(len(cross(v1,v2)))) continue;
                Point v=cross(v1,v2);
                v=v/len(v);
                Point mx={-inf,-inf,-inf},mn={inf,inf,inf};
                for(int i5=1;i5<=n;i5++)
                {
                    Point tmp=proj(p[i5],v);
                    if(tmp<mn) mn=tmp;
                    if(mx<tmp) mx=tmp;
                }
                ans=min(ans,len(mx-mn));
            }
    if(ans==inf) ans=0;
    cout<<fixed<<setprecision(12)<<ans<<'\n';
    return 0;
}
ACM
#dp #哈希 #计算几何 #2023CCPC #三分 #gcd #补图最短路
The 2023 CCPC Online Contest
https://je3ter.github.io/2023/10/10/ACM/The 2023 CCPC Online Contest/
作者
Je3ter
发布于
2023年10月10日
许可协议