Contestant_. Rank 240. Rating +152 (+652 -500).
A. Escalator Conversations
题意
给定 \(m\) 个台阶，以及相邻两个台阶的平面所在的高度差 \(k\)。
另给定 \(n\) 个人，每个人的高度是 \(h_i\)。
若两个人站在两个不同的台阶上，且 两个人的身高差 等于 这两个台阶的高度差，那么他们可以一起聊天。
给定 \(A\) 的身高 \(H\)，输出他可以和多少人聊天。
思路
题意简化为：遍历 \(h_i\)，设 \(x = abs(H - h_i)\)，记录满足 \(x | k\) 且 \(1 \leq \frac{x}{k} \leq m - 1\) 的个数。
时间复杂度：\(O(n)\)
对应AC代码
#include <bits/stdc++.h>
using namespace std;
//#define FLOATING_OCEAN
#define int long long
#define pii pair<int, int>
#define pipi pair<pii, pii>
#define ppii pair<int, pii>
#define pci pair<char, int>
#define fs first
#define sc second
#define pb emplace_back
#define rall(x) x.rbegin(),x.rend()
#define all(x) x.begin(),x.end()
const int N = 2e5 + 10, M = 2e5 + 10, mod = 998244353, inf = 0x3f3f3f3f3f3f3f3f;
void solve() {
int n, m, k, h;
cin >> n >> m >> k >> h;
int cnt = 0;
for(int i=0;i<n;i++){
int cur;
cin >> cur;
if(abs(cur - h) / k > 0 && abs(cur - h) / k <= (m - 1) && abs(cur - h) % k == 0){
cnt ++;
}
}
cout << cnt << '\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);
int t = 1;
cin >> t;
while (t--) solve();
}有点阅读理解了（
B. Parity Sort
题意
给定一个序列，定义一次操作为选择两个奇偶性相同的元素，并将其交换。
输出任意次交换后是否可以让序列不递减。
思路
我们记原序列为 \(a\)，并直接把序列升序排个序，记为序列 \(b\)。
我们遍历所有位，判断 \(a_i\) 和 \(b_i\) 的奇偶性是否都相等即可。
不相等，那就一定不可以。
时间复杂度：\(O(n \log n)\)
对应AC代码
#include <bits/stdc++.h>
using namespace std;
//#define FLOATING_OCEAN
#define int long long
#define pii pair<int, int>
#define pipi pair<pii, pii>
#define ppii pair<int, pii>
#define pci pair<char, int>
#define fs first
#define sc second
#define pb emplace_back
#define rall(x) x.rbegin(),x.rend()
#define all(x) x.begin(),x.end()
const int N = 2e5 + 10, M = 2e5 + 10, mod = 998244353, inf = 0x3f3f3f3f3f3f3f3f;
void solve() {
int n;
cin >> n;
vector<int> a(n), b(n);
for(int i=0;i<n;i++) cin >> a[i], b[i] = a[i];
sort(all(b));
for(int i=0;i<n;i++){
if(a[i] % 2 != b[i] % 2){
cout << "NO\n";
return;
}
}
cout << "YES\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);
int t = 1;
cin >> t;
while (t--) solve();
}签到
C. Tiles Comeback
题意
给定排成一行的 \(n\) 个方块，每个方块都有一个颜色 \(c_i\)。
现在，判断是否能找出一条 不后退的 从起点到终点的 路径，满足下面的条件：
路径长度是 \(k\) 的倍数；
路径可切割为若干段长为 \(k\) 的子段，每个子段需满足颜色相同
思路
很显然，我们直接找最短的路径。
也就是说，如果起点和终点颜色都为 \(p\)，我们直接在起点和终点中挑 \(k-2\) 个颜色为 \(p\) 的点即可。
如果起点和终点颜色分别为 \(p, q\)，那么我们取前 \(k\) 个颜色为 \(p\) 的点和后 \(k\) 个颜色为 \(q\) 的点即可。
前者直接判点的个数，后者还需多判一个条件，即 从左往右数第 \(k\) 个颜色为 \(p\) 的点 在 从右往左数第 \(k\) 个颜色为 \(q\) 的点的左边。
时间复杂度：\(O(n)\)
对应AC代码
#include <bits/stdc++.h>
using namespace std;
//#define FLOATING_OCEAN
#define int long long
#define pii pair<int, int>
#define pipi pair<pii, pii>
#define ppii pair<int, pii>
#define pci pair<char, int>
#define fs first
#define sc second
#define pb emplace_back
#define rall(x) x.rbegin(),x.rend()
#define all(x) x.begin(),x.end()
const int N = 2e5 + 10, M = 2e5 + 10, mod = 998244353, inf = 0x3f3f3f3f3f3f3f3f;
void solve() {
int n, k;
cin >> n >> k;
vector<int> a(n);
for(int i=0;i<n;i++) cin >> a[i];
if(a[0] == a[n - 1]){
int cnt = 0;
for(int i=0;i<n;i++){
if(a[i] == a[0]) cnt ++;
}
cout << (cnt >= k ? "YES\n" : "NO\n");
return;
}
int cnt = 0, l = -1, r = -1;
for(int i=0;i<n;i++){
if(a[i] == a[0]){
cnt ++;
if(cnt == k) {
l = i;
break;
}
}
}
if(cnt != k){
cout << "NO\n";
return;
}
cnt = 0;
for(int i=n-1;i>=0;i--){
if(a[i] == a[n - 1]){
cnt ++;
if(cnt == k) {
r = i;
break;
}
}
}
if(cnt != k){
cout << "NO\n";
return;
}
cout << (l < r ? "YES\n" : "NO\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);
int t = 1;
cin >> t;
while (t--) solve();
}简单思维题
D. Prefix Permutation Sums
题意
对于一个未知的原数组 \(t\)，将其进行前缀和运算后得到一个数组 \(a\)。
现在，将数组 \(a\) 中的一个数去掉，得到数组 \(b\)。
给定数组 \(b\)，判断其对应的原数组 \(t\) 是否是 \(n\) 的排列。
思路
我们先通过相邻项作差，得到差分数组 \(c\)。
因为存在删除了元素的情况，并且删除的位置不确定，因而我们会出现下面的几种情况：
删除的元素在序列的最后，此时得到的 \(c\) 相比 \(t\) 只会少一个数，且不会多出其他数；
删除的序列在其他位置，此时会少两个数，并多出一个数，多出的数是缺少的两个数之和
分讨判断即可。
至于判断，可以用 \(map\)。
时间复杂度：\(O(n \log n)\)
对应AC代码
#include <bits/stdc++.h>
using namespace std;
//#define FLOATING_OCEAN
#define int long long
#define pii pair<int, int>
#define pipi pair<pii, pii>
#define ppii pair<int, pii>
#define pci pair<char, int>
#define fs first
#define sc second
#define pb emplace_back
#define rall(x) x.rbegin(),x.rend()
#define all(x) x.begin(),x.end()
const int N = 2e5 + 10, M = 2e5 + 10, mod = 998244353, inf = 0x3f3f3f3f3f3f3f3f;
void solve() {
int n;
cin >> n;
n --;
vector<int> a(n + 1);
for(int i=1;i<=n;i++) cin >> a[i];
map<int, int> mp;
for(int i=1;i<=n;i++){
mp[a[i] - a[i - 1]] ++;
}
n ++;
for(int i=1;i<=n;i++){
mp[i] --;
}
int v0 = 0, v1 = 0, cnt1 = 0, cnt2 = 0;
for(auto [x, y] : mp){
if(y < 0) v0 += x, cnt1 ++;
else if(y > 0) v1 += x, cnt2 ++;
}
if(cnt1 == 1 && cnt2 == 0){
cout << "YES\n";
}else if(cnt1 == 2 && cnt2 == 1){
cout << (v0 == v1 ? "YES\n" : "NO\n");
}else cout << "NO\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);
int t = 1;
cin >> t;
while (t--) solve();
}应该是分讨全了
E. Nastya and Potions
题意
给定 \(n\) 种药水，每种药水具有价格 \(c_i\)。
初始状态下，给定 \(k\) 种无限供应的药水，其不需额外合成。
现在，给定每种药水的合成表，即每种药水可以用其他的药水进行合成。
合成时，如果某一个药水无限供应，或者已经被预先合成，那么这个药水无需购买；否则需要花费对应价格的金币。
输出合成每种药水需要的最小金币数。
思路
首先，我们不妨将无限供应的药水的价格设为 \(0\)，那么本题就等价于如何安排药水的合成顺序，来让每种药水合成的原材料尽可能已经被合成。
如果药水 \(p\) 可以由 \(a, b, c\) 合成，我们就建立三条有向边 \(a \rightarrow p, b \rightarrow p, c \rightarrow p\)。然后依照拓扑序来合成即可。
时间复杂度：\(O(n)\)
对应AC代码
#include <bits/stdc++.h>
using namespace std;
//#define FLOATING_OCEAN
#define int long long
#define pii pair<int, int>
#define pipi pair<pii, pii>
#define ppii pair<int, pii>
#define pci pair<char, int>
#define fs first
#define sc second
#define pb emplace_back
#define rall(x) x.rbegin(),x.rend()
#define all(x) x.begin(),x.end()
const int N = 2e5 + 10, M = 2e5 + 10, mod = 998244353, inf = 0x3f3f3f3f3f3f3f3f;
void solve() {
int n, k;
cin >> n >> k;
vector<int> a(n + 1);
for(int i=1;i<=n;i++) cin >> a[i];
for(int i=1;i<=k;i++) {
int cur;
cin >> cur;
a[cur] = 0;
}
vector<vector<int>> e(n + 1);
vector<int> in(n + 1);
for(int i=1;i<=n;i++){
int cur;
cin >> cur;
while(cur --){
int x;
cin >> x;
if(a[i] == 0) continue;
e[x].pb(i);
in[i] ++;
}
}
queue<int> q;
vector<int> val(n + 1);
for(int i=1;i<=n;i++){
if(in[i] == 0) {
val[i] = inf;
q.emplace(i);
}
}
while(!q.empty()){
int x = q.front();
q.pop();
a[x] = min(a[x], val[x]);
for(auto p : e[x]){
val[p] += a[x];
if(--in[p] == 0) q.emplace(p);
}
}
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(0), cout.tie(0);
int t = 1;
cin >> t;
while (t--) solve();
}有种奇怪的贪心的味道
F. Lisa and the Martians
题意
给定一个序列 \(a\)，满足 \(0 \leq a_i < 2^k\)，其中 \(k\) 给定。
现在，对于式子 \((a_i \oplus x) \& (a_j \oplus x), 0 \leq x < 2 ^ k\)，输出所有可能的答案中，最大的答案对应的 \(i, j, x\)。
思路
首先，如果我们不异或，那么我们一定希望取最高位尽量都是 \(1\) 的二元组。
那么，在异或的参与下，我们可以将 \(0\) 转变为 \(1\)，也就是说，如果某一位对应的 \(a_i, a_j\) 上的值相等，我们就可以通过异或将其改为全是 \(1\)，从而使其与运算后变为 \(1\)。
那么，不难发现，在异或的参与下，最后的最优答案就是 \(a_i,a_j\) 同或后的值的最大值。
也就是说，最后答案就是 使 \(a_i \oplus a_j\) 最小的 二元组 \(<i, j>\)。
至此，我们有两种做法。
一种做法是 \(\mathtt{01\ Trie}\)，我们利用贪心即可解决。
另一种做法是根据异或的性质。
我们将数组 \(a\) 排序，并计算相邻两个数的异或值的最小值，那么这个最小值对应的二元组在原数组的下标即为答案。
不难证明，数组中两个数的异或值的最小值 就是 排序后所有相邻数的异或值的最小值。
得到答案后，我们按照 \(a_i, a_j\) 每一位的关系构造 \(x\) 即可。
时间复杂度：\(O(n \log n)\)
对应AC代码（xor性质）
#include <bits/stdc++.h>
using namespace std;
//#define FLOATING_OCEAN
#define int long long
#define pii pair<int, int>
#define pipi pair<pii, pii>
#define ppii pair<int, pii>
#define pci pair<char, int>
#define fs first
#define sc second
#define pb emplace_back
#define rall(x) x.rbegin(),x.rend()
#define all(x) x.begin(),x.end()
const int N = 2e5 + 10, M = 2e5 + 10, mod = 998244353, inf = 0x3f3f3f3f3f3f3f3f;
void solve() {
int n, k;
cin >> n >> k;
vector<pii > a(n);
for (int i = 0; i < n; i++) cin >> a[i].fs, a[i].sc = i + 1;
sort(all(a));
int ind = 0, ans = 0;
for (int i = 1; i < n - 1; i++) {
if ((a[i].fs ^ a[i + 1].fs) < (a[ind].fs ^ a[ind + 1].fs)) {
ind = i;
ans = (a[i].fs ^ a[i + 1].fs);
}
}
cout << a[ind].sc << ' ' << a[ind + 1].sc << ' ';
int f1 = a[ind].fs;
int res = 0;
for (int i = k - 1; i >= 0; i--) {
int t1 = (f1 >> i) & 1, t2 = (f1 >> i) & 1;
res *= 2;
if (t1 == t2) res += (1 ^ t1);
else res++;
}
cout << res << '\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);
int t = 1;
cin >> t;
while (t--) solve();
}对应AC代码（01 Trie）
#include <bits/stdc++.h>
using namespace std;
//#define FLOATING_OCEAN
#define int long long
#define pii pair<int, int>
#define pipi pair<pii, pii>
#define ppii pair<int, pii>
#define pci pair<char, int>
#define fs first
#define sc second
#define pb emplace_back
#define rall(x) x.rbegin(),x.rend()
#define all(x) x.begin(),x.end()
const int N = 3e6 + 10, M = 2e5 + 10, mod = 998244353, inf = 0x3f3f3f3f3f3f3f3f;
struct TRIE01 {
int nxt[N][2], idx, cnt[N], len;
void init(int k) { len = k, memset(nxt, 0, (sizeof nxt[0]) * (idx + 1)), memset(cnt, 0, (sizeof cnt[0]) * (idx + 1)), idx = 0; }
void change(int x, bool del = false){
int now = 0;
for(int i= len - 1; i >= 0;i--) {
int p = (x >> i) & 1;
if(!nxt[now][p]) nxt[now][p] = ++ idx;
now = nxt[now][p], cnt[now] += (del ? -1 : 1);
}
}
void insert(int x) { change(x); }
void remove(int x) { change(x, true); }
int query(int s, bool large = true){ //查找和x异或后的最大值/最小值
int now = 0, ans = large ? 0 : (1 << len) - 1;
bool st = true; //取最小时，需要判断 是否是 第一次出现 cnt<2 的情况，防止自身异或
for (int i = len - 1; i >= 0; i--) {
int x = (s >> i) & 1;
if(large) x ^= 1;
if (!nxt[now][x] || (!large && st && cnt[nxt[now][x]] < 2)) {
st = false;
now = nxt[now][x ^ 1];
} else {
ans += (large ? 1 : -1) * (1 << i);
now = nxt[now][x];
}
}
return ans;
}
}trie01;
void solve() {
int n, k;
cin >> n >> k;
trie01.init(k);
vector<int> a(n);
map<int, vector<int>> mp; //存vector防止重复下标
for(int i=0;i<n;i++){
cin >> a[i];
trie01.insert(a[i]);
mp[a[i]].pb(i);
}
int ans = inf, ind = 0;
for(int i=0;i<n;i++) {
int x = trie01.query(a[i], false);
if(x <= ans) ind = i, ans = x;
}
cout << ind + 1 << ' ' << (mp[ans ^ a[ind]][0] == ind ? mp[ans ^ a[ind]][1] : mp[ans ^ a[ind]][0]) + 1 << ' ';
int f1 = a[ind];
int res = 0;
for (int i = k - 1; i >= 0; i--) {
int t1 = (f1 >> i) & 1, t2 = (f1 >> i) & 1;
res *= 2;
if (t1 == t2) res += (1 ^ t1);
else res ++;
}
cout << res << '\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);
int t = 1;
cin >> t;
while (t--) solve();
}这个性质太强了
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来自 Blog - Floating Ocean！
评论