2019 Multi-University Training Contest 7

﹏ヽ暗。殇╰゛Y 2021-10-29 11:40 214阅读 0赞

<table> 
 <thead> 
  <tr> 
   <th>Solved</th> 
   <th>Pro.ID</th> 
   <th>Title</th> 
   <th>Ratio(Accepted / Submitted)</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td></td> 
   <td>1001</td> 
   <td><a href="http://acm.hdu.edu.cn/contests/contest_showproblem.php?pid=1001&amp;cid=854" rel="nofollow">A + B = C</a></td> 
   <td>10.52%(302/2872)</td> 
  </tr> 
  <tr> 
   <td></td> 
   <td>1002</td> 
   <td><a href="http://acm.hdu.edu.cn/contests/contest_showproblem.php?pid=1002&amp;cid=854" rel="nofollow">Bracket Sequences on Tree</a></td> 
   <td>11.27%(16/142)</td> 
  </tr> 
  <tr> 
   <td></td> 
   <td>1003</td> 
   <td><a href="http://acm.hdu.edu.cn/contests/contest_showproblem.php?pid=1003&amp;cid=854" rel="nofollow">Cuber Occurrence</a></td> 
   <td>6.67%(1/15)</td> 
  </tr> 
  <tr> 
   <td></td> 
   <td>1004</td> 
   <td><a href="http://acm.hdu.edu.cn/contests/contest_showproblem.php?pid=1004&amp;cid=854" rel="nofollow">Data Structure Problem</a></td> 
   <td>23.08%(3/13)</td> 
  </tr> 
  <tr> 
   <td></td> 
   <td>1005</td> 
   <td><a href="http://acm.hdu.edu.cn/contests/contest_showproblem.php?pid=1005&amp;cid=854" rel="nofollow">Equation</a></td> 
   <td>0.00%(0/63)</td> 
  </tr> 
  <tr> 
   <td>已补</td> 
   <td>1006</td> 
   <td><a href="http://acm.hdu.edu.cn/contests/contest_showproblem.php?pid=1006&amp;cid=854" rel="nofollow">Final Exam</a></td> 
   <td>5.06%(297/5872)</td> 
  </tr> 
  <tr> 
   <td></td> 
   <td>1007</td> 
   <td><a href="http://acm.hdu.edu.cn/contests/contest_showproblem.php?pid=1007&amp;cid=854" rel="nofollow">Getting Your Money Back</a></td> 
   <td>12.42%(20/161)</td> 
  </tr> 
  <tr> 
   <td></td> 
   <td>1008</td> 
   <td><a href="http://acm.hdu.edu.cn/contests/contest_showproblem.php?pid=1008&amp;cid=854" rel="nofollow">Halt Hater</a></td> 
   <td>14.77%(61/413)</td> 
  </tr> 
  <tr> 
   <td></td> 
   <td>1009</td> 
   <td><a href="http://acm.hdu.edu.cn/contests/contest_showproblem.php?pid=1009&amp;cid=854" rel="nofollow">Intersection of Prisms</a></td> 
   <td>0.00%(0/2)</td> 
  </tr> 
  <tr> 
   <td></td> 
   <td>1010</td> 
   <td><a href="http://acm.hdu.edu.cn/contests/contest_showproblem.php?pid=1010&amp;cid=854" rel="nofollow">Just Repeat</a></td> 
   <td>15.04%(128/851)</td> 
  </tr> 
  <tr> 
   <td><img src="http://acm.hdu.edu.cn/images/ac.gif" alt="img"></td> 
   <td>1011</td> 
   <td><a href="http://acm.hdu.edu.cn/contests/contest_showproblem.php?pid=1011&amp;cid=854" rel="nofollow">Kejin Player</a></td> 
   <td>21.20%(544/2566)</td> 
  </tr> 
 </tbody> 
</table>

### 1006 ###

这题想了很久，但是题解只有一句话

换位思考, 考虑如果我们是出题人会怎么让学生做不出 k 题, 即最坏情况．显然, 我们会挑出学 生复习得最少的 \\(n - k + 1\\) 道题, 让每道题的难度都等于他复习的时间．（田忌赛马的策略）

因此, 回到学生视角, 我们要让自己复习的最少的 \\(n - k + 1\\) 题复习时间总和 > m, 构造方式显然． 那么, QQ 小方还来得及复习吗?

既然要让复习最少的\\(n-k+1\\)题复习时间总和大于m，首先要保证复习时间最少的题目有多少复习时间。即\\(m/(n-k+1)\\)。所以\\(m/(n-k+1) + 1\\)就是其他复习时间不是最少的题目的复习时间。

所以答案为\\((m/(n-k+1)+1)\*(k-1) + m+1\\)

#include <bits/stdc++.h>
    using namespace std;
    typedef long long ll;
    int t;
    ll n,m,k;
    
    int main(){
        cin>>t;
        while(t--){
            scanf("%lld%lld%lld",&n,&m,&k);
            ll d = k-1;
            ll now = n-d;//n-k+1
            ll ans = m + 1;
            ll maxn = m / now + 1;
            ans = ans + maxn * d;
            printf("%lld\n",ans);
        }
        return 0;
    }

### 1011 ###

设\\(E\_i\\) 为第\\(i\\) 关到\\(i+1\\) 的期望花费，那么

\\\[E\_i = p \* a\_i + (1-p)\*(sum\_\{ \{j=x\_i\}\}^\{ \{i-1\}\}E\_j+E\_i+a\_i)\\\]

则

\\\[E\_i = \{(sum\_\{ \{j=x\_i\}\}^\{ \{i-1\}\}E\_j+a\_i)\*(1-p)\\over p\} + a\_i\\\]

最后\\(l\\)到\\(r\\) 的期望花费即\\(sum\_\{j=l\}^\{r-1\}E\_j\\)

#include <bits/stdc++.h>
    using namespace std;
    typedef long long ll;
    const ll mod = 1e9 + 7;
    inline int read()
    {
        char c=getchar();int x=0,f=1;
        while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
        while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}
        return x*f;
    }
    ll gcd(ll x, ll y) {
        if(y == 0) return x;
        return gcd(y, x % y);
    }
    ll pow_mod(ll x, ll y) {
        ll res = 1;
        while(y) {
            if(y & 1) res = res * x % mod;
            x = x * x % mod;
            y >>= 1;
        }
        return res;
    }
    int r[500005];
    int s[500005];
    int x[500005];
    int a[500005];
    ll pre[500005];
    
    int main() {
        int T;
        scanf("%d", &T);
        while(T--) {
            int n, m;
            n = read(); m = read();
            for(int i = 1; i <= n; i++) {
                r[i] = read(), s[i] = read(), x[i] = read(), a[i] = read();
            }
            pre[0] = 0LL;
            for(int i = 1; i <= n; i++) {
                ll tmp = 1LL * (s[i] - r[i]) * pow_mod(1LL * r[i], mod - 2LL) % mod;
                tmp = ((pre[i - 1] - pre[x[i] - 1] + a[i]) * tmp % mod + a[i]) % mod;
                pre[i] = (pre[i - 1] + tmp) % mod;
                pre[i] = (pre[i] + mod) % mod;
            }
            while(m--) {
                int l, r;
                l = read();
                r = read();
                printf("%lld\n", ((pre[r - 1] - pre[l - 1]) + mod) % mod);
            }
        }
        return 0;
    }

转载于:https://www.cnblogs.com/1625--H/p/11348857.html