2023年9月2日
今天是ACWING和牛客小白的最新月赛77期，这次的题读题读了半天...
ACWING3724 街灯
题目理解
用差分得到光找的，用0代表没照到。然后是0的连续串，分别进行0串长度 / (k * 2 + 1)向上取整求和。
代码实现
#include<iostream>
#include<cstring>
#include<cmath>
using namespace std;
const int N = 1010;
int n, m, k;
int a[N];
int main()
{
while(cin >> n >> m >> k)
{
memset(a, 0, sizeof a);
for(int i = 1; i <= m; i++)
{
int p;
cin >> p;
a[max(1, p - k)] += 1;
a[min(n + 1, p + k + 1)] -= 1;
}
for(int i = 1; i <= n; i++)
a[i] += a[i - 1];
pair<int, int> q[N];
int cnt = 0;
for(int i = 1; i <= n; i++)
{
if(a[i] == 0)
{
q[cnt].first = i;
q[cnt].second = 0;
while(a[i] == 0 && i <= n)
{
q[cnt].second += 1;
i++;
}
cnt++;
}
}
int res = 0;
for(int i = 0; i < cnt; i++)
res += ceil(1.0 * q[i].second / (k * 2 + 1));
cout << res << endl;
}
return 0;
}
ACWING5181 好五好四
题目理解
求出数字里面的！！四最多！！一种情况。然后四和五可以相互转换的：5个四可以和4个五交换。然后每交换一次就是一个答案。
代码实现
#include<iostream>
using namespace std;
int main()
{
int n;
cin >> n;
int t = n;
int res = 0;
// 4、5混杂，得到4和5的个数，然后进行替换
int cnt4 = 0, cnt5;
while(n % 5 != 0 && n - 4 >= 0)
{
cnt4++;
n -= 4;
}
cnt5 = n / 5;
// 替换法则是5个4可以和4个5替换
if(cnt4 * 4 + cnt5 * 5 == t)
{
res++;
res += cnt4 / 5 + cnt5 / 4;
}
cout << res;
return 0;
}
ACWING5180 正方形泳池
题目理解
枚举树，限制两边进行枚举。
代码实现
#include<iostream>
#include<algorithm>
using namespace std;
const int N = 110;
pair<int, int> a[N];
int n, T;
int solve()
{
// 先排个序
sort(a + 1, a + 1 + T);
int res = 0;
for(int i = 1; i <= T; i++)
{
int up = n + 1, down = 0;
for(int j = i + 1; j <= T; j++)
{
// 如果在同一行
if(a[j].first == a[i].first) continue;
if(a[j].first - a[i].first > up - down) break;
res = max(res, a[j].first - a[i].first - 1);
// 更新边界
if(a[j].second >= a[i].second) up = min(up, a[j].second);
if(a[j].second <= a[i].second) down = max(down, a[j].second);
}
}
return res;
}
int main()
{
cin >> n >> T;
for(int i = 1; i <= T; i++)
cin >> a[i].first >> a[i].second;
// 加边界
a[++T] = {0, 0};
a[++T] = {0, n + 1};
a[++T] = {n + 1, 0};
a[++T] = {n + 1, n + 1};
// 找左右被限制的情况
int res = solve();
// 进行轴对称
for(int i = 1; i <= T; i++) swap(a[i].first, a[i].second);
cout << max(res, solve());
return 0;
}
牛客小白月赛77期 小why的方阵
题目理解
哎，想多了。直接暴力模拟
代码实现
#include<iostream>
using namespace std;
const int N = 5;
int a[N];
int main()
{
cin >> a[1] >> a[2] >> a[3] >> a[4];
int flag = 0;
for(int i = 1; i <= 4; i++)
{
int t = a[i];
for(int j = 0; j <= 9; j++)
{
a[i] = j;
int x1 = a[1] + a[2], x2 = a[3] + a[4], x3 = a[2] + a[4], x4 = a[1] + a[3];
if(x1 == x2 && x1 == x3 && x1 == x4 && x2 == x3 && x2 == x4 && x3 == x4)
flag = 1;
}
a[i] = t;
}
if(flag)
cout << "YES";
else
cout << "NO";
return 0;
}
牛客小白月赛77期 小why的循环置换
题目理解
这个题目一定要读懂题，就是把n个数字，放到数组里，然后数组的值和数组的下标进行建边。我们很容易得到的是最终的结果是需要n个自环。已经有m个环，所以还差n - m个环。
然后我们每次交换，就可以对一个，所以交换的次数也是n - m。
代码实现
#include<iostream>
using namespace std;
int main()
{
int n, m;
cin >> n >> m;
cout << n - m;
return 0;
}
牛客小白月赛77期 小why的商品归为
题目理解
一维差分实现，比如某个商品是在1但是要去8，所以在1~7的时候他就有用购物车。所以我们只需要让占用车车最多的数 / k向上取整。
向上取整的方法除了ceil还可以用，(n - 1) / k + 1
代码实现
#include<iostream>
using namespace std;
const int N = 1e6 + 10;
int n, m, k;
int a[N];
int main()
{
cin >> n >> m >> k;
for(int i = 1; i <= m; i++)
{
int l, r;
cin >> l >> r;
a[l] += 1;
a[r] -= 1;
}
int val = 0;
for(int i = 1; i <= n; i++)
{
a[i] += a[i - 1];
val = max(val, a[i]);
}
cout << (val - 1) / k + 1;
return 0;
}