Hile_Meow's Blog

2017CCPC女生赛

2021-10-15 分类 个人训练 作者 Hile_Meow ~13.16K 字

最近组队赛有点拉跨，于是个人vp加训，写写题解。

A - Automatic Judge

签到，模拟。

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
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 2e5+7;
const int MOD = 1e9+7;
int n,m;
int main(){
    int T=1;
    scanf("%d",&T);
    while(T--){
        scanf("%d%d",&n,&m);
        vector<pair<int,int>> ve[22];
        for(int i=1,a,b,c;i<=m;i++){
            char d[22];
            scanf("%d %d:%d %s",&a,&b,&c,d);
            int t=b*60+c;
            if(d[0]=='A'&&d[1]=='C'){
                ve[a-1000].push_back({t,1});
            }else {
                ve[a-1000].push_back({t,0});
            }
        }
        int ans=0,cnt=0;
        for(int i=1;i<=n;i++){
            int s=0;
            sort(ve[i].begin(),ve[i].end());
            for(auto j:ve[i]){
                if(j.second){
                    cnt++;
                    ans+=s+j.first;
                    break;
                }else{
                    s+=20;
                }
            }
        }
        printf("%d %d\n",cnt,ans);
    }
}

B - Building Shops

dp。先对每个pair按照位置排序，$f[i][j]$为考虑前$i$个点，上一次选在$j$时的答案，则有

$f[i][j]=min(f[i][j],f[i-1][j]+x[i]-x[j])(i!=j)$

$f[i][j]=min(f[i][j],f[i-1][j]+c[i])(i==j)$

最终答案为$max(\{f[n][1…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
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 3000+7;
const int MOD = 1e9+7;
int n,x[N],c[N];
ll f[N][N];
pair<int,int> p[N];
ll solve(){
    sort(p+1,p+1+n);
    memset(f,0x3f,sizeof f);
    f[1][1]=p[1].second;
    for(int i=2;i<=n;i++){
        for(int j=1;j<i;j++){
            f[i][j]=min(f[i][j],f[i-1][j]+p[i].first-p[j].first);
            f[i][i]=min(f[i][i],f[i-1][j]+p[i].second);
        }
    }
    return *min_element(f[n]+1,f[n]+1+n);
}
int main(){
    int T=1;
    while(~scanf("%d",&n)){
        for(int i=1;i<=n;i++){
            scanf("%d%d",x+i,c+i);
            p[i]={x[i],c[i]};
        }
        printf("%lld\n",solve());
    }
}

C - Coprime Sequence

签到，处理出前后缀$\gcd$然后枚举删的位置。

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
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 100000+7;
const int MOD = 1e9+7;
int n,a[N];
int l[N],r[N];
int main(){
    int T=1;
    scanf("%d",&T);
    while(T--){
        scanf("%d",&n);
        for(int i=1;i<=n;i++){
            scanf("%d",a+i);
        }
        for(int i=1;i<=n;i++){
            l[i]=__gcd(l[i-1],a[i]);
        }
        r[n+1]=0;
        for(int i=n;i>=1;i--){
            r[i]=__gcd(r[i+1],a[i]);
        }
        int ans=max(r[2],l[n-1]);
        for(int i=2;i<n;i++){
            ans=max(ans,__gcd(l[i-1],r[i+1]));
        }
        printf("%d\n",ans);
    }
}

D - Deleting Edges

图论。考虑最终形成的是一棵以0为根的生成树，可以枚举最后形成的树中每个点连向父亲的那条边，对每个结点来说，删边方案是相互独立的（因为树上每个点的父亲唯一），乘起来就是最终答案。

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
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 50+7;
const int MOD = 1e9+7;
int n,a[N][N],b[N][N];
int main(){
    int T=1;
    while(~scanf("%d",&n)){
        for(int i=0;i<n;i++){
            for(int j=0;j<n;j++){
                scanf("%1d",&a[i][j]);
                b[i][j]=a[i][j];
                if(!b[i][j])b[i][j]=0x3f3f3f3f;
                if(i==j)b[i][j]=0;
            }
        }
        for(int k=0;k<n;k++)
        for(int i=0;i<n;i++){
            for(int j=0;j<n;j++){
                if(b[i][k]&&b[k][j]){
                    b[i][j]=min(b[i][j],b[i][k]+b[k][j]);
                }
            }
        }
        ll ans=1;
        for(int i=1;i<n;i++){
            ll res=0;
            for(int j=0;j<n;j++){
                if(a[j][i]&&b[0][j]+a[j][i]==b[0][i]){
                    res++;
                }
            }
            ans=ans*res%MOD;
        }
        printf("%lld\n",ans);
    }
}

E - Easy Summation

签到，怎么做都行。

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
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 10000+7;
const int MOD = 1e9+7;
int n,m;
ll ans[6][N];
ll qpow(ll a,ll n=MOD-2,ll m=MOD){
    ll res=1;
    a%=m;
    while(n){
        if(n&1)res=res*a%m;
        a=a*a%m,n>>=1;
    }
    return res;
}
int main(){
    for(int i=0;i<=5;i++){
        for(int j=1;j<N;j++){
            ans[i][j]=(ans[i][j-1]+qpow(j,i))%MOD;
        }
    }
    int T=1;
    scanf("%d",&T);
    while(T--){
        scanf("%d%d",&n,&m);
        printf("%lld\n",ans[m][n]);
    }
}

F - Forgiveness

赛中没过，待补。感觉是个$O(10\times n\times\sqrt{n}\times\log{n})$的分块（应该没有$\log{n}$？）。

（后记：Claris出的防AK，据说要bitset搞搞）

G - Graph Theory

图论。考虑每个1和前面的2匹配，剩下的1两两匹配，剩下2或者n为奇数就是No。

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
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 100000+7;
const int MOD = 1e9+7;
int n,a[N];
int main(){
    int T=1;
    scanf("%d",&T);
    while(T--){
        scanf("%d",&n);
        int cnt=1;
        a[1]=2;
        for(int i=2;i<=n;i++){
            scanf("%d",a+i);
            if(a[i]==1){
                if(cnt>0)cnt--;
            }else{
                cnt++;
            }
        }
        puts((cnt==0&&n%2==0)?"Yes":"No");
    }
}

H - Happy Necklace

打表，数学。题意等价求长为n且两个0的距离大于2的01串的方案数，赛中人工打了个表(2,3,4,6,9,13)，发现是$f[n]=f[n-1]+f[n-3]$，矩阵快速幂即可。

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
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 100000+7;
const int MOD = 1e9+7;
const int K=3+7;
struct mat{
    int a[K][K];
    mat(){memset(a,0,sizeof a);}
    int* operator [] (int i){return a[i];}
    mat operator * (mat b){
        mat res;
        for(int i=0;i<3;i++){
            for(int j=0;j<3;j++){
                for(int k=0;k<3;k++){
                    (res[i][j]+=1LL*a[i][k]*b[k][j]%MOD)%=MOD;
                }
            }
        }
        return res;
    }
};
mat qpow(mat a,ll n){
    mat res;
    for(int i=0;i<3;i++){
        res.a[i][i]=1;
    }
    while(n){
        if(n&1)res=res*a;
        a=a*a,n>>=1;
    }
    return res;
}
ll n;
int main(){
    int T=1;
    scanf("%d",&T);
    while(T--){
        scanf("%lld",&n);
        ll ans=0;
        mat A,B;
        A[0][0]=1;
        A[0][1]=2;
        A[0][2]=3;
        B[2][1]=B[0][2]=B[1][0]=B[2][2]=1;
        A=A*qpow(B,n-2);
        printf("%d\n",A[0][2]);
    }
}

I - Innumerable Ancestors

树论。结论：$k$个点中LCA深度最大的两点dfs序一定相邻（考虑反证法），所以对集合A,B按照dfs序排序并双指针处理。

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
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 100000+7;
const int MOD = 1e9+7;
int n,m,k1,k2,dfn[N],tot,a[N],b[N];
int dep[N],fa[N][20];
vector<int> G[N];
void dfs(int u,int pre=0){
    dep[u]=dep[pre]+1;
    fa[u][0]=pre;
    dfn[u]=++tot;
    for(int v:G[u])
        if(v!=pre)
            dfs(v,u);
}
void init(int n){
    for(int i=1;(1<<i)<=n;i++)
        for(int j=1;j<=n;j++)
            fa[j][i]=fa[fa[j][i-1]][i-1];
}
int lca(int u,int v){
    if(dep[u]<dep[v])swap(u,v);
    int d=dep[u]-dep[v];
    for(int i=0;(1<<i)<=d;i++)
        if(d&(1<<i))u=fa[u][i];
    if(u==v)return u;
    for(int i=17;i>=0;i--)
        if(fa[u][i]!=fa[v][i])u=fa[u][i],v=fa[v][i];
    return fa[u][0];
}
bool cmp(int a,int b){
    return dfn[a]<dfn[b];
}
int main(){
    int T=1;
    while(~scanf("%d%d",&n,&m)){
        tot=0;
        for(int i=1;i<=n;i++){
            G[i].clear();
        }
        memset(dep,0,sizeof dep);
        memset(fa,0,sizeof fa);
        memset(dfn,0,sizeof dfn);
        for(int i=1,u,v;i<n;i++){
            scanf("%d%d",&u,&v);
            G[u].push_back(v);
            G[v].push_back(u);
        }
        dfs(1);
        init(n);
        while(m--){
            scanf("%d",&k1);
            for(int i=1;i<=k1;i++){
                scanf("%d",a+i);
            }
            scanf("%d",&k2);
            for(int i=1;i<=k2;i++){
                scanf("%d",b+i);
            }
            sort(a+1,a+1+k1,cmp);
            sort(b+1,b+1+k2,cmp);
            int p=1,ans=0;
            for(int q=1;q<=k2;q++){
                while(p+1<=k1&&dfn[a[p+1]]<=dfn[b[q]]){
                    p++;
                }
                ans=max(ans,dep[lca(a[p],b[q])]);
            }
            p=1;
            for(int q=1;q<=k2;q++){
                while(p+1<=k1&&dfn[a[p]]<=dfn[b[q]]){
                    p++;
                }
                ans=max(ans,dep[lca(a[p],b[q])]);
            }

            printf("%d\n",ans);
        }
    }
}

J - Judicious Strategy

博弈，打表。直接$O(n^3\log n)$预处理出所有子串及其权值，然后打表，记录一个$(win,A,B)$的三元组表示胜负状态和玩家分数，注意一个字符串中的同一个子串只算出现一次（如”aaaa”中，”aa”的出现次数为1）。

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
97
98
99
100
101
102
103
104
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 30+7;
const int MOD = 1e9+7;
const int INF = 0x3f3f3f3f;
int n;
map<string,int> mp,w;
struct node{
    int win,S[2];
};
map<string,node> f;
int getW(string s){
    int sum=0,mx=0;
    for(int i=0;i<s.size();i++){
        mx=max(mx,s[i]-'a'+1);
        sum+=s[i]-'a'+1;
    }
    return sum*mx+mp[s];
}
node dfs(string s,int p){
    int q=1^p;
    if(f.count(s))return f[s];
    node res;
    res.win=0;
    res.S[p]=-INF;
    res.S[q]=INF;
    for(int i=0;i<26;i++){
        string tt;
        tt.push_back(char(i+'a'));
        string t=tt+s;
        if(mp.count(t)){
            node tmp=dfs(t,q);
            if(tmp.win==0){
                if(tmp.S[p]==res.S[p]&&tmp.S[q]<res.S[q]||tmp.S[p]>res.S[p]){
                    res=tmp;
                }
                res.win=1;
            }else if(res.win==0){
                if(tmp.S[p]==res.S[p]&&tmp.S[q]<res.S[q]||tmp.S[p]>res.S[p]){
                    res=tmp;
                }
                res.win=0;
            }
        }
        t=s+tt;
        if(mp.count(t)){
            node tmp=dfs(t,q);
            if(tmp.win==0){
                if(tmp.S[p]==res.S[p]&&tmp.S[q]<res.S[q]||tmp.S[p]>res.S[p]){
                    res=tmp;
                }
                res.win=1;
            }else if(res.win==0){
                if(tmp.S[p]==res.S[p]&&tmp.S[q]<res.S[q]||tmp.S[p]>res.S[p]){
                    res=tmp;
                }
                res.win=0;
            }
        }
    }
    if(res.win==0&&res.S[p]==-INF){
        res.S[0]=res.S[1]=0;
    }
    res.S[q]+=w[s];
    return f[s]=res;
}
string s[N];
void solve(){
    mp.clear();
    w.clear();
    f.clear();
    for(int i=1;i<=n;i++){
        set<string> se;
        for(int j=0;j<s[i].size();j++){
            string tmp;
            for(int k=j;k<s[i].size();k++){
                tmp.push_back(s[i][k]);
                se.insert(tmp);
            }
        }
        for(auto j:se){
            mp[j]++;
        }
    }
    for(auto i:mp){
        w[i.first]=getW(i.first);
    }
    string emp;
    node res=dfs(emp,0);
    if(res.win==0){
        cout<<"Bob\n";
    }else cout<<"Alice\n";
    cout<<res.S[0]<<" "<<res.S[1]<<"\n";
}
int main(){
    ios::sync_with_stdio(false);
    while(cin>>n){
        for(int i=1;i<=n;i++){
            cin>>s[i];
        }
        solve();
    }
}
本作品采用 知识共享署名-相同方式共享 4.0 国际许可协议 进行许可
最后编辑：2021-10-16