题目链接

1.上车

算法(暴力枚举) \(O(n)\)

只需要判断出车辆空余是否大于二即可

时间复杂度

暴力一遍即可，复杂度位\(O(n)\)

C++ 代码

#include
#include
#include
using namespace std;
const int N = 1e5 + 10;
int n, m, k;
int main()
{
	cin.tie(0);
    cout.tie(0);
    ios::sync_with_stdio(0);
    int cnt = 0;
    cin >> n;
    while(n--)
    {
        int a, b;
        cin >> a >> b;
        if(b - a >= 2)
            cnt++;
    }
    cout << cnt;
    return 0;
}

2.连通分量

算法(dfs + 模拟) \(O(n^3)\)

题目是找将障碍物假设位空格是的联通分量的数目
所以我们先预处理将连通块给找出来，并且将每一个连通块的数目找出来即可。

时间复杂度

预处理是n*m + 一次深搜， 枚举每一个障碍物是n*m*4,所以时间复杂度最大位\(O(n^3)\)

C++ 代码

#include
#include 
#include
#include
using namespace std;
const int N = 10100;
int n, m, k;
char a[N][N];
int vis[N][N];
int cnt = 0;
int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};

int check(int x, int y)
{
    return x >= 1 && x <= n && y >= 1 && y <= m;
}

int dfs(int x, int y)
{
    vis[x][y] = cnt;    //标记是哪个连通块
    int res = 0;
    for(int i = 0; i < 4; i++)
    {
        int tx = x + dx[i], ty = y + dy[i];
        if(check(tx, ty) && !vis[tx][ty] && a[tx][ty] == '.')
        {
            res += dfs(tx, ty); //计算数目
        }
    }
    return res + 1; //加上自己
}

int main()
{
    int Hash[1000005];//记录每一个联通块的联通数目
    cin >> n >> m;
    for(int i = 1; i <= n; i++)
        cin >> a[i] + 1;
    for(int i = 1; i <= n; i++)
    {
        for(int j = 1; j <= m; j++)
        {            
            if(a[i][j] == '.' && !vis[i][j])
            {
                ++cnt;
                int c = dfs(i, j);
                Hash[cnt] = c;
            }         
        } 
}
    for(int i = 1; i <= n; i++)
    {
        for(int j = 1; j <= m; j++)
        {
             if(a[i][j] == '*')
             {
                set umap;  //用于去重
                umap.clear();
                for(int k=0;k<4;k++)
                {
                    int tx = i + dx[k], ty = j + dy[k];
                    if(check(tx, ty) && a[tx][ty] == '.' && umap.find(vis[tx][ty]) == umap.end())
                      umap.insert(vis[tx][ty]);
                    int res = 1;  
                    for(auto c : umap) res += Hash[c];
                    a[i][j] = (res % 10) + '0';
                }
             }
        }   
    }  
    for (int i = 1; i <= n; i++)
        cout << a[i] + 1 << endl;

    return 0;
}

3.信号

算法(贪心) \(O(n)\)

题目让我们找最小个数覆盖全部房子。
分析可得如果我们找到一个覆盖范围比前面一个大的，我们就可以选择后面一个最为一个最值

时间复杂度

一次遍历即可求出 \(O(n)\)

C++代码

#include 
#include 
#include 

#include 
using namespace std;
const int N = 1010;
int n,r,cnt;
int qu[N];
int main()
{
    cin >> n >> r;
    for(int i= 1; i <= n;i++)
    {
        int x;
        cin >> x;
        if(x)  
            qu[cnt++]=i;
    }
    int last = 0, res = 0;
    for(int i = 0; i < cnt; i++)
    {
        if(last >= n)
            break;
        if(qu[i] - r + 1 > last + 1)
        {
            res = -1;
            break;
        }
        int j = i;
        while(j + 1 < cnt && qu[j + 1] - r <= last) j++;
        last = qu[j] + r - 1;
        res++;
        i = j;
    }
    if(last >= n)
        cout << res;
    else
        cout << -1;
    return 0;
}