2024.7.12 暑期训练记录（4）

• 之后的训练方式是上午板刷2000的题，下午学新算法or vp，如果近期没有新算法要学也不vp就换成继续板刷，晚上补题，没有题要补就继续板刷
• 在尝试新的做题方式，看完题先把主要信息写在纸上，如果有思路就顺着思路走，没有思路就玩玩样例，想到什么都写下来，可以增加自己做出题的概率

CF

1354C2 - Not So Simple Polygon Embedding（几何 *2000）

• 一道简单版几何题，参考Codeforces 1354C2 - Not So Simple Polygon Embedding （几何）
• 
• 这是最终矩形的四分之一，观察这一部分：
  • 首先一共有 $2n$ 条边，所以每条边所对应的角 $each=\frac{360^{\circ }}{2n}$，这样的角一共有 $2n$ 个，所以四分之一个矩形所对的角有 $cnt=\frac{2n}{4}$ 个，凸多边形与正方形的交点是最接近中间位置的点，所以图中 $\theta =\frac{cnt}{2}\times each$
  • 之后可以利用 $\theta$ 计算出多边形每个小三角形的腰 $x=\frac{\frac{1.0}{2}}{\sin \frac{\theta }{2}}$
  • 图中的 $ans1$ 和 $ans2$ 均可通过正弦定理求出

#include <bits/stdc++.h>

using namespace std;

#define int long long
using i64 = long long;

typedef pair<int, int> PII;
typedef pair<int, char> PIC;
typedef pair<double, double> PDD;
typedef pair<int, PII> PIII;
typedef pair<int, pair<int, bool>> PIIB;

const int N = 1e6 + 10;
const int maxn = 1e6 + 10;
const int mod = 998244353;
const int mod1 = 954169327;
const int mod2 = 906097321;
const int INF = 0x3f3f3f3f3f3f3f3f;
const double PI = acos(-1.0);
const double epsilon = PI / 180.0;

void solve()
{
	int n;
	cin >> n;
	double each = 180.0 / n;
	double ang = round(n / 4.0) * each;
	double x = 1.0 / (2.0 * sin(each / 2.0 * epsilon));
	double x1 = x / sin(45 * epsilon) * sin(ang * epsilon);
	double x2 = x / sin(45 * epsilon) * sin((90 - ang) * epsilon);
	printf("%.10lf\n", x1 + x2);
}

signed main()
{
	ios::sync_with_stdio(false);
	cin.tie(0), cout.tie(0);

	int t = 1;
	cin >> t;
	while (t--)
	{
		solve();
	}
}

1344B - Monopole Magnets（思维，bfs *2000）

• 首先看样例，可以发现一种不合法的情况，就是同一行同一列中不能出现两个不相邻的黑格子，原因略
• 另外对于每行每列至少有一个 $s$ 磁铁这一条，我们可以判断是否有至少一列全是白格子和至少一行全是白格子，要不就都没有，要不然就都有
• 如果上述都满足，直接bfs，黑色连通块数量就是答案

#include <bits/stdc++.h>

using namespace std;

#define int long long
using i64 = long long;

typedef pair<int, int> PII;
typedef pair<int, char> PIC;
typedef pair<double, double> PDD;
typedef pair<int, PII> PIII;
typedef pair<int, pair<int, bool>> PIIB;

const int N = 1e6 + 10;
const int maxn = 1e6 + 10;
const int mod = 998244353;
const int mod1 = 954169327;
const int mod2 = 906097321;
const int INF = 0x3f3f3f3f3f3f3f3f;

int dx[] = {0, 0, 1, -1}, dy[] = {1, -1, 0, 0};

void solve()
{
    int n, m;
    cin >> n >> m;
    vector<string> g(n + 1);
    for (int i = 1; i <= n; i ++ )
    {
        cin >> g[i];
        g[i] = " " + g[i];
    }
	vector<vector<bool>> st(n + 1, vector<bool>(m + 1));
    int cnt = 0;
    auto bfs = [&](int x, int y)
    {
        queue<PII> q;
        q.push({x, y});
        st[x][y] = true;
        while (q.size())
        {
            auto t = q.front();
            q.pop();
            for (int i = 0; i < 4; i ++ )
            {
                int nx = t.first + dx[i], ny = t.second + dy[i];
                if (nx <= 0 || nx > n || ny <= 0 || ny > m) continue;
                if (st[nx][ny] || g[nx][ny] == '.') continue;
                st[nx][ny] = true;
                q.push({nx, ny});
            }
        }
    };
    for (int i = 1; i <= n; i ++ )
    {
        for (int j = 1; j <= m; j ++ )
        {
            if (g[i][j] == '.') continue;
            if (st[i][j]) continue;
            bfs(i, j);
            cnt ++ ;
        }
    }
    int idx = 0;
    // 每一行是否符合要求
    for (int i = 1; i <= n; i ++ )
    {
        int flag = 0;
        for (int j = 1; j <= m; j ++ )
        {
            if (g[i][j] == '#' && g[i][j - 1] != '#') flag ++ ;
        }
        if (flag > 1)
        {
            cout << "-1\n";
            return;
        }
        else if (!flag)
        {
            idx = 1;
        }
    }
    // 每一列
    int tmp = 0;
    for (int j = 1; j <= m; j ++ )
    {
        int flag = 0;
        for (int i = 1; i <= n; i ++ )
        {
            if (g[i][j] == '#' && g[i - 1][j] != '#') flag ++ ;
        }
        if (flag > 1)
        {
            cout << -1 << '\n';
            return;
        }
        else if (!flag)
        {
            tmp = 1;
        }
    }
    idx += tmp;
    if (idx == 0 || idx == 2) cout << cnt << '\n';
    else cout << -1 << '\n';
}

signed main()
{
	ios::sync_with_stdio(false);
	cin.tie(0), cout.tie(0);

	int t = 1;
	// cin >> t;
	while (t--)
	{
		solve();
	}
}

1416B - Make Them Equal（思维 *2000）

• $xi$ 我们不好处理，但是当 $i=1$ 时，我们可以轻松地控制 $x$
• 所以把所有数挪到第一个，后面的一个个分配
• 总和不能均分为 $n$ 份时输出 $-1$

#include <bits/stdc++.h>

using namespace std;

#define int long long
using i64 = long long;

typedef pair<int, int> PII;
typedef pair<int, char> PIC;
typedef pair<double, double> PDD;
typedef pair<int, PII> PIII;
typedef pair<int, pair<int, bool>> PIIB;

const int N = 1e6 + 10;
const int maxn = 1e6 + 10;
const int mod = 998244353;
const int mod1 = 954169327;
const int mod2 = 906097321;
const int INF = 0x3f3f3f3f3f3f3f3f;

struct node {
    int i, j, x;
};

void solve()
{
    int n;
    cin >> n;
    vector<int> a(n + 1);
    int sum = 0;
    for (int i = 1; i <= n; i ++ )
    {
        cin >> a[i];
        sum += a[i];
    }
    if (sum % n != 0)
    {
        cout << -1 << '\n';
        return;
    }
    sum /= n;
    vector<node> ans;
    for (int i = 2; i <= n; i ++ )
    {
        if (a[i] % i == 0)
        {
            ans.push_back({i, 1, a[i] / i});
            a[1] += a[i];
            a[i] = 0;
        }
        else
        {
            ans.push_back({1, i, i - a[i] % i});
            ans.push_back({i, 1, a[i] / i + 1});
            a[1] += a[i];
            a[i] = 0;
        }
    }
    for (int i = 2; i <= n; i ++ )
    {
        ans.push_back({1, i, sum});
    }
    cout << ans.size() << '\n';
    for (auto t : ans) cout << t.i << ' ' << t.j << ' ' << t.x << '\n';
}

signed main()
{
	ios::sync_with_stdio(false);
	cin.tie(0), cout.tie(0);

	int t = 1;
	cin >> t;
	while (t--)
	{
		solve();
	}
}

337D - Book of Evil（树的直径/树形dp *2000）

• 这题想到了树形dp但是没想出来具体怎么实现
• 树形dp的模板就是两层dfs，第一层用子结点更新父结点，第二层用父结点更新子结点
• dp[i][0/1] 表示第 i 个结点为根的子树里，最远的影响结点的距离（0表示最远距离 1表示次远距离）
• dist[i] 表示除去第 i 个结点为根的子树，其余部分中最远的影响结点的距离

#include <bits/stdc++.h>

using namespace std;

#define int long long
using i64 = long long;

typedef pair<int, int> PII;
typedef pair<int, char> PIC;
typedef pair<double, double> PDD;
typedef pair<int, PII> PIII;
typedef pair<int, pair<int, bool>> PIIB;

const int N = 1e6 + 10;
const int maxn = 1e6 + 10;
const int mod = 998244353;
const int mod1 = 954169327;
const int mod2 = 906097321;
const int INF = 0x3f3f3f3f3f3f3f3f;

void solve()
{
    int n, m, d;
    cin >> n >> m >> d;
    vector<bool> flag(n + 1);
    for (int i = 0; i < m; i ++ )
    {
        int x; cin >> x;
        flag[x] = true;
    }
    vector<vector<int>> g(n + 1);
    for (int i = 0; i < n - 1; i ++ )
    {
        int u, v;
        cin >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    vector<vector<int>> dp(n + 1, vector<int>(2, -INF));
    vector<int> dist(n + 1, -INF);
    function<void(int, int)> dfs1 = [&](int u, int fa)
    {
        if (flag[u]) dp[u][0] = dp[u][1] = 0;
        for (int i = 0; i < g[u].size(); i ++ )
        {
            int v = g[u][i];
            if (v == fa) continue;
            dfs1(v, u);
            if (dp[v][0] + 1 >= dp[u][0])
            {
                dp[u][1] = dp[u][0];
                dp[u][0] = dp[v][0] + 1;
            }
            else dp[u][1] = max(dp[u][1], dp[v][0] + 1);
        }
    };
    function<void(int, int)> dfs2 = [&](int u, int fa)
    {
        for (int i = 0; i < g[u].size(); i ++ )
        {
            int v = g[u][i];
            if (v == fa) continue;
            if (dp[u][0] == dp[v][0] + 1) dist[v] = max(dist[u] + 1, dp[u][1] + 1);
            else dist[v] = max(dist[u] + 1, dp[u][0] + 1);
            dfs2(v, u);
        }
    };
    dfs1(1, -1);
    dfs2(1, -1);
    int ans = 0;
    for (int i = 1; i <= n; i ++ )
        if (dp[i][0] <= d && dist[i] <= d) ans ++ ;
    cout << ans << '\n';
}

signed main()
{
	ios::sync_with_stdio(false);
	cin.tie(0), cout.tie(0);

	int t = 1;
	// cin >> t;
	while (t--)
	{
		solve();
	}
}

算法

最大流的几个模板