Contestant_. Rank 344. Rating +183.
A. Two Vessels
题意
给定两个水槽，初始状态下有 \(a, b\) 单位的水。现在给定一个容量为 \(c\) 的水杯，输出最少需要舀几次水，让两个水槽的水体积相等
思路
显然我们缺少 \(\frac{abs(a- b)}{2}\)，设其为 \(p\)，那么我们需要舀 \(\lceil \frac{p}{c} \rceil\) 次。
时间复杂度：\(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()
const int N = 1e6 + 10, M = 2e5 + 10, mod = 1e9 + 7, inf = 0x3f3f3f3f3f3f3f3f;
const double eps = 1e-9, PI = acos(-1);
void solve() {
int a, b, c;
cin >> a >> b >> c;
cout << (abs(a - b) / 2 / c + (abs(a - b) % (2 * c) != 0)) << '\n';
}
signed main() {
# ifdef FLOATING_OCEAN
freopen("1.in","r",stdin);
freopen("1.out","w",stdout);
# endif
ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
// init();
int t = 1;
cin >> t;
while (t--) solve();
}很形象的签到
B. The Corridor or There and Back Again
题意
给定一个数轴，数轴上有一些障碍物，位于 \(d_i\) 的障碍物会在 \(s_i\) 时刻出现。
输出最远能到达的距离，满足以一个单位时间移动一格的速度下从原点走到该点再走回原点，路上不会碰到障碍物。
思路
我们直接暴力枚举最远能到的距离，然后检查每一个障碍物是否会在路上出现即可。
对于判断，如果我们最远到达 \(k\)，那么需要满足 \(s[j] \leq 2(k - d[j])\)。
时间复杂度：\(O(10000n)\)
对应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()
const int N = 1e6 + 10, M = 2e5 + 10, mod = 1e9 + 7, inf = 0x3f3f3f3f3f3f3f3f;
const double eps = 1e-9, PI = acos(-1);
void solve() {
int n;
cin >> n;
vector<int> s(n + 1), d(n + 1);
for(int i=0;i<n;i++) cin >> s[i] >> d[i];
int ans = 0;
for(int i=1;i<=10000;i++){
bool st = true;
for(int j=0;j<n;j++){
if(d[j] <= (i - s[j]) * 2) {
st = false;
break;
}
}
if(st) ans = max(ans, i);
}
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(0), cout.tie(0);
// init();
int t = 1;
cin >> t;
while (t--) solve();
}也是没想到去直接枚举
C. Non-coprime Split
题意
给定两个整数 \(l, r\)，满足 \(l \leq r\)，输出两个整数 \(a, b\)，满足：
\(l \leq a + b \leq r\)；
\(\gcd(a, b) \neq 1\)
如果不存在，输出 \(-1\)。
思路
首先，如果 \(a + b\) 可以取到偶数，那么显然，两个偶数的 \(\gcd\) 一定是不等于 \(1\) 的。
那么我们对 \(l, r\) 进行特判：
如果 \(l < r\)，我们将 \(l := l + l \bmod 2, r := r - r \bmod 2\)，并令 \(p = \max(l, r)\)，那么如果 \(p = 2\) 就是无解，否则答案就是 \(2, l - 2\)。
如果 \(l = r\)，那么如果 \(l\) 为偶数，就等价于上面的判断，否则我们枚举 \(a \in [3, \sqrt l]\)，并暴力判断即可。
至于为什么只要枚举到 \(\sqrt l\)，因为我们需要满足的是 \(l - a\) 具有因数 \(l\)。
时间复杂度：\(O(\sqrt 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()
const int N = 1e6 + 10, M = 2e5 + 10, mod = 1e9 + 7, inf = 0x3f3f3f3f3f3f3f3f;
const double eps = 1e-9, PI = acos(-1);
void solve() {
int l, r;
cin >> l >> r;
if(l < r){
if(l % 2 == 1) l ++;
if(r % 2 == 1) r --;
l = max(l, r);
if(l == 2){
cout << -1 << '\n';
return;
}
cout << 2 << ' ' << l - 2 << '\n';
return;
}
if(l % 2 == 0){
if(l == 2){
cout << -1 << '\n';
return;
}
cout << 2 << ' ' << l - 2 << '\n';
}else{
for(int i=3;i*i<=l;i++){
if((l - i) % i == 0){
cout << i << ' ' << l - i << '\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(0), cout.tie(0);
// init();
int t = 1;
cin >> t;
while (t--) solve();
}其实也可以暴力枚举 \(l\)，可以证明不需要枚举很多就可以得到结果
D. Plus Minus Permutation
题意
给定三个整数 \(n, x, y\)，构造一个长为 \(n\) 的排列 \(p\)，\(a - b\) 最大。
其中，\(a\) 定义为 \(p\) 中所有下标是 \(x\) 的倍数的数之和，\(b\) 为 \(p\) 中所有下标是 \(y\) 的倍数的数之和。
输出 \(a- b\)。
思路
这是一个类似于容斥的想法，因为我们减的时候，会将下标是 \(lcm(x, y)\) 倍数的数抵消掉，所以我们无需考虑这些数。
那么可以发现，筛除这些数后，\(a\) 中数的取法和 \(b\) 中数的取法是互不相交的，因而我们直接用最大的几个减去最小的几个即可。
时间复杂度：\(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()
const int N = 1e6 + 10, M = 2e5 + 10, mod = 1e9 + 7, inf = 0x3f3f3f3f3f3f3f3f;
const double eps = 1e-9, PI = acos(-1);
void solve() {
int n, x, y;
cin >> n >> x >> y;
int cnt1 = n / x, cnt2 = n / y, cnt3 = n / (x * y / __gcd(x, y));
cnt1 -= cnt3, cnt2 -= cnt3;
cout << ((n + (n - cnt1 + 1)) * cnt1 / 2 - (1 + cnt2) * cnt2 / 2) << '\n';
}
signed main() {
# ifdef FLOATING_OCEAN
freopen("1.in","r",stdin);
freopen("1.out","w",stdout);
# endif
ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
// init();
int t = 1;
cin >> t;
while (t--) solve();
}也是差点用 \(x \times y\) 去做了（
E. Data Structures Fan
题意
给定一个长为 \(n\) 的序列 \(a\) 以及二进制字符串，定义询问如下：
\(1\ l\ r\)，将 \([l, r]\) 内所有 \(s_i\) 翻转；
\(2\ g, g \in [0, 1]\)，将字符串中为 \(g\) 的所有位置对应的 \(a\) 的值取异或总和并输出
回答询问。
思路1
题目有说数据结构，无脑线段树可过。
时间复杂度：\(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()
const int N = 1e6 + 10, M = 2e5 + 10, mod = 1e9 + 7, inf = 0x3f3f3f3f3f3f3f3f;
const double eps = 1e-9, PI = acos(-1);
struct Node{
int l, r;
int val, x0, x1, lazy;
};
struct SegTree{
vector<Node> tr;
explicit SegTree(int _n){
tr = vector<Node>(_n << 2);
}
static int ls(int x){ return x << 1; }
static int rs(int x){ return x << 1 | 1; }
void push_up(int rt){
tr[rt].val = tr[ls(rt)].val ^ tr[rs(rt)].val;
tr[rt].x0 = tr[ls(rt)].x0 ^ tr[rs(rt)].x0;
tr[rt].x1 = tr[ls(rt)].x1 ^ tr[rs(rt)].x1;
}
void build(int rt, int l, int r, vector<int> &a, string &s){
if(l == r){
tr[rt] = {l, r, a[l], s[l] == '0' ? a[l] : 0, s[l] == '1' ? a[l] : 0, 0};
return;
}
int mid = (l + r) >> 1;
build(ls(rt), l, mid, a, s);
build(rs(rt), mid + 1, r, a, s);
tr[rt] = {l, r};
push_up(rt);
}
void push_down(int rt){
if(tr[rt].lazy){
swap(tr[ls(rt)].x0, tr[ls(rt)].x1);
swap(tr[rs(rt)].x0, tr[rs(rt)].x1);
tr[ls(rt)].lazy ^= 1;
tr[rs(rt)].lazy ^= 1;
tr[rt].lazy = 0;
}
}
void modify(int rt, int l, int r){
if(l <= tr[rt].l && tr[rt].r <= r){
tr[rt].lazy ^= 1;
swap(tr[rt].x0, tr[rt].x1);
return;
}
push_down(rt);
int mid = (tr[rt].l + tr[rt].r) >> 1;
if(l <= mid) modify(ls(rt), l, r);
if(r > mid) modify(rs(rt), l, r);
push_up(rt);
}
int query(int rt, int l, int r, int zero) {
if (l <= tr[rt].l && tr[rt].r <= r) {
return zero == 0 ? tr[rt].x0 : tr[rt].x1;
}
push_down(rt);
int mid = (tr[rt].l + tr[rt].r) >> 1;
int sum = 0;
if (l <= mid) sum ^= query(ls(rt), l, r, zero);
if (r > mid) sum ^= query(rs(rt), l, r, zero);
return sum;
}
};
void solve() {
int n;
cin >> n;
vector<int> a(n + 1);
for(int i=1;i<=n;i++) cin >> a[i];
string s;
cin >> s;
s = " " + s;
SegTree tr(n);
tr.build(1, 1, n, a, s);
int q;
cin >> q;
while(q --){
int op;
cin >> op;
if(op == 1){
int l, r;
cin >> l >> r;
tr.modify(1, l, r);
}else{
int x;
cin >> x;
cout << tr.query(1, 1, n, x) << ' ';
}
}
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(0), cout.tie(0);
// init();
int t = 1;
cin >> t;
while (t--) solve();
}思路2
首先，异或两次等于没有异或。
那么我们考虑前缀异或 \(p\)，对于 \(0\) 所对应的异或总和，如果我们异或 \(p[r] \oplus p[l - 1]\)，那么等价于我们将 \([l, r]\) 内的字符翻转，因为原本为 \(0\) 的异或抵消，原本为 \(1\) 的现在异或上去了。
那么很显然，我们维护一个 \(msk\)，然后将所有 \([l, r]\) 修改映射到这个 \(msk\) 上，即 \(msk = msk \oplus (p[r] \oplus p[l - 1])\)。
在处理询问之前，我们预处理 \(0\) 对应的所有数的异或和 \(ans0\)，以及 \(1\) 对应的所有数的异或和 \(ans1\)，那么最后答案就是 \(ans0 \oplus msk, ans1 \oplus msk\)。
时间复杂度：\(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()
const int N = 1e6 + 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);
for(int i=1;i<=n;i++) cin >> a[i];
string s;
cin >> s;
s = " " + s;
vector<int> pre(n + 1);
int ans0 = 0, ans1 = 0;
for(int i=1;i<=n;i++){
pre[i] = a[i] ^ pre[i - 1];
if(s[i] == '0') ans0 ^= a[i];
else ans1 ^= a[i];
}
int q;
cin >> q;
int msk = 0;
while(q --){
int tp;
cin >> tp;
if(tp == 1){
int l, r;
cin >> l >> r;
msk ^= pre[r] ^ pre[l - 1];
}else{
int g;
cin >> g;
if(g == 0) cout << (ans0 ^ msk) << ' ';
else cout << (ans1 ^ msk) << ' ';
}
}
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(0), cout.tie(0);
// init();
int t = 1;
cin >> t;
while (t--) solve();
}用线段树多少有点费时间了（x
F. Selling a Menagerie
题意
给定 \(n\) 个动物，每个动物都有害怕的对象，动物 \(i\) 害怕 \(a_i, a_i \neq i\)，每个动物也有对应的价格 \(c_i\)。
现在，需要按照一定的顺序将所有动物卖掉，如果一个动物害怕的动物没有被卖掉，那么卖掉这个动物的价格会翻倍。
输出一种方案。
思路
首先，如果没有环，那么我们直接跑拓扑即可。
那么我们可以用类似的思路实现这道题。
首先，我们以 \(i \rightarrow a_i\) 的方式建立有向边，然后跑一边拓扑，那么剩下的点肯定都在环上。
那么显然，我们需要删掉一个点来让这个环变成链。因为一条链的最后一个删掉的点不可以价格翻倍，所以我们需要将环中的最小值放在最后一个删除。
从而，我们跑完拓扑后，枚举所有环，对于每个环，找出最小值 \(c_i\) 所在的位置 \(i\)，然后从 \(a_i\) 开始删除即可。
时间复杂度：\(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()
const int N = 1e6 + 10, M = 2e5 + 10, mod = 1e9 + 7, inf = 0x3f3f3f3f3f3f3f3f;
const double eps = 1e-9, PI = acos(-1);
void solve() {
int n;
cin >> n;
vector<vector<int>> e(n + 1);
vector<int> a(n + 1), in(n + 1);
for(int i=1;i<=n;i++){
cin >> a[i];
in[a[i]] ++;
e[i].pb(a[i]);
}
vector<int> v(n + 1);
for(int i=1;i<=n;i++) cin >> v[i];
vector<int> ans;
queue<int> q;
for(int i=1;i<=n;i++) {
if(in[i] == 0) q.ep(i);
}
vector<bool> st(n + 1);
while(!q.empty()){
int x = q.front(); q.pop();
ans.pb(x);
st[x] = true;
for(auto y : e[x]){
if(-- in[y] == 0) q.ep(y);
}
}
auto dfs = [&](auto dfs, int x, int p, vector<int> &v) -> void{
v.pb(x);
for(auto y : e[x]){
if(y == p || st[y]) continue;
st[y] = true;
dfs(dfs, y, x, v);
}
};
for(int i=1;i<=n;i++){
if(st[i]) continue;
st[i] = true;
vector<int> p;
dfs(dfs, i, -1, p);
int mn = *min_element(all(p), [&](int a, int b) -> bool{
return v[a] < v[b];
});
int start = a[mn];
int cur = start;
ans.pb(cur);
cur = a[cur];
while(cur != start){
ans.pb(cur);
cur = a[cur];
}
}
for(auto x : ans) cout << x << ' ';
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(0), cout.tie(0);
// init();
int t = 1;
cin >> t;
while (t--) solve();
}环不参与拓扑，因为入度不会减到 \(0\)
G. Replace With Product
题意
给定一个序列，定义一次操作为选定 \(l, r, l \leq r\)，并将 \(a_{[l, r]}\) 替换为区间所有数的乘积。
输出 一次操作后 序列总和的最大值 对应的方案。
思路
首先，直观上可以发现，我们只需考虑 \(1\) 的选择，因为只有 \(1\) 是改为乘后使总和减小的。
那么，如果出现乘积大于 \(2n\) 的情况，显然是全部乘起来更好（当然，两端的 \(1\) 不考虑），因为此时 \(1\) 不够让答案减小。
注意到 \(2n \leq 2 ^ {19}\)，实际上我们最多只需对 \(19\) 个非 \(1\) 的数进行相乘。
那么，我们重新整理一下思路：
找出所有非 \(1\) 的数；
预处理 前缀和 和 前缀乘；
在前缀乘的时候，判断乘积是否已经大于 \(2n\)，是的话直接令左端点为第一个非 \(1\) 的数，右端点为最后一个非 \(1\) 的数，并输出；
暴力枚举所有非 \(1\) 的数，作为左端点和右端点，并找出最后答案的最大值对应的方案。
时间复杂度：\(O(m ^ 2), m << 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()
const int N = 1e6 + 10, M = 2e5 + 10, mod = 1e9 + 7, inf = 0x3f3f3f3f3f3f3f3f;
const double eps = 1e-9, PI = acos(-1);
void solve() {
int n;
cin >> n;
vector<int> a(n + 1), sum(n + 1);
vector<pii> g;
int cur = 1;
for(int i=1;i<=n;i++){
cin >> a[i];
sum[i] = sum[i - 1] + a[i];
if(a[i] != 1) g.pb(i, a[i]);
}
if(g.size() <= 1){
cout << 1 << ' ' << 1 << '\n';
return;
}
for(int i=1;i<=n;i++){
cur *= a[i];
if(cur >= n * 2){
cout << g[0].fs << ' ' << g[g.size() - 1].fs << '\n';
return;
}
}
vector<int> prod(g.size() + 1);
prod[0] = 1;
for(int i=0;i<g.size();i++) prod[i + 1] = prod[i] * g[i].sc;
int mx = 0, tl = 0, tr = 0;
for(int i=0;i<g.size();i++){
for(int j=i+1;j<g.size();j++){
int k = prod[j + 1] / prod[i] - sum[g[j].fs] + sum[g[i].fs - 1];
if(k > mx){
tl = g[i].fs, tr = g[j].fs;
mx = k;
}
}
}
if(tl == 0) {
cout << 1 << ' ' << 1 << '\n';
return;
}
cout << tl << ' ' << tr << '\n';
}
signed main() {
# ifdef FLOATING_OCEAN
freopen("1.in","r",stdin);
freopen("1.out","w",stdout);
# endif
ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
// init();
int t = 1;
cin >> t;
while (t--) solve();
}妥妥一个诈骗题，最后几秒没交上去qaq
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来自 Blog - Floating Ocean！
评论