Rank 66/3225. Solved 9/11.这次的标题是 Arcaea 主线2 的时代了!
A. 宇宙的终结
题意
给定两个正整数 \(l, r\),找出 \([l, r]\) 中的一个数,满足其为三个不同素数的乘积。
思路
范围很小,直接打出 \(6\) 个素数然后暴力算一下就行。
时间复杂度:\(O(6^3)\)
对应AC代码
#define chatgpt3_5 "bits/stdc++.h"
#define chatgpt4 "bits/extc++.h"
#include chatgpt3_5
using namespace std;
//#define FLOATING_OCEAN
#define int long long
#define pii pair<int, int>
#define pipi pair<pii, pii>
#define tpi tuple<int, int, int>
#define fs first
#define sc second
#define pb emplace_back
#define ep emplace
#define rall(x) (x).rbegin(),(x).rend()
#define all(x) (x).begin(),(x).end()
constexpr int N = 2e5 + 10, M = 2e5 + 10, mod = 998244353, inf = 0x3f3f3f3f3f3f3f3f;
const double eps = 1e-9, PI = acos(-1);
void solve() {
vector<int> pri = {2, 3, 5, 7, 11, 13};
int l, r;
cin >> l >> r;
for(int i=0;i<6;i++) {
for(int j=i+1;j<6;j++) {
for(int k=j+1;k<6;k++) {
int now = pri[i] * pri[j] * pri[k];
if(now >= l && now <= r) {
cout << now << '\n';
return;
}
}
}
}
cout << -1 << '\n';
}
signed main() {
# ifdef FLOATING_OCEAN
freopen("1.in", "r", stdin);
freopen("1.out", "w", stdout);
# endif
ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
// init();
int t = 1;
// cin >> t;
while (t--) solve();
}
压根没看到 \(42\)
B. 爱恨的纠葛
题意
给定两个长度相等的数组 \(a, b\),在可以任意打乱 \(a\) 的条件下,使 \(\min\{|a_i - b_i|\}\) 最小,并输出方案。
思路
首先,这题不是让绝对值的和最小,不然直接按照 \(b\) 排个序就行了。
我们直接将 \(a\) 排序,然后对于每个 \(b\),通过二分的方式在 \(a\) 中找出最相近的元素,由此找出差值绝对值最小的 \(a_i\),以及 \(b_j\) 所在的位置 \(j\)。
此时,我们直接交换 \(a_i, a_j\),即可得到正确的构造方案。
时间复杂度:\(O(n \log n)\)
对应AC代码
#define chatgpt3_5 "bits/stdc++.h"
#define chatgpt4 "bits/extc++.h"
#include chatgpt3_5
using namespace std;
//#define FLOATING_OCEAN
#define int long long
#define pii pair<int, int>
#define pipi pair<pii, pii>
#define tpi tuple<int, int, int>
#define fs first
#define sc second
#define pb emplace_back
#define ep emplace
#define rall(x) (x).rbegin(),(x).rend()
#define all(x) (x).begin(),(x).end()
constexpr int N = 2e5 + 10, M = 2e5 + 10, mod = 998244353, inf = 0x3f3f3f3f3f3f3f3f;
const double eps = 1e-9, PI = acos(-1);
void solve() {
int n;
cin >> n;
vector<int> a(n + 1), b(n + 1);
for(int i=1;i<=n;i++) cin >> a[i];
for(int i=1;i<=n;i++) cin >> b[i];
sort(all(a));
int ans = inf, val = -1, ind = -1;
for(int i=1;i<=n;i++) {
auto it = lower_bound(all(a), b[i]);
if(it != a.end()) {
if(abs(b[i] - *it) < ans) {
val = *it;
ind = i;
ans = abs(b[i] - *it);
}
}
if(it != a.begin()) {
--it;
if(abs(b[i] - *it) < ans) {
val = *it;
ind = i;
ans = abs(b[i] - *it);
}
}
}
for(int i=1;i<=n;i++) {
if(a[i] == val) {
swap(a[i], a[ind]);
break;
}
}
for(int i=1;i<=n;i++) cout << a[i] << ' ';
cout << '\n';
}
signed main() {
# ifdef FLOATING_OCEAN
freopen("1.in", "r", stdin);
freopen("1.out", "w", stdout);
# endif
ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
// init();
int t = 1;
// cin >> t;
while (t--) solve();
}
一开始被骗了!
C. 心绪的解剖
题意
给定 \(q\) 次询问,每次询问给定一个正整数 \(n\),判断其是否能分解为三个斐波那契数之和,并输出方案。
思路
数据范围在 \(10 ^ 9\) 范围内,我们不妨直接递推,打表出 \(10^9\) 内的斐波那契数。
有趣的是,只有 \(45\) 个在范围内。
那就很简单了,我们以 \(O(n ^ 3)\) 的复杂度,预处理所有组合,以及组合对应的三个数之和,然后直接用于询问的查询即可。
一种简单的方式是用 \(map\) 存储,以和作为键,组合方案作为值,然后询问的时候判断是否存在这个键即可。
时间复杂度:\(O(45^3+q \log(45^3))\)
对应AC代码
#define chatgpt3_5 "bits/stdc++.h"
#define chatgpt4 "bits/extc++.h"
#include chatgpt3_5
using namespace std;
//#define FLOATING_OCEAN
#define int long long
#define pii pair<int, int>
#define pipi pair<pii, pii>
#define tpi tuple<int, int, int>
#define fs first
#define sc second
#define pb emplace_back
#define ep emplace
#define rall(x) (x).rbegin(),(x).rend()
#define all(x) (x).begin(),(x).end()
constexpr int N = 2e5 + 10, M = 2e5 + 10, mod = 998244353, inf = 0x3f3f3f3f3f3f3f3f;
const double eps = 1e-9, PI = acos(-1);
int fb[N], cnt;
map<int, array<int, 3>> ok;
void init() {
fb[0] = 0, fb[1] = 1, cnt = 2;
for(int i=2;;i++) {
fb[i] = fb[i - 1] + fb[i - 2];
if(fb[i] >= 1e9) break;
cnt ++;
}
for(int i=0;i<cnt;i++) {
for(int j=0;j<cnt;j++) {
for(int k=0;k<cnt;k++) {
ok.insert({fb[i] + fb[j] + fb[k], {fb[i], fb[j], fb[k]}});
}
}
}
}
void solve() {
int q;
cin >> q;
while(q --) {
int n;
cin >> n;
if(ok.count(n)) {
auto [i, j, k] = ok[n];
cout << i << ' ' << j << ' ' << k << '\n';
}else cout << -1 << '\n';
}
}
signed main() {
# ifdef FLOATING_OCEAN
freopen("1.in", "r", stdin);
freopen("1.out", "w", stdout);
# endif
ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
init();
int t = 1;
// cin >> t;
while (t--) solve();
}
就很暴力,很诈骗
D. 友谊的套路
题意
对于 \(A, B\) 间的比赛,每一局 \(A\) 获胜的概率是 \(p\),输出在比 \(5\) 局的条件下,出现 \(3\) 胜 \(2\) 负的概率。
思路
对于 \(A\) 来说,要么 \(3\) 胜 \(2\) 负,要么 \(2\) 胜 \(3\) 负,把概率加起来就行。
时间复杂度:\(O(1)\)
对应AC代码
#define chatgpt3_5 "bits/stdc++.h"
#define chatgpt4 "bits/extc++.h"
#include chatgpt3_5
using namespace std;
//#define FLOATING_OCEAN
#define int long long
#define pii pair<int, int>
#define pipi pair<pii, pii>
#define tpi tuple<int, int, int>
#define fs first
#define sc second
#define pb emplace_back
#define ep emplace
#define rall(x) (x).rbegin(),(x).rend()
#define all(x) (x).begin(),(x).end()
constexpr int N = 2e5 + 10, M = 2e5 + 10, mod = 998244353, inf = 0x3f3f3f3f3f3f3f3f;
const double eps = 1e-9, PI = acos(-1);
void solve() {
double p;
cin >> p;
double ans1 = p * p * (1 - p) * (1 - p) * (1 - p),
ans2 = (1 - p) * (1 - p) * p * p * p;
cout << fixed << setprecision(7) << ans1 + ans2 << '\n';
}
signed main() {
# ifdef FLOATING_OCEAN
freopen("1.in", "r", stdin);
freopen("1.out", "w", stdout);
# endif
ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
// init();
int t = 1;
// cin >> t;
while (t--) solve();
}
签到
E. 未来的预言
题意
定义 \(\mathtt{BO}x\) 为两个队之间的比赛规则,当某一队获胜局数超过 \(x\) 的一半时,该队获胜。
保证 \(x\) 为奇数的条件下,给定一段时间内两队的获胜情况,判断哪队获胜,并输出能判断时,进行了几局。
思路
直接按题意模拟即可。
时间复杂度:\(O(n)\)
对应AC代码
#define chatgpt3_5 "bits/stdc++.h"
#define chatgpt4 "bits/extc++.h"
#include chatgpt3_5
using namespace std;
//#define FLOATING_OCEAN
#define int long long
#define pii pair<int, int>
#define pipi pair<pii, pii>
#define tpi tuple<int, int, int>
#define fs first
#define sc second
#define pb emplace_back
#define ep emplace
#define rall(x) (x).rbegin(),(x).rend()
#define all(x) (x).begin(),(x).end()
constexpr int N = 2e5 + 10, M = 2e5 + 10, mod = 998244353, inf = 0x3f3f3f3f3f3f3f3f;
const double eps = 1e-9, PI = acos(-1);
void solve() {
char tmp;
int x;
cin >> tmp >> tmp >> x;
string s;
cin >> s;
int cnt1 = 0, cnt2 = 0;
for(char e : s) {
if(e == 'R') cnt1 ++;
else cnt2 ++;
if(cnt1 == (x + 1) / 2) {
cout << "kou!" << '\n';
cout << cnt1 + cnt2 << '\n';
return;
}
if(cnt2 == (x + 1) / 2) {
cout << "yukari!" << '\n';
cout << cnt1 + cnt2 << '\n';
return;
}
}
cout << "to be continued." << '\n';
cout << cnt1 + cnt2 << '\n';
}
signed main() {
# ifdef FLOATING_OCEAN
freopen("1.in", "r", stdin);
freopen("1.out", "w", stdout);
# endif
ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
// init();
int t = 1;
// cin >> t;
while (t--) solve();
}
又是这俩打架(
F. 命运的抉择
题意
给定一个数组 \(a\),将其划分为两个非空数组 \(b, c\),满足对于 \(b\) 中的任意元素 \(x\) 和 \(c\) 中的任意元素 \(y\),都有 \(gcd(x, y) = 1\)。
输出一个方案。
思路
这是一个暴力但是没有超时的做法。
我们可以先将一个元素放入 \(b\),然后枚举这个元素的所有质因子,将包含该质因子的所有元素都放入 \(b\),同时记录多出来的质因子,重复上述操作直到没有质因子多出来即可。
速度取决于实现,这里采取枚举质因子的倍数的方式,而不是直接分解因子再判是否包含,能快很多。
而分解质因子的时候,预处理了一个数组 \(st\),\(st[x]\) 为 \(x\) 的最小质因子,这样我们直接用 \(while\) 循环就可以快速得到所有因子,速度优于 \(\log\) 的米勒罗宾,而后者会 \(tle\)。
时间复杂度:\(O(能过)\)
对应AC代码
#define chatgpt3_5 "bits/stdc++.h"
#define chatgpt4 "bits/extc++.h"
#include chatgpt3_5
using namespace std;
//#define FLOATING_OCEAN
#define int long long
#define pii pair<int, int>
#define pipi pair<pii, pii>
#define tpi tuple<int, int, int>
#define fs first
#define sc second
#define pb emplace_back
#define ep emplace
#define rall(x) (x).rbegin(),(x).rend()
#define all(x) (x).begin(),(x).end()
constexpr int N = 1e6 + 10, M = 2e5 + 10, mod = 998244353, inf = 0x3f3f3f3f3f3f3f3f;
const double eps = 1e-9, PI = acos(-1);
bool not_pri[N];
int pr[N], cnt;
//线性筛求积性函数
static void sieve_mul_func(const int n, bool not_pri[], int pr[], int &cnt, const auto &&new_pri, const auto &&stop, const auto &&on) {
for (int i = 2; i <= n; i ++) {
if (!not_pri[i]) pr[cnt++] = i, new_pri(i);
for (int j = 0; j < cnt && i * pr[j] <= n; j ++) {
not_pri[i * pr[j]] = true;
if (i % pr[j] == 0) {
stop(i, pr[j]);
break;
}
on(i, pr[j]);
}
}
}
//线性筛: pr[] 所有素数
static void get_prime(const int n, bool not_pri[], int pr[], int &cnt) {
sieve_mul_func(n, not_pri, pr, cnt, [&](const int i) {}, [&](const int i, const int pr_) {}, [&](const int i, const int pr_) {});
}
int st[N];
void init() {
get_prime(1e6, not_pri, pr, cnt);
for(int i_=0;i_<cnt;i_++) {
int i = pr[i_];
for(int j=i;j<=1e6;j+=i) {
if(st[j] != 0) continue;
st[j] = i;
}
}
}
void solve() {
int n;
cin >> n;
vector<int> a(n + 1);
vector<int> l;
map<int, int> cnt;
set<int> fac, ok;
for(int i=1;i<=n;i++) {
cin >> a[i];
cnt[a[i]] ++;
}
int tp = (*cnt.begin()).fs;
l.pb(tp);
cnt[tp] --;
if(cnt[tp] == 0) cnt.extract(tp);
while(tp > 1) {
int x = st[tp];
fac.ep(x);
ok.ep(x);
while(tp % x == 0) tp /= x;
}
while(!fac.empty() && !cnt.empty()) {
int i = *fac.begin(), mx = (*cnt.rbegin()).fs;
fac.extract(i);
for(int j=i;j<=mx;j+=i) {
if(!cnt.count(j)) continue;
for(int p=1;p<=cnt[j];p++) l.pb(j);
cnt.extract(j);
tp = j;
while(tp > 1) {
int x = st[tp];
if(!ok.count(x)) fac.ep(x);
ok.ep(x);
while(tp % x == 0) tp /= x;
}
}
}
vector<int> r;
for(auto [x, y] : cnt) {
while(y --) r.pb(x);
}
if(l.empty() || r.empty()) {
cout << -1 << ' ' << -1 << '\n';
return;
}
cout << l.size() << ' ' << r.size() << '\n';
for(auto &e : l) cout << e << ' ';
cout << '\n';
for(auto &e : r) cout << e << ' ';
cout << '\n';
}
signed main() {
# ifdef FLOATING_OCEAN
freopen("1.in", "r", stdin);
freopen("1.out", "w", stdout);
# endif
ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
init();
int t = 1;
cin >> t;
while (t--) solve();
}
写麻了,还是并查集简单
G. 人生的起落
题意
定义若三元组 \(<x, y, z>\) 满足 \(x = z > y\),那么这个三元组称为 "v-三元组"。
给定三个整数 \(n, S, k\),构造一个长为 \(n\) 且和为 \(S\) 的数组,满足其中恰好有 \(k\) 个长为 \(3\) 的连续子序列为 "v-三元组"。
思路
首先,我们不可以 \(212121212 \ldots\) 这样构造,因为可能会出现格子恰好放下 \(k + 1\) 个 \(2\) 的情况,这个时候多出来的数就没地方搁了。
我们考虑 \(x\_x\_x\_x\_xy11111\ldots\) 的构造方式,其中 \(x\) 为将空格和 \(y\) 都填上 \(1\) 后能取到的最大值。
然后我们从左往右,把剩下的数放到空格中,每当空格值为 \(x - 1\) 时,切换到下一个空格,空格全填满时,将多余的数放到 \(y\) 中,如果不存在 \(y\) 这个空位,那么就是无解。
当然,格子不够放 \(x\) 也是无解的。
时间复杂度:\(O(n)\)
对应AC代码
#define chatgpt3_5 "bits/stdc++.h"
#define chatgpt4 "bits/extc++.h"
#include chatgpt3_5
using namespace std;
//#define FLOATING_OCEAN
#define int long long
#define pii pair<int, int>
#define pipi pair<pii, pii>
#define tpi tuple<int, int, int>
#define fs first
#define sc second
#define pb emplace_back
#define ep emplace
#define rall(x) (x).rbegin(),(x).rend()
#define all(x) (x).begin(),(x).end()
constexpr int N = 2e5 + 10, M = 2e5 + 10, mod = 998244353, inf = 0x3f3f3f3f3f3f3f3f;
const double eps = 1e-9, PI = acos(-1);
void solve() {
int n, sum, k;
cin >> n >> sum >> k;
k ++;
if(2 * k - 1 > n) {
cout << -1 << '\n';
return;
}
vector<int> ans(n + 1, 1);
int each = (sum - (n - k)) / k;
sum -= each * k + (n - k);
for(int i=1;i<=k;i++) {
ans[i * 2 - 1] = each;
}
for(int i=1;i<k;i++) {
int add = min(each - ans[i * 2] - 1, sum);
if(add <= 0) {
if(ans[i * 2] >= each) {
cout << -1 << '\n';
return;
}
}else {
ans[i * 2] += add;
sum -= add;
}
}
if(sum > 0) {
if(k * 2 > n) {
cout << -1 << '\n';
return;
}
ans[k * 2] += sum;
}
for(int i=1;i<=n;i++) cout << ans[i] << ' ';
cout << '\n';
}
signed main() {
# ifdef FLOATING_OCEAN
freopen("1.in", "r", stdin);
freopen("1.out", "w", stdout);
# endif
ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
// init();
int t = 1;
cin >> t;
while (t--) solve();
}
还好我没往 \(21212\) 上想(
H. 纷乱的红线
待补充
I. 时空的交织
题意
对于一个 \(n \times m\) 的矩阵,给定一个长度为 \(n\) 的数组 \(a\),以及一个长度为 \(m\) 的数组 \(b\),矩阵中 \((i, j)\) 所在的元素值为 \(a_i \times b_j\)。
在矩阵中,找出一个子矩阵,使子矩阵中所有元素的和最大。
思路
如果我们选择的子矩阵的右下对角线的端点为 \((l_1, r_1), (l_2, r_2)\),那么元素的和为 \(\sum_{i=l_1}^{l_2} \sum_{j=r_1}^{r_2} (a_i \times b_j)\)。
因为两个求和符号之间毫无关系,从而我们可以将其写为 \((\sum_{i=l_1}^{l_2} a_i) \times (\sum_{j=r_1}^{r_2} b_j)\)。
这就很简单了,我们要求的就是 \(a, b\) 中连续子序列的最大和的乘积,这是一个再经典不过的 \(dp\)。
当然,需要注意的是,因为存在负数,所以相乘可能会变成最小值,从而我们考虑再找出连续子序列的最小和,然后组合一下,对 \(4\) 种情况取最大值即可。
时间复杂度:\(O(n + m)\)
对应AC代码
#define chatgpt3_5 "bits/stdc++.h"
#define chatgpt4 "bits/extc++.h"
#include chatgpt3_5
using namespace std;
//#define FLOATING_OCEAN
#define int long long
#define pii pair<int, int>
#define pipi pair<pii, pii>
#define tpi tuple<int, int, int>
#define fs first
#define sc second
#define pb emplace_back
#define ep emplace
#define rall(x) (x).rbegin(),(x).rend()
#define all(x) (x).begin(),(x).end()
constexpr int N = 2e5 + 10, M = 2e5 + 10, mod = 998244353, inf = 0x3f3f3f3f3f3f3f3f;
const double eps = 1e-9, PI = acos(-1);
int maxSubArray(vector<int>& nums) {
int len = nums.size();
if (len == 0) return 0;
int sum = nums[1];
int ans = nums[1];
for (int i = 2;i < len;i++){
sum = max(nums[i], sum + nums[i]);
ans = max(ans,sum);
}
return ans;
}
int minSubArray(vector<int>& nums) {
int len = nums.size();
if (len == 0) return 0;
int sum = nums[1];
int ans = nums[1];
for (int i = 2;i < len;i++){
sum = min(nums[i], sum + nums[i]);
ans = min(ans,sum);
}
return ans;
}
void solve() {
int n, m;
cin >> n >> m;
vector<int> a(n + 1), b(m + 1);
for(int i=1;i<=n;i++) cin >> a[i];
for(int i=1;i<=m;i++) cin >> b[i];
int ans = maxSubArray(a) * maxSubArray(b);
ans = max(ans, minSubArray(a) * minSubArray(b));
ans = max(ans, minSubArray(a) * maxSubArray(b));
ans = max(ans, maxSubArray(a) * minSubArray(b));
cout << ans << '\n';
}
signed main() {
# ifdef FLOATING_OCEAN
freopen("1.in", "r", stdin);
freopen("1.out", "w", stdout);
# endif
ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
// init();
int t = 1;
// cin >> t;
while (t--) solve();
}
常数什么的无所谓啦(
J. 绝妙的平衡
题意
给定一棵根为 \(1\) 的有根树,每个节点具有点权 \(1\) 或 \(2\)。
有部分结点被标记,被标记结点需要满足 所有子树的点权和 加上 该结点本身的点权 为 \(3\) 的倍数。
输出一种构造方案,无解输出 \(-1\)。
思路
我们考虑先给所有结点都赋上点权 \(1\),然后将某些结点改成 \(2\)。
我们从底往上 \(\mathtt{dfs}\),如果我们当前枚举到结点 \(x\),那么我们可以得到当前的和为 \(sum\)。
如果当前结点没被标记,我们就不用管了,否则我们需要满足 \(sum\) 是 \(3\) 的倍数。
如果 \(sum \equiv 2 \pmod 3\),那么我们还缺一个 \(1\),此时我们直接将结点 \(x\) 的点权改为 \(2\) 即可。
如果 \(sum \equiv 1 \pmod 3\),那么在上面操作的基础上,我们还缺一个 \(1\)。这个时候,我们枚举 \(x\) 的所有子结点,如果存在一个没有被标记过的子结点,那么我们就将其点权改为 \(2\)。注意我们不能修改被标记的点,因为我们自底往上搜索的时候,保证了子树一定合法,修改之后就一定不合法了。
如上即可完成构造,为最优解。
时间复杂度:\(O(n)\)
对应AC代码
#define chatgpt3_5 "bits/stdc++.h"
#define chatgpt4 "bits/extc++.h"
#include chatgpt3_5
using namespace std;
//#define FLOATING_OCEAN
#define int long long
#define pii pair<int, int>
#define pipi pair<pii, pii>
#define tpi tuple<int, int, int>
#define fs first
#define sc second
#define pb emplace_back
#define ep emplace
#define rall(x) (x).rbegin(),(x).rend()
#define all(x) (x).begin(),(x).end()
constexpr int N = 2e5 + 10, M = 2e5 + 10, mod = 998244353, inf = 0x3f3f3f3f3f3f3f3f;
const double eps = 1e-9, PI = acos(-1);
void solve() {
int n;
cin >> n;
string s;
cin >> s;
vector<vector<int>> adj(n);
for(int i=1;i<n;i++) {
int x;
cin >> x;
x --;
adj[x].pb(i);
}
bool valid = true;
vector<int> ans(n, 1);
auto dfs = [&](auto self, int x, int p) -> int {
int sum = ans[x];
for(auto y : adj[x]) {
if(y == p) continue;
sum += self(self, y, x);
}
if(s[x] == 'R') {
int add = 0;
if(sum % 3 != 0) {
ans[x] = 2;
add ++;
}
if(sum % 3 == 1) {
bool ok = false;
for(auto y : adj[x]) {
if(y == p) continue;
if(s[y] != 'R') {
ans[y] = 2;
add ++;
ok = true;
break;
}
}
if(!ok) {
valid = false;
}
}
sum += add;
}
return sum;
};
dfs(dfs, 0, -1);
if(valid) {
for(auto e : ans) cout << e;
cout << '\n';
}else cout << -1 << '\n';
}
signed main() {
# ifdef FLOATING_OCEAN
freopen("1.in", "r", stdin);
freopen("1.out", "w", stdout);
# endif
ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
// init();
int t = 1;
// cin >> t;
while (t--) solve();
}
构造大师
K. 错综的统一
待补充