A - Air Conditioner
#include <iostream>
using namespace std;
int main() {
int x;
cin >> x;
if( x >= 30 ) cout << " Yes\n";
else cout << "No\n";
return 0;
}
B - Distance
#include <iostream>
using namespace std;
#define int long long
int32_t main() {
int n, d, res = 0;
cin >> n >> d;
d = d * d;
for (int i = 1, x, y; i <= n; i++) {
cin >> x >> y;
if (x * x + y * y <= d) res++;
}
cout << res << "\n";
return 0;
}
C - Repsept
其实是可以直接暴力做的,根据任意取模,实际上我们可以在构造一串的7的过程中直接取模就好了,这样可以避免爆long long
的情况。如果连续k
个7
都不行的话就可以直接结束了。
#include <bits/stdc++.h>
using namespace std;
#define int long long
int32_t main() {
int x;
cin >> x;
if( x % 2 == 0 ) {
cout << "-1\n";
return 0;
}
if( x == 1 || x == 7 ) {
cout << "1\n";
return 0;
}
for( int d = 7 , t = 1 ; t <= x ; t ++ , d = (d * 10 + 7 ) % x ){
if( d == 0 ){
cout << t << "\n";
return 0;
}
}
cout << "-1\n";
return 0;
}
D - Alter Altar
要把序列变成符合条件的有三种策略,全部变R
,全部变W
,只做交换。三种情况中一定包含最优解。我们贪心计算然后取min即可。
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
int n;
string s;
cin >> n >> s;
int cnt = 0, d = 0;
for (auto i: s)
if (i == 'R') d++;
for (int i = 0; i < n; i++) {
if (i < d) {
if (s[i] == 'W') cnt++;
} else {
if (s[i] == 'R') cnt++;
}
}
cout << min({d, n - d, cnt / 2});
return 0;
}
E - Logs
首先可以二分答案来做,想如何进行判定,显然把长度为\(L\)的分割为长度小于等于\(K\)的最少次数为\(\left \lceil \frac{L}{K} \right \rceil -1\)。这样我们就能直接进行\(O(n)\)的判定。
#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 , k;
cin >> n >> k;
vector<int> a(n);
for( auto & i : a ) cin >> i;
auto check = [a,k]( int x ){
int cnt = 0;
for( auto i : a )
cnt += ( i + x - 1 ) / x - 1;
return cnt <= k;
};
int l = 1 , r = 1e9 , res = -1;
while( l <= r ) {
int mid = ( l + r ) >> 1;
if( check(mid) ) res = mid , r = mid - 1;
else l = mid + 1;
}
cout << res << "\n";
return 0;
}
F - Range Set Query
本题是在无修改的情况下进行区间查询。一个比较简单的思路就是离线做。离线之后把询问区间排序,然后维护前缀数量,如果已经有相同的颜色,此时我们可以贪心的保留最靠右的。至于数量的维护可以用树状数组实现,树状数组每一位表示该位置上的时候被选择,这样直接用区间求和就可以完成回答。
#include <bits/stdc++.h>
using namespace std;
#define int long long
struct node {
int l, r, id;
node(int l = 0, int r = 0, int id = 0) : l(l), r(r), id(id) {};
bool operator<(const node &b) const {
if (r != b.r) return r < b.r;
return id < b.id;
}
};
struct BinaryIndexedTree {
#define lowbit(x) ( x & -x )
int n;
vector<int> b;
BinaryIndexedTree(int n) : n(n), b(n + 1, 0) {};
void add(int i, int y) {
for (; i <= n; i += lowbit(i)) b[i] += y;
return;
}
int calc(int i) {
int sum = 0;
for (; i; i -= lowbit(i)) sum += b[i];
return sum;
}
int calc(int l, int r) {
return calc(r) - calc(l - 1);
}
};
int32_t main() {
ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
int n, q;
cin >> n >> q;
vector<int> c(n + 1);
vector<int> lastC(n + 1, 0);
vector<int> res(q);
vector<node> query(q);
for (int i = 1; i <= n; i++)
cin >> c[i];
for (int i = 0; i < q; i++)
cin >> query[i].l >> query[i].r, query[i].id = i;
sort(query.begin(), query.end());
int L = 1;
BinaryIndexedTree bit(n);
for (const auto &[l, r, id]: query) {
for (int i = L; i <= r; i++) {
if (lastC[c[i]] != 0) bit.add(lastC[c[i]], -1);
lastC[c[i]] = i, bit.add(i, 1);
}
L = r + 1;
res[id] = bit.calc( l , r );
}
for( auto i : res )
cout << i << "\n";
return 0;
}
- Beginner AtCoder Contest 174beginner atcoder contest 174 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