A - Filter
#include <bits/stdc++.h>
using namespace std;
#define int long long
int32_t main() {
ios::sync_with_stdio(false) , cin.tie(nullptr) , cout.tie(nullptr);
int n;
cin >> n;
for( int x ; n ; n -- ){
cin >> x;
if( x & 1 ) continue;
cout << x << " ";
}
return 0;
}
B - ASCII Art
#include <bits/stdc++.h>
using namespace std;
#define int long long
int32_t main() {
ios::sync_with_stdio(false) , cin.tie(nullptr) , cout.tie(nullptr);
int n , m;
cin >> n >> m;
for( int i = 1 , x ; i <= n ; i ++ ){
for( int j = 1 ; j <= m ; j ++ ){
cin >> x;
if( x == 0 ) cout << ".";
else cout << (char)('A'+x-1);
}
cout << "\n";
}
return 0;
}
C - Merge Sequences
模拟一下归并排序的过程
#include <bits/stdc++.h>
using namespace std;
#define int long long
int32_t main() {
ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
int n, m;
cin >> n >> m;
vector<int> a(n), b(m), c, d;
for (auto &i: a)
cin >> i;
for (auto &i: b)
cin >> i;
for (int t = 1, i = 0, j = 0; t <= n + m; t++) {
if (i == n) d.push_back(t), j++;
else if (j == m) c.push_back(t), i++;
else if (a[i] <= b[j]) c.push_back(t), i++;
else d.push_back(t), j++;
}
for (auto i: c)
cout << i << " ";
cout << "\n";
for (auto i: d)
cout << i << " ";
cout << "\n";
return 0;
}
D - Bank
用两个set
模拟一下这个过程就好了。
#include <bits/stdc++.h>
using namespace std;
#define int long long
int cnt[26];
int32_t main() {
ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
int n, q;
cin >> n >> q;
set<int> a, b;
for (int i = 1; i <= n; i++)
a.insert(i);
for (int op, x; q; q--) {
cin >> op;
if (op == 1)
b.insert(*a.begin()), a.erase(*a.begin());
else if( op == 2 ){
cin >> x;
b.erase(x);
}else
cout << *b.begin() << "\n";
}
return 0;
}
E - 2xN Grid
这个双指针就可以做
#include <bits/stdc++.h>
using namespace std;
#define int long long
int32_t main() {
ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
int n, na, nb, res = 0;
cin >> n >> na >> nb;
vector<pair<int, int>> a(na);
for (auto &[x, y]: a)
cin >> x >> y;
for( int i = 1 , pa = 0 , v , l ; i <= nb ; i ++ ){
cin >> v >> l;
while( l ){
int len = min( l , a[pa].second );
if( v == a[pa].first ) res += len;
a[pa].second -= len , l -= len;
if( a[pa].second == 0 ) pa ++;
}
}
cout << res << "\n";
return 0;
}
F - Sugar Water 2
我们的做法就是二分答案。二分第\(k\)大的浓度是\(x\),然后统计有多少种情况混合浓度大于\(x\)
浓度大于\(x\)的情况是$\frac{A_i+C_j}{A_i+B_i+C_j+D_j} > x \(,化简可以得到\)(1-x)A_i-B_ix>(x-1)C_j+D_jx$
发现不等式两边互补影响,我们算出两种糖水的参数\(p_i=(1-x)A_i-B_ix,q_i=(x-1)C_j+D_jx\)
把\(p,q\)排序后用双指针算出有多少对\((i,j)\)满足\(p_i>q_j\)即可,复杂度\(O(\log10^{12}N\log N)\)
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define double long double
int n, m, k;
vector<double> a, b, c, d;
constexpr double eps = 1e-12;
bool check(double x) {
int cnt = 0;
vector<double> p, q;
for (int i = 0; i < n; i++)
p.push_back((1.0 - x) * a[i] - b[i] * x);
for (int i = 0; i < m; i++)
q.push_back((x - 1.0) * c[i] + d[i] * x);
sort(p.begin(), p.end()), sort(q.begin(), q.end());
for (int i = 0, j = 0; i < n; i++) {
while (j < m && q[j] < p[i]) j++;
cnt += j;
}
return cnt >= k;
}
int32_t main() {
ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
cin >> n >> m >> k;
a = vector<double>(n), b = vector<double>(n);
c = vector<double>(m), d = vector<double>(m);
for (int i = 0; i < n; i++)
cin >> a[i] >> b[i];
for (int i = 0; i < m; i++)
cin >> c[i] >> d[i];
double l = 0, r = 1, mid, res;
while (r - l > eps) {
mid = (l + r) / 2.0;
if (check(mid)) res = mid, l = mid + eps;
else r = mid - eps;
}
cout << fixed << setprecision(9) << res * 100.0;
return 0;
}
- Beginner AtCoder Contest 294beginner atcoder contest 294 contest programming beginner atcoder beginner atcoder contest 296 beginner atcoder contest 295 beginner atcoder contest abcde beginner atcoder contest 335 beginner atcoder contest 332 beginner atcoder contest 328 beginner atcoder contest 334 beginner atcoder contest 315