2023年华北水利水电大学acm校赛题解
A.给学生们排个序吧
- 知识点：循环
- 难度：2
- 题解：简单的结构体排序
- 代码：
#include<bits/stdc++.h>
using namespace std;
struct node{
int x;
int y;
}a[1005];
bool cmp(node p,node q){
if(p.x!=q.x){
if(p.x>q.x){
return true;
}
else{
return false;
}
}
else{
return p.y<q.y;
}
}
int main()
{
int n;
cin>>n;
int i,j;
for(i=0;i<n;i++){
cin>>a[i].x>>a[i].y;
}
sort(a,a+n,cmp);
for(i=0;i<n;i++){
cout<<a[i].x<<' '<<a[i].y<<'\n';
}
return 0;
}
B.象棋棋盘搜索问题
- 知识点：搜索，dfs或bfs
- 难度：3
- 题解：基础爆搜题目，先找到黑卒的位置和红将之后，对黑卒或红将进行搜索，深度优先搜索需要标记已搜索位置，广度优先搜索直接搜索即可。若能搜索到，输出yes，否则输出no
- 代码：
#include<bits/stdc++.h>
using namespace std;
string s[10];
int flag = 0;
void dfs(int a,int b)
{
if(a<0||a>=10||b<0||b>=9||flag==1)
return;
if(s[a][b]=='1')
return;
if(s[a][b]=='3')
{
flag = 1;
return;
}
s[a][b] = '1';
dfs(a + 1, b);
dfs(a - 1, b);
dfs(a, b + 1);
dfs(a, b - 1);
}
int main()
{
for (int i = 0; i < 10;i++)
cin >> s[i];
for (int i = 0; i < 10;i++)
{
for (int j = 0; j < 9;j++)
{
if(s[i][j]=='2')
dfs(i, j);
}
}
if(flag==1)
cout << "yes";
else
cout << "no";
return 0;
}
C.三角形问题
- 知识点：签到
- 难度：1
- 题解：简单的判断三角形，可以先将其按顺序排列好，再进行判断即可。
- 代码：
#include <bits/stdc++.h>
using namespace std;
#define ll long long
void solve()
{
vector<int> v;
int x;
for (int i = 0; i < 3; i++)
{
cin >> x;
v.push_back(x);
}
sort(v.begin(), v.end());
if (v[0] + v[1] <= v[2])
{
cout << "error";
return;
}
if (v[0] == v[1] && v[1] == v[2])
{
cout << "equilateral";
return;
}
if (v[0] * v[0] + v[1] * v[1] == v[2] * v[2])
{
cout << "right";
return;
}
cout << "normal";
}
int main()
{
ll _ = 1;
// cin >> _;
while (_--)
{
solve();
}
}
D.耗子哥的新书包
- 知识点：dp
- 难度：4
- 题解：经典dp题目，dp又叫动态规划，即用空间换时间，这道题就是将横坐标表示书包剩余空间，然后将物品按顺序一个个插入尝试，最终获得最优解。
- 代码：
#include <bits/stdc++.h>
using namespace std;
int t,m,dp[1005],ti[105],val[105];
int main()
{
int i,j;
cin>>t>>m;
for(i=1; i<=m; i++)
cin>>ti[i]>>val[i];
for(i=1; i<=m; i++)/**< 特别注意滚动的方向必须从大到小 */
for(j=t; j>=ti[i]; j--) /**< dp[j]不选择i物品,dp[j-ti[i]]+val[i]选择i */
dp[j]=max(dp[j],dp[j-ti[i]]+val[i]);
cout<<dp[t];
return 0;
}
E.我要当学霸
- 知识点：循环统计
- 难度：2
- 题解：对于每个同学拿书之后，将其统计起来，最后对学号进行排序，然后找出所有拿书数量大于等于k的同学，将其学号输出即可。这道题数据比较大，所以需要开longlong来存储。
- 代码：
#include<bits/stdc++.h>
using namespace std;
#define ll long long
void solve()
{
ll m, n, k;
map<ll, ll> a;
cin >> m >> n >> k;
int flag=1;
for (int i = 0; i < m;i++)
{
ll x, y;
cin >> x >> y;
a[x]+=y;
}
for (auto it = a.begin(); it != a.end();it++)
{
if(it->second>=k)
{cout << it->first << " ";flag=0;}
}
if(flag)
cout<<0;
cout<<endl;
}
int main()
{
ll _;
cin >> _;
while (_--)
{
solve();
}
}
F.新阶乘
- 知识点：计算
- 难度：1
- 题解：简单的循环计算，但每次只取最后一位。也可以直接进行计算，阶乘的最后一位当n大于5的时候就恒为0，前n项和也可以直接用公式计算即可。
- 代码：
#include <bits/stdc++.h>
using namespace std;
#define ll long long
void solve()
{
int x;
cin >> x;
int a=1, b=0, c;
for (int i = 1; i <= x;i++)
{
a = (a * i) % 10;
b = (b + i) % 10;
}
c = (a + b) % 10;
cout << c;
}
int main()
{
ll _ = 1;
// cin >> _;
while (_--)
{
solve();
}
}
G.小凡的孤岛
- 知识点：floyd，思维
- 难度：5
- 题解：对于这道题，需要先用floyd算法，求出多元最短路，然后找公共路，对每条路都进行遍历，最终使用某条公共路时，总花费最小。
- 代码：
#include <bits/stdc++.h>
#define maxn 410
#define inf 100000000
using namespace std;
int n, m, mp[maxn][maxn], a1, a2, a3, a4, ans;
int main()
{
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++)
if (i != j)
{
mp[i][j] = inf;
}
for (int i = 1; i <= m; i++)
{
scanf("%d%d%d", &a1, &a2, &a3);
mp[a1][a2] = mp[a2][a1] = a3;
}
for (int k = 1; k <= n; k++)
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++)
{
mp[i][j] = min(mp[i][j], mp[i][k] + mp[k][j]);
}
scanf("%d%d%d%d", &a1, &a2, &a3, &a4);
ans = mp[a1][a2] + mp[a3][a4];
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++)
{
ans = min(ans, mp[i][j] + mp[a1][i] + mp[j][a2] + min(mp[a3][i] + mp[j][a4], mp[a4][i] + mp[j][a3]));
}
printf("%d", ans);
return 0;
}
H.最近的人
- 知识点：bfs搜索
- 难度：4
- 题解：使用bfs进行广度优先搜索，将距离为1的点先找出，然后周围为距离为2的点，依次类推。最后将所有点最近的1标记距离。
- 代码：
#include <iostream>
#include <algorithm>
#include <cstring>
#include <queue>
using namespace std;
const int N = 1e3 + 5;
typedef pair<int, int> PII;
int dis[N][N];
int n, m;
char g[N][N];
void bfs() { // 广搜
queue<PII> q;
memset(dis, -1, sizeof dis);
for (int i = 0; i < n; i++) { //为1的点全部加入队列
for (int j = 0; j < m; j++) { //并且距离为零
if (g[i][j] == '1') {
dis[i][j] = 0;
q.push({i, j});
}
}
}
int dt[4][2] = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}};
while (!q.empty()) { // 广搜
auto t = q.front();
q.pop();
int x = t.first, y = t.second;
for (int i = 0; i < 4; i++) {
int dx = x + dt[i][0];
int dy = y + dt[i][1];
if (dx >= 0 && dx < n && dy >= 0 && dy < m && dis[dx][dy] == -1) {
dis[dx][dy] = dis[x][y] + 1;
q.push({dx, dy});
}
}
}
}
int main() {
cin >> n >> m;
for (int i = 0; i < n; i++) cin >> g[i];
bfs();
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
cout << dis[i][j] << " ";
}
cout << endl;
}
return 0;
}
I.耗子哥裁布条
- 知识点：字符串
- 难度：2
- 题解：简单的查询字符串，直接双循环暴力即可，有能力的可以使用字符串对比算法KMP算法。
- 代码：
#include <bits/stdc++.h>
using namespace std;
#define ll long long
void solve()
{
string s, s1;
while (1)
{
cin >> s;
if (s[0] == '#')
return;
cin >> s1;
int num = 0;
for (int i = 0; i < s.length(); i++)
{
int j = 0, k = i;
for (; j < s1.length(); j++, k++)
{
if (s[k] != s1[j])
break;
}
if (j == s1.length())
{
i = k - 1;
num++;
}
}
cout << num << endl;
}
}
int main()
{
ll _ = 1;
// cin >> _;
while (_--)
{
solve();
}
}
J.苗学长要毕业了
-
知识点：stl的使用
-
难度：4
-
题解：使用map函数，来找到有多少个以k为倍数结束的串，若串中包含数字为奇数个，那么这个串就只有一种选择方法，个数为（n+1）/2，n为串中数字个数。若串中包含数字个数为偶数个，那么其选择方法有（n/2)+1种，其选择之后的个数为n/2种。选择方法之间是相乘的关系。例如：
k=2的时候，串为1 2 4 8 16 32，其为偶数，选择其中3个作为邀请人，有四种不同邀请方式
1 4 16，1 4 32，1 8 32， 2 8 32。
-
代码：
#include <bits/stdc++.h>
using namespace std;
#define ll long long
const ll mod = 1e9 + 7;
int main() {
ll n, k;
cin >> n >> k;
map<ll, ll> mp;
while (n--) {
ll x;
cin >> x;
mp[x] = 1;
}
int sum = 0, sum1 = 1;
for (map<ll, ll>::iterator it = mp.begin(); it != mp.end(); it++) {
if (it->second == 2)
continue;
ll x = it->first;
ll num = 0;
while (mp.find(x) != mp.end()) {
mp[x] = 2;
num++;
x = x * k;
}
sum += ((num + 1) / 2);
if (num % 2 == 0)
sum1 = ((sum1 % mod) * ((num / 2 + 1) % mod)) % mod;
}
cout << sum<<" "<<sum1 ;
}
