AtCoder Beginner Contest 272「ABCDE」
AtCoder Beginner Contest 272
A - Integer Sum
题目描述：
输入n个数字，求数字和
#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
#define inf 0x3f3f3f3f
#define mod7 1000000007
#define mod9 998244353
#define m_p(a,b) make_pair(a, b)
#define mem(a,b) memset((a),(b),sizeof(a))
#define io ios::sync_with_stdio(false)
typedef long long ll;
typedef pair <int,int> pii;
#define MAX 300000 + 50
int n, m, k, x;
int tr[MAX];
void work(){
cin >> n;
for(int i = 1; i <= n; ++i){
cin >> x;
m += x;
}
cout << m << endl;
}
int main(){
io;
work();
return 0;
}
B - Everyone is Friends
题目描述：
给出m场演出，以及每场演出的参加人员，如果存在任意两个人没有一起参加过演出，则输出No，否则是Yes
思路：
暴力计算即可
#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
#define inf 0x3f3f3f3f
#define mod7 1000000007
#define mod9 998244353
#define m_p(a,b) make_pair(a, b)
#define mem(a,b) memset((a),(b),sizeof(a))
#define io ios::sync_with_stdio(false)
typedef long long ll;
typedef pair <int,int> pii;
#define MAX 300000 + 50
int n, m, k, x;
bool tr[105][105];
void work(){
cin >> n >> m;
for(int i = 1; i <= m; ++i){
cin >> k;
vector<int>v;
for(int j = 1; j <= k; ++j){
cin >> x;
v.push_back(x);
}
for(int j = 0; j < v.size(); ++j){
for(int p = 0; p < v.size(); ++p){
tr[v[j]][v[p]] = tr[v[p]][v[j]] = 1;
}
}
}
for(int i = 1; i <= n; ++i){
for(int j = 1; j <= i; ++j){
if(i != j && !tr[i][j]){
cout << "No\n";
return;
}
}
}
cout << "Yes\n";
}
int main(){
io;
work();
return 0;
}
C - Max Even
题目描述：
给n个数字，让你任意挑两个不同的数字，使得数字之和最大，问最大可以是多少
思路：
奇偶分开，奇+奇=偶 偶+偶=偶，所以找大最大的两个奇数和最大的两个偶数求最大值就行
#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
#define inf 0x3f3f3f3f
#define mod7 1000000007
#define mod9 998244353
#define m_p(a,b) make_pair(a, b)
#define mem(a,b) memset((a),(b),sizeof(a))
#define io ios::sync_with_stdio(false)
typedef long long ll;
typedef pair <int,int> pii;
#define MAX 300000 + 50
int n, m, k;
ll x;
void work(){
cin >> n;
vector<ll>odd,even;
for(int i = 1; i <= n; ++i){
cin >> x;
if(x % 2)odd.push_back(x);
else even.push_back(x);
}
sort(odd.begin(), odd.end());
sort(even.begin(), even.end());
ll ans = -1;
if(odd.size() > 1)ans = max(ans, odd.back() + odd[(int)odd.size() - 2]);
if(even.size() > 1)ans = max(ans, even.back() + even[(int)even.size() - 2]);
cout << ans << endl;
}
int main(){
io;
work();
return 0;
}
D - Root M Leaper
题目描述：
给定
n*n的方格矩阵，你每一步都只能到达与你当前点距离为 m \sqrt{m} m的点 ，你需要输出一个n*n的方格矩阵，每个点(i,j)的需要输出从(1,1)到(i,j)的最短步数
思路：
bfs
假设当前在
(i,j)，到达(p,q)，需要满足： ( p − i ) 2 + ( q − j ) 2 = m (p-i)^2+(q-j)^2=m (p−i)2+(q−j)2=m枚举
m等于哪两个平方数的和，然后可以往八个方向跑，暴力bfs即可
#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
#define inf 0x3f3f3f3f
#define mod7 1000000007
#define mod9 998244353
#define m_p(a,b) make_pair(a, b)
#define mem(a,b) memset((a),(b),sizeof(a))
#define io ios::sync_with_stdio(false)
typedef long long ll;
typedef pair <int,int> pii;
#define MAX 300000 + 50
int n, m, k, x, y;
int tr[405][405];
vector<pii>v;
bool judge(int x, int y){
if(x < 1 || x > n || y > n || y < 1)return false;
if(tr[x][y]!=inf)return false;
return true;
}
void bfs(){
queue<pii>q;
q.push(m_p(1, 1));
while(!q.empty()){
auto [x, y] = q.front();q.pop();
// cout << x << ' ' << y << endl;
for(auto [dx, dy] : v){
int xx = x + dx;
int yy = y + dy;
// cout << xx << ' ' << yy << ' ' << judge(xx, yy) << endl;
if(!judge(xx, yy))continue;
tr[xx][yy] = min(tr[xx][yy], tr[x][y] + 1);
q.push(m_p(xx, yy));
}
}
}
void work(){
cin >> n >> m;
mem(tr, inf);
tr[1][1] = 0;
for(int i = 1; i <= 1000; ++i){
x = i;
y = sqrt(m - x*x);
if(y*y == m - x*x){
// cout << x << ' ' << y << endl;
v.push_back(m_p(x, y));
v.push_back(m_p(-x, y));
v.push_back(m_p(x, -y));
v.push_back(m_p(-x, -y));
v.push_back(m_p(y, -x));
v.push_back(m_p(-y, x));
v.push_back(m_p(-y, -x));
v.push_back(m_p(y, x));
}
}
bfs();
for(int i = 1; i <= n; ++i){
for(int j = 1; j <= n; ++j){
if(tr[i][j] == inf)cout << -1 << ' ';
else cout << tr[i][j] << ' ';
}
cout << endl;
}
}
int main(){
io;
work();
return 0;
}
E - Add and Mex
题目描述：
n个数，m轮，每轮都会给第i个元素a[i]加上i，输出每一轮最小未出现的非负数
思路：
不难发现答案的最大不会超过
n,最极端的情况是当前轮结束后剩下的数字是0 1 2 3 4...n-1,此时答案就是n所以我们可以考虑开一个大小为
n+1的vector，记做tr，记录当i等于a中未出现的最小的非负数时的所有可能的轮数，处理方法是对每个a[i]，假设0<=a[i]+k*i<=n，就在tr[a[i]+k*i]中push一个k我们从
tr[0]跑到tr[n],维护一个集合表示1-m中当前还没确定答案的所有的数，对于tr[i]，我们找出还没确定答案的且出现在tr[i]中的数字id，则ans[id]=i
#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
#define inf 0x3f3f3f3f
#define mod7 1000000007
#define mod9 998244353
#define m_p(a,b) make_pair(a, b)
#define mem(a,b) memset((a),(b),sizeof(a))
#define io ios::sync_with_stdio(false)
typedef long long ll;
typedef pair <int,int> pii;
#define MAX 300000 + 50
int n, m, k, x;
vector<int>tr[MAX];
int ans[MAX];
void work(){
cin >> n >> m;
for(int i = 1; i <= n; ++i){
cin >> x;
int num = x >= 0 ? 0 : (-x + i - 1) / i;
if(x < 0)x = (x%i+i)%i;
while(x <= 2e5){
tr[x].push_back(num);
x += i;
++num;
}
}
set<int>s;
for(int i = 1; i <= m; ++i)s.insert(i);
for(int i = 0; i <= 2e5; ++i){
set<int>ss;
for(auto x : tr[i])ss.insert(x);
for(auto x : s){
if(!ss.count(x))ans[x] = i;
}
set<int>fuck;
for(auto x : ss){
if(s.count(x))fuck.insert(x);
}
s = fuck;
if(s.size() == 0)break;
}
for(int i = 1; i <= m; ++i)cout << ans[i] << endl;
}
int main(){
io;
work();
return 0;
}