Codeforces Round 1028 (Div. 2)（ABC）-海口c网

Codeforces Round 1028 (Div. 2)（ABC）

article/2025/8/4 5:33:24

A. Gellyfish and Tricolor Pansy

翻译：

        水母和小花在玩一个叫 “决斗 ”的游戏。

        水母有 a HP，花花有 b HP。

        它们各有一个骑士。水母的骑士有 c HP，而花花的骑士有 d HP。

        他们将进行一轮游戏，直到其中一方获胜。对于 k=1、2、... 的顺序，他们将执行以下操作：

如果 k 为奇数，且水母的骑士活着：
如果 b≤0 则水母获胜。或者，水母的骑士可以攻击花花的骑士并将 d
如果 d≤0，花花的骑士死亡。

如果 k 为偶数，且花花的骑士活着：
如果a≤0，花花获胜。或者，花花的骑士可以攻击水母的骑士并将 c
如果 c≤0 海蜇的骑士死亡。

        作为世界上最聪明的人之一，你想在比赛前告诉他们谁会赢。假设双方都以最佳状态下棋。

可以证明对局永远不会以和棋结束。也就是说，一方拥有在有限步数内结束对局的策略。

思路：

只要将敌方的任意一人杀死，即可获胜。（模拟，贪心）

实现：

#include<bits/stdc++.h>
using namespace std;
using ll = long long;void solve(){ll a,b,c,d;cin>>a>>b>>c>>d;if (min(a,c)>=min(b,d)){cout<<"Gellyfish"<<endl;}else{cout<<"Flower"<<endl;}
}int main(){// 关闭输入输出流同步ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);// 不使用科学计数法// cout<<fixed;// 四舍五入中间填保留几位小数，不填默认// cout.precision();int t=1;cin>>t;while (t--) solve();return 0;
}

B. Gellyfish and Baby's Breath

翻译：

        Flower 给 Gellyfish 提供了 [0,1,...,n-1]的两个排列∗： $p_0,p_1,...,p_{n-1}$ 和 $q_0,q_1,...,q_{n-1}$ 。

        现在，Gellyfish 希望通过以下方法计算一个数组 $r_0,r_1,...,r_{n-1}$ 的计算方法如下：

对于所有 i (0≤i≤n-1)， $r_imax^i_{j=0}(2^{p_j}+2^{q_{i-j}})$ 。

        但由于水母很懒，你必须帮她算出 r 的元素。

        由于 r 的元素非常大，你只需输出 r 的元素 modulo 998244353。

思路：

2的i次从二进制数来看2^i+2^j与其他同类型的比较，一般由i,j中的较大部分即可。

即我们在遍历r中，记录p,q最大值的下标，再通过比较两者及其对应的qp值大小，可得到最大值。（位运算）

实现：

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const ll MX = 1e6+10;
const ll mod = 998244353;
vector<ll> pow_2(MX,1);
void solve(){int n;cin>>n;vector<ll> a(n),b(n),ans(n);for (auto &i:a) cin>>i;for (auto &i:b) cin>>i;ll ind_a_max = 0,ind_b_max = 0;for (int i=0;i<n;i++){// updateif (a[i]>a[ind_a_max]) ind_a_max = i;if (b[i]>b[ind_b_max]) ind_b_max = i;if (a[ind_a_max]>b[ind_b_max] || (a[ind_a_max]==b[ind_b_max] && b[i-ind_a_max]>a[i-ind_b_max])){ans[i] = (pow_2[a[ind_a_max]]+pow_2[b[i-ind_a_max]])%mod;}else{ans[i] = (pow_2[a[i-ind_b_max]]+pow_2[b[ind_b_max]])%mod;}}for (int i=0;i<n;i++){cout<<ans[i]<<" \n"[i==n-1];}
}int main(){// 关闭输入输出流同步ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);// 不使用科学计数法// cout<<fixed;// 四舍五入中间填保留几位小数，不填默认// cout.precision();// initiationfor (int i=1;i<MX;i++){pow_2[i] = (pow_2[i-1]*2)%mod;}int t=1;cin>>t;while (t--) solve();return 0;
}

C. Gellyfish and Flaming Peony

翻译：

        水母讨厌数学问题，但她必须完成数学作业：

        给水母一个由 n 个正整数 a1、a2......、an 组成的数组。

        她需要进行以下两步运算，直到 a 的所有元素都相等为止的所有元素都相等：

选择满足 1≤i,j≤n 和 i≠j 的两个索引 i、j。
用 gcd(ai,aj) 代替 ai。

        现在，水母向你询问实现目标所需的最少运算次数。

        可以证明，水母总能实现她的目标。

思路：

最后a数组的值每个都必定是 $gcd(\sum\limits^{n}_{i=1}ai)$ 。那么先用最小的次数将一个值变为最终值（广度优先搜索），再通过这个值，与其他不同的值gcd，即可最快完成目标。（数学，bfs）

实现：

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const ll mod = 998244353;
void solve(){int n,mx=0;cin>>n;vector<int> a(n);for (int&i:a) cin>>i;int res = a[0];for (int& i:a) res = gcd(res,i),mx = max(mx,i);// bfs:查找最小得到res的集合vector<int> cnt(mx+1,-1);queue<array<int,2>> pq;for (int &i:a){pq.push({i,0});}while (!pq.empty()){auto[now,step] = pq.front();pq.pop();if (cnt[now]!=-1) continue;cnt[now] = step;if (now==res){break;}for (int &i:a){int new_gcd = gcd(i,now);if (cnt[new_gcd]==-1){pq.push({new_gcd,step+1});}}}int need = cnt[res],ans = 0;for (int &i:a) ans+=(res!=i);if (need>0) ans+=need-1;cout<<ans<<"\n;
}int main(){// 关闭输入输出流同步ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);// 不使用科学计数法// cout<<fixed;// 四舍五入中间填保留几位小数，不填默认// cout.precision();int t=1;cin>>t;while (t--) solve();return 0;
}