A. Gamer Hemose
一开始看错题目,以为是同一个武器不能用两遍,原来是不能连续用两边。
那么最优解就是威力最大的和次大的轮流即可。
这里因为\(H\)~\(10^9\),因此直接循环会超时,那么就直接算答案好了。
// Problem: A. Gamer Hemose
// Contest: Codeforces - Codeforces Round #746 (Div. 2)
// URL: https://codeforces.com/contest/1592/problem/0
// Memory Limit: 256 MB
// Time Limit: 1000 ms
//
// Powered by CP Editor (https://cpeditor.org)
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
void solve() {
int n,h;
cin >> n >> h;
vector<int> a(n);
for(int i = 0;i < n;++i) {
cin >> a[i];
}
sort(a.begin(),a.end());
int res = 0;
res = (h / (a[n - 1] + a[n - 2])) * 2;
h %= (a[n-1] + a[n - 2]);
if (h == 0){
cout << res << endl;
return;
}
if (h <= a[n - 1]) res++;
else res+=2;
cout << res << endl;
}
int main() {
int t;cin >> t;
while (t--)
solve();
return 0;
}
B. Hemose Shopping
注意到当\(x\)比较大的时候,中间的某些数可能不会被碰到,假如这些无法移动的数并未处于正确排序位置,那么就不可能排序。否则其他任何情况都是可行的。
如果\(n≥2x\),那么所有数字都可以移动,这样一定可以排好序。否则处于区间\([n-x,x-1]\)(这里编号从0开始)的所有数都不会被移动,检查是否处于正确位置,只要一个数字不符合即为“NO”。
// Problem: B. Hemose Shopping
// Contest: Codeforces - Codeforces Round #746 (Div. 2)
// URL: https://codeforces.com/contest/1592/problem/B
// Memory Limit: 256 MB
// Time Limit: 1000 ms
//
// Powered by CP Editor (https://cpeditor.org)
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
void solve() {
int n,x;
cin >> n >> x;
vector<int> a(n);
vector<int> b(n);
for (int i = 0;i < n;++i) {
cin >> a[i];
b[i] = a[i];
}
sort(b.begin(),b.end());
if (n >= 2 * x){
puts("YES");
}else{
bool f = 1;
for (int i = n - x;i < x;++i) {
//cout << a[i] << " " << b[i] << endl;
if (a[i] != b[i]) {
f = 0;
break;
}
}
if (f)
puts("YES");
else
puts("NO");
}
}
int main() {
int t;cin >> t;
while (t--)
solve();
return 0;
}
C. Bakry and Partitioning
给定一棵\(n\)节点,\(n-1\)条边的树,问是否可以删除\([1,k-1]\)条边,使所有相连部分的异或和都相等。
首先,由于\(x\oplus x = 0\),因此如何所有节点的异或和为0,那么删除一条边就可以分为相等的两部分。
又因为\(x\oplus x\oplus x = x\),因此,对于任意的\(x\),我们如果可以将其分为异或和均为\(x\)的三部分(切两条边,\(k≥2\)),也是符合题意的。
除此之外的所有情况均无解。
对于第二种情况,我们统计所有节点的异或和为\(x\),并用dfs统计以i为根节点的子树的异或和\(a_i\),若至少有两个节点满足\(a_i=x\),则符合条件。
// Problem: C. Bakry and Partitioning
// Contest: Codeforces - Codeforces Round #746 (Div. 2)
// URL: https://codeforces.com/contest/1592/problem/C
// Memory Limit: 256 MB
// Time Limit: 1000 ms
//
// Powered by CP Editor (https://cpeditor.org)
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 100010;
vector<int> a;
int res;
int ans;
vector<int> g[N];
void dfs(int u,int v) {
for (auto i : g[u]) {
//cout << i << endl;
if (i == v) continue;
dfs(i,u);
if (ans == a[i]) res++;
else a[u] ^= a[i];
}
}
void solve() {
int n,k;
cin >> n >> k;
ans = 0;
res = 0;
for (int i = 1;i <= n;++i) {
g[i].clear();
}
a.resize(n + 1);
for (int i = 1;i <= n;++i) {
int x;cin >> x;
a[i] = x;
ans ^= x;
}
for (int i = 1;i <= n - 1;++i) {
int x,y;
cin >> x >> y;
g[x].push_back(y);
g[y].push_back(x);
}
if (ans == 0) {
puts("YES");
return;
}
if (k > 2) {
dfs(1,0);
//cout << res << endl;
if (res >= 2)
puts("YES");
else
puts("NO");
}else {
puts("NO");
}
}
int _;
int main() {
for (scanf("%d",&_);_;_--)
solve();
return 0;
}