2021 CCPC 女生赛

发表于 更新于 分类于
Solved A B C D E F G H I J K
7/11 Ø Ø Ø Ø - - Ø - Ø - Ø

题目链接

https://codeforces.com/gym/103389

Problem A. 公交线路

题意：

思路：

代码：

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
#include <bits/stdc++.h>
#define SZ(x) (int)(x).size()
#define ALL(x) (x).begin(),(x).end()
#define PB push_back
#define EB emplace_back
#define MP make_pair
#define FI first
#define SE second
using namespace std;
typedef double DB;
typedef long double LD;
typedef long long LL;
typedef unsigned long long ULL;
typedef pair<int,int> PII;
typedef vector<int> VI;
typedef vector<LL> VLL;
typedef vector<PII> VPII;
// head
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n,x,y;cin>>n>>x>>y;
    VI a(n+1);
    for(int i=1;i<=n;i++) cin>>a[i];
    int m;cin>>m;
    VI b(m+1);
    for(int i=1;i<=m;i++) cin>>b[i];
    bool l=false,r=false;
    if(x-m<1) l=true;
    else for(int i=1;i<=m;i++) if(a[x-i]!=b[i]) {
        l=true;
        break;
    }
    if(x+m>n) r=true;
    else for(int i=1;i<=m;i++) if(a[x+i]!=b[i]) {
        r=true;
        break;
    }
    if(!l&&!r) cout<<"Unsure\n";
    else if(x<y) cout<<(!r?"Right":"Wrong")<<'\n';
    else if(x>y) cout<<(!l?"Right":"Wrong")<<'\n';
    return 0;
}

Problem B. 攻防演练

题意：

长度为 $n$ 的字符串 $s$，字符集为前 $m$ 个小写字母，$q$ 次询问，每次询问一个区间，求该区间内子序列无法构成的该字符集最短字符串的长度。

$1\le n,q \le 2e5$。

思路：

记 $nxt_{i,j}$ 为 $s_i$ 后第 $j$ 个字符的最近位置。

原问题可转化为：从 $l-1$ 开始沿着 $nxt$ 往后跳要跳多少步才能跳到 $>r$ 的位置，倍增解决。

代码：

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>
#define SZ(x) (int)(x).size()
#define ALL(x) (x).begin(),(x).end()
#define PB push_back
#define EB emplace_back
#define MP make_pair
#define FI first
#define SE second
using namespace std;
typedef double DB;
typedef long double LD;
typedef long long LL;
typedef unsigned long long ULL;
typedef pair<int,int> PII;
typedef vector<int> VI;
typedef vector<LL> VLL;
typedef vector<PII> VPII;
// head
const int N=2e5+5;
int nxt[N][26],pos[26],f[N][20];
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n,m;cin>>m>>n;
    string s;cin>>s;
    fill(pos,pos+26,n+1);
    for(int i=0;i<=18;i++) f[n+1][i]=n+1;
    for(int i=n-1;~i;i--) {
        for(int j=0;j<m;j++) {
            f[i+1][0]=max(f[i+1][0],pos[j]);
        }
        pos[s[i]-'a']=i+1;
    }
    for(int i=0;i<m;i++) f[0][0]=max(f[0][0],pos[i]);
    for(int i=n;~i;i--) {
        for(int j=1;j<=18;j++) {
            f[i][j]=max(f[i][j],f[f[i][j-1]][j-1]);
        }
    }
    int q;cin>>q;
    while(q--) {
        int l,r;cin>>l>>r;
        int res=0;
        --l;
        for(int i=18;~i;i--) if(f[l][i]<=r) {
            l=f[l][i];
            res|=1<<i;
        }
        cout<<res+1<<'\n';
    }
    return 0;
}

Problem C. 连锁商店

题意：

一共有 $n$ 个景点，按照海拔高度从低到高依次编号为 $1 \sim n$。

搭建了 $m$ 条缆车路线。每条缆车路线只可能把游客们从某个海拔较低的景点运送到另一个海拔较高的景点。

在每个景点都有一家纪念品连锁商店，其中第 $i$ 个景点的商店隶属第 $c_i$ 号公司，两家连锁店 $(i,j)$ 隶属同一公司当且仅当 $c_i=c_j$。

每家公司都有新客优惠活动，其中第 $i$ 家公司对于新客的优惠红包为 $w_i$ 元，一旦领取了隶属该公司的某家连锁店的一份红包，就不能再领取该公司所有分店的红包。

你正在 $1$ 号景点，你将会搭乘缆车去往各个景点，每到一个景点，你都可以领取该景点的连锁商店的新客优惠红包（包括 $1$ 号景点）。当然，同一家公司的红包最多只能领一次。

对于每个可能的终点 $k$，找到一条从 $1$ 号景点出发到达 $k$ 号景点的游览路线，使得可以领取到总金额最多的优惠红包。

思路：

如果某家公司开的连锁店数量不超过 $1$，那么可以无视 “每家公司的红包只能领一份” 这个限制，这是因为任何一条路线都无法访问多次该公司开的商店。

如果某家公司开的连锁店数量至少为 $2$，那么这样的公司数最多为 $\frac n 2 \le 18$。

由于第二类公司数量并不多，因此可以使用状压 DP 来求解这个问题。

设 $dp_{i,S}$ 表示从 $1$ 出发到达了 $i$ 点，一路上访问过的第二类公司集合为 $S$ 时，访问过的红包总价值最大是多少，枚举下一个景点进行转移。

时间复杂度 $O(n^22^\frac n 2)$。

代码：

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
#include <bits/stdc++.h>
#define SZ(x) (int)(x).size()
#define ALL(x) (x).begin(),(x).end()
#define PB push_back
#define EB emplace_back
#define MP make_pair
#define FI first
#define SE second
using namespace std;
typedef double DB;
typedef long double LD;
typedef long long LL;
typedef unsigned long long ULL;
typedef pair<int,int> PII;
typedef vector<int> VI;
typedef vector<LL> VLL;
typedef vector<PII> VPII;
// head
const int N=40;
int c[N],w[N],b[N],dp[N][1<<20],cnt[N];
VI g[N];
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n,m;cin>>n>>m;
    VI a;
    for(int i=1;i<=n;i++) {
        cin>>c[i];
        ++cnt[c[i]];
        if(cnt[c[i]]==2) {
            a.PB(c[i]);
            b[c[i]]=SZ(a)-1;
        }
    }
    for(int i=1;i<=n;i++) {
        cin>>w[i];
    }
    for(int i=1;i<=m;i++) {
        int u,v;cin>>u>>v;
        g[u].PB(v);
    }
    memset(dp,0xc0,sizeof dp);
    if(cnt[c[1]]==1) dp[1][0]=w[c[1]];
    else dp[1][1<<b[c[1]]]=w[c[1]];
    for(int u=1;u<n;u++) {
        for(int i=0;i<1<<SZ(a);i++) if(dp[u][i]>0) {
            for(auto v:g[u]) {
                if(cnt[c[v]]==1) dp[v][i]=max(dp[v][i],dp[u][i]+w[c[v]]);
                else {
                    if(i&(1<<b[c[v]])) dp[v][i]=max(dp[v][i],dp[u][i]);
                    else dp[v][i|(1<<b[c[v]])]=max(dp[v][i|(1<<b[c[v]])],dp[u][i]+w[c[v]]);
                }
            }
        }
    }
    for(int i=1;i<=n;i++) {
        int mx=0;
        for(int j=0;j<1<<SZ(a);j++) {
            mx=max(mx,dp[i][j]);
        }
        cout<<mx<<'\n';
    }
    return 0;
}

Problem D. 修建道路

题意：

添加 $n−1$ 条无向边使 $n$ 个点连通，点 $i$ 与点 $j$ $(j>i)$ 相连，那么需要 $\max_{i \le k \le j}{a_k}$ 的费用。

求最小费用。

思路：

点 $i$ 与点 $j$ $(j>i)$ 相连，需要 $\max_{i \le k \le j}{a_k}$ 的费用。

显然 $j-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
#include <bits/stdc++.h>
#define SZ(x) (int)(x).size()
#define ALL(x) (x).begin(),(x).end()
#define PB push_back
#define EB emplace_back
#define MP make_pair
#define FI first
#define SE second
using namespace std;
typedef double DB;
typedef long double LD;
typedef long long LL;
typedef unsigned long long ULL;
typedef pair<int,int> PII;
typedef vector<int> VI;
typedef vector<LL> VLL;
typedef vector<PII> VPII;
// head
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;cin>>n;
    VI a(n+1);
    for(int i=1;i<=n;i++) cin>>a[i];
    LL res=0;
    for(int i=2;i<=n;i++) {
        if(a[i]>a[i-1]) res+=a[i];
        else res+=a[i-1];
    }
    cout<<res<<'\n';
    return 0;
}

Problem G. 3G网络

题意：

思路：

代码：

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
#include <bits/stdc++.h>
#define SZ(x) (int)(x).size()
#define ALL(x) (x).begin(),(x).end()
#define PB push_back
#define EB emplace_back
#define MP make_pair
#define FI first
#define SE second
using namespace std;
typedef double DB;
typedef long double LD;
typedef long long LL;
typedef unsigned long long ULL;
typedef pair<int,int> PII;
typedef vector<int> VI;
typedef vector<LL> VLL;
typedef vector<PII> VPII;
// head
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;cin>>n;
    for(int i=1;i<=n;i++) {
        int x,y;cin>>x>>y;
    }
    cout<<fixed<<setprecision(15)<<1.0/n<<'\n';
    return 0;
}

Problem 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
53
54
55
56
57
58
59
#include <bits/stdc++.h>
#define SZ(x) (int)(x).size()
#define ALL(x) (x).begin(),(x).end()
#define PB push_back
#define EB emplace_back
#define MP make_pair
#define FI first
#define SE second
using namespace std;
typedef double DB;
typedef long double LD;
typedef long long LL;
typedef unsigned long long ULL;
typedef pair<int,int> PII;
typedef vector<int> VI;
typedef vector<LL> VLL;
typedef vector<PII> VPII;
// head
const int N=55;
const int DIR[8][2]={-1,0,-1,1,0,1,1,1,1,0,1,-1,0,-1,-1,-1};
char s[N][N];
int n,m;
bool valid1(int x,int y) {
    if(x>=1&&x<=n&&y>=1&&y<=m&&s[x][y]!='#') return true;
    return false;
}
bool valid2(int x,int y,int t) {
    if(s[x+DIR[t][0]][y]=='#'&&s[x][y+DIR[t][1]]=='#') return false;
    return true;
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin>>n>>m;
    int x,y;
    for(int i=1;i<=n;i++) {
        cin>>s[i]+1;
        for(int j=1;j<=m;j++) if(s[i][j]=='*') {
            x=i,y=j;
        }
    }
    int o;cin>>o;
    for(int i=1,v=0,now=0;i<=o;i++) {
        char c;cin>>c;
        if(c=='U') ++v;
        else if(c=='D') v=max(0,v-1);
        else if(c=='L') now=(now+7)%8;
        else now=(now+1)%8;
        bool f=false;
        for(int j=0;j<v;j++) {
            int tx=x+DIR[now][0],ty=y+DIR[now][1];
            if(valid1(tx,ty)&&(now&1?valid2(x,y,now):1)) x=tx,y=ty;
            else {v=0;f=true;break;}
        }
        if(f) cout<<"Crash! ";
        cout<<x<<' '<<y<<'\n';
    }
    return 0;
}

Problem K. 音乐游戏

题意：

思路：

代码：

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>
#define SZ(x) (int)(x).size()
#define ALL(x) (x).begin(),(x).end()
#define PB push_back
#define EB emplace_back
#define MP make_pair
#define FI first
#define SE second
using namespace std;
typedef double DB;
typedef long double LD;
typedef long long LL;
typedef unsigned long long ULL;
typedef pair<int,int> PII;
typedef vector<int> VI;
typedef vector<LL> VLL;
typedef vector<PII> VPII;
// head
int main() {
    int n;cin>>n;
    int res=0;
    getchar();
    for(int i=1;i<=n;i++) {
        string s;getline(cin,s);
        for(auto c:s) if(c=='-') ++res;
    }
    cout<<res<<'\n';
    return 0;
}