Codeforces Round 888 (Div. 3)（视频讲解全部题目）

@[TOC](Codeforces Round 888 (Div. 3)（视频讲解全部题目）)

Codeforces Round 888 (Div. 3)（A–G）全部题目详解

A Escalator Conversations

#include<bits/stdc++.h>
#define endl '\n'
#define INF 0x3f3f3f3f
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int N = 1e5 + 10;void solve()
{int n, m, k, H;cin >> n >> m >> k >> H;int ans = 0;for(int i = 0; i < n; i ++){int h;cin >> h;int dis = abs(h - H);if(h != H && dis % k == 0 && dis / k < m)ans ++;}cout << ans << endl;
}signed main()
{ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);int t;cin >> t;while(t--)solve();
}

B Parity Sort

#include<bits/stdc++.h>
#define endl '\n'
#define INF 0x3f3f3f3f
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int N = 1e5 + 10;void solve()
{int n;cin >> n;vector<int>a(n);for(int i = 0; i < n; i ++)cin >> a[i];vector<int>b;b = a;sort(b.begin(), b.end());for(int i = 0; i < n; i ++){if(a[i] % 2 != b[i] % 2){cout << "NO" << endl;return;}}cout << "YES" << endl;
}signed main()
{ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);int t;cin >> t;while(t--)solve();
}

C Tiles Comeback

#include<bits/stdc++.h>
#define endl '\n'
#define INF 0x3f3f3f3f
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int N = 1e5 + 10;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.back()){if(count(a.begin(), a.end(), a[0]) >= k)cout << "YES" << endl;elsecout << "NO" << endl;}else{int c1 = count(a.begin(), a.end(), a[0]);int c2 = count(a.begin(), a.end(), a.back());int cnt = 0;for(int i = 0; i < n; i ++){if(a[i] == a[0])cnt ++;if(a[i] == a.back())c2 --;if(cnt == k)break;}if(c1 >= k && c2 >= k){cout << "YES" << endl;}else{cout << "NO" << endl;}}
}signed main()
{ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);int t;cin >> t;while(t--)solve();
}

D Prefix Permutation Sums

#include<bits/stdc++.h>
#define endl '\n'
#define INF 0x3f3f3f3f
#define int long long
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int N = 1e5 + 10;void solve()
{int n;cin >> n;vector<int>a(n - 1);for(int i = 0; i < n - 1; i ++)cin >> a[i];int sum = n * (n + 1) / 2;if(sum != a.back()){a.push_back(sum);map<int,bool>st;for(int i = 0; i < n; i ++){int b;if(!i)b = a[i];elseb = a[i] - a[i - 1];if(b <= 0 || b > n || st[b]){cout << "NO" << endl;return;}st[b] = true;}cout << "YES" << endl;}else{map<int,bool>st;int x, cnt = 0;for(int i = 0; i < n - 1; i ++){int b;if(!i)b = a[i];elseb = a[i] - a[i - 1];if(b <= 0 || b > 2 * n){cout << "NO" << endl;return;}if(b > n || st[b]){x = b;cnt ++;}st[b] = true;}if(cnt > 1){cout << "NO" << endl;return;}else{int sum = 0;int c = 0;for(int i = 1; i <= n; i ++){if(!st[i]){sum += i;c ++;}}if(c == 2 && sum == x){cout << "YES" << endl;}else{cout << "NO" << endl;}}}
}signed main()
{ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);int t;cin >> t;while(t--)solve();
}

E Nastya and Potions

#include<bits/stdc++.h>
#define endl '\n'
#define INF 0x3f3f3f3f
#define int long long
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int N = 2e5 + 10;
int c[N], idx[N], ans[N];
map<int,bool>p;
int n, k;
vector<int>edge[N];void bfs()
{queue<int>q;for(int i = 0; i < n; i ++){if(idx[i] == 0){q.push(i);if(p[i])ans[i] = 0;elseans[i] = c[i];}}while(q.size()){int t = q.front();q.pop();for(int i = 0; i < edge[t].size(); i ++){int son = edge[t][i];ans[son] += ans[t];idx[son] --;if(idx[son] == 0){if(p[son])ans[son] = 0;elseans[son] = min(ans[son], c[son]);q.push(son);}}}
}void solve()
{cin >> n >> k;for(int i = 0; i < n; i ++){c[i] = idx[i] = ans[i] = 0;edge[i].clear();}p.clear();for(int i = 0; i < n; i ++)cin >> c[i];for(int i = 0; i < k; i ++){int x;cin >> x;x --;p[x] = true;}for(int i = 0; i < n; i ++){int m;cin >> m;for(int j = 0; j < m; j ++){int x;cin >> x;x --;idx[i] ++;edge[x].push_back(i);}}bfs();for(int i = 0; i < n; i ++)cout << ans[i] << " ";cout << endl;
}signed main()
{ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);int t;cin >> t;while(t--)solve();
}

F Lisa and the Martians

#include<bits/stdc++.h>
#define endl '\n'
#define INF 0x3f3f3f3f
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int N = 1e5 + 10;void solve()
{int n, k;cin >> n >> k;vector<pii>a(n);for(int i = 0; i < n; i ++){cin >> a[i].first;a[i].second = i + 1;}sort(a.begin(), a.end());int minv = INT_MAX, a1, a2, p1, p2;for(int i = 0; i < n - 1; i ++){if(minv > (a[i].first ^ a[i + 1].first)){a1 = a[i].first, a2 = a[i + 1].first;p1 = a[i].second, p2 = a[i + 1].second;minv = a1 ^ a2;}}int x = 0;for(int i = 0; i < k; i ++){int x1 = (a1 >> i) & 1, x2 = (a2 >> i) & 1;if(x1 + x2 == 0)x += 1 << i;}cout << p1 << " " << p2 << " " << x << endl;
}signed main()
{ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);int t;cin >> t;while(t--)solve();
}

G Vlad and the Mountains

#include<bits/stdc++.h>
#define endl '\n'
#define INF 0x3f3f3f3f
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int N = 2e5 + 10;
int h[N], p[N];
struct NODE
{int a, b, w;
};
struct QRY
{int a, b, h_max, ii;
};
vector<NODE>edge;
vector<QRY>Q;
bool cmp1(NODE x, NODE y)
{return x.w < y.w;
}
bool cmp2(QRY x, QRY y)
{return x.h_max < y.h_max;
}int find(int x)
{if(x != p[x])p[x] = find(p[x]);return p[x];
}
void solve()
{edge.clear();Q.clear();int n, m;cin >> n >> m;for(int i = 1; i <= n; i ++)cin >> h[i];for(int i = 0; i < m; i ++){int a, b;cin >> a >> b;edge.push_back({a,b, max(h[a], h[b])});}sort(edge.begin(), edge.end(), cmp1);int q;cin >> q;vector<bool>ans(q);for(int i = 0; i <= n; i ++)p[i] = i;for(int i = 0; i < q; i ++){int a, b, e;cin >> a >> b >> e;Q.push_back({a, b, h[a] + e, i});}sort(Q.begin(), Q.end(), cmp2);int cnt = 0;for(int i = 0; i < q; i ++){while(cnt < m && Q[i].h_max >= edge[cnt].w){int pa = find(edge[cnt].a), pb = find(edge[cnt].b);if(pa != pb)p[pa] = pb;cnt ++;}if(find(Q[i].a) == find(Q[i].b))ans[Q[i].ii] = true;elseans[Q[i].ii] = false;}for(int i = 0; i < q; i ++){if(ans[i])cout << "YES" << endl;elsecout << "NO" << endl;}cout << endl;
}signed main()
{ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);int t;cin >> t;while(t--)solve();
}