2019 January Silver

T1.Grass Planting

这道题是一道结论题：我们发现点的度数越多，答案越多，所以我们可以发现答案为最大的点的度数+1。

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
int n;
int deg[N];
int main()
{
    int ans = 0;
    freopen("planting.in", "r", stdin);
    freopen("planting.out", "w", stdout);
    cin >> n;
    for (int i = 1; i < n; i++)
    {
        int x, y;
        cin >> x >> y;
        deg[x]++;
        deg[y]++;
        ans = max(ans, max(deg[x], deg[y]) + 1);
    }
    cout << ans << endl;
    return 0;
}

T2.Icy Perimeter

这道题第一个答案为这个冰淇淋中最大的连通块。

第二个答案是这样的，我们先让他往四个地方扩展

1. 如果他为'.' 或者在外围，就把周长加1
2. 否则周长不变。

dfs做法

#include <bits/stdc++.h>
using namespace std;
int dx[4] = {0, 1, 0, -1}, dy[4] = {1, 0, -1, 0};
int n, area, girth, S = 0, C = 0;
char a[1005][1005];
int f[1005][1005];

void dfs(int x, int y)
{
    if (f[x][y])
        return;
    f[x][y] = 1;
    area++;
    for (int i = 0; i < 4; i++)
    {
        int xx = x + dx[i], yy = y + dy[i];
        if (xx < 1 || xx > n || yy < 1 || yy > n || a[xx][yy] == '.')
            girth++;
        if (a[xx][yy] == '#')
            dfs(xx, yy);
    }
}

void work()
{
    memset(f, 0, sizeof(f));
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
        {
            if (a[i][j] == '#' && !f[i][j])
            {
                area = 0, girth = 0;
                dfs(i, j);
                if (area > S)
                {
                    S = area;
                    C = girth;
                }
                else
                {
                    if (area == S && girth < C)
                        C = girth;
                }
            }
        }
}

int main()
{
    freopen("perimeter.in", "r", stdin);
    freopen("perimeter.out", "w", stdout);
    cin >> n;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
            cin >> a[i][j];
    work();
    cout << S << ' ' << C;
    return 0;
}

T3 Mountain View

首先我们先求出每个山峰中的左端点和右端点，然后我们可以得到一个结论

如果这个山能被看见，就说明它的右端点比之前的右端点都大。

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
int n;
struct node
{
    int x, y;
} a[N];

bool cmp(node aa, node bb)
{
    return aa.x < bb.x || (aa.x == bb.x && aa.y > bb.y);
}
int ans = 0, last = 0;
int main()
{
    freopen("mountains.in", "r", stdin);
    freopen("mountains.out", "w", stdout);
    cin >> n;
    for (int i = 1; i <= n; i++)
    {
        int xx, yy;
        cin >> xx >> yy;
        a[i].x = xx - yy;
        a[i].y = xx + yy;
    }
    sort(a + 1, a + n + 1, cmp);
    for (int i = 1; i <= n; i++)
        if (a[i].y > last)
        {
            ans++;
            last = a[i].y;
        }
    cout << ans << endl;
    return 0;
}