• 2022“杭电杯” 中国大学生算法设计超级联赛（3）2 9题解

    1002-Boss Rush

    题目大意：
    Boss有H血量，现在有n个技能（1<=n<=18），每个技能都有持续伤害时间，持续时间内每秒都会造成伤害，同时释放每个技能后会进入冷却时间，冷却时间结束后才可以释放另一个技能，每个技能只能释放一次，技能在释放后就会造成伤害。问最少需要多少时间将Boss击败。

    思路：
    对于每个技能，先预处理伤害的前缀和。
    因为技能只有18个，因此可以用二进制01表示一个技能是否释放。
    但是这样无法引入时间的维度，因此考虑用二分枚举时间。
    于是用dp[i]表示i中为对应位为1的技能释放所能造成的最大伤害，冷却总时间和技能释放顺序无关，可以根据i中1的位来算出，状态转移方程也就很容易得到了。

    AC代码：

    #include 
const int N = 1e5 + 5;
using namespace std;

long long n, h;
int t[20], len[20];
long long dsum[20][N], dp[(1 << 18) + 5]; // dp[i]中为1的位表示释放了对应的技能

inline int get_t(int x)
{
    int res = 0;
    for (int i = 0; i < n; i++)
        if ((1 << i) & x) res += t[i + 1];
    return res;
}

bool check(int tm)
{
    int bit, ts;
    for (int i = 1; i < (1 << n); i++)
        dp[i] = -1;
    for (int i = 0; i < (1 << n); i++)
    {
        if (dp[i] < 0) continue;
        if (dp[i] >= h) return 1;
        ts = get_t(i);
        if (ts >= tm) continue;
        for (int j = 1; j <= n; j++)
        {
            bit = 1 << (j - 1);
            if (!(bit & i))
            {
                if (ts + len[j] <= tm)
                    dp[i | bit] = max(dp[i] + dsum[j][len[j]], dp[i | bit]);
                else
                    dp[i | bit] = max(dp[i] + dsum[j][tm - ts], dp[i | bit]);
            }
        }
    }
    return 0;
}
signed main()
{
    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    for (int i = 0; i < 20; i++)
        dsum[i][0] = 0;
    dp[0] = 0;
    int T;
    cin >> T;
    while (T--)
    {
        int tsum = 0, maxlen = 0;
        cin >> n >> h;
        for (int i = 1; i <= n; i++)
        {
            cin >> t[i] >> len[i];
            tsum += t[i];
            maxlen = max(len[i], maxlen);
            for (int j = 1; j <= len[i]; j++)
            {
                cin >> dsum[i][j];
                dsum[i][j] += dsum[i][j - 1]; //伤害前缀和
            }
        }
        int l = 1, r = tsum + maxlen + 1, mid, ans = -1;
        while (l <= r)
        {
            mid = (l + r) / 2;
            if (check(mid))
            {
                r = mid - 1;
                ans = mid;
            }
            else
                l = mid + 1;
        }
        cout << (ans == -1 ? -1 : ans - 1) << endl;
    }
    return 0;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60
    • 61
    • 62
    • 63
    • 64
    • 65
    • 66
    • 67
    • 68
    • 69
    • 70
    • 71
    • 72
    • 73
    • 74
    • 75
    • 76
    • 77
    • 78
    • 79
    • 80

    1009-Package Delivery

    题目大意：
    有n个快递，每个快递有到达时间和最迟取件时间，去一次驿站能取k件快递，问最少几次可以把快递取完。

    思路：
    可以将快递看作区间[l,r]
    贪心地想，每次选取r最小的时间点去取快递一定是最优的。
    因此分别对r和l进行排序，当取定一个ri时，选取所有l小于ri的区间，用一个堆来维护，将其中r最小的k个区间取出（也可能不足k）。然后重复以上过程直到快递取完。

    AC代码：

    #include 
const int N = 1e5 + 5;
using namespace std;

struct node
{
    int r, idx;
};
bool operator<(node a, node b) { return a.r > b.r; }
pair<int, int> p[N];
int l[N], r[N];
bool vis[N];
bool cmpl(int a, int b) { return p[a].first < p[b].first; }   //按照左端点对下标进行排序
bool cmpr(int a, int b) { return p[a].second < p[b].second; } //按照右端点对下标进行排序

void solve()
{
    int n, k, ans = 0;
    priority_queue<node> q;
    cin >> n >> k;
    for (int i = 1; i <= n; i++)
    {
        cin >> p[i].first >> p[i].second;
        l[i] = i;
        r[i] = i;
        vis[i] = 0;
    }
    sort(l + 1, l + n + 1, cmpl); //按左端点对下标进行排序
    sort(r + 1, r + n + 1, cmpr); //按右端点对下标进行排序
    for (int i = 1, j = 1; i <= n; i++)
    {
        if (vis[r[i]]) continue;
        while (j <= n && p[l[j]].first < p[r[i]].second) //将所有左端点小于当前右端点的快递入队
        {
            q.push({p[l[j]].second, l[j]});
            j++;
        }
        ans++;
        int cnt = k;
        while (q.size() && cnt--) //取出k个快递
        {
            vis[q.top().idx] = 1;
            q.pop();
        }
    }
    cout << ans << "\n";
}
signed main()
{
    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    int T;
    cin >> T;
    while (T--)
        solve();
    return 0;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56

    1011-Taxi

    题目大意：
    小Q有一张出租车会员卡，从第i个城镇到第k个城镇的减免为二者的曼哈顿距离和wk中的最小值。现在告诉你小Q位于的城镇，问接下来去哪个城镇的减免最多。

    思路：
    首先考虑没有wk限制的情况：
    那么就是求|xi - xk| + |yi - yk|的最大值。
    将其展开后得到以下式子：
    在这里插入图片描述
    那么我们只要维护xk + yk 、xk - yk 、-xk + yk 、-xk - yk 的最大值即可在O(1)的时间里得到最大的曼哈顿距离。

    现在考虑有wk限制的情况：
    首先将所有的城镇按照wk从小到大进行排序，同时维护xk + yk 、xk - yk 、-xk + yk 、-xk - yk的后缀最大值。
    记排序后第k个城镇之后的最大曼哈顿距离为d

    • 如果wk < d，那么对答案有贡献的是wk，越往后wk越大，[1,k-1]的城镇不会对答案有贡献，因此在[k+1,n]这一段中继续寻找要去的城镇。
    • 如果wk > d，那么对答案有贡献的是d，越往后wk越大，已经可以确定后面的城市对答案的最大贡献是d，因此在[1,k-1]这一段查找是否有城镇能贡献更大的值。
    • 如果wk == d，那么答案就是d，此时不管往前还是往后，对答案的贡献都是减小的。

    AC代码：

    #include 
const int N = 1e5 + 5;
using namespace std;

struct town
{
    int x, y, w;
} t[N];
bool cmp(town a, town b) { return a.w < b.w; }

int zz[N], zf[N], fz[N], ff[N]; //分别维护x+y x-y -x+y -x-y的后缀最大值

void solve()
{
    int n, q;
    cin >> n >> q;
    for (int i = 1; i <= n; i++)
        cin >> t[i].x >> t[i].y >> t[i].w;
    sort(t + 1, t + 1 + n, cmp);
    zz[n] = t[n].x + t[n].y;
    zf[n] = t[n].x - t[n].y;
    fz[n] = -t[n].x + t[n].y;
    ff[n] = -t[n].x - t[n].y;
    for (int i = n - 1; i >= 1; i--) //预处理后缀最大值
    {
        zz[i] = max(t[i].x + t[i].y, zz[i + 1]);
        zf[i] = max(t[i].x - t[i].y, zf[i + 1]);
        fz[i] = max(-t[i].x + t[i].y, fz[i + 1]);
        ff[i] = max(-t[i].x - t[i].y, ff[i + 1]);
    }
    while (q--)
    {
        int ans = 0, l = 1, r = n, mid, d, x, y;
        cin >> x >> y;
        while (l <= r)
        {
            mid = (l + r) / 2;
            d = max({x + y + ff[mid], x - y + fz[mid], -x + y + zf[mid], -x - y + zz[mid]});
            if (t[mid].w < d)
            {
                ans = max(ans, t[mid].w);
                l = mid + 1;
            }
            else if (t[mid].w > d)
            {
                ans = max(ans, d);
                r = mid - 1;
            }
            else
            {
                ans = max(ans, d);
                break;
            }
        }
        cout << ans << "\n";
    }
}
signed main()
{
    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    int T;
    cin >> T;
    while (T--)
        solve();
    return 0;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60
    • 61
    • 62
    • 63
    • 64
    • 65
    • 66
  • 相关阅读:
    Gateway基本配置
    Elasticsearch字段类型与类型区别
    公众号留言功能怎么使用？如何开启？
    强化学习中的基本术语
    华为云云耀云服务器 L 实例评测｜配置教程 + 用 Python 简单绘图
    《uni-app》一个非canvas的飞机对战小游戏实现（一）准备
    git使用X篇_SVN和GIT的版本控制区别及git等的使用方法
    卷积和转置卷积矩阵计算 convolution和deconvolution或者transposed_convolution
    Star CCM+相关资料分享
    说说 React 性能优化的手段有哪些？
  • 原文地址：https://blog.csdn.net/Shanhj/article/details/126512907