2019 HDOJ Multi-University Training Contest Stage 7(杭电多校)

应该是最毒瘤的一场多校。

题目链接：http://acm.hdu.edu.cn/contests/contest_show.php?cid=854

---

A：

F：

有n个问题，每道问题的分数取值范围是[0,m]，所有分数加起来等于m。每道题知识点无关联，若要解决分数为x的题，则需复习对应知识点x+1个小时。问：解决k道题所需最少复习时间。

可以反向思考这个问题：若出卷老师知道学生每道题的复习时间，怎样出卷才能使得学生做不出k题。

很简单，可以让学生做出复习时间最多的k-1道题，然后令学生复习得最少的m-k+1道题都做不出来，让做不出来的题的难度等于学生的复习时间即可。

回到学生视角，要防止这种情况发生，就应该让复习得最少的m-k+1道题的总复习时间大于m，保证这m-k+1道题中一定能做出一题。

/* basic header */
#include <bits/stdc++.h>
/* define */
#define ll long long
#define dou double
#define pb emplace_back
#define mp make_pair
#define sot(a,b) sort(a+1,a+1+b)
#define rep1(i,a,b) for(int i=a;i<=b;++i)
#define rep0(i,a,b) for(int i=a;i<b;++i)
#define eps 1e-8
#define int_inf 0x3f3f3f3f
#define ll_inf 0x7f7f7f7f7f7f7f7f
#define lson (curpos<<1)
#define rson (curpos<<1|1)
/* namespace */
using namespace std;
/* header end */

int main() {
    int t; scanf("%d", &t);
    while (t--) {
        ll n, m, k; scanf("%lld%lld%lld", &n, &m, &k);
        // m/(n-k+1)+1是前k-1题复习时间，m+1是第k题复习时间
        printf("%lld
", (m / (n - k + 1) + 1) * (k - 1) + m + 1);
    }
    return 0;
}

J：

一个游戏角色要升级，总共有n级，最低级为1级。给定相邻等级升级成功的概率、代价和失败后变成的等级。给出q次查询，每次查询给定两个等级p和q，输出从p级升到q级的期望代价。

显然满足前缀和性质，递推期望即可。

/* basic header */
#include <bits/stdc++.h>
/* define */
#define ll long long
#define dou double
#define pb emplace_back
#define mp make_pair
#define sot(a,b) sort(a+1,a+1+b)
#define rep1(currLevel,a,b) for(int currLevel=a;currLevel<=b;++currLevel)
#define rep0(currLevel,a,b) for(int currLevel=a;currLevel<b;++currLevel)
#define eps 1e-8
#define int_inf 0x3f3f3f3f
#define ll_inf 0x7f7f7f7f7f7f7f7f
#define lson (curpos<<1)
#define rson (curpos<<1|1)
/* namespace */
using namespace std;
/* header end */

const int mod = 1e9 + 7, maxn = 1e6 + 10;
int sum[maxn];

int qp(ll a, ll n) {
    ll ret = 1;
    while (n) {
        if (n & 1) ret = ret * a % mod;
        a = a * a % mod;
        n >>= 1;
    }
    return ret;
}

int main() {
    int t; scanf("%d", &t);
    while (t--) {
        int n, q; scanf("%d%d", &n, &q);
        rep1(currLevel, 1, n) {
            int p, q, lostLevel, cost; scanf("%d%d%d%d", &p, &q, &lostLevel, &cost);
            ll preCost = (sum[currLevel - 1] - sum[lostLevel - 1] + mod) % mod;
            sum[currLevel] = (preCost + cost) % mod * q % mod * qp(p, mod - 2) % mod; // (preCost+addCost)/(p/q)
            sum[currLevel] = (sum[currLevel] - preCost + mod) % mod; // -preCost
            sum[currLevel] = (sum[currLevel - 1] + sum[currLevel]) % mod; // 重新计算前缀和
        }
        while (q--) {
            int l, r; scanf("%d%d", &l, &r);
            printf("%d
", (sum[r - 1] - sum[l - 1] + mod) % mod);
        }
    }
    return 0;
}