Dashboard - Codeforces Round 886 (Div. 4) - Codeforces
A. To My Critics
判断任意两个大于10即可
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 2e5 + 10;
signed main() {
ios::sync_with_stdio(false);cin.tie(nullptr);
int a,b,c;
cin >> a >> b >> c;
if(a + b >= 10 || b + c >= 10|| a + c >= 10)
cout << "YES" << endl;
else
cout << "NO" << endl;
return 0;
}
B. Ten Words of Wisdom
把质量大于10的pass掉,剩下的排个序即可
#include <bits/stdc++.h>
#define int long long
using namespace std;
typedef pair<int,int> PII;
signed main() {
ios::sync_with_stdio(false);cin.tie(nullptr);
int T;
cin >> T;
while(T--){
int n;
cin >> n;
vector<PII> a;
for(int i = 1, x,y;i <= n;i ++){
cin >> x >> y ;
if(x > 10) continue;
else
a.emplace_back(i,y);
}
sort(a.begin(),a.end(),[](PII x,PII y){
return x.second > y.second;
});
cout << a.front().first << endl;
}
return 0;
}
C. Word on the Paper
模拟题,因为它没有逆字符串,所以遇到字符就加上即可
#include <bits/stdc++.h>
#define int long long
using namespace std;
signed main() {
ios::sync_with_stdio(false);cin.tie(nullptr);
int T;
cin >> T;
while(T--){
vector<string> g(8);
for(int i = 0;i < 8;i ++)
cin >> g[i];
string ans = "";
for(int i = 0;i < 8;i ++){
for(int j = 0;j < 8;j ++){
if(g[i][j] == '.')
continue;
else
ans += g[i][j];
}
}
cout << ans << endl;
}
return 0;
}
D. Balanced Round
就是找连续的数的差值在k的范围内的有多少,找到最大的之后其余的数就是至少要删掉的了
#include <bits/stdc++.h>
#define int long long
using namespace std;
typedef pair<int,int> PII;
signed main() {
ios::sync_with_stdio(false);cin.tie(nullptr);
int T;
cin >> T;
while(T--){
int n,k;
cin >> n >> k;
vector<int> a(n);
for(auto &i : a) cin >> i;
sort(a.begin(),a.end());
int ans = 0, now = 1;
for(int i = 0;i < n - 1;i ++ ){
if(a[i + 1] - a[i] <= k){
now++;
}else{
ans = max(now,ans);
now = 1;
}
}
ans = max(ans, now);
cout << n - ans << endl;
}
return 0;
}
E. Cardboard for Pictures
根据题意就是求\(\sum\limits_{i=1}^{n} (2 \times w + s_i)^2 = C\)这样一个公式中的\(w\)存在的,答案存在递增性,于是我们可以用二分答案来做,每次判断是否符合条件在计算过程中,可能会爆\(long long\),需要开__int128,如果你是只要大于就提前返回的话就不用开,另外因为要开方,所以\(w\)最大只能取\(1e9\).
#include <bits/stdc++.h>
#define int long long
using namespace std;
typedef pair<int,int> PII;
signed main() {
ios::sync_with_stdio(false);cin.tie(nullptr);
int T;
cin >> T;
while(T--){
int n,c;
cin >> n >> c;
vector<int> s(n);
for(auto &i : s) cin >> i;
auto check = [&](int x){
__int128 ans = 0;
for(auto i : s){
ans += ((__int128)2 * x + i) * ((__int128)2 * x + i);
if(ans > c) return true;
}
return ans > c;
};
int l = 1, r = 1e9;
while(l <= r){
int mid = (l + r) >> 1;
if(check(mid))
r = mid - 1;
else
l = mid + 1;
}
cout << l - 1 << endl;
}
return 0;
}
F. We Were Both Children
用一个桶\(s\)去维护每只青蛙能跳到的最大倍数,暴力枚举每个\(a_i\)能贡献到的最大的\(s_j\),即\(j\)是\(a_i\)的倍数,最后在桶里找一个最大值即可\(\mathcal{O}(nlogn)\)
#include <bits/stdc++.h>
#define int long long
using namespace std;
typedef pair<int,int> PII;
signed main() {
ios::sync_with_stdio(false);cin.tie(nullptr);
int T;
cin >> T;
while(T--){
int n,c;
cin >> n ;
vector<int> s(n + 1);
for(int i = 0;i < n;i ++) {
cin >> c;
if(c <= n)
s[c] ++;
}
for(int i = n;i >= 1; i--){
for(int j = 2 * i; j <= n;j += i)
s[j] += s[i];
}
cout << *max_element(s.begin(),s.end()) << endl;
}
return 0;
}
G. The Morning Star
可以用map来维护四个桶,记录四个方向,另外四个方向都是在同一条直线上,所以我计算出结果后乘2即可,对于\(N,S,x相同,W,E,y相同,NE,SW,x - y相同,SE,NW,x+y相同\),将星星个数全部累加起来即可
#include <bits/stdc++.h>
#define int long long
using namespace std;
typedef pair<int,int> PII;
signed main() {
ios::sync_with_stdio(false);cin.tie(nullptr);
int T;
cin >> T;
while(T--){
int n;
cin >> n;
map<int,int> mp[4];
int ans = 0;
for(int i = 0,x,y;i < n;i ++){
cin >> x >> y;
ans += mp[0][x] ++ ;
ans += mp[1][y] ++ ;
ans += mp[2][x - y] ++ ;
ans += mp[3][y + x] ++ ;
}
cout << ans * 2 << endl;
}
return 0;
}