多校联赛7补题

, ,
暴零不多说

2019-08-12
####1Kejin Player
#####思路
dp[i]=dp[i−1]+pi×wi+(1−pi)×(wi+dp[i]−dp[x])dp[i]=dp[i-1]+p_i\times w_i+(1-p_i)\times (w_i+dp[i]-dp[x])
p:概率
w:花费
x:回到的关卡
化简:dp[i]=(dp[i−1]+wi−dp[x])/pidp[i]=(dp[i-1]+w_i-dp[x])/p_i
pi=pqp_i=\frac{p}{q}，故求p的逆元即可

小费马定理：在p是素数的情况下，对任意的整数都有xp≡x(mod  p)x^p\equiv x(\mod p)
其中若x无法被p整除，我们有xp≡1(mod  p)x^p\equiv 1(\mod p)。利用这条性质，在p是素数的情况下，很容易求出一个数的逆元。
把上面的式子变形得到a−1≡ap−2(mod  p)a^{-1} \equiv a^{p-2} (\mod p)，因此可以通过快速幂运算求逆元

//p, q, x, a；$p_i=\frac{p}{q} $，x下降对应等级，a花费

1
2
3
4
5
scanf("%d%d%d%d", &p, &q, &x, &a);
LL tmp = (sum[i - 1] - sum[x - 1] + modd) % modd;
sum[i] = (tmp + a) % modd * q % modd * quieck_pow(p, modd - 2) % modd;
sum[i] = (sum[i] - tmp + modd) % modd;
sum[i] = (sum[i - 1] + sum[i]) % modd;

#####标程

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
#include <bits/stdc++.h>

using namespace std;
typedef long long LL;
const int modd = 1e9 + 7;
const int MAXN = 1e6 +7;
int sum[MAXN];

int quieck_pow(LL a, int n)
{
    LL ans = 1;
    while (n)
    {
        if (n & 1)
            ans = ans * a % modd;
        a = a * a % modd;
        n >>= 1;
    }
    return  ans;
}

int main()
{
    int cas, n, Q, L, R, p, q, a, x;
    scanf("%d", &cas);
    while (cas--)
    {
        scanf("%d%d", &n, &Q);
        for (int i = 1; i <= n; i++)
        {
            scanf("%d%d%d%d", &p, &q, &x, &a);
            LL tmp = (sum[i - 1] - sum[x - 1] + modd) % modd;
            sum[i] = (tmp + a) % modd * q % modd * quieck_pow(p, modd - 2) % modd;
            sum[i] = (sum[i] - tmp + modd) % modd;
            sum[i] = (sum[i - 1] + sum[i]) % modd;
        }
        while (Q--)
        {
            scanf("%d%d", &L, &R);
            printf("%d\n", (sum[R - 1] - sum[L - 1] + modd) % modd);
        }
    }
}

#####我的代码

记住取模时加一个mod防止产生负数

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
/*************************************************************************
 > FileName:
 > Author:      huangchangsheng
 > Mail:        lancelot_hcs@qq.com
 > Date:        9102.1.8
 > Description:
 ************************************************************************/
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
#include <stack>
#include <vector>
#include <map>
#include <set>
#include <bitset>
#include <string>
#include <cmath>
#include <sstream>
using namespace std;
typedef long long ll;
const double pi = acos(-1.0);
const int eps = 1e-10;
const int mod = 1e9 + 7;
const int MOD = 1e9 + 7;
const int INF = 0x3f3f3f3f;                            
const int maxn = 500005;

ll q_pow(ll a, ll b)
{
    ll res = 1;
    while (b)
    {
        if (b & 1)
        {
            res = (res * a) % mod;
        }
        a = a * a % mod;
        b >>= 1;
    }
    return res % mod;
}

ll t, n, q, pre[maxn], s, x, a, l, r;

int main()
{
    scanf("%lld", &t);
    while (t--)
    {
        memset(pre, 0, sizeof(pre));
        scanf("%lld%lld", &n, &q);
        for (int i = 1; i <= n; i++)
        {
            scanf("%lld%lld%lld%lld", &r, &s, &x, &a);
            pre[i + 1] = ((pre[i] + a - pre[x] + mod) % mod * s % mod * q_pow(r, mod - 2) % mod + pre[x] % mod) % mod;
            //(pre[i] + a - pre[x] + mod)必须加mod
        }
        for (int i = 1; i <= q; i++)
        {
            scanf("%lld%lld", &l, &r);
            printf("%lld\n", (pre[r] - pre[l] + mod) % mod);
        }
    }
    return 0;
}

#####参考大佬博客

####2A + B = C

#####这题解也是没谁了太好了

解一补零到a; b; c 长度相等之后, 可能的情况只有四种: b | (c - a); b | (10c - a); a | (c - b); a | (10c - b)．逐个判断．

解二首先把a; b; c 末尾的0 都去掉得到A;B;C, 方便处理．去掉的0, 显然是可以通过调整相对
大小补回来的．

考虑C10kC10^k , k > 0 的情况只存在于A + B, 因为如果是A10n+B=C10k(n0;k>0)A10^n + B = C 10^k (n 0; k > 0)
的情况, 显然B 的末尾是存在0 的, 这和我们上面已经去掉了末尾的0 矛盾．
那么接下来, 显然就是k = 0 的情况, 这样的话, 显然n = 0 或者m = 0, 因为C 的最后以为是
非0 的．确定一个数和C 末尾对齐以后, 另一个要么是和C 首位对齐, 要么就是和C 第二位对齐
（发生了进位）．
还有一种情况是, A (不失一般性) 和C 长度相等, 这个时候B 的位置是不确定的, 但我们可以
通过从A 的末尾开始和C 比较, 不相同的最后以为就是B 的末尾所在的位置．
技巧这道题目其实可以不用到高精度．判断两个数相加结果是否等于第三个数, 可以直接用hash
判断．

#####标程

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
81
82
83
84
85
86
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int maxn = 5e5 + 5, lim = 3e5;
int a[maxn], b[maxn], c[maxn], d[maxn];
int sa, sb, sc;
char s[maxn];
int check(int c[], int sc, int a[], int sa, int b[], int sb)
{
    int i;
    for (i = 0; i < lim; i++)
        if (c[i] != a[i])
        {
            if (c[i] < a[i])
                return -1;
            break;
        }
    for (i = 0; i < lim; i++)
        d[i] = c[i] - a[i];
    for (i = lim - 1; i; i--)
        if (d[i] < 0)
        {
            d[i - 1]--;
            d[i] += 10;
        }
    int t = 0;
    while (!d[t] && t < lim)
        t++;
    if (t == lim)
        return -1;
    for (i = 0; i < sb; i++)
        if (d[t + i] != b[i])
            return -1;
    for (i = sb; i < lim; i++)
        if (d[t + i])
            return -1;
    return lim - sb - t;
}

int main()
{
    int tt;
    int i, t;
    scanf("%d", &tt);
    while (tt--)
    {
        memset(a, 0, sizeof(a));
        scanf("%s", s);
        for (i = 0; s[i]; i++)
            a[i + 1] = s[i] - '0';
        sa = i;
        memset(b, 0, sizeof(b));
        scanf("%s", s);
        for (i = 0; s[i]; i++)
            b[i + 1] = s[i] - '0';
        sb = i;
        memset(c, 0, sizeof(c));
        scanf("%s", s);
        for (i = 0; s[i]; i++)
            c[i + 1] = s[i] - '0';
        sc = i;
        if ((t = check(c + 1, sc, a + 1, sa, b + 1, sb)) != -1)
        {
            printf("%d %d %d\n", lim - sa, t, lim - sc);
            continue;
        }
        if ((t = check(c + 1, sc, a, sa + 1, b + 1, sb)) != -1)
        {
            printf("%d %d %d\n", lim - sa - 1, t, lim - sc);
            continue;
        }
        if ((t = check(c + 1, sc, b + 1, sb, a + 1, sa)) != -1)
        {
            printf("%d %d %d\n", t, lim - sb, lim - sc);
            continue;
        }
        if ((t = check(c + 1, sc, b, sb + 1, a + 1, sa)) != -1)
        {
            printf("%d %d %d\n", t, lim - sb - 1, lim - sc);
            continue;
        }
        puts("-1");
    }
    return 0;
}

#####参考大佬博客

####3Final Exam
#####口胡题解

换位思考, 考虑如果我们是出题人会怎么让学生做不出k 题, 即最坏情况．显然, 我们会挑出学
生复习得最少的n - k + 1 道题, 让每道题的难度都等于他复习的时间．（田忌赛马的策略）
因此, 回到学生视角, 我们要让自己复习的最少的n - k + 1 题复习时间总和> m, 构造方式显
然．(这谁特喵能想到)

输入样例:
t (case个数)
n m k (分别代表总题，总分数，至少过题目)

例如输入n=5,m=10,k=3
则最坏情况是3 3 4 0 0，而应对策略是前三个只要有一个通过就可以通过，所以田忌赛马就是3 4 4 4 4

#####标程

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include<bits/stdc++.h>
#define LL long long
using namespace std;
 
int T;
LL n,m,k;
 
int main()
{
    cin>>T;
    while(T--)
    {
        cin>>n>>m>>k;
        cout<<(m/(n-k+1)+1)*(k-1)+m+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
/*************************************************************************
 > FileName:
 > Author:      Lance
 > Mail:        lancelot_hcs@qq.com
 > Date:        9102.1.8
 > Description:
 ************************************************************************/
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll t, n, m, k;
int main()
{
    scanf("%lld", &t);
    while (t--)
    {
        ll ans = 0;//这里竟然因为数据类型int和%lld卡了一下。。
        scanf("%lld%lld%lld",&n, &m, &k);
        int max_1 = (m + 1) / (n - k + 1) + ((m + 1) % (n - k + 1) == 0 ? 0 : 1);
        ans = m + 1 +(k - 1) * max_1;
        printf("%lld\n", ans);
    }
    return 0;
}

#####(感谢我杰哥的精彩讲解)