“科林明伦杯”哈尔滨理工大学第十届程序设计竞赛

A 点对最大值

对于每个点

AC代码：

typedef pair<int, int> P;
const int N = 1e6 + 10;
int n, x;

vector<P> G[N];
int dp[N]; // dp[i]:i子树价值最大链
int ans;

void add(int u, int v, int val)
{
  G[u].push_back(P(v, val));
  G[v].push_back(P(u, val));
}

void dfs(int u, int fa)
{
  int maxn = dp[u], maxx = -inf;
  rep(i, 0, G[u].size() - 1)
  {
    if (G[u][i].fi == fa)
      continue;
    int v = G[u][i].fi, val = G[u][i].se;
    dfs(v, u);
    maxx = max(maxx, val + dp[v]);
    if (maxx > maxn)
      swap(maxn, maxx);
  }
  ans = max(ans, maxx + maxn);
  dp[u] = maxn;
}

int main()
{
  int t;
  sd(t);
  while (t--)
  {
    sd(n);
    rep(i, 0, n)
    {
      G[i].clear();
    }
    ans = -inf;
    rep(i, 2, n)
    {
      int x, val;
      sdd(x, val);
      add(i, x, val);
    }
    rep(i, 1, n)
      sd(dp[i]);
    dfs(1, -1);
    pd(ans);
  }
  return 0;
}

B 减成一

每个都先减去最小的那个，然后选择没有变成

AC代码;

const int N = 1e6 + 50;
int n, m;
int a[N];
 
int main()
{
    int t;
    sd(t);
    while (t--)
    {
        sd(n);
        ll ans = 0;
        rep(i, 1, n)
        {
            sd(a[i]);
            a[i]--;
            ans += max(0, a[i] - a[i - 1]);
        }
        pld(ans);
    }
    return 0;
}

C 面积

注意精度就行。

AC代码;

int n, k;

int main()
{
  int T;
  sd(T);
  while (T--)
  {
    double x;
    cin >> x;
    double ans = x * x;
    x /= 2;
    ans += 2 * PI * x * x;
    printf("%.2lf\n",ans);
  }
  return 0;
}

D 扔硬币

当 时，题目中描述的情况是不存在的，直接输出

枚硬币一共是 种情况，去掉少于 个硬币是反面的情况,假设事件 是至少 枚硬币是反面，事件 是恰好有 枚硬币是正面，所以答案就是 ，

分子即 和 同时成立的方案数就是相当于 枚硬币里恰好有 枚硬币是正面，为 。分母用总的方案数减去不合法的情况 ， 就是有 枚硬币是反面而且 的所有情况。
答案就是 。

AC代码：

const int N = 5e5 + 50;
int n, m, k;
ll F[N], Finv[N], inv[N]; //F是阶乘，Finv是逆元的阶乘


void init()
{
  inv[1] = 1;
  for (int i = 2; i < N; i++)
  {
    inv[i] = (MOD - MOD / i) * 1ll * inv[MOD % i] % MOD;
  } //递推求逆元

  F[0] = Finv[0] = 1;
  for (int i = 1; i < N; i++)
  {
    F[i] = F[i - 1] * 1ll * i % MOD;
    Finv[i] = Finv[i - 1] * 1ll * inv[i] % MOD;
  }
}

int comb(int n, int m) //comb(n, m)就是C(n, m)
{
  if (m < 0 || m > n)
    return 0;
  return F[n] * 1ll * Finv[n - m] % MOD * Finv[m] % MOD;
}

int main()
{
  int T;
  sd(T);
  init();
  while (T--)
  {
    sddd(n, m, k);
    if (k + m > n)
    {
      puts("0");
      continue;
    }
    ll fz = comb(n, k);
    ll sum = 0;
    rep(i, 0, m - 1)
      sum = (sum + comb(n, i) % MOD) % MOD;
    ll fm = qpow(2, n, MOD) - sum;
    if (fm < 0)
      fm = (fm + MOD) % MOD;
    ll ans = fz * qpow(fm, MOD - 2, MOD) % MOD;
    pld(ans);
  }
  return 0;
}

E 赛马

田忌赛马的原题，分类讨论即可，具体看代码吧。

AC代码：

int n, k;
int a[N], b[N];

int main()
{
  int T;
  sd(T);
  while (T--)
  {
    sd(n);
    rep(i, 1, n)
      sd(a[i]);
    rep(i, 1, n)
      sd(b[i]);
    sort(a + 1, a + 1 + n);
    sort(b + 1, b + 1 + n);
    int ans = 0;
    int x1 = 1, y1 = 1;
    int g = 1;
    int x2 = n, y2 = n;
    while (g++ <= n)
    {
      if (a[x1] > b[y1])//赢一局
      {
        ans++;
        x1++;
        y1++;
      }
      else if (a[x1] < b[y1])//让最劣的马和齐王最好的马比 ，输一局
      {
        x1++;
        y2--;
      }
      else//.如果平局的话 让双方的两匹最好的马相比
      {
        if (a[x2] > b[y2])//赢一局
        {
          ans++;
          x2--;
          y2--;
        }
        else if (a[x1] < b[y2])//用最差的马和最好的比，输一局
        {
          x1++;
          y2--;
        }
      }
    }
    pd(ans);
  }
  return 0;
}

F 三角形

题解写的很好。我是打表看出来的。

三角形两边之和大于第三边， 因此不构成三角形的条件就是存在两边之和不超过另一边。 所以按照斐波那契数列的方法切割可以使得切割的段数最大，

AC代码;

const int N = 1e6 + 50;
ll f[N];
 
int main()
{
    int t;
    sd(t);
    f[1] = 1;
    rep(i, 2, 100010)
        f[i] = f[i - 1] + f[i - 2];
    while (t--)
    {
        ull n;
        cin >> n;
        int ans = 0;
        rep(i, 1, 100000)
        {
            if (n < f[i])
                break;
            else
            {
                ans++;
                n -= f[i];
            }
        }
        pd(ans);
    }
    return 0;
}

G 养花

H 直线

这个规律很好找的，标准的递推打表，然后发现规律就是 ，因为给的 比较大所以可以使用大数或者

AC代码:

inline __int128 rea()
{
  __int128 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;
}

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

const int N = 1e6 + 50;

int main()
{
  int t;
  sd(t);
  while (t--)
  {
    __int128 n = read();
    if (n < 2)
      puts("0");
    else
    {
      __int128 ans = n * (n - 1) / 2;
      print(ans);
      puts("");
    }
  }
  return 0;
}

I 字典序

J 最大值

这道题想了半天然后发现就是 中

数组代表当前字符之前的字符串中，有多大长度的相同前缀后缀。例如如果 ，代表j 之前的字符串中有最大长度为

AC代码 ；

const int N = 2e5 + 10;
int n, x;
int nxt[N];
char p[N];

void GetNext(char *p, int next[])
{
  int pLen = strlen(p);
  next[0] = -1;
  int k = -1;
  int j = 0;
  while (j < pLen)
  {
    if (k == -1 || p[j] == p[k])
    {
      ++k;
      ++j;
      next[j] = k;
    }
    else
    {
      k = next[k];
    }
  }
}

int main()
{
  int t;
  sd(t);
  while (t--)
  {
    cin >> p;
    int len = strlen(p);
    GetNext(p, nxt);
    int ans = 0;
    rep(i, 0, len)
      ans = max(ans, nxt[i]);
    pd(ans);
  }
  return 0;
}