Acwing——第88场周赛

题目链接

4800. 下一个
4801. 强连通图
4802. 金明的假期

题目描述

4800. 下一个

给定一个整数 $x$，请你找到严格大于 $x$ 且各位数字均不相同的最小整数 $y$。

输入格式

一个整数 x。

输出格式

一个整数 y 。保证一定有解。

数据范围

• $1000\le x\le 9000$

输入样例1：

1987

输出样例1：

2013

输入样例2：

2013

输出样例2：

2014

代码：

#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;

int x;

int cnt[10];


bool check(string s){
    int n = s.size();
    //每次都需要重置cnt数组
    memset(cnt,0,sizeof cnt);
    
    for(int i = 0;i < n;i++){
        //如果出现重复数字 说明不符合要求
        if(++cnt[s[i] - '0'] == 2) return false;
    }
    return true;
}

int main(){
    scanf("%d",&x);
    x++;
    
    int ans = 0;
    while(true){
        if(check(to_string(x))){
            ans = x;
            break;
        }
        x++;
    }
    cout<<ans<<endl;
    return 0;
}

4801. 强连通图

给定一个平面。

平面中有 $n$ 条与 $x$ 轴平行的有向边，从上到下依次编号为 $1\sim n$ ，每条边都无限长，且两两不重合。

平面中有 $m$ 条与 $y$ 轴平行的有向边，从左到右依次编号为 $1\sim m$，每条边都无限长，且两两不重合。

这些边一共有 $n\times m$ 个交点。

给定每条边的具体方向，请你判断这 $n\times m$ 个交点是否满足：从任意交点出发可以到达任意其它交点。

输入格式

第一行包含两个整数 $n,m$。

第二行包含一个长度为 $n$，由 <和 >构成的字符串，其中第 i 个字符用来表示第 i 条与 x 轴平行的有向边的方向，如果为 <表示方向从右向左，如果为 >表示方向从左向右。

第三行包含一个长度为 $m$，由 ^和 v构成的字符串，其中第 i 个字符用来表示第 i 条与 y 轴平行的有向边的方向，如果为 ^表示方向从下向上，如果为 v表示方向从上向下。

输出格式

如果所有交点满足题目要求，则输出 YES，否则输出 NO。

数据范围

• $2\le n,m\le 20$

输入样例1：

3 3
<>
v^v

输出样例1：

NO

输入样例2：

4 6
<><>
v^vv^

输出样例2：

YES

分析：

这里直接给出结论：如果四个角的符号能够形成一个闭环，无论中间是怎么样的，其中任意一点都可以到达其他任意的点，反之则不行。

这里的闭环指的是下面的两种情况，并且只有这两种情况合法。

第一种情况：

 >    v
 ^     < 

第二种情况：

 <    ^
 v     >

时间复杂度： $O(1)$

代码：

#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;

int main(){
    int n,m;
    cin>>n>>m;
    string s,t;
    cin>>s>>t;
    //只有这两种情况符合要求
    if((s[0] == '>' && s[n - 1] == '<' && t[0] == '^' && t[m-1] == 'v') ||
        (s[0] == '<' && s[n - 1] == '>' && t[0] == 'v' && t[m-1] == '^')){
        puts("YES");
        return 0;
    }

    puts("NO");
    return 0;
}

4802. 金明的假期

金明有 n天假期，编号 $1\sim n$。

整个假期期间，他每天只可能有三种选择：

• 去健身房健身一整天。（前提是当天健身房开放）
• 去图书馆看书一整天。（前提是当天图书馆开放）
• 在家休息一整天。

用一个长度为 $n$ 的整数数组 $a_1,a_2,\dots ,a_n$ 来表示这 n天健身房与图书馆的开放情况，其中：

• $a_i$ 等于 0 表示第 i 天健身房关闭且图书馆关闭。
• $a_i$ 等于 1 表示第 i 天健身房关闭但图书馆开放。
• $a_i$ 等于 2 表示第 i 天健身房开放但图书馆关闭。
• $a_i$ 等于 3 表示第 i 天健身房开放且图书馆开放。

金明希望自己用来休息的天数尽可能少，但是，他一定不会 连续两天(或更多天) 去健身房健身，也一定不会连续两天（或更多天) 去图书馆看书。

请你计算，金明用来休息的最少可能天数。

输入格式

第一行包含一个整数 n。

第二行包含n个整数 $a_1,a_2,\dots ,a_n$。

输出格式

一个整数，表示金明用来休息的最少可能天数。

数据范围

• $1\le n\le 100,0\le a_i\le 3$

输入样例1：

4
1 3 2 0

输出样例1：

2

输入样例2：

7
1 3 3 2 1 2 3

输出样例2：

0

输入样例3：

2
2 2

输出样例3：

1

分析：

本题用 动态规划 求解。

我们定义 $f(i,j)$ 即第 $i$ 天 去做事情 $j$($j=0,1,2$，分别代表去健身房，去图书馆，休息) 休息的最少天数。

按照定义，最终的答案就为 $min(f(n,0),f(n,1),f(n,2))$。

• 当 $a_i==0$ 时，第 i 天只能休息。即 $f(i,2)=min(f(i-1,0),f(i-1,1),f(i-1,2))+1$

• 当 $a_i==1$ 时，第 i 天可以休息，也可以去图书馆。即

• • $f(i,2)=min(f(i-1,0),f(i-1,1),f(i-1,2))+1$
• • $f(i,1)=min(f(i-1,0),f(i-1,2))$

• 当 $a_i==2$ 时，第 i 天可以休息，也可以去健身房。即

• • $f(i,2)=min(f(i-1,0),f(i-1,1),f(i-1,2))+1$
• • $f(i,0)=min(f(i-1,1),f(i-1,2))$

• 当 $a_i==3$ 时，第 i 天三件事都可以干。即

• • $f(i,2)=min(f(i-1,0),f(i-1,1),f(i-1,2))+1$
• • $f(i,0)=min(f(i-1,1),f(i-1,2))$
• • $f(i,1)=min(f(i-1,0),f(i-1,2))$

时间复杂度： $O(n)$

代码：

#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;

const int N = 110;

int a[N];
int f[N][3];


int main(){
    int n;
    scanf("%d",&n);
    
    for(int i = 1;i <= n;i++) scanf("%d",&a[i]);
    //初始化为无穷大，因为我们要求的是最小值
    memset(f,0x3f,sizeof f);
    
    f[0][0] = 0;
    f[0][1] = 0;
    f[0][2] = 0;
    
    
    for(int i = 1;i <= n;i++){
        if(a[i] == 0) f[i][2] = min(f[i-1][0],min(f[i-1][1],f[i-1][2])) + 1;
        else if(a[i] == 1){
            f[i][1] = min(f[i-1][2],f[i-1][0]);
            f[i][2] = min(f[i-1][0],min(f[i-1][1],f[i-1][2])) + 1;
        }
        else if(a[i] == 2){
            f[i][0] = min(f[i-1][1],f[i-1][2]);
            f[i][2] = min(f[i-1][0],min(f[i-1][1],f[i-1][2])) + 1;
        }
        else if(a[i] == 3){
            f[i][0] = min(f[i-1][1],f[i-1][2]);
            f[i][1] = min(f[i-1][2],f[i-1][0]);
            f[i][2] = min(f[i-1][0],min(f[i-1][1],f[i-1][2])) + 1;
        }
    }
    cout<<min(f[n][0],min(f[n][1],f[n][2]))<<endl;
    return 0;
}