dodola · blog

🫟2024牛客暑假多校训练营Day7||补题

1,455 words5 min read#算法#竞赛编程#牛客多校#补题记录算法2024 牛客暑假多校训练营 7/9
Categories算法Series2024 牛客暑假多校训练营 7/9

I-Fight Against the Monster

题意

使用机器对抗怪兽，一台机器有以下两种功能：

  • 战斗：使怪兽血量减少1点，后技巧丧失所有功能
  • 创造：需要mm台机器同时使用，创造出kk台新机器，每台机器仅能使用一次创造功能。

怪兽初始血量是hh，血量下降至00​时死亡，请计算初始最少需要多少机器才能打败怪兽。

数据范围

  • 1≤t≤2×1051\leq t\leq 2\times 10^5
  • 1≤k≤m≤1061\leq k\leq m \leq 10^6
  • 0≤h≤1090\leq h\leq 10^9

思路

根据机器的功能特点，我们尽可能让每台机器进行创造。若最初有xx台机器，则进行一次创造之后拥有x+k(x≥m)x+k(x\ge m)台机器，其中有k+x−mk+x-m台机器拥有创造能力，最多拥有的机器数目是直到拥有创造能力的机器数目低于mm时拥有的机器数目。可以发现除了第一次使用mm台机器进行创造，之后使用mm台机器进行创造时，可以使用kk台新制造的机器加上m−km-k台最初拥有的机器进行创造，那么最多拥有的机器数目是：

f(x)={xx<mx+k×(⌊(x−m)/(m−k)⌋+1)f(x)= \begin{cases} x\quad x\lt m\\ x+k\times (\lfloor (x-m)/(m-k)\rfloor+1) \end{cases}

二分寻找符合条件的最少的最初机器数即可。

不过队友在赛时提供了一种更加直观不必二分求解的方法：

怪兽每受到mm点攻击时，可以将这mm点攻击看成是花费m−km-k台机器，在保证至少能发出一次mm点攻击时，最初的机器数目要有mm个，同时，怪物剩余不足mm点血量时，只能再用额外的机器进行攻击。相关代码也贴在下面了。

代码

// 二分
ll m, k, h;
ll getmax(ll x) {
    if (x < m)return x;
    return x + k * ((x - m) / (m - k) + 1);
}


void solve() {
    cin >> m >> k >> h;
    if (m == k || h <= m) {
        cout << min(h, m) << "\n";
        return;
    }
    ll l = m, r = h + 1;
    while (l < r) {// [l,r)
        ll x = (l + r) >> 1;
        if (h > getmax(x)) {
            l = x + 1;
        }
        else {
            r = x;
        }
    }
    cout << l << "\n";
}


// 直接求解
void solve(){
    cin >> m >> k >> h;
    ll ans = (h / m) * (m - k);
    if(h / m) ans += max(h % m, k);
    else ans = h;
    cout << ans << "\n";
}

J-Ball

题意

坐标轴上有一根木棒，左端点在原点(0,0)(0,0)处，垂直yy轴放置，右端点在(l,0)(l,0)处，在坐标轴上有一个点P(x,y)P(x,y)，询问在木棒上是否有一个点，满足当木棒绕着该点旋转时可以击中点PP，如有则输出该点坐标，若无输出−1-1。

数据范围

  • 1≤T≤1041\leq T\leq 10^4
  • 1≤l≤1051\leq l\leq 10^5
  • −105≤x,y≤105-10^5\leq x,y \leq 10^5

思路

木棒可以到达的最大范围是以(0,0)(0,0)为旋转中心和以(l,0)(l,0)为旋转中心的旋转范围的并集。

代码

ld sqr(ld dx, ld dy) {
    return sqrt(dx * dx + dy * dy);
}


ld dist(ll x1, ll y1, ll x2, ll y2) {
    return sqr(1.0 * (x1 - x2), 1.0 * (y1 - y2));
}


void solve() {
    ll l, x, y;cin >> l >> x >> y;
    ld d1 = dist(0, 0, x, y), d2 = dist(l, 0, x, y);
    if (d1 > l && d2 > l) {
        cout << "No\n";return;
    }
    cout << "Yes\n";
    if (d1 <= l) {
        cout << "0.00000000\n";
    }
    else if (d2 <= l) {
        printf("%.8lf\n", 1.0 * l);
    }
}

K-Strings, Subsequences, Reversed Subsequences, Prefixes

题意

给出一个字符串ss和一个字符串tt，要求在ss中寻找以tt为前缀，以tt的翻转串为后缀的ss的子串，求这样的本质不同的子串数目。

数据范围

  • 1≤n,m≤1061\leq n,m \leq 10^6
  • si,ti∈[a,z]s_i,t_i\in [a,z]

思路

前缀和后缀可以直接暴力从ss最左侧和最右侧枚举，前后缀还要加上有公共重叠部分的数目，之后的问题就是如何计算中间部分的本质不同的子串了。

另中间部分的字符串为s′s'，在s′s'上，设f[i]f[i]表示到第ii位时拥有多少个本质不同的子串，将a[i]a[i]加入时，a[i]a[i]可以加入在f[i−1]f[i-1]时的所有本质不同的子串的后面，这样形成的字符串中，与原来答案重复的是上一个字符a[i]a[i]加入时拥有的本质不同的字符串数目，所以转移方程是这样：

f[i]=2×f[i−1]−f[last[a[i]]−1]f[i]=2\times f[i-1]-f[last[a[i]]-1]

在处理前后缀的时候，当前后缀所处的最小区域有相交时，枚举允许重叠的长度时要至少从重叠部分的长度开始进行枚举。

代码

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef double ld;
const ll mo998 = 998244353;
const ll mo109 = 1000000007;
const int maxn = 1e5 + 50;


void solve() {
    ll n, m;cin >> n >> m;
    string s, t;cin >> s >> t;
    ll l = 0, r = n - 1;
    ll p0 = 0;
    while (p0 < m && l < n) {
        if (t[p0] == s[l]) {
            p0++;
        }
        l++;
    }
    if (p0 != m) {
        cout << 0 << "\n";
        return;
    }
    p0 = 0;
    ll pos = 0;
    while (p0 < m && r >= 0) {
        if (t[p0] == s[r]) {
            p0++;
            if (r >= l)pos = p0; // 独自能自匹配的长度
        }
        r--;
    }
    if (p0 != m) {
        cout << 0 << "\n";
        return;
    }
    // 处理回文
    ll cnt = 0;
    vector<ll>h1(m + 5), h2(m + 5), p(m + 5);
    ll b = 131;
    t = " " + t;
    p[0] = 1;
    for (int i = 1;i <= m;i++) {
        h1[i] = h1[i - 1] * b + t[i];
        h2[i] = h2[i - 1] * b + t[m - i + 1];
        p[i] = p[i - 1] * b;
    }
    for (int i = 1;i <= m;i++) { // 判断长度为i的前后缀是否相同
        ll hh1 = h1[m] - h1[m - i] * p[i];
        ll hh2 = h2[i] - h2[0] * p[i];
        if (hh1 == hh2)cnt++;
    }


    int len = r - l + 1;
    if (len < 0) {
        ll ans = 0;
        len = m - pos;
        for (ll i = len;i <= m;i++) {
            ll hh1 = h1[m] - h1[m - i] * p[i];
            ll hh2 = h2[i] - h2[0] * p[i];
            if (hh1 == hh2)ans++;
        }
        cout << ans << "\n";
        return;
    }
    string a = s.substr(l, len);
    vector<ll>f(len + 5, 0), las(30, -1);
    a = " " + a;
    f[0] = 1;
    for (ll i = 1;i <= len;i++) {
        int c = a[i] - 'a';
        if (las[c] != -1)
            f[i] = (2 * f[i - 1] % mo109 - f[las[c] - 1] + mo109) % mo109;
        else
            f[i] = 2 * f[i - 1] % mo109;
        las[c] = i;
    }
    cout << f[len] + cnt << "\n";
}


int main() {
    int _ = 1;
    while (_--)
        solve();


    return 0;
}