【题解】[NOI2018]屠龙勇士

Resory
编程OI题解

发布于：2020年10月8日
次浏览

题目链接

算是一个比较简单的NOI题，数论萌（神）新（仙）练（秒）手（切）题。

前置知识：扩展中国剩余定理（excrt）

求解一个线性同余方程组：

（$q_1,q_2,q_3\dots,q_n$ 不两两互质）

由于并没有简单的直接求解的办法，所以考虑分开求解。

假设求解到第 $i$ 个方程，前面 $i-1$ 个方程结果为 $ans$ ，模数的 $\operatorname{lcm}$ 是 $M$ ，则可以列出一个方程组：

为了简便，我们用 $a_{1,2}$ 代表余数， $b_{1,2}$ 代表模数，则有：

移项得：

令 $G=\gcd(b_1,b_2)$ ，若 $G \not| (a_2-a_1)$ ，则无解。否则用 exgcd 求解方程 $b_1x’+b_2y’=G$，可得 $k_1=\dfrac{x’ \cdot (a_2-a_1)}{G}$ ，带回即可求出 $x$ 的值。

本题题解

Part 1 初始化

首先我们发现，杀死龙的顺序是确定的，每次杀龙的剑也是确定的，这就说明我们可以用 $multiset$ 模拟选剑的过程，每次 upper_bound 一下就行了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
ll n,m,a[maxn],p[maxn],award[maxn],atk[maxn];
multiset < ll > sword;

void input() {
    n = func::read(),m = func::read(); // read是定义在命名空间func中的快读函数
    for(int i = 1;i <= n;i ++) a[i] = func::read(); // 第i条龙的生命值
    for(int i = 1;i <= n;i ++) p[i] = func::read(); // 第i条龙的恢复能力
    for(int i = 1;i <= n;i ++) award[i] = func::read(); // 杀死第i条龙的奖励
    for(int i = 1;i <= m;i ++) sword.insert(func::read()); // 把所有剑的攻击力存储进multiset中
}

void init() {
    multiset < ll >::iterator it;
    for(int i = 1;i <= n;i ++) {
        it = sword.upper_bound(a[i]); // upper_bound出第i把剑的攻击力
        if(it != sword.begin()) it --;
        atk[i] = *it;
        sword.erase(it);
        sword.insert(award[i]); // 插入杀死第i条龙的奖励
   }
}

我们又发现，杀死龙的步骤为：以 $atk_i$ 的攻击力攻击 $x$ 下，回复若干次 $p_i$ 生命值，生命值变为 $0$ 。这是不是感觉很耳熟？没错，这就是一个同余方程。我们可以根据这个过程列出这样一个方程：

然而这并不符合 excrt 的规范，因此我们可以移项，两边同时乘上 $atk_i$ 关于 $p_i$ 的 $atk_i^{-1}$ ：

于是我们得到了得到方程组的代码：

1
2
3
4
5
6
7
8
9
10
11
bool init_equotion() {
    for(int i = 1;i <= n;i ++ ) {
        ll g = func::gcd(p[i],a[i]); // 此段代码中gcd定义在命名空间func中
        g = func::gcd(g,atk[i]);
        a[i] /= g,p[i] /= g,atk[i] /= g;
        if(func::gcd(atk[i],p[i]) != 1) return false; // 不互质则不存在逆元 返回false表示无解
		q1[i] = func::fmul(a[i],func::inv(atk[i],p[i]),p[i]); // 处理方程组
		p1[i] = p[i];
	}
    return true;
}

Part 2 一些特例

我们发现，有的数据并不保证 $a_i\le p_i$ ，这时可能就会出现一种情况：龙的生命值依旧大于0，但是已经和 $p_i$ 同余了。

怎么办呢？

多半是废了！

但是，经过仔细观察数据范围，可以发现，对于所有不满足 $a_i\le p_i$ 的数据，都保证 $p_i=1$ ！这意味着我们可以直接特判掉这些情况，答案即为 $\max\left\{\left\lfloor\dfrac{a_i}{atk_i}\right\rfloor\right\}$。代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
namespace sp {
    bool check() { // 检查是否符合特殊情况
        for(int i = 1;i <= n;i ++) if(p[i] != 1) return false;
        return true;
    }

    void solve_sp() {
        ll ans = -1;
        for(int i = 1;i <= n;i ++) ans = func::max(ans,(a[i] + atk[i] - 1) / atk[i]);
        printf("%lld\n",ans);
    }
}

Part 3 解决普遍情况

当解决完特殊情况并且处理完方程组后，我们就可以套上 excrt 的板子大干一场了：

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
void excrt() {
    ll M = p1[1];
    ll ans = q1[1];
    for(int i = 2;i <= n;i ++) {
        ll k1,x,y;
        // 按照excrt的方法求解
        ll g = func::exgcd(M,p1[i],x,y);
        ll c = (q1[i] - ans % p1[i] + p1[i]) % p1[i];
        if(c % g != 0) { puts("-1"); return ; } // 无解
        k1 = func::fmul(x,c / g,p1[i] / g); // 龟速乘 防爆long long
        ans = M * k1 + ans;
        M =  M / g * p1[i];
        ans = (ans % M + M) % M;
    }
    ans = (ans % M + M) % M;
    printf("%lld\n",ans);
}

void solve() {
    sword.clear();
    n = func::read(),m = func::read();
    for(int i = 1;i <= n;i ++) a[i] = func::read();
    for(int i = 1;i <= n;i ++) p[i] = func::read();
    for(int i = 1;i <= n;i ++) award[i] = func::read();
    for(int i = 1;i <= m;i ++) sword.insert(func::read());
    func::init();
    if(sp::check()) sp::solve_sp();
    else if(init_equotion()) excrt();
    else puts("-1");
}

完整代码：

查看代码 
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
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
#include <algorithm>
#include <cstdio>
#include <set>

typedef long long ll;
using std::multiset;
const int maxn = 100005;

ll t,n,m,a[maxn],p[maxn],award[maxn],atk[maxn];
multiset < ll > sword;

namespace func {
    inline ll max(ll a,ll b) { return a > b ? a : b; }

    inline ll read() {
#define gc c = getchar()
        ll d = 0;
        int f = 0,gc;
        while(c < 48 || c > 57) f |= (c == '-'),gc;
        while(c > 47 && c < 58) d = (d << 1) + (d << 3) + (c ^ 48),gc;
#undef gc
        return f ? -d : d;
    }

    ll gcd(ll a,ll b) {
        if(!b) return a;
        return gcd(b,a % b);
    }

    ll exgcd(ll a,ll b,ll& x1,ll& y1) {
        if(!b) {
            x1 = 1,y1 = 0;
            return a;
        }
        ll x2,y2,ans = exgcd(b,a % b,x2,y2);
        x1 = y2;
        y1 = x2 - a / b * y2;
        return ans;
    }

    ll inv(ll a,ll p) {
        ll x,y;
        exgcd(a,p,x,y);
        return (x % p + p) % p;
    }

    ll fmul(ll a,ll b,ll mod) {
        ll rep = 0;
        while(b) {
            if(b & 1) rep = (rep + a) % mod;
            a = (a << 1) % mod,b >>= 1;
        }
        return rep;
    }

    void init() {
        multiset < ll >::iterator it;
        for(int i = 1;i <= n;i ++) {
            it = sword.upper_bound(a[i]);
            if(it != sword.begin()) it --;
            atk[i] = *it;
            sword.erase(it);
            sword.insert(award[i]);
        }
    }
}

namespace sp {
    bool check() {
        for(int i = 1;i <= n;i ++) if(p[i] != 1) return false;
        return true;
    }

    void solve_sp() {
        ll ans = -1;
        for(int i = 1;i <= n;i ++) ans = func::max(ans,(a[i] + atk[i] - 1) / atk[i]);
        printf("%lld\n",ans);
    }
}

namespace soln {
    ll p1[maxn],q1[maxn];

    bool init_equotion() {
        for(int i = 1;i <= n;i ++ ) {
            ll g = func::gcd(p[i],a[i]);
            g = func::gcd(g,atk[i]);
            a[i] /= g,p[i] /= g,atk[i] /= g;
            if(func::gcd(atk[i],p[i]) != 1) return false;
			q1[i] = func::fmul(a[i],func::inv(atk[i],p[i]),p[i]);
			p1[i] = p[i];
		}
        return true;
    }

    void excrt() {
        ll M = p1[1];
        ll ans = q1[1];
        for(int i = 2;i <= n;i ++) {
            ll k1,x,y;
            ll g = func::exgcd(M,p1[i],x,y);
            ll c = (q1[i] - ans % p1[i] + p1[i]) % p1[i];
            if(c % g != 0) { puts("-1"); return ; }
            k1 = func::fmul(x,c / g,p1[i] / g);
            ans = M * k1 + ans;
            M =  M / g * p1[i];
            ans = (ans % M + M) % M;
        }
        ans = (ans % M + M) % M;
        printf("%lld\n",ans);
    }

    void solve() {
        sword.clear();
        n = func::read(),m = func::read();
        for(int i = 1;i <= n;i ++) a[i] = func::read();
        for(int i = 1;i <= n;i ++) p[i] = func::read();
        for(int i = 1;i <= n;i ++) award[i] = func::read();
        for(int i = 1;i <= m;i ++) sword.insert(func::read());
        func::init();
        if(sp::check()) sp::solve_sp();
        else if(init_equotion()) excrt();
        else puts("-1");
    }
}

int main() {
    freopen("dragon.in","r",stdin);
    freopen("dragon.out","w",stdout);
    t = func::read();
    for(;t;t --) soln::solve();
    fclose(stdin);
    fclose(stdout);
    return 0;
}
-------------EOF-------------

📚 本文由Resory创作，转载请注明出处

🧾 博客内容遵循 署名-非商业性使用-相同方式共享 4.0 国际 (CC BY-NC-SA 4.0) 协议

🔗本文永久链接是：https://resorie.github.io/blog/posts/soln-P4774/

更新于：2021年2月27日

OI

评论