多校联赛7补题

暴零不多说

2019-08-12
####1Kejin Player
#####思路
dp[i]=dp[i1]+pi×wi+(1pi)×(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[i1]+widp[x])/pidp[i]=(dp[i-1]+w_i-dp[x])/p_i
pi=pqp_i=\frac{p}{q},故求p的逆元即可

小费马定理:在p是素数的情况下,对任意的整数都有xpx(modp)x^p\equiv x(\mod p)
其中若x无法被p整除,我们有xp1(modp)x^p\equiv 1(\mod p)。利用这条性质,在p是素数的情况下,很容易求出一个数的逆元。
把上面的式子变形得到a1ap2(modp)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;
}

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