AcWing2022春季每日一题-2-第三周

AcWing2022春季每日一题，第三周题解

AcWing 1683. 困牛放牧—原题链接

题目标签：

思路：
分情况讨论即可
对于最小的情况，如果三者已经连续了，那便不需要调整，如果两两之间有唯一空位，填充空位即可，否则只需要第一次将端点移到空一位的地方，接着填充即可
对u有最大的情况，从不相连到相连的过程就是填充点和点之间的距离，输出两个线段最长的一段的距离也就是要填充的最大值

#include <bits/stdc++.h>
using namespace std;

int a, b, c;

int main()
{
    cin >> a >> b >> c;
    // cout << abs(a - b) - 1 << "-" << abs(b - c) - 1 << endl;
    if(abs(a - b) - 1 == 1 || abs(b - c) - 1 == 1)  puts("1");
    else if(abs(a - b) - 1 == 0 && abs(b - c) - 1 == 0) puts("0");
    else puts("2");
    
    cout << max(abs(a - b) - 1, abs(b - c) - 1) << endl;
    return 0;
}

---

AcWing 1470. 水桶传递队列—原题链接

题目标签：BFS

思路：
知道了起点和终点求最短路，直接BFS即可，模板题

#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> PII;

const int N = 15;
char g[N][N];
int dist[N][N];
PII st, ed;
int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, -1, 0, 1};

void bfs()
{
    queue<PII> q;
    dist[st.first][st.second] = 0;
    q.push(st);

    while(q.size())
    {
        auto t = q.front();
        q.pop();

        for(int i=0; i<4; i++)
        {
            int a = t.first + dx[i], b = t.second + dy[i];
            if(a >= 1 && a <= 10 && b >= 1 && b <= 10 && g[a][b] != 'R' && dist[a][b] == -1)
            {
                dist[a][b] = dist[t.first][t.second] + 1;
                if(a == ed.first && b == ed.second) return;
                else q.push({a, b});
            }
        }
    }
}

int main()
{
    memset(dist, -1, sizeof dist);
    for(int i=1; i<=10; i++)
    {
        string s;
        cin >> s;
        for(int j=0; j<10; j++)
        {
            char c = s[j];
            g[i][j+1] = c;
            if(c == 'L') st = {i, j+1};
            if(c == 'B') ed = {i, j+1};
        }
    }

    bfs();
    cout << dist[ed.first][ed.second]-1 << endl;
    return 0;
}

---

AcWing 1761. 阻挡广告牌—原题链接

题目标签：暴力 | 区间求交集 | 计算几何

思路：
因为两个广告牌互不相交，所以求分别相交的两个部分即可，平面中香蕉部分即右端点的最小值*左端点的最大值

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;

int a[3][4];

int get(int a, int b, int c, int d)
{
    return max(0, min(b, d) - max(a, c));
}

int area(int a[])
{
    return (a[2] - a[0]) * (a[3] - a[1]);
}

int main()
{
    for(int i=0; i<3; i++)
    {
        for(int j=0; j<4; j++)
        {
            cin >> a[i][j];
        }
    }

    int res = 0;
    for(int i=0; i<2; i++)
    {
        res += get(a[i][0], a[i][2], a[2][0], a[2][2]) * get(a[i][1], a[i][3], a[2][1], a[2][3]);
    }

    cout << area(a[0]) + area(a[1]) - res << endl;
    // system("pause");
    return 0;
}

---

AcWing 1749. 阻挡广告牌 II—原题链接

题目标签：模拟 | 分类讨论（不推荐）

思路：
看样子是个分类讨论，但是一方面需要分不少类，另一方面数据并不大，因此直接上暴力模拟，需要注意的是边转换为方格时的边界问题

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;

const int N = 2010, B = N / 2;
bool st[N][N];

int main()
{
    int a, b, c, d;

    cin >> a >> b >> c >> d;
    a += B, b += B, c += B, d += B;
    for(int i=a; i<c; i++)
    for(int j=b; j<d; j++) st[i][j] = true;

    cin >> a >> b >> c >> d;
    a += B, b += B, c += B, d += B;
    for(int i=a; i<c; i++)
    for(int j=b; j<d; j++) st[i][j] = false;

    a = b = N, c = d = 0;
    for(int i=0; i<N; i++)
    {
        for(int j=0; j<N; j++)
        {
            if(st[i][j] == true)
            {
                a = min(a, i);
                b = min(b, j);
                c = max(c, i);
                d = max(d, j);
            }
        }
    }
    int len = max(0, d - b + 1), height = max(0, c - a + 1);
    cout << len * height << endl;
    // system("pause");
    return 0;
}

---

AcWing 1737. 传送—原题链接

题目标签：分类讨论

思路：
也就三种情况，应该是某复杂最短路题目的阉割版

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;

int a, b, x, y;

int main()
{
    cin >> a >> b >> x >> y;
    int d1 = abs(a - b);
    int d2 = abs(a - x) + abs(y - b);
    int d3 = abs(a - y) + abs(x - b);
    cout << min(d1, min(d2, d3)) << endl;
    // system("pause");
    return 0;
}

---

AcWing 1725. 组队井字游戏—原题链接

题目标签：模拟 | 暴力

思路：
因为只有3x3的棋盘，所以直接暴力模拟一次就可以了，这里可以巧妙的运用set的自动查重

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<int, int> PII;

char g[3][3];
set<set<char>> s1, s2;

int main()
{
    for(int i=0; i<3; i++)
    {
        string s;
        cin >> s;
        for(int j=0; j<3; j++)
        {
            g[i][j] = s[j];
        }
    }

    for(int i=0; i<3; i++)
    {
        set<char> s;
        for(int j=0; j<3; j++)
        {
            s.insert(g[i][j]);
        }
        if(s.size() == 1) s1.insert(s);
        else if(s.size() == 2) s2.insert(s);
    }
    for(int i=0; i<3; i++)
    {
        set<char> s;
        for(int j=0; j<3; j++)
        {
            s.insert(g[j][i]);
        }
        if(s.size() == 1) s1.insert(s);
        else if(s.size() == 2) s2.insert(s);
    }

    set<char> s;
    s.insert(g[0][0]);s.insert(g[1][1]); s.insert(g[2][2]);
    if(s.size() == 1) s1.insert(s);
    else if(s.size() == 2) s2.insert(s);
    s.clear();
    s.insert(g[2][0]);s.insert(g[1][1]); s.insert(g[0][2]);
    if(s.size() == 1) s1.insert(s);
    else if(s.size() == 2) s2.insert(s);
    cout << s1.size() << endl << s2.size() << endl;
    // system("pause");
    return 0;
}

---