专栏文章

MX Day 18

OOIer_ACMer
生活·游记参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@minbkbne
此快照首次捕获于
2025/12/01 23:43
3 个月前
此快照最后确认于
2025/12/01 23:43
3 个月前
查看原文

T1：

1762603466338.png

思路：

首先，我们发现这道题每种颜色只能用一次，且颜色之间可以根据涂色顺序依次覆盖，尽管我考试时想了个错误但是非常明显的想法，但是事后诸葛亮，我们先来考虑怎么处理依次覆盖的问题。
因为颜色只能用一次，那么我们在遍历的时候就要像剥皮一样一层一层找出此时应该涂什么颜色，我们每遇到一个新颜色就记录下它出现了，若之后的颜色与当前最高层颜色不同且在之前已经出现过，则肯定无法完成涂色，输出-1，否则继续进程。
上述过程说白了就是对题目要求的形象化转述，这一类题算是非常简单了，由于考试时一直在考虑原先错误的想法，导致最后的代码繁琐且超时一个点，S组考试时更改了策略，但还是遇到了犹豫不决的情况，记得改正。

Code：

CPP
#include <bits/stdc++.h>
using namespace std;
#define int long long
inline int read()
{
    register int x = 0, f = 1;
    char ch = getchar();
    while (ch < '0' || ch > '9')
    {
        if (ch == '-')
            f = -1;
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9')
    {
        x = x * 10 + ch - 48;
        ch = getchar();
    }
    return x * f;
}
int n, m;
pair<int, pair<int, int>> sta[1000019], ans[1000019];
int col[1000019], tp, l;
int r[1000019], vis[1000019], viss[1000019];
bool check(int id)
{
    for (int i = 1; i <= n; i++)
    {
        // cout << "i=" << i << " col[i]=" << col[i] << endl;
        while (tp && sta[tp].second.second < i)
        {
            tp--;
        }
        if (vis[col[i]] == id)
        {
            int co = sta[tp].first;
            int l = sta[tp].second.first;
            int r = sta[tp].second.second;
            // cout << "1 co=" << co << " l=" << l << " r=" << r << endl;
            if (i >= l && i <= r)
            {
                if (col[i] != co)
                {
                    return 0;
                }
            }
        }
        else
        {
            // cout << "2 col[i]=" << col[i] << " vis[col[i]]=" << vis[col[i]] << endl;
            sta[++tp] = {col[i], {i, r[col[i]]}};
            vis[col[i]] = id;
        }
    }
    return 1;
}
signed main()
{
    freopen("paint.in", "r", stdin);
    freopen("paint.out", "w", stdout);
    int t = read();
    while (t--)
    {
        int T = t + 10;
        n = read();
        m = read();
        l = 0;
        tp = 0;
        for (int i = 1; i <= n; i++)
        {
            r[i] = 0;
            col[i] = read();
        }
        for (int i = 1; i <= n; i++)
        {
            r[col[i]] = i;
        }
        for (int i = 1; i <= n; i++)
        {
            r[col[i]] = max(r[col[i]], i);
        }
        // cout << "r=";
        // for (int i = 1; i <= n; i++)
        // {
        //     cout << r[i] << ' ';
        // }
        // cout << endl;
        if (check(T) == 0)
        {
            cout << -1 << endl;
            // printf("%lld\n", -1);
            continue;
        }
        // cout << "OK\n\n";
        for (int i = 1; i <= n; i++)
        {
            if (viss[col[i]] != T)
            {
                viss[col[i]] = T;
                ans[++l] = {col[i], {i, r[col[i]]}};
            }
        }
        printf("%lld\n", l);
        for (int i = 1; i <= l; i++)
        {
            printf("%lld %lld %lld\n", ans[i].first, ans[i].second.first, ans[i].second.second);
        }
    }
    return 0;
}
/*
1
5 2
1 2 1 2 1
*/

T2：

1762604291339.png

思路：

首先，贪心，注定坠机，因为你TM样例都过不了。
好吧，老样子，从暴力看起。由于我们的交换一定固定范围，所以我们可以考虑搜索，反正我们的DFS也是干这行的。
我们可以考虑是给 x×2x \times 2 的位子交换，还是 x×2+1x\times 2 + 1 的位子交换，由于我们要保证我们的字典序尽量小，且我们也不知道给谁交换最终得到的位子那个更靠前，所以我们都要考虑。
首先，如果后面的两个待交换位子全部都是0，那么直接结束。
然后我们考虑只有两个数的情况，由于我们要保证字典序最小，肯定是越小的数扔前面，否则就是扔后面，遮掩就能保证A和B之间的关系符合最小字典序。
之后，就是三个数的情况，首先是A仍是最小值，那么就还好，如果是中间的这个数是最小值，那么直接和A交换，没有其他的方法让它扔到前面去。不过如果最后一个数是最小值的话，那就有很多情况了，我们会出现CAB和CBA两种情况，且都是合法交换而来，怎么保证字典序最小呢，由于我们目前的任务是将A扔到哪去，所以我们现将A，B两者小的分别放到 x×2x \times 2，x×2+1x \times 2 + 1 上，然后比较两者最终所在位置前后，，如果一开始A就小于B，说明我们就是拿A交换的，直接将res被较小的结果赋值，否则的话，我们还要再考虑一层，要将A扔给那个最终得到的结果偏后的那种交换方案（方案分为两种，也就是我们之前提到的将A，B两者小的分别放到 x×2x \times 2，x×2+1x \times 2 + 1 上）。
什么，你问我为何在更新第三种情况res时用的是val而不是带进去的minn，那不很简单，反正我们的A>B，带进去只可能深度加深，不可能减少。

Code:

CPP
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define ls id << 1
#define rs id << 1 | 1
inline int read()
{
    register int x = 0, f = 1;
    char ch = getchar();
    while (ch < '0' || ch > '9')
    {
        if (ch == '-')
        {
            f = -1;
        }
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9')
    {
        x = x * 10 + ch - '0';
        ch = getchar();
    }
    return x * f;
}
int n;
map<int, int> ans[1000009];
int a[1000009];
int dfs(int id, int val)
{
    if (ans[id].count(val))
    {
        return ans[id][val];
    }
    int res = id;
    int A = val;
    int B = a[ls];
    int C = a[rs];
    if (C == 0 && B == 0)
    {
        res = id;
    }
    else if (C == 0)
    {
        if (B < A)
        {
            res = ls;
        }
        else
        {
            res = id;
        }
    }
    else
    {
        if (A == min({A, B, C}))
        {
            res = id;
        }
        else if (B == min({A, B, C}))
        {
            res = dfs(ls, val);
        }
        else
        {
            int maxn = max(A, B);
            int minn = min(A, B);
            int LS = dfs(ls, minn), RS = dfs(rs, minn);
            if (A < B)
            {
                res = min(LS, RS);
            }
            else
            {
                if (LS < RS)
                {
                    res = dfs(rs, val);
                }
                else
                {
                    res = dfs(ls, val);
                }
            }
        }
    }
    return ans[id][val] = res;
}
void solve(int id)
{
    int A = a[id], B = a[ls], C = a[rs];
    if (B == 0 && C == 0)
    {
        return;
    }
    else if (C == 0)
    {
        if (A < B)
        {
            return;
        }
        else
        {
            swap(a[id], a[ls]);
        }
    }
    else
    {
        if (A == min({A, B, C}))
        {
            solve(ls);
            solve(rs);
            // return;
        }
        else if (B == min({A, B, C}))
        {
            swap(a[id], a[ls]);
            solve(ls);
            solve(rs);
        }
        else
        {
            a[id] = C;
            int maxn = max(A, B), minn = min(A, B);
            int LS = dfs(ls, minn), RS = dfs(rs, minn);
            if (LS < RS)
            {
                a[ls] = minn, a[rs] = maxn;
            }
            else
            {
                a[rs] = minn, a[ls] = maxn;
            }
            solve(ls), solve(rs);
        }
    }
}
signed main()
{
    freopen("swap.in", "r", stdin);
    freopen("swap.out", "w", stdout);
    n = read();
    for (int i = 1; i <= n; i++)
    {
        a[i] = read();
    }
    solve(1);
    for (int i = 1; i <= n; i++)
    {
        cout << a[i] << ' ';
    }
    return 0;
}

T3：

1762611842761.png

思路：

首先我们肯定是要排序，毕竟我们的三角形面积最小要么瘦瘦高高要么胖胖矮矮，从小到大排序方便选择。
我们确定a和b，令a<b，发现面积会随着c的增大反而从小变大又从大变小，那么我们的c只可能是第一个或者最后一个。
如果我们要选第一个c，那么b和c肯定是连在一起的，这很容易想到，然后O(n)枚举就可以了。
不过，如果你想选最后一个的话，那就要考虑的多一点。我们可以将a+b确定为s，知道s和c之后，那么随着a增大而增大，那么我们只需要确定a和s-a同时存在就可以了，这个可以用bitset来确定。

Code：

CPP
#include <bits/stdc++.h>
using namespace std;
#define int long long
inline int read()
{
    int x = 0, f = 1;
    char ch = getchar();
    while (!isdigit(ch))
    {
        if (ch == '-')
            f = -1;
        ch = getchar();
    }
    while (isdigit(ch))
    {
        x = x * 10 + ch - 48;
        ch = getchar();
    }
    return x * f;
}
int n, m;
int a[1000009];
double calc(long long a, long long b, long long c)
{
    double s = (a + b + c) / 2.0;
    return sqrt(s * (s - a) * (s - b) * (s - c));
}
void solve()
{
    bitset<300009> b1{}, b2{};
    // b.reset;
    int maxn = 0;
    n = read();
    m = read();
    for (int i = 1; i <= n; i++)
    {
        a[i] = read();
    }
    sort(a + 1, a + n + 1);
    maxn = a[1] + a[n];
    for (int i = 1; i <= n; i++)
    {
        b1[a[i]] = b2[maxn - a[i]] = 1;
    }
    double ans = 10000000.0;
    for (int i = 1; i <= n - 2; i++)
    {
        int wz = upper_bound(a + 1, a + i + 1, a[i + 2] - a[i + 1]) - (a);
        if (wz >= 1 && wz <= i)
        {
            // cout << "triangle: " << a[wz] << ' ' << a[i + 1] << ' ' << a[i + 2] << endl;
            ans = min(ans, calc(a[i + 1], a[i + 2], a[wz]));
        }
        // cout << "wz=" << wz << ' ' << a[wz] << ' ' << a[i + 1] << ' ' << a[i + 2] << endl;
    }
    for (int s = 1; s <= maxn; s++)
    {
        int wz = lower_bound(a + 1, a + n + 1, s) - (a);
        wz--;
        if (a[wz] < s - a[wz])
        {
            continue;
        }
        if (wz >= 1 && wz <= n)
        {
            bitset<300009> b3 = b1 & b2 >> (maxn - s);
            int x = b3._Find_next(s - a[wz]);
            int y = s - x;
            int z = a[wz];
            if (x < y && y < z)
            {
                ans = min(ans, calc(x, y, z));
            }
        }
    }
    if (ans == 10000000.0)
    {
        cout << -1 << endl;
    }
    else
    {
        cout << fixed << setprecision(15) << ans << endl;
    }
    // cout << endl;
}
signed main()
{
    freopen("triangle.in", "r", stdin);
    freopen("triangle.out", "w", stdout);
    int T = read();
    while (T--)
    {
        solve();
    }
    return 0;
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...