1001. Mod, Or and Everything

题意

\((n\%1) | (n\%2) | ...|(n\%n)\)

分析

直接打表,发现答案是 \(2^k - 1\)\(k\)​ 是二进制位数,2 的幂次需要特判一下

总结

一开始右移的 1 没加 ll,浪费了一点时间

代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int N = 1e5 + 7;
int T = 1;
int n, m;
void solve()
{
    ll n, ans;
    scanf("%lld", &n);
    if (n <= 2)
    {
        puts("0");
        return;
    }
    for (ll i = 1; n > (1ll << i); i++)
        ans = (1ll << i) - 1ll;
    printf("%lld\n", ans);
}
int main()
{
    scanf("%d", &T);
    while (T--)
    {
        solve();
    }
}

1005. Minimum spanning tree

题意

给 n-1 个点,编号 2~n,要求连边变成一棵树,边权为 lcm(i, j),求树所有边权之和的最小值

分析

对于编号为 3~n 的点,将所有编号为合数的点向其约数连边,编号为质数的点向 2 连边。所以,计算最小的边权和,需要计算 2~n 内的质数和 \(S_1\) 以及合数和 \(S_2\),得出最终答案为 \(S_1 * 2 + S_2\)

总结

就 ans 数组要开 long long,其他基本无坑点

代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int N = 1e7 + 7;
int T = 1;
int n;
int pri[N], cnt;
ll ans[N];
bool ispri[N];
void solve()
{
    int n;
    scanf("%d", &n);
    printf("%lld\n", ans[n]);
}

int main()
{
    for (int i = 2; i < N; i++)
        ispri[i] = 1;
    for (int i = 2; i < N; i++)
    {
        if (ispri[i])
            pri[++cnt] = i;
        for (int j = 1; j <= cnt; j++)
        {
            if (i * pri[j] >= N)
                break;
            ispri[i * pri[j]] = 0;
            if (i % pri[j] == 0) // 只在最小素因子处筛一次
                break;
        }
    }
    for (int i = 3; i < N; i++)
        if (ispri[i])
            ans[i] = ans[i - 1] + i * 2;
        else
            ans[i] = ans[i - 1] + i;
    scanf("%d", &T);
    while (T--)
    {
        solve();
    }
}

1008. Maximal submatrix

题意

给定矩阵,求一个最大的满足每列非递减的子矩阵

分析

预处理每行自该位置向上满足单调不减的数的个数,记为 \(h[i][j]\)​ ,枚举子矩阵最后一行位置,每次枚举跑一遍柱状图中的最大面积,最后取 max 即可。

总结

柱状图中的最大面积做法就是枚举高度,认为枚举的高度即为子矩阵的高度,则向两边拓展,找到两端高度大于枚举高度的位置,下标之差即为宽度,用单调栈去维护两个位置。

代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int N = 1e5 + 7;
int T = 1;
int n, m, g[2010][2010], h[2010][2010];
void solve()
{
    scanf("%d %d", &n, &m);
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
        {
            scanf("%d", &g[i][j]);
            if (i != 1 && g[i][j] >= g[i - 1][j])
                h[i][j] = h[i - 1][j] + 1;
            else
                h[i][j] = 1;
        }
    int ans = 0;
    for (int d = 1; d <= n; d++)
    {
        vector<int> le(m + 1, 0), ri(m + 1, m + 1);
        stack<int> st;
        for (int i = 1; i <= m; i++)
        {
            while (!st.empty() && h[d][st.top()] >= h[d][i])
            {
                ri[st.top()] = i;
                st.pop();
            }
            if (!st.empty())
                le[i] = st.top();
            st.push(i);
        }
        int tmp = 0;
        for (int i = 1; i <= m; i++)
            tmp = max(tmp, (ri[i] - le[i] - 1) * h[d][i]);
        ans = max(ans, tmp);
    }
    printf("%d\n", ans);
}
int main()
{
    scanf("%d", &T);
    while (T--)
    {
        solve();
    }
    fclose(stdin);
}

1009. KD-Graph

题意

定义 KD-Graph 的图,具有以下性质:1)无向加权图,2)n 个点可以分成 K 组,每组至少有一个点,对于分在同一组的 p 和 q 两个点,它们之间的路径中至少有一条路径的最大边权是小于等于 D 的,即这条路径的所有边权都小于等于 D,对于不在同一组的 p 和 q 两点,不能找到这样一条路径,使得最大边权小于等于 D 。现在要我们求这个最小的 D ,使得这个图成为一张 KD-Graph

分析

看题中的最小最大值可以想到二分答案,每次 check,我们将图中边权大于 D 的边删除,然后统计连通块个数 K',判断与 K 的大小关系。这时我们发现了 D 的单调性,D 越大,删去的边就越少,那么连通块的数量也就越少。所以,对于每一个二分的 D,如果 K’>K,则将 D 扩大,反之缩小,当 K’=K 时更新答案。考虑删边的操作,我们可以将删边转化为连边,将边权小于等于 D 的边连上,用并查集维护连通块个数

总结

思考 check 函数,我们发现,可以直接对所有的边按边权排序,每次插入所有当前最小边权的边至并查集,若此时连通块数量等于 K,则当前的边权就为答案,若插入前大于 K,插入后小于,则无解。代码无坑点,直接上手写就行

代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int N = 1e5 + 7, M = 5e5 + 7;
int T = 1;
struct edges
{
    int u, v, c;
} E[M];
int p[N], tot;
int getp(int x)
{
    if (p[x] != x)
        p[x] = getp(p[x]);
    return p[x];
}
void setp(int x, int y)
{
    x = getp(x);
    y = getp(y);
    p[x] = y;
}
bool cmp(struct edges &a, struct edges &b)
{
    return a.c < b.c;
}
void solve()
{
    int n, m, k;
    scanf("%d %d %d", &n, &m, &k);
    for (int i = 1; i <= m; i++)
    {
        scanf("%d %d %d", &E[i].u, &E[i].v, &E[i].c);
    }
    if (n == k)
    {
        puts("0");
        return;
    }
    sort(E + 1, E + m + 1, cmp);
    tot = n;
    for (int i = 1; i <= n; i++)
        p[i] = i;

    for (int i = 1, now; i <= m; i++)
    {
        now = E[i].c;
        if (getp(E[i].u) != getp(E[i].v))
            tot--, setp(E[i].u, E[i].v);
        while (i < m && E[i + 1].c == now)
        {
            i++;
            if (getp(E[i].u) != getp(E[i].v))
                tot--, setp(E[i].u, E[i].v);
        }
        if (tot == k)
        {
            printf("%d\n", E[i].c);
            return;
        }
        else if (tot < k)
        {
            puts("-1");
            return;
        }
    }
    if (tot > k)
        puts("-1");
}
int main()
{
    scanf("%d", &T);
    while (T--)
    {
        solve();
    }
}

间歇性踌躇满志,持续性混吃等死