CF699 - LeAf146

1
signed main(){
2
    int n;cin>>n;
3
    string s;cin>>s;
4
    vector<int> p(n);
5
    for(int i=0;i<n;i++)cin>>p[i];
6
    int ans=0x7fffffff;
7
    for(int i=1;i<n;i++){
8
        if(s[i]=='L'&&s[i-1]=='R')ans=min((p[i]-p[i-1])/2,ans);
9
    }
10
    if(ans==0x7fffffff)cout<<"-1\n";
11
    else cout<<ans<<endl;
12
    return 0;
13
}

B. One Bomb #

大小为 $n \times m$ 的矩阵，矩阵中有若干点位有障碍物。炸弹可以清除所在行列的所有障碍物。问是否有一位置可以放置一个炸弹后清除所有障碍物。

记录每行每列的障碍物数量 hang[n] lie[m]，以及总数量 tot。对于一位置 $(i,j)$ ，若当前位置有障碍物，则当 hang[i]+lie[j]==tot+1 时，该位置即为答案；若没有障碍物，则当 hang[i]+lie[j]==tot 时，该位置即为答案。若不存在位置，即无正确答案。

1
signed main(){
2
    int n,m;cin>>n>>m;
3
    int tot=0;
4
    vector<string> g(n);
5
    vector<int> hang(n),lie(m);
6
    for(int i=0;i<n;i++){
7
        cin>>g[i];
8
        string s=g[i];
9
        for(int j=0;j<m;j++){
10
            if(s[j]=='*'){
11
                hang[i]++;
12
                lie[j]++;
13
                tot++;
14
            }
15
        }
16
    }
17
    for(int i=0;i<n;i++){
18
        for(int j=0;j<m;j++){
19
            if(g[i][j]=='*'){
20
                if(hang[i]+lie[j]-1==tot){
21
                    cout<<"YES\n"<<i+1<<' '<<j+1<<endl;
22
                    return 0;
23
                }
24
            }else{
25
                if(hang[i]+lie[j]==tot){
26
                    cout<<"YES\n"<<i+1<<' '<<j+1<<endl;
27
                    return 0;
28
                }
29
            }
30
        }
31
    }
32
    cout<<"NO\n";
33
    return 0;
34
}

C. Vacations #

共 $n$ 天，每天有健身房是否开门，是否有比赛，组合共四种状态。若不参加比赛且不去健身房则为休息，求休息的最少天数。

反方向思考，休息的最少天数即为总天数减去工作的最多天数。有 dp[i][j] 为第 i 天参与活动 j 的最多工作天数，当 j 分别为 0, 1, 2 时，对应休息，健身，比赛。具体状态转移见代码。

1
signed main(){
2
    int n;cin>>n;
3
    vector<int> a(n);
4
    vector<vector<int>> dp(n,vector<int>(3));
5
    for(int i=0;i<n;i++)cin>>a[i];
6
    dp[0][0]=0;
7
    dp[0][1]=(a[0]==1||a[0]==3?1:0);
8
    dp[0][2]=(a[0]==2||a[0]==3?1:0);
9
    for(int i=1;i<n;i++){
10
        dp[i][0]=max(dp[i-1][0],max(dp[i-1][1],dp[i-1][2]));
11
        dp[i][1]=(a[i]==1||a[i]==3?max(dp[i-1][0],dp[i-1][2])+1:dp[i][0]);
12
        dp[i][2]=(a[i]==2||a[i]==3?max(dp[i-1][0],dp[i-1][1])+1:dp[i][0]);
13
    }
14
    if(a[n-1]==3)cout<<n-max(dp[n-1][0],max(dp[n-1][1],dp[n-1][2]));
15
    else if(a[n-1]==2)cout<<n-max(dp[n-1][0],dp[n-1][2]);
16
    else if(a[n-1]==1)cout<<n-max(dp[n-1][0],dp[n-1][1]);
17
    else cout<<n-dp[n-1][0];
18
    return 0;
19
}