2021牛客寒假算法基础集训营6【解题报告】

A 回文括号序列计数

题目描述

我们定义一个字符串S是回文的，表示S的左右反转和S相同。

我们定义一个字符串是括号序列：

  1. 空串是括号序列。
  2. 两个括号序列P和Q的拼接是括号序列。
  3. 如果P是括号序列，'('+P+')'是括号序列。

求长度为 n (0<=n<=10^9) 的回文括号序列的方案数，对 998244353 取膜。

输入描述:

第一行一个 T 表示数据组数。T<=1000000。

接下来 T 行，每行一个 n 。

输出描述:

T 行。对于每组数据，你的答案。

分析：

文字游戏....

代码实现：

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef double db;
typedef long double ldb;

const int M = (int)1e5;
const int N = (int)1e2;
const ll inf = 0x3f3f3f3f3f3f3f3f;
const double eps = 1e-6;
const ll mod = (ll)998244353;

void work()
{
    int n;
    scanf("%d", &n);
    if(n)   printf("0\n");
    else        printf("1\n");
}

int main()
{
//    freopen("input.txt", "r", stdin);
//    freopen("output.txt", "w", stdout);
    int T; scanf("%d", &T);
    while(T--) work();
//    work();
//    cerr << 1.0 * clock() / CLOCKS_PER_SEC << "\n";
    return 0;
}

B 系数

题目描述

给定一个多项式 ，求它的第 k 项系数。

输入描述:

第一行，输入 T ，表示数据组数。

接下来 T 行，每行输入 n 和 k 。

输出描述:

对于每组询问，输出系数模 3 后的结果。

分析：

.

因此第 项的系数等于 .

代码实现：

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef double db;
typedef long double ldb;

const int M = (int)2e3;
const int N = (int)3e3;
const ll inf = 0x3f3f3f3f3f3f3f3f;
const double eps = 1e-6;
const ll mod = (ll)998244353;

int fac[] = {1, 1, 2, 0};

int C(int n, int m)
{
    if(m > n)   return 0;
    return fac[n] * fac[m] * fac[n - m] % 3;
}

int Lucas(ll n, ll m)
{
    if(!m)  return 1;
    return C(n % 3, m % 3) * Lucas(n / 3, m / 3) % 3;
}

void work()
{
    ll n, k; scanf("%lld %lld", &n, &k);
    int ans = Lucas(2 * n, k);
    if((2 * n - k) & 1) ans = -ans;
    ans = (ans % 3 + 3) % 3;
    printf("%d\n", ans);
}

int main()
{
//    freopen("input.txt", "r", stdin);
//    freopen("output.txt", "w", stdout);
    int T; scanf("%d", &T);
    while(T--) work();
//    work();
//    cerr << 1.0 * clock() / CLOCKS_PER_SEC << "\n";
    return 0;
}

C 末三位

题目描述

牛牛最近刚学完指数，他理解了 ......

但是，他现在想知道：的末三位是多少？

输入描述:

有多组输入数据。

每组数据输入一个数n，表示指数。

输出描述:

输出 的末三位。

分析：

直接快速幂.

代码实现：

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef double db;
typedef long double ldb;

const int M = (int)1e5;
const int N = (int)1e6;
const ll inf = 0x3f3f3f3f3f3f3f3f;
const double eps = 1e-6;
const ll mod = (ll)998244353;

ll quick(ll a, ll b, ll p = mod)
{
    ll s = 1;
    while(b)
    {
        if(b & 1) s = s * a % p;
        a = a * a % p;
        b >>= 1;
    }
    return s;
}

void print(int n)
{
    if(n < 10)   printf("0");
    if(n < 100)  printf("0");
    printf("%d\n", n);
}

void work()
{
    int n;
    while(~scanf("%d", &n))
    {
        print(quick(5, n, 1000));
    }

}

int main()
{
//    freopen("input.txt", "r", stdin);
//    freopen("output.txt", "w", stdout);
//    int T; scanf("%d", &T);
//    while(T--) work();
    work();
//    cerr << 1.0 * clock() / CLOCKS_PER_SEC << "\n";
    return 0;
}

D 划数

题目描述

一个智能机器人在黑板上写了n个数，它每次划去任意两个数，并在数列的后面写上这两个数的和对11取模的值。

例：5 6 7 8 9，划去5 6后，数列变为7 8 9 0.

有趣的是，机器人在还剩下两个数的时候突然“罢工”了，已知其中一个数cnt（cnt >= 11），求另外一个数的值。

输入描述:

多组测试数据，以 EOF 结尾。

每组数据，第一行输入n和cnt。

第二行输入n个数，第i个数表示num[i]。

输出描述:

每组数据，输出另外一个数的值。

分析：

小坑点是要特判 的情况.

代码实现：

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef double db;
typedef long double ldb;

const int M = (int)1e5;
const int N = (int)1e2;
const ll inf = 0x3f3f3f3f3f3f3f3f;
const double eps = 1e-6;
const ll mod = (ll)998244353;

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 - '0';
        ch = getchar();
    }
    return x * f;
}

int n, cnt;

void work()
{
    while(~scanf("%d %d", &n, &cnt))
    {
        if(n == 2)
        {
            int ans = 0;
            for(int i = 1, a; i <= n; ++i)
            {
                scanf("%d", &a);
                if(a != cnt || i == 2 && ans == 0) ans = a;
            }
            printf("%d\n", ans);
        }
        else
        {
            int ans = 0;
            for(int i = 1, a; i <= n; ++i)
            {
                scanf("%d", &a);
                ans = (ans + a) % 11;
            }
            ans = ((ans - cnt) % 11 + 11) % 11;
            printf("%d\n", ans);
        }
    }
}

int main()
{
//    freopen("input.txt", "r", stdin);
//    freopen("output.txt", "w", stdout);
//    int T; scanf("%d", &T);
//    while(T--) work();
    work();
//    cerr << 1.0 * clock() / CLOCKS_PER_SEC << "\n";
    return 0;
}

E 网格

题目描述

有一个 n 行 m 列的网格，第 i 行 j 列上有数字 。每个位置需要从上下左右四个方向中选择互相垂直的两个。

定义 w(x)=x+popcnt(x) ，其中 popcnt(x) 表示 x 的二进制位中 1 的位的数量。

如果两个相邻的位置 互相位于对方选择的某个方向上，则对答案由 的贡献，其中 xor 表示二进制中的按位异或。

小 Z 想问你答案的最大值是多少。

输入描述:

第一行，输入 n,m 。

接下来 n 行 m 列，输入这个网格。

输出描述:

输出答案的最大值。

分析：

“每个位置需要从上下左右四个方向中选择互相垂直的两个” 也就是说每个位置在水平方向选一个方向并在竖直方向选一个方向.

由于在水平方向上选 与 在竖直方向上选是独立且对称的，所以只需要解决如何在水平方向上选.

显然 dp.
设 表示点 选择了左边的第 行最大值， 表示点 选择了右边的第 行最大值.

答案即为 .

代码实现：

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef double db;
typedef long double ldb;

const int M = (int)1e3;
const int N = (int)3e3;
const ll inf = 0x3f3f3f3f3f3f3f3f;
const double eps = 1e-6;
const ll mod = (ll)998244353;

int a[M + 5][M + 5];
int f[M + 5][2];

inline int w(int n)
{
    int ans = n;
    while(n)
    {
        if(n & 1) ++ans;
        n >>= 1;
    }
    return ans;
}

void work()
{
    int n, m; scanf("%d %d", &n, &m);
    for(int i = 1; i <= n; ++i)
    {
        for(int j = 1; j <= m; ++j)
        {
            scanf("%d", &a[i][j]);
        }
    }

    int ans = 0;

    for(int i = 1; i <= n; ++i)
    {
        f[1][0] = f[1][1] = 0;
        for(int j = 2; j <= m; ++j)
        {
            f[j][0] = max(f[j - 1][0], f[j - 1][1] + w(a[i][j - 1]^a[i][j]));
            f[j][1] = max(f[j - 1][0], f[j - 1][1]);
        }
        ans += max(f[m][0], f[m][1]);
    }

    for(int i = 1; i <= m; ++i)
    {
        f[1][0] = f[1][1] = 0;
        for(int j = 2; j <= n; ++j)
        {
            f[j][0] = max(f[j - 1][0], f[j - 1][1] + w(a[j - 1][i]^a[j][i]));
            f[j][1] = max(f[j - 1][0], f[j - 1][1]);
        }
        ans += max(f[n][0], f[n][1]);
    }
    printf("%d\n", ans);
}

int main()
{
//    freopen("input.txt", "r", stdin);
//    freopen("output.txt", "w", stdout);
//    int T; scanf("%d", &T);
//    while(T--) work();
    work();
//    cerr << 1.0 * clock() / CLOCKS_PER_SEC << "\n";
    return 0;
}

F 组合数问题

题目描述

小 M 很喜欢组合数。

小 Z 给了她一个数 n （n为偶数），让她计算 ，小 M 一下子就秒掉了，觉得题好简单。

因此，小 Z 给了她一个难题：给定一个数 n （n 是4的倍数），计算 ，答案对 998244353 取模。

小 M 不会做，请你来帮帮她吧！

输入描述:

输入一个数 n 。

输出描述:

输出答案对 998244353 取模的值。

分析：

杜教筛BM YYDS!（笑

代码实现：

#include <bits/stdc++.h>

using namespace std;
typedef vector<long long> VI;
typedef long long ll;
const ll mod=998244353;
ll powmod(ll a,ll b)
{
    ll res=1;
    a%=mod;
    assert(b>=0);
    for(; b; b>>=1)
    {
        if(b&1)res=res*a%mod;
        a=a*a%mod;
    }
    return res;
}
namespace linear_seq
{
#define rep(i,a,n) for (long long i=a;i<n;i++)
#define pb push_back
#define SZ(x) ((long long)(x).size())
const long long N=10010;
ll res[N],base[N],_c[N],_md[N];

vector<long long> Md;
void mul(ll *a,ll *b,long long k)
{
    rep(i,0,k+k) _c[i]=0;
    rep(i,0,k) if (a[i]) rep(j,0,k)
        _c[i+j]=(_c[i+j]+a[i]*b[j])%mod;
    for (long long i=k+k-1; i>=k; i--) if (_c[i])
            rep(j,0,SZ(Md)) _c[i-k+Md[j]]=(_c[i-k+Md[j]]-_c[i]*_md[Md[j]])%mod;
    rep(i,0,k) a[i]=_c[i];
}
long long solve(ll n,VI a,VI b)
{
    // a 系数 b 初值 b[n+1]=a[0]*b[n]+...
    //        printf("%d\n",SZ(b));
    ll ans=0,pnt=0;
    long long k=SZ(a);
    assert(SZ(a)==SZ(b));
    rep(i,0,k) _md[k-1-i]=-a[i];
    _md[k]=1;
    Md.clear();
    rep(i,0,k) if (_md[i]!=0) Md.push_back(i);
    rep(i,0,k) res[i]=base[i]=0;
    res[0]=1;
    while ((1ll<<pnt)<=n) pnt++;
    for (long long p=pnt; p>=0; p--)
    {
        mul(res,res,k);
        if ((n>>p)&1)
        {
            for (long long i=k-1; i>=0; i--) res[i+1]=res[i];
            res[0]=0;
            rep(j,0,SZ(Md)) res[Md[j]]=(res[Md[j]]-res[k]*_md[Md[j]])%mod;
        }
    }
    rep(i,0,k) ans=(ans+res[i]*b[i])%mod;
    if (ans<0) ans+=mod;
    return ans;
}
VI BM(VI s)
{
    VI C(1,1),B(1,1);
    long long L=0,m=1,b=1;
    rep(n,0,SZ(s))
    {
        ll d=0;
        rep(i,0,L+1) d=(d+(ll)C[i]*s[n-i])%mod;
        if (d==0) ++m;
        else if (2*L<=n)
        {
            VI T=C;
            ll c=mod-d*powmod(b,mod-2)%mod;
            while (SZ(C)<SZ(B)+m) C.pb(0);
            rep(i,0,SZ(B)) C[i+m]=(C[i+m]+c*B[i])%mod;
            L=n+1-L;
            B=T;
            b=d;
            m=1;
        }
        else
        {
            ll c=mod-d*powmod(b,mod-2)%mod;
            while (SZ(C)<SZ(B)+m) C.pb(0);
            rep(i,0,SZ(B)) C[i+m]=(C[i+m]+c*B[i])%mod;
            ++m;
        }
    }
    return C;
}
long long gao(VI a,ll n)
{
    VI c=BM(a);
    c.erase(c.begin());
    rep(i,0,SZ(c)) c[i]=(mod-c[i])%mod;
    return solve(n,c,VI(a.begin(),a.begin()+SZ(c)));
}
};

int main()
{
    long long n;
    while(~scanf("%lld", &n))
    {
        n /= 4;
        printf("%lld\n",linear_seq::gao(VI{1,2,72,992,16512,261632},
                                         n));
    }
}

G 机器人

题目描述

有 n 个机器人，每个机器人会读入一个 x ，并返回 ax+b 。

现在银临姐姐手里有一个数 x ，她想将机器人按某种顺序排列，使得最终返回得到的 x 尽可能大。

但是计算量太大啦，请你编个程序帮帮她吧。

输入描述:

第一行读入 n,x ，接下来 n 行依次输入 。

输出描述:

输出最大值。

分析：

这题可以贪心也可以状压 dp.

因此这里使用了模拟退火（？

代码实现：

#include <bits/stdc++.h>
using namespace std;

typedef __int128 ll;
typedef unsigned long long ull;
typedef double db;
typedef long double ldb;

const int M = (int)1e5;
const int N = (int)1e2;
const ll inf = 0x3f3f3f3f3f3f3f3f;
const double eps = 1e-6;
const ll mod = (ll)998244353;

int n, x;
int a[25], b[25];

ll cal()
{
    ll ans = x;
    for(int i = 1; i <= n; ++i) ans = ans * a[i] + b[i];
    return ans;
}

double Rand(double l, double r)
{
    return (double)rand() / RAND_MAX * (r - l) + l;
}

ll sa()
{
    ll ans = cal();
    for(double T = 1e3; T > 1e-2; T *= 0.995)
    {
        int x = 1, y = 1;
        while(x == y)
        {
            x = rand() % n + 1, y = rand() % n + 1;
        }
        double dt = cal();
        swap(a[x], a[y]), swap(b[x], b[y]);
        dt -= cal();
        if(exp(-dt / T) < Rand(0, 1)) swap(a[x], a[y]), swap(b[x], b[y]);
    }
    return cal();
}

void print(ll x)
{
    if(x < 0)
    {
        putchar('-');
        print(-x);
    }
    if(x > 9) print(x / 10);
    putchar(x % 10 + '0');
}

int id[25];

ll cal2()
{
    ll ans = x;
    for(int i = 1; i <= n; ++i) ans = ans * a[id[i]] + b[id[i]];
    return ans;
}

void work()
{
    scanf("%d %d", &n, &x);
    for(int i = 1; i <= n; ++i) scanf("%d %d", &a[i], &b[i]), id[i] = i;
    if(n <= 10)
    {
        ll ans = 0;
        do
        {
            ans = max(ans, cal2());
        }while(next_permutation(id + 1, id + n + 1));
        print(ans); putchar('\n');
    }
    else
    {
        ll ans = 0;
        while(1.0 * clock() / CLOCKS_PER_SEC < 2.0) ans = max(ans, sa());
        print(ans); putchar('\n');
    }
}

/**
2207528421052631578947368420
2207528421052631578947368420
**/

int main()
{
//    freopen("input.txt", "r", stdin);
//    freopen("output.txt", "w", stdout);
//    int T; scanf("%d", &T);
//    while(T--) work();
    srand(time(NULL));
    work();
    cerr << 1.0 * clock() / CLOCKS_PER_SEC << "\n";
    return 0;
}

H 动态最小生成树

题目描述

小 Z 喜欢最小生成树。

小 Z 有一张 个点 条边的图，每条边连接点 ，边权为 。他想进行 次操作，有如下两种类型：

修改第 条边为连接点 ，边权为 ；
查询只用编号在 范围内的边，得到的最小生成树权值是多少。
由于修改和查询量实在是太大了，小 Z 想请你用程序帮他实现一下。

输入描述:

第一行，输入 n,m,q 。

接下来 m 行，输入 。

接下来 q 行，读入 opt ，若 opt=1 则继续读入 x,y,z,t ，否则读入 l,r 。

输出描述:

对于每次询问，输出最小生成树权值。如果无解，输出 Impossible 。

分析：

赛时暴力给艹过去了....

补一下正解（好像是个经典题：动态最小生成树）

线段树维护边，每个节点存的是当前边区间的最小生成树的边

在 push_up 的时候可以用归并排序合并.

代码实现：

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef double db;
typedef long double ldb;

const int M = (int)3e4;
const int N = (int)2e2;
const ll inf = 0x3f3f3f3f3f3f3f3f;
const double eps = 1e-6;
const ll mod = (ll)998244353;

int n, m, q;
int fa[N + 5];

struct enode
{
    int u, v, w;
} Edge[M + 5];

struct tnode
{
    int len, w, id[N + 5];
    tnode() = default;
    tnode(const tnode& b)
    {
        this->len = b.len;
        this->w = b.w;
        for(int i = 1; i <= this->len; ++i)
        {
            this->id[i] = b.id[i];
        }
    }
} tree[M * 8 + 5];

inline int lc(int k) {return k<<1;}
inline int rc(int k) {return k<<1|1;}

int tmp[M + 5];
tnode ans;

int tofind(int x)
{
    if(x == fa[x]) return x;
    return fa[x] = tofind(fa[x]);
}

void push_up(tnode& u, const tnode& s1, const tnode& s2, bool f = 0)
{
    int len = 0, p1 = 1, p2 = 1;
    while(p1 <= s1.len && p2 <= s2.len)
    {
        if(Edge[s1.id[p1]].w <= Edge[s2.id[p2]].w) tmp[++len] = s1.id[p1++];
        else                                       tmp[++len] = s2.id[p2++];
    }
    while(p1 <= s1.len)   tmp[++len] = s1.id[p1++];
    while(p2 <= s2.len)   tmp[++len] = s2.id[p2++];
    for(int i = 1; i <= n; ++i) fa[i] = i;
    u.len = u.w = 0;
    for(int i = 1, a, b; i <= len; ++i)
    {
        a = tofind(Edge[tmp[i]].u), b = tofind(Edge[tmp[i]].v);
        if(a != b)
        {
            fa[a] = b;
            u.id[++u.len] = tmp[i];
            u.w += Edge[tmp[i]].w;
        }
    }
}

void build(int k, int l, int r)
{
    if(l == r)
    {
        tree[k].id[tree[k].len = 1] = l;
        tree[k].w = Edge[l].w;
        return;
    }
    int mid = (l + r) >> 1;
    build(lc(k), l, mid);
    build(rc(k), mid + 1, r);
    push_up(tree[k], tree[lc(k)], tree[rc(k)]);
}

void update(int k, int l, int r, int a)
{
    if(l == r) return;
    int mid = (l + r) >> 1;
    if(a <= mid)    update(lc(k), l, mid, a);
    else            update(rc(k), mid + 1, r, a);
    push_up(tree[k], tree[lc(k)], tree[rc(k)]);
}

void query(int k, int l, int r, int a, int b)
{
    if(l >= a && r <= b)
    {
        push_up(ans, tnode(ans), tree[k], 1);
        return;
    }
    int mid = (l + r) >> 1;
    if(a <= mid)    query(lc(k), l, mid, a, b);
    if(mid < b)     query(rc(k), mid + 1, r, a, b);
}

void work()
{
    scanf("%d %d %d", &n, &m, &q);
    for(int i = 1; i <= m; ++i) scanf("%d %d %d", &Edge[i].u, &Edge[i].v, &Edge[i].w);
    build(1, 1, m);
    int op, x, y, z, t, l, r;
    for(int i = 1; i <= q; ++i)
    {
        scanf("%d", &op);
        if(op == 1)
        {
            scanf("%d %d %d %d", &x, &y, &z, &t);
            Edge[x].u = y, Edge[x].v = z, Edge[x].w = t;
            update(1, 1, m, x);
        }
        else
        {
            scanf("%d %d", &l, &r);
            ans.len = ans.w = 0;
            query(1, 1, m, l, r);
            if(ans.len == n - 1)    printf("%d\n", ans.w);
            else                    printf("Impossible\n");
        }
    }
}

int main()
{
//    freopen("input.txt", "r", stdin);
//    freopen("output.txt", "w", stdout);
//    int T; scanf("%d", &T);
//    while(T--) work();
    work();
//    cerr << 1.0 * clock() / CLOCKS_PER_SEC << "\n";
    return 0;
}

I 贪吃蛇

题目描述

无限增长的贪吃蛇小游戏：

在一个n*m的迷宫中，有一条小蛇，地图中有很多围墙，猥琐的出题者用“#”表示，而可以走的路用“.”表示，小蛇他随机出生在一个点上，出生点表示为“S”，他想抵达的终点表示为“E”，小蛇有一个奇怪的能力，他每走一格便会增长一格，即他走了一格后，他的尾巴不会缩回。

小蛇想知道他怎么到达他想去的地方，请你帮助他。

PS：每格长1米，贪吃蛇规定不能撞墙，不能咬自己的身体。

输入描述:

第一行：输入N,M；

第二行：输入S的坐标Xs，Ys，E的坐标Xe，Ye;

后面的N行：

每行输入M个数，描述每一行的情况。

输出描述:

输出一个数，小蛇到达终点的最短距离（单位：cm），若无法达到，输出-1

分析：

直接 bfs.

代码实现：

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef double db;
typedef long double ldb;

const int M = (int)1e5;
const int N = (int)1e2;
const ll inf = 0x3f3f3f3f3f3f3f3f;
const double eps = 1e-6;
const ll mod = (ll)998244353;

int n, m;
int xs, ys, xe, ye;
char s[N + 5][N + 5];
int vis[N + 5][N + 5];

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

struct node
{
    int x, y;
    node(int _x = 0, int _y = 0): x(_x), y(_y){}
};

queue<node> q;

int bfs(int x, int y)
{
    vis[x][y] = 1;
    q.push(node(x, y));
    while(!q.empty())
    {
        node u = q.front(); q.pop();
        int x = u.x, y = u.y;
        if(x == xe && y == ye) return (vis[x][y] - 1) * 100;
        for(int i = 0; i < 4; ++i)
        {
            int xx = x + dx[i], yy = y + dy[i];
            if(xx < 1 || xx > n || yy < 1 || yy > m || s[xx][yy] == '#') continue;
            if(!vis[xx][yy])
            {
                vis[xx][yy] = vis[x][y] + 1;
                q.push(node(xx, yy));
            }
        }
    }
    return -1;
}

void work()
{
    scanf("%d %d", &n, &m);
    scanf("%d %d %d %d", &xs, &ys, &xe, &ye);
    for(int i = 1; i <= n; ++i) scanf("%s", s[i] + 1);
    int ans = bfs(xs, ys);
    printf("%d\n", ans);
}

int main()
{
//    freopen("input.txt", "r", stdin);
//    freopen("output.txt", "w", stdout);
//    int T; scanf("%d", &T);
//    while(T--) work();
    work();
//    cerr << 1.0 * clock() / CLOCKS_PER_SEC << "\n";
    return 0;
}

J 天空之城

题目描述

天空之城有5个小镇，名字分别为Ada, Aed, Akk, Orz, Apq，他们也有相互的路径长度。

希达早已期盼着天空之城，如今她登上了天空之城，就想走遍天空之城的每一个城市，但是她希望自己走的路的长度越小越好，以节省体力和节约时间。

巴鲁同意了，但由于他是主力（男孩子嘛），需要帮希达计算出走遍所有城市的最短路径长度。

由于天空之城具有魔力，如果希达想再走一次自己之前走过的路，则她可以在这条路上不花费任何时间。

但是天空之城的城市太多了，他实在计算不过来，只得请你来帮帮忙了。

输入描述:

第一行，输入n，q, 表示有n个城市，q条边；

第二行，输入一个名字tmp，表示希达想要从tmp城市开始行走；

接下来q行，每行输入两个名字a,b和一个数字val, 表示a城市与b城市之间的距离为val.(注意可能有重边和自环)

输出描述:

帮助巴鲁计算出最短的路径长度，如果无法走遍所有城市，输出“No!”。

分析：

最小生成树模板题.

代码实现：

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef double db;
typedef long double ldb;

const int M = (int)1e5;
const int N = (int)1e2;
const ll inf = 0x3f3f3f3f3f3f3f3f;
const double eps = 1e-6;
const ll mod = (ll)998244353;

int n, q;
int idcnt;
map<string, int> mp;
int fa[5000 + 5];

struct enode
{
    int u, v, w;
    enode(int _u = 0, int _v = 0, int _w = 0): u(_u), v(_v), w(_w){}
    bool operator<(const enode& b)const
    {
        return w < b.w;
    }
} Edge[200000 + 5];

inline int id(const string& s)
{
    if(!mp.count(s)) mp[s] = ++idcnt;
    return mp[s];
}

int tofind(int x)
{
    if(x == fa[x]) return x;
    return fa[x] = tofind(fa[x]);
}

void kruskal(int st)
{
    ll ans = 0;
    sort(Edge + 1, Edge + q + 1);
    for(int i = 1, a, b; i <= q; ++i)
    {
        a = tofind(Edge[i].u);
        b = tofind(Edge[i].v);
        if(a != b)
        {
            fa[a] = b;
            ans += Edge[i].w;
        }
    }
    for(int i = 1; i <= n; ++i)
    {
        if(tofind(i) != tofind(st))
        {
            cout << "No!\n";
            return;
        }
    }
    cout << ans << "\n";
    assert(idcnt <= n);
}

void work()
{
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    while(cin >> n >> q)
    {
        mp.clear();
        idcnt = 0;
        for(int i = 1; i <= n; ++i) fa[i] = i;

        string st, a, b; cin >> st; id(st);
        for(int i = 1, ida, idb, w; i <= q; ++i)
        {
            cin >> a >> b >> w;
            ida = id(a), idb = id(b);
            Edge[i].u = ida, Edge[i].v = idb, Edge[i].w = w;
        }
        kruskal(id(st));
    }
}

int main()
{
//    freopen("input.txt", "r", stdin);
//    freopen("output.txt", "w", stdout);
//    int T; scanf("%d", &T);
//    while(T--) work();
    work();
//    cerr << 1.0 * clock() / CLOCKS_PER_SEC << "\n";
    return 0;
}
全部评论

相关推荐

头像
GaoMemg
04-26 13:39
门头沟学院 地理科学类
点赞 评论 收藏
转发
头像
纠结的牛牛在看面经
04-25 14:43
电子科技大学 电子信息类
点赞 评论 收藏
转发
头像
找实习的机械生
03-27 08:09
西安交通大学 机械类
点赞 评论 收藏
转发
头像
fireflies2000
04-26 14:54
已编辑
西安交通大学 计算机类
点赞 评论 收藏
转发
点赞 收藏 评论
分享

全站热榜

正在热议
# 牛友的五一计划 #
28910次浏览 498人参与
# 市场营销面经 #
1897次浏览 82人参与
# 牛客帮帮团来啦！有问必答 #
426950次浏览 8096人参与
# 许愿池 #
67586次浏览 1489人参与
# 晒一晒我的offer #
2878492次浏览 50305人参与
# 2022届毕业生现状 #
287972次浏览 4123人参与
# 实习好累，可以辞职全力准备秋招吗 #
2897次浏览 61人参与
# 你的秋招进展怎么样了 #
451710次浏览 13002人参与
# 如何看待offer收割机的行为 #
199965次浏览 3044人参与
# 互联网公司评价 #
64420次浏览 913人参与
# 非技术岗薪资爆料 #
11633次浏览 225人参与
# 硬件人的春招flag #
14838次浏览 204人参与
# 双非本科求职如何逆袭 #
176704次浏览 2648人参与
# 找工作，你会甘心进小厂还是猛冲大厂 #
26356次浏览 262人参与
# 23届的你们都什么时候入职？ #
77646次浏览 692人参与
# 产品实习，你更倾向大公司or小公司 #
31802次浏览 500人参与
# 秋招开了，你想投哪些公司呢 #
103026次浏览 3136人参与
# 浅聊一下我实习的辛苦费 #
71959次浏览 656人参与
# 提前批真的不会影响正式批吗 #
18426次浏览 233人参与
# 在国企工作的人，躺平了吗？ #
75068次浏览 922人参与
牛客网
牛客企业服务