文章目录
A.Showstopper【贪心,模拟】
分析
考虑保证最大值的最大性,考虑最优的swap,首先维护第一行,如过说两列都是大于最大值的,就是非法的,如果有一个可以的,把那个小放到这里,如果都可以,考虑大的,使得第二行更安全。
实现
#include <bits/stdc++.h>
#define inf 0x3f3f3f3f
#define ll long long
#define ls (id << 1)
#define rs (id << 1 | 1)
using namespace std;
const int N = 105;
int a[N], b[N];
void solve() {
int n;
cin >> n;
for (int i = 1; i <= n; i++) cin >> a[i];
for (int i = 1; i <= n; i++) cin >> b[i];
for (int i = 1; i <= n - 1; i++) {
if (a[i] > a[n] && b[i] > a[n]) {
cout << "No\n";
return;
}
if (a[i] > a[n]) swap(a[i], b[i]);
else if (b[i] > a[n]) continue;
else {
int maxn = max(a[i], b[i]);
int minn = min(a[i], b[i]);
a[i] = maxn;
b[i] = minn;
}
}
for (int i = 1; i <= n - 1; i++) {
if (b[i] > b[n]) {
cout << "No\n";
return;
}
}
cout << "Yes\n";
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
int T = 1;
cin >> T;
while (T--) {
solve();
}
return 0;
}
B.Three Sevens【STL(邻接表)、倒着贪心】
分析
本题关键是如果在某个时间出现了,那么在先前就不可能是winner,首先考虑最后一天,最后一天出现的日子都不可能是其他日子的winner,所以我们可以任选一个,对于倒数第二天出现的人,除去倒数第一天出现过的人,我们可以任选一个,但是这些剩下的人也无法在更早的时间成为winner,依次类推。为了防止memset超时,我们使用vector邻接表来维护,并且使用set来记录是否出现过。
时间复杂度
O
(
n
l
o
g
n
)
O(nlogn)
O(nlogn)
实现
#include <bits/stdc++.h>
#define inf 0x3f3f3f3f
#define ll long long
#define ls (id << 1)
#define rs (id << 1 | 1)
using namespace std;
const int N = 5e4 + 5;
vector<int> a[N];
void solve() {
int m;
cin >> m;
set<int> st;
for (int i = 1; i <= m; i++) a[i].clear();//清空
for (int i = 1; i <= m; i++) {
int n;
cin >> n;
for (int j = 0; j < n; j++) {
int c;
cin >> c;
a[i].push_back(c);
}
}
vector<int> ans;
for (int i = m; i >= 1; i--) {
int flag = 0;
for (auto j : a[i]) {
if (!st.count(j)) {
if (!flag) ans.push_back(j), flag = 1;
st.insert(j);
}
}
if (!flag) {
cout << -1 << '\n';
return;
}
}
int sz = ans.size();
for (int i = sz - 1; i >= 0; i--) {
cout << ans[i] << " \n"[i == 0];
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
int T = 1;
cin >> T;
while (T--) {
solve();
}
return 0;
}
C.Candy Store【整除问题,贪心】
分析
我们尽可能使得更多的pack具有相同的价格。首先对于所有的价格,肯定是能被所有的单价整除,所以我们取lcm,最后的价格必须是lcm或者是lcm的倍数,但是我们应该如何检验,能否凑出这样的单价呢?考虑首先,最后所以取相等的价格必然是所有ai*bi的gcd,因为都是因子凑出来的,而且这些因子在所有的积中都存在。然后我们应该怎样操作呢?我们只需判断gcd能否整除lcm即可。我们对于所有求出来的最大公因子gcd,我们需要保证其能,所有的b[i]整除,这样才能凑出相同的价格。例如样例
20 3
6 2
gcd = gcd(60, 12) = 12,最多的公因子是12,我们需要凑出pack包裹价格为6 或者是6的倍数,既然能凑出6的倍数,既然6的倍数可以,那么6也是一定可以的,所以只要保证能构造出最小公倍数6即可。首先gcd % lcm 除不尽的话,说明没有lcm这个因子,必定不行。如果除得尽,必然可以凑出来,因为lcm中,对于每一对,包含了所有b[i],能除得尽的话我们可以从装成 lcm / b[i]个一包,这些因子在gcd中存在,所以每一对都是可以整除的,这样我们可以保证这些糖果包的价格均为lcm。
#include <bits/stdc++.h>
#define inf 0x3f3f3f3f
#define ll long long
#define ls (id << 1)
#define rs (id << 1 | 1)
using namespace std;
const int N = 2e5 + 5;
ll a[N], b[N];
ll lcm(ll a, ll b) {
return a / __gcd(a, b) * b;
}
void solve() {
int n;
cin >> n;
for (int i = 1; i <= n; i++) cin >> a[i] >> b[i];
ll may = a[1] * b[1], need = b[1];
int cnt = 1;
for (int i = 1; i <= n; i++) {
may = __gcd(a[i] * b[i], may);
need = lcm(b[i], need);
if (may % need) {
cnt++;
may = a[i] * b[i];
need = b[i];
}
}
cout << cnt << '\n';
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
int T = 1;
cin >> T;
while (T--) {
solve();
}
return 0;
}
D.Shocking Arrangement【结论题、数学】
分析
问题转换最大子段和小于最大差值d(定值),子段和可以转换为两个前缀和的差,只需要保证,最大的前缀和和最小的前缀和的差值不超过d,我赛时想了一个比较清奇的思路,我先放最小值,最小值一定是负数,如果再放一个负数会超过d,再放正数,依次类推。这样写法的正确性,首先当某个前缀和大于等于d的时候必定是错的,容易知道,最小值如果是非负的话必定会出问题,所以最小前缀和必定是负数,如果说最大前缀和是负数,那么最大前缀和与最小前缀和的绝对值均小于d,两者值差必然小于d,那么如果说,最大前缀是正的,那么能否存在两者值差大于等于d呢。
例如-1 0 3
首先前缀是负的部分一定满足,而且由于由于正数不能过多,只能有一个正的前缀,这样这个正的前缀必然小于等于最大值,所以必然小于d。
1
4
-1 0 3 5
No
实现
#include <bits/stdc++.h>
#define inf 0x3f3f3f3f
#define ll long long
#define ls (id << 1)
#define rs (id << 1 | 1)
using namespace std;
const int N = 3e5 + 5;
int a[N];
void solve() {
int n;
cin >> n;
for (int i = 1; i <= n; i++) cin >> a[i];
sort(a + 1, a + 1 + n);
ll d = a[n] - a[1];
ll sum = 0;
int l = 1, r = n;
vector<int> ans;
while (l < r) {
ll suml = abs(sum + a[l]), sumr = abs(sum + a[r]);
if (suml >= d && sumr >= d) {//这样一定是非法的
cout << "No\n";
return;
}
if (suml < d) {
sum += a[l];
ans.push_back(a[l]);
l++;
continue;
}
if (sumr < d) {
sum += a[r];
ans.push_back(a[r]);
r--;
continue;
}
}
if (l == r) {
if (abs(sum + a[l]) >= d) {
cout << "No\n";
return;
}
ans.push_back(a[l]);
}
int sz = ans.size();
cout << "Yes\n";
for (int i = 0; i < sz; i++) {
cout << ans[i] << " \n"[i == sz - 1];
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
int T = 1;
cin >> T;
while (T--) {
solve();
}
return 0;
}