牛客小白月赛60

A. 小竹与妈妈

• 题意
  • ay+b=x, 已知a,b,x,求y
• 题解
  • 显然小竹的年龄为 直接输出即可。
• 代码

#include <bits/stdc++.h>
using namespace std;
int main()
{
    long long a, b, x;
    scanf("%lld%lld%lld", &a, &b, &x);
    printf("%lld\n", (x - b) / a);
    return 0;
}

B.走丢的小竹

• 题意

  • 有 n 个出口，每个出口都连着 m 个房间其中一个，有 q 次询问，每次都问如果不能去 x 号房间的话，有多少出口能走。

    1≤n,m,q≤105

• 题解

  • 记录每个房间有多少个出口连接记为,每次询问输出即可。

• 代码

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
int a[N];
int main()
{
    int n, m, q;
    scanf("%d%d%d", &n, &m, &q);
    map<int, int> mp;
    // set<int> s;
    for (int i = 1; i <= n; i++)
    {
        scanf("%d", &a[i]);
        mp[a[i]]++;
        // s.insert(a[i]);
    }
    while (q--)
    {
        int ans;
        scanf("%d", &ans);
        printf("%d\n", n - mp[ans]);
    }
    return 0;
}

C.小竹关禁闭

• 题意

  • 有 n 个绳子，第 i 条绳子长度为 ai ，当你使用第 i 条绳子的时候，后面的 k 条绳子就都不能用了，问能拿到的所有绳子长度总和最大是多少。

• 题解

  • 用一个 的 即可解决该问题。
    设 为选择前 个数绳子的最大长度。

    很容易能列出 。

    由于允许 通过,直接模拟该过程即。最后的答案为。

• 代码1 从前往后推

  #include <bits/stdc++.h>
  using namespace std;
  int n, k;
  int a[2005];
  int dp[2005];
  int ans;
  
  int main()
  {
      cin >> n >> k;
      for (int i = 1; i <= n; ++i)
      {
          cin >> a[i];
      }
      for (int i = 1; i <= n; ++i)
          for (int j = 0; j <= max(0, i - k - 1); ++j)
          {
              dp[i] = max(dp[j] + a[i], dp[i]);
              ans = max(ans, dp[i]);
          }
      cout << ans << '\n';
      return 0;
  }

• 代码2 从后往前推

#include <bits/stdc++.h> 
using namespace std;
const int N = 2e3 + 10;
int a[N];
int dp[N];
int main()
{
    int n, k;
    scanf("%d%d", &n, &k);
    for (int i = 1; i <= n; i++)
    {
        scanf("%d", &a[i]);
    }
    // dp[0][0] = dp[0][1] = 0;
    // dp[1][1] = a[1];
    // dp[1][0] = 0;
    int maxn = 0;
    for (int i = n; i >= 1; i--)
    {
        dp[i] = max(dp[i + 1], dp[min(n + 1, i + k + 1)] + a[i]);
        maxn = max(maxn, dp[i]);
    }
    printf("%d\n", maxn);
    return 0;
}

D. 游戏购买！

• 题意

  • 有一个 n∗m 的矩阵，矩阵上有数值。玩家当前分数为 0 ，想从 (sx,sy) 走到 (ex,ey) ，每一步都可以将自己的分数更新为当前所在位置的数值。问想从(sx,sy) 走到 (ex,ey) ，且分数超过 x 需要的最小步数是多少。

• 题解

  • 从起点开始 求出起点到每个位置的最短路,从终点开始同样跑一遍 求出终点到每个位置的最短路.对于每一个拥有刺激度高于 游戏的店铺 ,要经过该店铺的答案即为起点到 的最短路,加上终点到 的最短路

• 代码

#include <bits/stdc++.h>
using namespace std;
#pragma GCC optimize(2)
const int N = 2e3 + 10;
int a[N][N];
int ans;
int n, m;
int sx, sy, ex, ey;
int sum = 0;
int dx[] = {0, 0, 1, -1};
int dy[] = {1, -1, 0, 0};
int vis[N][N];
int xx, yy;
int dis1[N][N];
int dis2[N][N];
struct node
{
    int x, y, cnt;
};
void bfs1(int x, int y)
{
    dis1[x][y] = 0;
    queue<node> q;
    q.push({x, y, 0});
    vis[x][y] = 1;
    while (!q.empty())
    {
        node t = q.front();
        q.pop();
        for (int i = 0; i < 4; i++)
        {
            int xx = t.x + dx[i];
            int yy = t.y + dy[i];
            if (vis[xx][yy] == 0 && xx >= 1 && xx <= n && yy >= 1 && yy <= m && a[xx][yy] != -1)
            {
                vis[xx][yy] = 1;
                node p;
                p.x = xx;
                p.y = yy;
                p.cnt = t.cnt + 1;
                dis1[xx][yy] = p.cnt;
                q.push(p);
            }
        }
    }
}
void bfs2(int x, int y)
{
    dis2[x][y] = 0;
    queue<node> q;
    q.push({x, y, 0});
    vis[x][y] = 1;
    while (!q.empty())
    {
        node t = q.front();
        q.pop();
        for (int i = 0; i < 4; i++)
        {
            int xx = t.x + dx[i];
            int yy = t.y + dy[i];
            if (vis[xx][yy] == 0 && xx >= 1 && xx <= n && yy >= 1 && yy <= m && a[xx][yy] != -1)
            {
                vis[xx][yy] = 1;
                node p;
                p.x = xx;
                p.y = yy;
                p.cnt = t.cnt + 1;
                dis2[xx][yy] = p.cnt;
                q.push(p);
            }
        }
    }
}
int main()
{
    scanf("%d%d%d", &n, &m, &ans);
    scanf("%d%d%d%d", &sx, &sy, &ex, &ey);
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= m; j++)
        {
            scanf("%d", &a[i][j]);
        }
    }
    memset(vis, 0, sizeof(vis));
    bfs1(sx, sy);
    memset(vis, 0, sizeof(vis));
    bfs2(ex, ey);
    int minn = 0x3f3f3f3f;
    int flag = 0;
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= m; j++)
        {
            if (a[i][j] > ans)
            {
                if (dis1[i][j] == 0 || dis2[i][j] == 0)
                {
                    continue;
                }
                else
                {
                    flag = 1;
                    minn = min(minn, dis1[i][j] + dis2[i][j]);
                }
            }
        }
    }
    if (flag == 1)
    {
        printf("%d\n", minn);
    }
    else
    {
        printf("-1\n");
    }
    return 0;
}

E.寻找小竹！

• 题意

  • 给定树上 n 个节点和 n−1 条边，如果一条边上的两个点存在至少两个不同的质因子，称这两个节点为共同优雅的。问整棵树上包含节点最多的共有优雅连通块有多少个节点。

• 题解

  • 相邻结点满足有至少两个不同的共同质因子,也就相当于,相邻两个结点的 满足不为任何质数的幂次,且不为1

    我们可以把所有质数的幂次使用一个标记数组 标记起来,然后进行树形dp

    设 为以 为根的最大优雅联通块,设 为 的子节点的集合，则

    

• 代码

#include <bits/stdc++.h>
using namespace std;
const int N = 5e6 + 10;
int prime[N], cnt;
int st[N];
int a[N];
int son[N];
vector<int> e[N];
int vis[N];
int maxn = 0;
void dfs(int u, int fa)
{
    son[u] = 1;
    for (auto t : e[u])
    {
        if (t == fa)
        {
            continue;
        }
        dfs(t, u);
        if (st[__gcd(a[u], a[t])] == 0)
        {
            son[u] += son[t];
        }
    }
    // maxn = max(son[u], maxn);
}
void init(int n)
{
    st[1] = 1;
    for (int i = 2; i <= n; i++)
    {
        if (!vis[i])
        {
            for (int j = i * 2; j <= n; j += i)
            {
                vis[j] = 1;
            }
            for (long long j = i; j <= n; j *= i)
            {
                st[j] = 1;
            }
        }
    }
}
int main()
{
    init(N);
    int n;
    scanf("%d", &n);
    for (int i = 1; i <= n; i++)
    {
        scanf("%d", &a[i]);
    }
    int p, q;
    for (int i = 1; i <= n - 1; i++)
    {
        scanf("%d%d", &p, &q);
        e[p].push_back(q);
        e[q].push_back(p);
    }
    dfs(1, 0);
    for (int i = 1; i <= n; i++)
    {
        maxn = max(son[i], maxn);
    }
    printf("%d\n", maxn);
    return 0;
}

F.被抓住的小竹

• 题意
• 题解
  • 
• 代码

#include <bits/stdc++.h>
using namespace std;
#define ll long long
int t;
int n;
vector<int> js;
const int mod = 1e9 + 7;
ll fac[100006];
ll ifac[100006];
int maxn = 1e5 + 4;
ll ksm(ll x, ll y)
{
    ll ans = 1;
    while (y)
    {
        if (y & 1)
        {
            ans = ans * x % mod;
        }
        y >>= 1;
        x = x * x % mod;
    }
    return ans;
}
void init()
{
    fac[0] = 1;
    for (int i = 1; i <= maxn; i++)
    {
        fac[i] = fac[i - 1] * i % mod;
    }
    // ifac[1] = 1;
    // for (int i = 2; i <= maxn; i++)
    // {
    //     ifac[i] = (ll)(mod - mod / i) * ifac[mod % i] % mod;
    // }
    ifac[maxn - 1] = ksm(fac[maxn - 1], mod - 2);
    for (int i = maxn - 1; i >= 1; i--)
    {
        ifac[i - 1] = ifac[i] * i % mod;
    }
}
ll C(ll x, ll y)
{
    return fac[x] * ifac[y] % mod * ifac[x - y] % mod;
}
int main()
{
    init();
    int t;
    cin >> t;
    while (t--)
    {
        int n;
        cin >> n;
        ll ans = (((C(n + 3, 4)) % mod * fac[(n - 2)] % mod * (1ll * n * (n - 1) / 2) % mod * (1ll * n * (n - 1) / 2) % mod)) % mod;
        cout << ans << '\n';
    }
    return 0;
}