AtCoder Beginner Contest 272(A~D)
本文最后更新于 847 天前,其中的信息可能已经有所发展或是发生改变。

A. Integer Sum


Origional Link

题目大意

  • NN 个数求和。

思想

  • 签到题。

代码

#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <sstream>
#include <vector>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <unordered_map>
#include <unordered_set>
using namespace std;
#define IOS ios::sync_with_stdio(false),cin.tie(nullptr),cout.tie(nullptr)
#define re register
#define fi first
#define se second
#define endl '\n'
typedef long long LL;
typedef pair<int, int> PII;
typedef pair<LL, LL> PLL;
const int N = 1e6 + 3;
const int INF = 0x3f3f3f3f, mod = 1e9 + 7;
const double eps = 1e-6, PI = acos(-1);
void solve(){
int n; cin >> n;
LL sum = 0;
while(n --){
LL x; cin >> x;
sum += x;
}
cout << sum << endl;
return ;
}
int main(){
IOS;
int _ = 1;
// cin >> _;
while(_ --){
solve();
}
return 0;
}

B. Everyone is Friends


Origional Link

题目大意

  • 给定编号 1N1\sim N 的人和编号 1M1\sim M 的聚会。
  • ii 行第一个数为 kik_i 代表参加编号为 MiM_i 的人共有 kik_i 个,之后是 kik_i 个参加该聚会的人的编号。
  • 问是否存在某两个人没有一起参加某个聚会。

思想

  • 模拟题。
  • 某两个人没有一起参加某个聚会,具体地,指编号为 ii 的人是否和除了自己本身之外所有编号的人参加了至少一次聚会。
  • 数据范围很小,可以用邻接矩阵来存储编号为 ii 和编号为 jj 的人是否一起参加过聚会的状态。
  • 最后扫一遍状态矩阵,判断是否满足题意即可。

#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <sstream>
#include <vector>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <unordered_map>
#include <unordered_set>
using namespace std;
#define IOS ios::sync_with_stdio(false),cin.tie(nullptr),cout.tie(nullptr)
#define re register
#define fi first
#define se second
#define endl '\n'
typedef long long LL;
typedef pair<int, int> PII;
typedef pair<LL, LL> PLL;
const int N = 200;
const int INF = 0x3f3f3f3f, mod = 1e9 + 7;
const double eps = 1e-6, PI = acos(-1);
int n, m;
int vis[N][N];
void solve(){
cin >> n >> m;
for(int i = 1; i <= m; i ++){
int t; cin >> t;
int num[N];
for(int j = 0; j < t; j ++) cin >> num[j]; //读入参加该聚会的人的编号
for(int j = 0; j < t; j ++){
for(int k = 0; k < t; k ++){
if(k != j) vis[num[j]][num[k]] = 1; //去除自己本身,所有参加该聚会的人两两组合。
}
}
}
bool flag = 1;
for(int i = 1; i <= n; i ++){
for(int j = i + 1; j <= n; j ++){
if(vis[i][j] == 0){
flag = 0;
break;
}
}
if(!flag) break;
}
if(flag) cout << "Yes" << endl;
else cout << "No" << endl;
return ;
}
int main(){
IOS;
int _ = 1;
// cin >> _;
while(_ --){
solve();
}
return 0;
}

C. Max Even


Origional Link

题目大意

  • 给定一个长度为 NN 的非负整数序列 A=(A1,A2,,AN)A = (A_1,A_2,\dots,A_N)
  • 求序列中某两个数之和为偶数的最大值,若不存在输出 1-1

思想

  • 思维题。
  • 维护最大和次大的两个奇数和偶数的值即可。
  • 不存在的条件是无法使两数相加为偶数的情况。

代码

#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <sstream>
#include <vector>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <unordered_map>
#include <unordered_set>
using namespace std;
#define IOS ios::sync_with_stdio(false),cin.tie(nullptr),cout.tie(nullptr)
#define re register
#define fi first
#define se second
#define endl '\n'
typedef long long LL;
typedef pair<int, int> PII;
typedef pair<LL, LL> PLL;
const int N = 200;
const int INF = 0x3f3f3f3f, mod = 1e9 + 7;
const double eps = 1e-6, PI = acos(-1);
LL o_1, o_2, e_1, e_2;
void solve(){
o_1 = o_2 = e_1 = e_2 = -1; //初始化为 -1
int n; cin >> n;
int O = 0, E = 0; //O为当前维护偶数的个数,E同理
while(n --){
LL x; cin >> x;
if(x % 2 == 0){ //偶数
if(o_1 == -1 && o_2 == -1) o_1 = x, O ++; //第一个偶数出现
else if(o_1 != -1 && o_2 == -1) o_2 = x, O ++; //第二个偶数出现
else{ //第三个及之后的偶数出现
if(x > o_2) o_2 = x; //x大于较小偶数则更新o_2
if(o_1 < o_2) swap(o_1, o_2); //维护o_1为最大的偶数
}
}
else{ //奇数同理
if(e_1 == -1 && e_2 == -1) e_1 = x, E ++;
else if(e_1 != -1 && e_2 == -1) e_2 = x, E ++;
else{
if(x > e_2) e_2 = x;
if(e_1 < e_2) swap(e_1, e_2);
}
}
}
if(O == 2 && E == 2){ //两个偶数相加为偶数,两个奇数相加为偶数,两种情况取最大
cout << max(o_1 + o_2, e_1 + e_2) << endl;
}
else if(O == 2 && E != 2){ //只存在两个偶数加和的情况
cout << o_1 + o_2 << endl;
}
else if(O != 2 && E == 2){ //只存在两个奇数加和的情况
cout << e_1 + e_2 << endl;
}
else cout << -1 << endl; //不存在的情况
}
int main(){
IOS;
int _ = 1;
// cin >> _;
while(_ --){
solve();
}
return 0;
}

D. Root M Leaper


Origional Link

题目大意

  • 存在 N×NN\times N 的矩阵,给定正整数 MM
  • 可以执行如下操作数次:
    • 从当前坐标 (i,j)(i,j) 移动到 (k,l)(k,l),当且仅当 (ik)2+(jl)2=M\sqrt{(i-k)^2+(j-l)^2}=\sqrt{M} 时。
  • (1,1)(1,1) 开始执行上述操作,输出到达某点执行上述操作的最少步数,若无法走到则输出 1-1

思想

  • BFS 搜索,难点在于移动的条件如何判断。
  • 我们需要进行枚举查找对于 (i,j)(i,j) 满足移动的点的偏移量,从而构建偏移量数组。
  • 即使 MM 的值再大,我们移动的范围也不会超过 N×NN\times N,故在初始化距离的同时进行计算。
  • 设当前坐标为 (0,0)(0,0)(虽然不在矩阵范围内,但方便直接计算偏移量),我们构建偏移量数组的条件为:i * i + j * j == m,其中 i,ji,j 的偏移是双向的,即满足该条件的偏移量实际为 (i,j),(i,j),(i,j),(i,j){(i,j),(-i,j),(i,-j),(-i,-j) }
  • 最后套用 BFS 搜索最小步数即可。

代码

#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <sstream>
#include <vector>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <unordered_map>
#include <unordered_set>
using namespace std;
#define IOS ios::sync_with_stdio(false),cin.tie(nullptr),cout.tie(nullptr)
#define re register
#define fi first
#define se second
#define endl '\n'
typedef long long LL;
typedef pair<int, int> PII;
typedef pair<LL, LL> PLL;
const int N = 505;
const int INF = 0x3f3f3f3f, mod = 1e9 + 7;
const double eps = 1e-6, PI = acos(-1);
int n, m;
int ans[N][N]; //记录步数,初始化为-1
bool vis[N][N]; //标记是否走过该点
vector<PII> d; //偏移量数组
void bfs(int l, int r){
vis[l][r] = 1; //标记起始点已经走过
ans[l][r] = 0; //起始点的不少恒为0
queue<PII> st;
st.push({l, r});
while(!st.empty()){
auto p = st.front(); st.pop();
for(int i = 0; i < d.size(); i ++){
int x = p.fi + d[i].fi, y = p.se + d[i].se;
if(x >= 1 && x <= n && y >= 1 && y <= n & !vis[x][y]){ //下一步在矩阵范围内且没有走过
ans[x][y] = ans[p.fi][p.se] + 1; //步数为上一个格子的步数+1
vis[x][y] = 1;
st.push({x, y});
}
}
}
}
void solve(){
cin >> n >> m;
for(int i = 0; i <= n; i ++){
for(int j = 0; j <= n; j ++){
ans[i][j] = -1;
if(i * i + j * j == m){ //初始化偏移量
d.push_back({i, j});
d.push_back({i, -j});
d.push_back({-i, j});
d.push_back({-i, -j});
}
}
}
bfs(1, 1); //从(1,1)开始搜索
for(int i = 1; i <= n; i ++){
for(int j = 1; j <= n; j ++){
cout << ans[i][j] << ' ';
}
cout << endl;
}
return ;
}
int main(){
IOS;
int _ = 1;
// cin >> _;
while(_ --){
solve();
}
return 0;
}
暂无评论

发送评论 编辑评论


				
|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
(╯‵□′)╯︵┴─┴
 ̄﹃ ̄
(/ω\)
∠( ᐛ 」∠)_
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ`)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ( ̄∇ ̄o)
ヾ(´・ ・`。)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò。)
Σ(っ °Д °;)っ
( ,,´・ω・)ノ"(´っω・`。)
╮(╯▽╰)╭
o(*////▽////*)q
>﹏<
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
颜文字
Emoji
小恐龙
花!
上一篇
下一篇