2021-08-11 12:44 北京大学 C++

关注

牛客多校第三场题解

B Black and white

题意：给定一个 $n\times n$ 的全白方阵，每个小方格有一个点权 $w_{i,j}$ ，先要将其全部染黑，对于方格 $(i,j)$ 其染黑代价为 $w_{i,j}$ 。若对于某一个方格 $(i,j)$ ，存在另外一行一列满足 $(i,k),(l,k),(l,j)$ 均已被染色，则当前无条件染色。问最小全部染黑代价。

解法：一个非常常见的方法是将点化边，边化点。对于每一横行和纵行，都认为是一个点；对于每一个点，都认为是沟通了其行列的一条边，其权值为 $w_{i,j}$ 。那么原问题就转化成为了一个最小生成树：显然，只要两行两列均被连接，那么最后那个已经连接的边就不必要加入了——可以由其他的三条边导通。

类似题如洛谷 P5089 [eJOI2018]元素周期表，和此题如出一辙。

因而最后跑一个 Kruskal 即可。此题卡常，因而不可直接对全部的边（数量级为 $2.5 \times 10^7$ ）进行排序，而应该对边权使用桶排。

#include <cstdio>
#include <algorithm>
#include <vector>
#include <utility>
using namespace std;
int w[5005 * 5005];
int cnt, father[10005];
int getfather(int x)
{
    return father[x] == x ? x : father[x] = getfather(father[x]);
}
vector<pair<int, int>> v[100005];
int main()
{
    int n, m;
    long long a, b, c, d, p;
    scanf("%d%d%lld%lld%lld%lld%lld", &n, &m, &a, &b, &c, &d, &p);
    w[0] = a;
    for (int i = 1; i <= n * m;i++)
        w[i] = ((long long)w[i - 1] * w[i - 1] * b + (long long)w[i - 1] * c + d) % p;
    int maximum = 0;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
        {
            maximum = max(maximum, w[(i - 1) * m + j]);
            v[w[(i - 1) * m + j]].push_back(make_pair(i, j + n));
        }
    for (int i = 1; i <= n + m;i++)
        father[i] = i;
    long long ans = 0;
    int times = 0;
    for (int i = 0; i <= maximum;i++)
        for (auto j : v[i])
            if (getfather(j.first) != getfather(j.second))
            {
                ans += i;
                times++;
                father[getfather(j.first)] = getfather(j.second);
                if (times >= n + m)
                    break;
            }
    printf("%lld\n", ans);
    return 0;
}

C Minimum grid

题意：给定一个 $n \times n$ 的矩阵，有些地方能填数而有些地方不能。然后给出每一行每一列的最大值，问最小的填数总和。

解法：此题和上题类似，也是进行了边和点的转化——每一行每一列视为点，而只有能填数并且该行该列最大值相同的点视为一条边。这是因为，如果这个点对应的横行和纵行最大值不相同，那么它不能作为公用的点——如果只作为一行的最大值，该列仍然需要一个更大的值来充当该列的真正最大值，因而无法减小总和。只有该行该列最大值相同，在这里填数才能尽可能的让该行该列都使用这一最大值，从而减小总值。

那么我们将全部权值相同且能有点沟通的集合找到了，剩下的就是对这些二部图进行最大匹配。显然匹配的越多答案越小，因为这几个图是互不干扰的。

#include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;
int match[4005];
bool vis[4005];
bool mp[2005][2005];
long long b[2005], c[2005];
vector<int> graph[4005];
//二分图匹配模板
bool dfs(int x)
{
    for(auto i:graph[x])
    {
        if(!vis[i])
        {
            vis[i] = 1;
            if(match[i]==0 || dfs(match[i]))
            {
                match[i] = x;
                return 1;
            }
        }
    }
    return 0;
}
int main()
{
    int n, m, k, u, v;
    long long ans = 0;
    scanf("%d%d%d", &n, &m, &k);
    for (int i = 1; i <= n;i++)
    {
        scanf("%lld", &b[i]);
        ans += b[i];
    } 
    for (int i = 1; i <= n;i++)
    {
        scanf("%lld", &c[i]);
        ans += c[i];
    }
    for (int i = 1; i <= m;i++)
    {
        scanf("%d%d", &u, &v);
        mp[u][v] = 1;
    }
    for (int i = 1; i <= n;i++)
        for (int j = 1; j <= n;j++)
            if(b[i]==c[j] && mp[i][j])
                graph[i].push_back(j + n);
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= 2 * n; j++)
            vis[j] = 0;
        if(dfs(i))
            ans -= b[i];
    }
    printf("%lld", ans);
    return 0;
}

E Math

题意：找到 $1\leq x \leq y \leq n$ 且满足 $xy+1|x^2+y^2$ 的 $(x,y)$ 对数。

解法：可以证明， $\displaystyle \frac{x^2+y^2}{xy+1}$ 为整数时必为完全平方（IMO 原题）。

可以发现，对于一个 $y$ ，至多只有一个 $x$ 与之配对满足上述条件。当 $y$ 为立方数， $x$ 为 $y$ 的立方根时，一定成立： $x^2+y^2=x^4(x^2+1)$ 。但是我们注意到还有一些其他的数也满足这个条件。不妨将对应的 $(x,y)$ 列举如下：

$2 \to 8 \to 30 \to 112 \to 418 \to 1560 \cdots$
$3 \to 27 \to 240 \to 2133 \cdots$
$4 \to 64 \to 1020 \to 16256 \cdots$
$5 \to 125 \to 3120 \cdots$

这么写的意思是，每一个 $\to$ 都表示了当 $x$ 取前一位数， $y$ 取后一位数的时候能满足条件。可以发现，所有的非立方数都可以由立方数或者其他的一些非立方数推出，并且它们可以被分为若干族，每一族都由一个立方数开始。

接下来找族内的规律。

$30 = 8 \times 4-2$ ， $112=30 \times 4 - 8$ ， $418 = 112 \times 4- 30$ ， $1560 = 418\times 4 - 112$ 。
$240 = 27 \times 9 -3$ ， $2133 = 240 \times 9 -27$ 。
$\cdots$

因而我们可以很快的发现每一族的递推式：对于第 $k$ 族，当 $i \geq 3$ 时， $f_i=f_{i-1} \times k^2-f_{i-2}$ 。这个数列是指数递增的，因而至多只有 $O(\log n)$ 级别的数字。这种族至多只有 $n^{\frac{1}{3}}$ 个，因而总的个数只有约三千万个，可以全部存放在一个 vector 中。

总体复杂度 $O(n^{\frac{1}{3}} \log n)$ 。注意乘法过大，需要使用 int128 进行中间计算。

#include<bits/stdc++.h>
using namespace std;
const __int128_t maxk=1000000000000000000LL;
vector<__int128_t> num;
int main()
{
    int t;
    long long n;
    num.push_back(1);
    for (__int128_t i = 2; i <= 1000000; i++)
    {
        __int128_t k = i, base = i, now = 0;
        k = i * i * base - now;
        now = base;
        base = k;
        while (k > 0 && k <= maxk)
        {
            num.push_back(k);
            k = i * i * base - now;
            now = base;
            base = k;
        }
    }
    sort(num.begin(), num.end());
    scanf("%d", &t);
    while(t--)
    {
        scanf("%lld", &n);
        printf("%lld\n", upper_bound(num.begin(), num.end(), n) - num.begin());
    }
    return 0;
}

F 24dian

题意：给定目标值 $m$ 和牌数 $n$ （ $n \leq 4$ ），要求用 $1-13$ 点的 $n$ 张牌组成目标值，要求计算过程中每步都有非整数，且不能存在不用分数就实现的情况。按字典序输出全部的答案。

解法：首先考虑怎么从给定的一串数中枚举所有的可能情况。容易想到，我们每一步计算都是将两个数通过加减乘除四种运算规则中的一个合并成一个数。因而我们可以模拟这个过程——枚举即将进行的操作数和方案，逐一进行转移。这样的好处在于，既可以不重复不遗漏的枚举所有情况，并且保留了所有的操作数，进而方便我们检查是否存在这样的方案。

其二，是对“不能存在不用分数就实现的情况”的讨论。考虑使用一个判定变量 $type$ 。如果当前这个方案使用到了分数，则或上 $2$ ；反之则或 $1$ 。对于一个给定的情况，可能存在多个方案组成目标值，因而在最后的时候会多次或上 $2$ 或者 $1$ 。如果所有情况都枚举完成发现值是 $2$ 而不是其他，则证明当前这几个数不存在不用分数就能实现的情况，可以加入答案。

最后，容易发现当 $n \leq 3$ 的情况下，答案恒不存在，因而只用讨论 $n=4$ 的情况即可。

#include <cstdio>
#include <algorithm>
#include <cmath>
using namespace std;
const double eps = 1e-7;
struct node
{
    int a;
    int b;
    int c;
    int d;
    bool operator <(const node &t)const
    {
        if(a!=t.a)
            return a < t.a;
        if(b!=t.b)
            return b < t.b;
        if(c!=t.c)
            return c < t.c;
        if(d!=t.d)
            return d < t.d;
    }
};
struct node ans[50005];
int cnt;
bool vis[15];
double num[15];
int type, m;
void check(int step)
{
    if(step==7)
    {
        if (abs(num[7] - m) >= eps)//如果值都不对直接回去
            return;
        bool flag = 0;
        for (int i = 1; i < 7;i++)
            if(abs(num[i]-round(num[i]))>=eps)//分数判定
            {
                flag = 1;
                break;
            }
        if(flag)
            type |= 2;
        else
            type |= 1;
        return;
    }
    for (int i = 1; i <= step;i++)
        if(vis[i])//vis[i]=1表示当前值可用
            for (int j = 1; j <= step;j++)
                if(i!=j && vis[j])
                {
                    vis[step + 1] = 1;
                    vis[i] = vis[j] = 0;
                    num[step + 1] = num[i] + num[j];//枚举四个操作符
                    check(step + 1);
                    num[step + 1] = num[i] * num[j];
                    check(step + 1);
                    num[step + 1] = num[i] - num[j];
                    check(step + 1);
                    if(abs(num[j])>=eps)
                    {
                        num[step + 1] = num[i] / num[j];
                        check(step + 1);
                    }
                    vis[i] = vis[j] = 1;
                    vis[step + 1] = 0;
                }
}
void dfs(int x,int step)
{
    if(step==5)
    {
        type = 0;
        for (int i = 1; i <= 4;i++)
            vis[i] = 1;
        check(4);
        if(type==2)
        {
            cnt++;
            ans[cnt].a = num[1];
            ans[cnt].b = num[2];
            ans[cnt].c = num[3];
            ans[cnt].d = num[4];
        }
        return;
    }
    for (int i = x; i <= 13;i++)//从小到大的枚举数。因为在check函数中已经考虑了将顺序打乱的情况，因而枚举的时候不需要乱序，按照从小到大的顺序即可
    {
        num[step] = i;
        dfs(i, step + 1);
    }
}
int main()
{
    int n;
    scanf("%d%d", &n, &m);
    if(n<=3 || m>=30000)
    {
        printf("0");
        return 0;
    }
    dfs(1, 1);
    printf("%d\n", cnt);
    for (int i = 1; i <= cnt;i++)
        printf("%d %d %d %d\n", ans[i].a, ans[i].b, ans[i].c, ans[i].d);
    return 0;
}

J Counting Triangles

题意：给定一个 $n \times n$ （ $n \leq 8\times 10^3$ ）的 01 矩阵，若 $w_{i,j}$ 为 $0$ 表示 $i$ 和 $j$ 之间边颜色为白，反之为黑。问有多少个三角形是三边完全同色的。

解法：考虑反选。全部三角形个数有 $\dbinom{n}{3}$ 个。考虑异色三角形的构成——一定是存在某两个顶角都延申出一黑一白的边。因而考虑每一个顶点——它对异色三角形个数答案的贡献为延申出去的黑边数乘以白边数除以二，因为这种三角形一定是异色的。减去即可。

#include <bits/stdc++.h>
namespace GenHelper
{
    unsigned z1,z2,z3,z4,b,u;
    unsigned get()
    {
        b = ((z1 << 6) ^ z1) >> 13;
        z1 = ((z1 & 4294967294U) << 18) ^ b;
        b = ((z2 << 2) ^ z2) >> 27;
        z2 = ((z2 & 4294967288U) << 2) ^ b;
        b = ((z3 << 13) ^ z3) >> 21;
        z3 = ((z3 & 4294967280U) << 7) ^ b;
        b = ((z4 << 3) ^ z4) >> 12;
        z4 = ((z4 & 4294967168U) << 13) ^ b;
        return (z1 ^ z2 ^ z3 ^ z4);
    }
    bool read()
    {
        while (!u)
            u = get();
        bool res = u & 1;
        u >>= 1;
        return res;
    }
    void srand(int x)
    {
        z1 = x;
        z2 = (~x) ^ 0x233333333U;
        z3 = x ^ 0x1234598766U;
        z4 = (~x) + 51;
        u = 0;
    }
}
using namespace GenHelper;
using namespace std;
bool edge[8005][8005];
long long black[8005], white[8005];
int main()
{
    int n, seed;
    std::cin >> n >> seed;
    GenHelper::srand(seed);
    for (int i = 0; i < n; i++)
        for (int j = i + 1; j < n; j++)
        {
            edge[j][i] = edge[i][j] = GenHelper::read();
            if(edge[j][i]==1)
            {
                black[i]++;
                black[j]++;
            }
            else
            {
                white[i]++;
                white[j]++;
            }
        }
    long long ans = (long long)n * (long long)(n - 1) * (long long)(n - 2) / 6;
    long long minus = 0;
    for (int i = 0; i < n;i++)
        minus += black[i] * white[i];
    printf("%lld", ans - minus / 2);
    return 0;
}