StarryCoding入门教育赛2 题解 C++代码（推荐学习）

比赛地址：https://www.starrycoding.com/contest/6

比赛介绍

• 系列赛名称：StarryCoding 入门教育赛
• 难度：语法~较低
• 时长：$1.5$小时
• 比赛时间：约每2-3天一场，一般为晚上18:30~20:00
• 赛后题解：赛后立即发布，包含文字题解
• Rating结算范围：$<3000$

面向群体

• 有学习过程序设计课程，希望提高自己的编程水平、思维能力、算法能力的同学。
• 准备参加各种程序设计、算法竞赛（例如ACM、蓝桥杯、GPLT天梯赛等）的同学。
• 希望通过保/考研的机试、就业的算法笔/面试的同学。
• 非计算机专业，但对编程/算法感兴趣的同学。
• 想要感受编程竞赛的计算机专业新生同学。

A 平方和判定

输入三个整数$a,b,c$，判断是否满足$a^2+b^2>c^2$，直接用if分支语句判断，或用三目运算符进行判断即可。

考察输入输出与分支语句。

#include <bits/stdc++.h>
using namespace std;
using ll = long long;void solve()
{ll a, b, c;cin >> a >> b >> c;cout << (a * a + b * b > c * c ? "YES" : "NO") << '\n';
}int main()
{ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);int _;cin >> _;while (_--)solve();return 0;
}

B 矩阵判定

枚举四元组$(i_1,j_1,i_2,j_2)$，判断对于所有四元组是否满足$A_{i_1,j_1}+A_{i_2,j_2}>A_{i_2,j_1}+A_{i_1,j_2}$即可。

时间复杂度为$O(n^2{m}^2)$。

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 53;
ll a[N][N];
void solve()
{int n, m;cin >> n >> m;for (int i = 1; i <= n; ++i)for (int j = 1; j <= m; ++j)cin >> a[i][j];for (int i = 1; i <= n; ++i){ // i1for (int j = i + 1; j <= n; ++j){ // i2for (int k = 1; k <= m; ++k){ // j1for (int l = k + 1; l <= m; ++l){ // j2if (a[i][k] + a[j][l] <= a[i][l] + a[j][k]){cout << "NO\n";return;}}}}}cout << "YES\n";
}int main()
{ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);int _;cin >> _;while (_--)solve();return 0;
}

C 曼哈顿种类

枚举所有点对，计算其曼哈顿距离后放入$set$中计算$size$，或放入数组中排序去重。

#include <bits/stdc++.h>
using namespace std;
using ll = long long;const int N = 1e3 + 9;ll x[N], y[N];ll getabs(ll x) { return x < 0 ? -x : x; }void solve()
{int n;cin >> n;for (int i = 1; i <= n; ++i)cin >> x[i] >> y[i];set<ll> st;for (int i = 1; i <= n; ++i)for (int j = i + 1; j <= n; ++j){st.insert(getabs(x[i] - x[j]) + getabs(y[i] - y[j]));}cout << st.size() << '\n';
}int main()
{ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);int _;cin >> _;while (_--)solve();return 0;
}

D 小e消消乐

根据题意，我们要联想到“栈”这个数据结构，并且注意题目中的弹珠大小不是$A_i$，而是$2^{A_i}$哟，所以两个大小相等的弹珠合并，相当于把指数（也就是$A_i$）增加$1$，而不是翻倍哦。

一些细节需要考虑，例如用while而不是if、栈内元素数量得大于$2$才能合并等等。

#include <bits/stdc++.h>
using namespace std;using ll = long long;
const ll N = 1e5 +9;
ll a[N];int main() 
{int n; cin >> n;int cnt = 0;for (int i = 1; i <= n; ++ i){cin >> a[++ cnt];while(cnt >= 2 && a[cnt] == a[cnt - 1])a[-- cnt]++;}cout << cnt << '\n';return 0;
}

E 妹妹太多怎么办呐！

首先通过数据范围猜测，可以接受时间复杂度$O(n!)$的做法，于是大胆去想$dfs$。

对于一种方案，实际上是一种“坐标的排列”，只要坐标排列确定了，那么最终的愉悦度也确定了，于是可以通过$dfs$枚举所有的方案，对于每种方案计算结果取最大即可。

这里需要注意的细节是，愉悦度不是单调的，有可能为负数。

如果对dfs深度优先搜索算法不熟悉的同学，推荐先看一下《算法基础课》https://www.starrycoding.com/course/1

#include <bits/stdc++.h>
using namespace std;
using ll = long long;const int N = 20;ll x[N], y[N], a[N];ll getabs(ll x) { return x < 0 ? -x : x; }ll dist(ll u, ll v)
{return getabs(x[u] - x[v]) + getabs(y[u] - y[v]);
}bitset<12> vis;
int n, k;
ll ans, asum;
int f[N]; // 表示选出的排列
// dep是层数，sum是当前的愉悦度
void dfs(int dep, ll sum)
{if(sum + asum <= ans)return;// 递归出口if (dep == k + 1){ans = max(ans, sum);return;}for (int i = 1; i <= n; ++i){// 已经去过了if (vis[i])continue;f[dep] = i;vis[i] = true;dfs(dep + 1, sum + a[i] - dist(f[dep - 1], i));vis[i] = false;}
}void solve()
{cin >> n >> k;for (int i = 1; i <= n; ++i)cin >> x[i] >> y[i] >> a[i];asum = 0;for(int i = 1;i <= n; ++ i)asum += a[i];ans = -2e18;vis.reset();dfs(1, 0);cout << ans << '\n';
}int main()
{ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);int _;cin >> _;while (_--)solve();return 0;
}