seuOJ 首页 题库 比赛 评测 排名 讨论 帮助
登录 注册
讨论
综合

第六届「帆软杯」东南大学大学生程序设计竞赛（冬季）新手组 题解

dd 2024-12-01 18:56:47 2024-12-05 23:20:14

A. 统计选手

输入四个数字，输出他们的和即可，时间复杂度 O(1)O(1)，空间复杂度 O(1)O(1)。

#include <bits/stdc++.h>
using namespace std;
int main() {
    int x1, x2, x3, x4;
    cin >> x1 >> x2 >> x3 >> x4;
    cout << x1 + x2 + x3 + x4 << '\n';
    return 0;
}

B. A Typical Codeforces Round

按照题意，在某一题目中 YiYi 得分的公式为 max⁡(ci,ai−bi×t−50×(s−1))\max(c_i,a_i-b_i\times t-50\times(s-1))，按照公式和题意计算每题得分的总和即可。同时，这题的数据范围使用 32为整数就可以表示。时间复杂度 O(n)O(n)，空间复杂度 O(n)O(n)。

#include<bits/stdc++.h>
using namespace std;
int main()
{
	int n,ans=0;
	cin>>n;
	vector<int>a(n+1),b(n+1),c(n+1);
	for(int i=1;i<=n;i++)cin>>a[i];
	for(int i=1;i<=n;i++)cin>>b[i];
	for(int i=1;i<=n;i++)cin>>c[i];
	for(int i=1;i<=n;i++)
	{
		int t,s;
		cin>>t>>s;
		if(s<=0)continue;
		ans+=max(c[i],a[i]-b[i]*t-50*(s-1));
	}
	cout<<ans;
}

C. 猫娘魔法

一道字符串模拟题，如果是猫娘的叫声，那么第 (ans−1)×5(ans-1)\times 5 到 ans×5−1ans\times 5 -1 个字符组成的字符串为 moew~，使用 .substr 方法截取子串判断即可，时间复杂度 O(n)O(n)，空间复杂度 O(n)O(n)。

#include <bits/stdc++.h>
using namespace std;
int main() {
    string s;
    cin >> s;
    for (int i = 0;; i += 5) {
        string ss = s.substr(i, 5);
        if (ss == "moew~") {
            cout<<i/5+1;
            break;
        }
    }
}

D. Permutation with MAX Score

观察可知，每个满足要求的位置 ii 上的数字的值 pip_i 都是逐步递增的，所以在 nn 的范围内，要是想有尽可能多的这样的位置，那么最优的选择是选择 k=1k=1。接下来考虑如何求出有多少个这样的位置，可以发现，其实每一次分数增加 11 的过程就是当前的数字乘以 22，并且第一个数字其实是 1+2=31+2=3，计算过程就是数字 33 每次翻倍，直到大于 nn。

时间复杂度 O(tlog⁡(n))O(t\log(n))，空间复杂度 O(1)O(1)。

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    int t;
    cin >> t;
    for (; t; t--) {
        long long n;
        cin >> n;
        if (n == 2)
            cout << 1 << '\n';
        else {
            long long sum = 1 + 2;
            int ans = 0;
            while (sum <= n) sum *= 2, ans += 1;
            cout << ans << '\n';
        }
    }
}

我们在比赛中注意到，许多选手使用了 .pow 或者 .log 方法导致在测试点 55 出现了错误，这是因为这些方法会使用 double 数据类型进行计算，而这种计算会造成精度损失，最后得到错误的答案。

E. 安排时间

先考虑一种比较朴素的做法，对于每一位同学有空的时间段 [l,r][l,r] 使用循环的方法，在数组这段时间内累加，然后枚举每一个时刻，得到答案。

但是，上述的方法太慢了，时间复杂度为 O(nm)O(nm)，无法通过本题。那么，我们可以使用一种叫做前缀和的方法加速这个计算过程。可以发现，对于一个区间 [l,r][l,r]，把这个区间里的所有数都加 11 其实等价于把 ll 位置加 11，把 r+1r+1 位置减 11 后然后使得每个位置 ii 加上 i−1i-1 位置的值，这样就可以快速得到每个时间有多少同学可以参加。

最后从左到右枚举时刻，得到答案，时间复杂度 O(pn+m)O(pn+m)，空间复杂度 O(m)O(m)。、

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
int sum[N];
int main() {
    int n, m;
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        int p;
        cin >> p;
        for (int j = 1; j <= p; j++) {
            int l, r;
            cin >> l >> r;
            sum[l]++, sum[r + 1]--;
        }
    }
    int idx = 1;
    for (int i = 1; i <= m; i++) sum[i] += sum[i - 1];
    for (int i = 1; i <= m; i++) {
        if (sum[i] > sum[idx]) {
            idx = i;
        }
    }
    cout << idx << ' ' << n - sum[idx] << '\n';
    return 0;
}

F. 全能猫娘的烦恼

贪心地考虑这题，可以发现对于一个任务来说，先结束地就需要我们先去做，所以按照每个任务地结束时间从小到大排序。对于每个任务来说，排序在它之间的和它花费地总时间假如为 sumsum，这项任务的结束时间为 tt，那么所有工作就至少要在 t−sumt-sum 时刻开始。对于排好序的每一个任务来说，答案就是所有的 t−sumt-sum 的最小值。时间复杂度 O(n+mlog⁡(m))O(n+m\log(m))。

#include <bits/stdc++.h>
using namespace std;
int main() {
    int n,m;
    cin>>n>>m;
    vector<array<ll,2>>a(m);
    for(auto&[x,y]:a)cin>>y>>x;
    sort(a.begin(),a.end());
    ll ans=ll_inf,sm=0;
    for(auto[x,y]:a)sm+=y,ans=min(ans,x-sm);
    cout<<(ans>=0?ans:-1);
}

G. The Greatest War

提示1：战斗过多久会结束？

因为造成伤害的过程等价于对所有的士兵和盾牌造成总计 11 点伤害，所以战斗时长等于 a1+⋯+an+min(a1,c1)+⋯+min(an,cn)a_1+\dots+a_n+min(a_1,c_1)+\dots+min(a_n,c_n)。

提示2：怎么分配矛

活的更久的士兵分配耐久度更高的矛。

提示3：贪心和排序

对于三个数字都按照从大到小排序，得到的就是最优的分配方案。

首先证明从大到小排序可以使得战斗持续的更久，对于两个士兵 a1,a2(a1>a2)a_1,a_2(a_1>a_2) 和两个盾牌 c1,c2(c1>c2)c_1,c_2(c_1>c_2)，假如按照 a1+c2,a2+c1a_1+c_2,a_2+c1 的方案分配，可以发现士兵 a2a_2 不会比按照 a1+c1,a2+c2a_1+c_1,a_2+c_2 分配活的更久，而且士兵 a1a_1 手持的盾牌 c2c_2 会更早地损坏，所以战斗会更早地结束。

所以分配盾牌是按照士兵生命值越高，盾牌防御力越大分配一定更好。

分配矛的道理同理，显然为了对龙造成更大的伤害，应该把耐久度更高的矛分配给或的更久的士兵，所以把三个数字都按照从大到小排序模拟士兵死亡的过程即可，实现的时候可以把每一个盾牌当成一个血量为 min(a,c)min(a,c)，矛的耐久度为 00 的士兵即可。

时间复杂度 O(nlog⁡(n))O(n\log(n))。

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
void solve() {
    ll n, m, k;
    cin >> n >> m >> k;
    vector<ll> a(n + 1), b(m + 1), c(k + 1);
    for (int i = 1; i <= n; i++) cin >> a[i];
    for (int i = 1; i <= m; i++) cin >> b[i];
    for (int i = 1; i <= k; i++) cin >> c[i];
    sort(a.begin() + 1, a.end(), greater<>());
    sort(b.begin() + 1, b.end(), greater<>());
    sort(c.begin() + 1, c.end(), greater<>());
    b.resize(n + 1), c.resize(n + 1);
    vector<array<ll, 2>> d(1);
    for (int i = 1; i <= n; i++) {
        d.push_back({ a[i], b[i] });
        if (c[i])
            d.push_back({ min(a[i], c[i]), 0 });
    }
    sort(d.begin() + 1, d.end());
    ll ans = 0, dec = 0, tim = 0, num = d.size() - 1;
    for (int i = 1; i < d.size(); i++) {
        ll dif = d[i][0] - dec;
        tim += num * dif;
        ans += min(tim, d[i][1]);
        --num, dec = d[i][0];
    }
    cout << ans << '\n';
}
signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int t;
    cin >> t;
    while (t--) solve();
}

H. YiYi Loves Beautiful Number String

提示1：是否存在划分方案只和每个数字的出现次数有关。

提示2：哪些数作为字符串中所有数位的和加起来是有答案的。

可以预处理 00 到 n×9n\times9 的所有数字 numnum，得到 num+f(num)(f(num)是数字num的数位和)num+f(num)(f(num)是数字num的数位和)，那么仅有这些数字是有划分方案的（存在 kk 的）。

对于相同的 sum=num+f(num)sum=num+f(num) 只会有最多两个不同的 numnum 会得到相同的 sumsum，所以可以预处理每个 sumsum 可能对应的 numnum，然后在每次询问时记录所有数字的和以及每一个数字的出现次数，询问答案时暴力检查每一个可能对应的 sumsum，检查字符串中有的数字能否组成 sumsum 即可。

时间复杂度 O(n×9×10+q×10)O(n\times 9\times10+q\times 10)。

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define all(x) x.begin(), x.end()
#define notall(x) x.begin() + 1, x.end()
const int maxn = 5e6;
vector<vector<int>> mp(maxn);
void prework() {
    for (int i = 0; i <= 4.5e6 + 5; i++) {
        int j = i, k = 0;
        while (j) k += j % 10, j /= 10;
        mp[i + k].push_back(i);
    }
}
void solve() {
    int n, q;
    cin >> n >> q;
    string s;
    cin >> s;
    int sum = 0;
    vector<int> cnt(10);
    for (auto x : s) sum += x - '0', cnt[x - '0']++;
    auto get = [&](int x) {
        vector<int> cnt(10);
        while (x) cnt[x % 10]++, x /= 10;
        return cnt;
    };
    for (int _ = 1; _ <= q; _++) {
        int pos;
        char c;
        cin >> pos >> c;
        --pos;
        cnt[s[pos] - '0']--, sum -= s[pos] - '0';
        s[pos] = c;
        cnt[s[pos] - '0']++, sum += s[pos] - '0';
        int f = 0;
        for (auto cadi : mp[sum]) {
            auto excnt = get(cadi);
            int ok = 1;
            for (int i = 0; i <= 9; i++)
                if (excnt[i] > cnt[i])
                    ok = 0;
            if (ok)
                f = 1;
        }
        cout << (f ? "YES" : "NO") << '\n';
    }
}
signed main() {
    ios::sync_with_stdio(false), cin.tie(0);
    prework();
    int t;
    cin >> t;
    while (t--) solve();
}

I. 心意无向，前程有向

首先考虑没有无向边，只有有向边。

考虑判断现在图中有没有环，即是判断这张有向图是否为 DAG\text{DAG} ，可以理解为是否成偏序关系。

可以使用离散数学中非常经典的方法：拓扑排序。实现方法即是用队列来模拟，每当一个点入度为零时，将此点入队尾。每轮操作是将在队头的点取出，从图中删去，更新其相连点的入度。如果存在环，则拓扑排序将无法将所有点入队，那么该图存在环，无解；否则进行 nn 轮后我们就得到了一张图的拓扑序，即是每个点从图中删去的次序。（注意，拓扑序并不唯一）

下面再考虑无向边。此时，我们已经得到了整张图的拓扑序，那么相当于每个点之间都是可比的。我们只需要按照拓扑序大小来决定边的方向即可。（也就是说，只要初始图中有向边没形成环，那么一定有解。）

整道题的时间复杂度就是拓扑排序的线性复杂度。

由此题，我们可以发现，拓扑排序的实质是将一些偏序关系转为一个整体的偏序关系。

时间复杂度为 O(n+m1+m2)O(n+m_1+m_2)。

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<cstring>
#include<cstdlib>
#include<vector>
using namespace std;
#define re int
inline int read(){
	int x=0,ff=1;char c=getchar();
	while(c<'0'||c>'9'){if(c=='-')ff=-1;c=getchar();}
	while(c>='0'&&c<='9'){x=(x<<1)+(x<<3)+(c^'0');c=getchar();}
	return x*ff;
}
int n,m1,m2,nt[200005],h[200005],to[200005],tot,qwq[200005][2],in[200005];
int d[200005],dl[200005],lt,rt,ans[200005][2];
inline void add(int x,int y){
	nt[++tot]=h[x];h[x]=tot;to[tot]=y;
}
int main(){
	int t=1;
	while(t--){lt=1;rt=0;
		n=read();m1=read();m2=read();
		int x,y,p=0;tot=0;
		for(re i=1;i<=n;i++)h[i]=0,in[i]=0,d[i]=0;
		for(re i=1;i<=m1;i++){
			x=read();y=read();
			qwq[i][0]=x,qwq[i][1]=y;
		}
		for(re i=1;i<=m2;i++){
			x=read();y=read();
			add(x,y),in[y]++,ans[++p][0]=x,ans[p][1]=y;
		}
		for(re i=1;i<=n;i++)if(!in[i])dl[++rt]=i;
		tot=0;
		while(lt<=rt){
			int u=dl[lt++];d[u]=++tot;
			for(re j=h[u];j;j=nt[j]){
				in[to[j]]--;
				if(!in[to[j]])dl[++rt]=to[j];
			}
		}
		if(tot<n){
			puts("-1");continue;
		}
		for(re i=1;i<=m1;i++){
			if(d[qwq[i][0]]>d[qwq[i][1]])swap(qwq[i][0],qwq[i][1]);
			cout<<qwq[i][0]<<" "<<qwq[i][1]<<"\n";
		}
	}
	return 0;
}

J. 我喜欢回文串

考虑动态规划，令 dpidp_i 表示从 11 到 ii 的子串最少可以被分成多少份，那么 dpi=∑j=0i−1min(dp[j]+1)[si,j是一个回文串]dp_i=\sum_{j=0}^{i-1} min(dp[j]+1)[s_{i,j}是一个回文串]。这样使用 O(n2)O(n^2) 的时间就可以计算出字符串最少被划分成多少份。

那么如何计算一个子串 si,js_{i,j} 是否可以是一个回文串呢，考虑枚举每一个位置 ii 或者是 i,i+1i,i+1 作为一个回文串的中心，最多可以向外延申多少次，就可以在 O(n2)O(n^2) 的时间内计算每一个子串是否可以是一个字符串。

接下来考虑如何在知道最少划分份数的基础上计算分割方案数。令 ti,jt_{i,j} 表示子串 si,js_{i,j} 在填充所有问号的基础上，一共有多少种填充方案，那么当在计算一个子串是否是回文串的过程中假如 sx=sy=′?′s_x=s_y='?'，那么此时这一段子串的填充方案数就要乘以 2626，这样就可以在 O(n2)O(n^2) 的时间内计算出每一个子串的填充方案数。

那么在 dp 时候顺便计算填充方案数即可，如果当前更新的时候，dpidp_i 的值变小了，那么就直接更新方案数为 dpj×ti,jdp_j\times t_{i,j} 即可，如果 dpi=dpj+1dp_i=dp_j+1 的话那就再当前的方案数上加上 dpj×ti,jdp_j\times t_{i,j} 即可。

时间复杂度 O(n2)O(n^2)。

#include <bits/stdc++.h>
using namespace std;
template <const int T>
struct ModInt {
    const static int mod = T;
    int x;
    ModInt(int x = 0) : x(x % mod) {}
    ModInt(long long x) : x(int(x % mod)) {}
    int val() { return x; }
    ModInt operator+(const ModInt &a) const {
        int x0 = x + a.x;
        return ModInt(x0 < mod ? x0 : x0 - mod);
    }
    ModInt operator-(const ModInt &a) const {
        int x0 = x - a.x;
        return ModInt(x0 < 0 ? x0 + mod : x0);
    }
    ModInt operator*(const ModInt &a) const { return ModInt(1LL * x * a.x % mod); }
    ModInt operator/(const ModInt &a) const { return *this * a.inv(); }
    bool operator==(const ModInt &a) const { return x == a.x; };
    bool operator!=(const ModInt &a) const { return x != a.x; };
    void operator+=(const ModInt &a) {
        x += a.x;
        if (x >= mod)
            x -= mod;
    }
    void operator-=(const ModInt &a) {
        x -= a.x;
        if (x < 0)
            x += mod;
    }
    void operator*=(const ModInt &a) { x = 1LL * x * a.x % mod; }
    void operator/=(const ModInt &a) { *this = *this / a; }
    friend ModInt operator+(int y, const ModInt &a) {
        int x0 = y + a.x;
        return ModInt(x0 < mod ? x0 : x0 - mod);
    }
    friend ModInt operator-(int y, const ModInt &a) {
        int x0 = y - a.x;
        return ModInt(x0 < 0 ? x0 + mod : x0);
    }
    friend ModInt operator*(int y, const ModInt &a) { return ModInt(1LL * y * a.x % mod); }
    friend ModInt operator/(int y, const ModInt &a) { return ModInt(y) / a; }
    friend ostream &operator<<(ostream &os, const ModInt &a) { return os << a.x; }
    friend istream &operator>>(istream &is, ModInt &t) { return is >> t.x; }
    ModInt pow(int64_t n) const {
        ModInt res(1), mul(x);
        while (n) {
            if (n & 1)
                res *= mul;

            mul *= mul;
            n >>= 1;
        }
        return res;
    }
    ModInt inv() const {
        int a = x, b = mod, u = 1, v = 0;
        while (b) {
            int t = a / b;
            a -= t * b;
            swap(a, b);
            u -= t * v;
            swap(u, v);
        }
        if (u < 0)
            u += mod;
        return u;
    }
};
using Z = ModInt<998244353>;
void solve() {
    int n;
    cin >> n;
    string s;
    cin >> s;
    s = ' ' + s;
    vector<vector<int>> isp(n + 1, vector<int>(n + 1));
    vector<vector<Z>> cnt(n + 1, vector<Z>(n + 1, 1));
    vector<pair<int, Z>> dp(n + 1, { 5001, 0 });
    vector<int> pre(n + 1);
    dp[0] = { 0, 1 };
    for (int i = 1; i <= n; i++) {
        isp[i][i] = 1;
        if (s[i] == '?')
            cnt[i][i] = 26;
        for (int j = i - 1, k = i + 1; j >= 1 && k <= n; j--, k++) {
            if (s[j] == '?' && s[k] == '?')
                cnt[j][k] = cnt[j + 1][k - 1] * 26;
            else if (s[j] == s[k] || s[j] == '?' || s[k] == '?') {
                cnt[j][k] = cnt[j + 1][k - 1];
            } else
                break;
            isp[j][k] = 1;
        }
    }
    for (int i = 1; i < n; i++) {
        if (s[i] == s[i + 1] || s[i] == '?' || s[i + 1] == '?') {
            if (s[i] == '?' && s[i + 1] == '?')
                cnt[i][i + 1] = 26;
            isp[i][i + 1] = 1;
            for (int j = i - 1, k = i + 2; j >= 1 && k <= n; j--, k++) {
                if (s[j] == '?' && s[k] == '?')
                    cnt[j][k] = cnt[j + 1][k - 1] * 26;
                else if (s[j] == s[k] || s[j] == '?' || s[k] == '?') {
                    cnt[j][k] = cnt[j + 1][k - 1];
                } else
                    break;
                isp[j][k] = 1;
            }
        }
    }
    for (int i = 1; i <= n; i++) {
        for (int j = 0; j < i; j++) {
            if (isp[j + 1][i]) {
                if (dp[j].first + 1 < dp[i].first) {
                    dp[i].first = dp[j].first + 1;
                    dp[i].second = dp[j].second * cnt[j + 1][i];
                    pre[i] = j;
                } else if (dp[j].first + 1 == dp[i].first) {
                    dp[i].second += dp[j].second * cnt[j + 1][i];
                }
            }
        }
    }
    int p = n;
    vector<string> ans;
    while (p) {
        int prep = pre[p] + 1;
        string t = s.substr(prep, p - prep + 1);
        int x = 0, y = t.size() - 1;
        while (x <= y) {
            if (t[x] == '?' && t[y] == '?') {
                t[x] = t[y] = 'a';
            } else if (t[x] == '?')
                t[x] = t[y];
            else if (t[y] == '?')
                t[y] = t[x];
            x++, y--;
        }
        ans.push_back(t);
        p = pre[p];
    }
    reverse(ans.begin(), ans.end());
    cout << dp[n].first << ' ' << dp[n].second << '\n';
    for (auto &x : ans) cout << x << ' ';
    cout << '\n';
}
signed main() {
    ios::sync_with_stdio(false), cin.tie(0);
    int t;
    cin >> t;
    while (t--) solve();
}

K. 青春小M不会梦到兽耳娘

线性空间的角度

如果这道题改成可以走实数步那么大家应该都会做。

改成有理数也一样。

但为啥整数不行？因为前两个代数结构都是域，整数不是，它对乘法不一定有逆元。

但是我们仍然可以仿照域上的线性空间分析问题。

记 span⁡(u1,u2,⋯un)\operatorname{span}(u_1,u_2,\cdots u_n) 表示由这些向量通过整系数线性组合生成的空间。

注意到有 span⁡(u1,u2,⋯un)=span⁡(u1±u2,u2,⋯un)\operatorname{span}(u_1,u_2,\cdots u_n)=\operatorname{span}(u_1\pm u_2,u_2,\cdots u_n)，因为可以从 u1±u2u_1\pm u_2 中减掉或者加上 u2u_2 得到原来的 u1u_1。

想想求 gcd⁡\gcd 的辗转相除法，它实际上是辗转相减法改进来的。上面的代数结构依然满足辗转相减法的性质，所以可以对它使用辗转相除法。

辗转相除法的边界是其中一个元素为 00。

那么，考虑对某一维运用辗转相减或者说辗转相除，最后该维只能有一个非零元素。

如果这个非零元素是 ±1\pm1，那么显然这一维上可以到达。

对两维同时运用该算法即可判别是否可以在允许可逆操作的前提下到达。

多元一次方程的角度

考虑求解一个整系数多元一次方程组：

p1x1+p2x2+⋯+pnxn=1p_1x_1 + p_2x_2 + \cdots+ p_nx_n=1 p1y1+p2y2+⋯+pnyn=0p_1y_1 + p_2y_2 + \cdots + p_ny_n=0

求这个方程组的整数解也是困难的，我们不妨考虑将第二项作为限制，看第一项能得到什么。

我们考虑求出集合 SS：

S={∑i=1npi×xi∣∑i=1npi×yi=0}S = \{\sum\limits_{i=1}^{n}p_i\times x_i | \sum\limits_{i=1}^{n}p_i\times y_i = 0\}

那么根据 Bezout’s Lemma\text{Bezout's Lemma}，方程组有解的充要条件是 gcd⁡(S)=1\gcd(S)=1。

SS 太大了不好判断，我们考虑找到 SS 的一个子集使得它的最大公约数和 SS 相同。

我们考虑所有的无序对 i,ji,j，只使用 yi,yjy_i,y_j，也就是 piyi+pjyj=0p_iy_i+p_jy_j=0，得到对应的 si,j=pixi+pjxjs_{i,j}=p_ix_i+p_jx_j。

这里我们最小化 pi,pjp_i,p_j，即让 pi=yjgcd(yi,yj),pj=−yigcd(yi,yj)p_i=\dfrac{y_j}{\text{gcd}(y_i, y_j)}, p_j=-\dfrac{y_i}{\text{gcd}(y_i, y_j)}，得到对应的 si,js_{i,j}。

如果这样的所有的 ss 的 gcd⁡\gcd 为 11，那么原方程组显然有解，这是一个充分条件。

事实上它也是必要的，证明过程较为繁琐，大致思想是利用 Bezout’s Lemma\text{Bezout's Lemma} 归纳的构造。

#include <bits/stdc++.h>
using namespace std;
const int N = 1e3 + 10;
int sum[N], a[N][2];
int gcd(int x, int y) { return !y ? x : gcd(y, x % y); }
int main() {
    int T;
    cin >> T;
    while (T--) {
        int m;
        cin >> m;
        for (int i = 1; i <= m; i++) {
            cin >> a[i][0] >> a[i][1];
        }
        for (int i = 2; i <= m; i++)
            if (a[i][0])
                swap(a[i][0], a[1][0]), swap(a[i][1], a[1][1]);
        if (!a[1][0]) {
            puts("NO");
            continue;
        }
        int x = a[1][0], y = a[1][1], fy = 0;
        for (int i = 2; i <= m; i++) {
            while (a[i][0]) {
                int len = x / a[i][0];
                int _x = a[i][0], _y = a[i][1];
                a[i][0] = x - a[i][0] * len, a[i][1] = y - a[i][1] * len;
                x = _x, y = _y;
            }
            fy = gcd(a[i][1], fy);
        }
        puts(abs(fy) == 1 && abs(x) == 1 ? "YES" : "NO");
    }
    return 0;
}
seuOJ Powered by SYZOJ.