牛客寒假算法基础集训营1
被暴打,拼尽全力还是没有让ACM大人尽兴…
顺开,补题…
A 茕茕孑立之影
链接:https://ac.nowcoder.com/acm/contest/95323/A
知识点:数学
难度: 794
签到题,考虑倍数很容易想到质数,注意范围!10^18.也就是找一个在规定范围内尽可能大的质数.
这里我们注意到10000000000000007是一个符合条件的质数.
#include <bits/stdc++.h>
#define ll long long
#define ld long double
using namespace std;
void func()
{
int T;
cin >> T;
for (int i = 0; i < T; i++)
{
int n;
cin >> n;
int ans = 0;
int* arr = (int*)malloc(n*sizeof(int));
for (int j = 0; j < n; j++)
{
cin >> arr[j];
}
for (int j = 0; j < n; j++)
{
if (arr[j] == 1)
{
printf("-1\n");
ans = 1;
break;
}
}
if (ans == 0)
{
ll a = 10000000000000007;
printf("%lld\n", a);
}
free(arr);
}
}
int main()
{
func();
}
B 一气贯通之刃
链接: https://ac.nowcoder.com/acm/contest/95323/B
知识点:树
难度: 875
数据结构,算是基础题.给定一棵树,要求一次遍历所有节点.
考查map的用法,看样例就可以知道,如果要一次遍历完,只需要找到只出现过一次的节点,当然要排除由多分支产生的一次节点.
感觉做复杂了…
#include <bits/stdc++.h>
#define ll long long
#define ld long double
using namespace std;
void func()
{
int n;
cin >> n;
map<int, int>mp;
int** arr = (int**)malloc(n * sizeof(int*));//动态创建二维数组
for (int i = 0; i < n; i++)
{
arr[i] = (int*)malloc(2 * sizeof(int));//将列数定为2
}
for (int i = 0; i < n-1; i++)
{
for (int j = 0; j < 2; j++)
{
cin >> arr[i][j];
mp[arr[i][j]]++; //hash list
}
}
int ans = 0;//记录分支数
if (mp.size() != n)//判断种类,!=n直接排除
{
printf("-1\n");
}
else
{
for (auto i = mp.begin(); i != mp.end(); i++) {
if (i->second == 1)
{
ans++;
}
}
if (ans != 2)//判断是否只有一个分支
{
printf("-1\n");
}
else
{
for (auto i = mp.begin(); i != mp.end(); i++) {
if (i->second == 1)
{
cout << i->first << " ";//按键值对进行输出
}
}
}
}
for (int i = 0; i < n; i++)
{
free(arr[i]);
}
free(arr);
}
int main()
{
func();
}
D 双生双宿之决
链接:https://ac.nowcoder.com/acm/contest/95323/D
知识点:模拟,排序/stl
难度: 621
签到题,按照题目的要求来就行,可以排序,也可以不排序.
限定条件:2种元素,次数相同.
有排序:
#include <bits/stdc++.h>
#define ll long long
#define ld long double
using namespace std;
void func()
{
int T;
cin >> T;
for (int j = 0; j < T; j++)
{
int n;
cin >> n;
int* arr = (int*)malloc(n * sizeof(int));
for (int i = 0; i < n; i++)
{
cin >> arr[i];
}
sort(arr, arr + n);
int ans = 0;
if (arr[n / 2] == arr[n / 2 - 1])
{
ans = 1;
}
if (n % 2 != 0)
{
ans = 1;
}
for (int i = 1; i < n / 2; i++)
{
if (arr[i] != arr[i - 1])
{
ans = 1;
break;
}
}
for (int i = n / 2 + 1; i < n; i++)
{
if (arr[i] != arr[i - 1])
{
ans = 1;
break;
}
}
if (ans == 0)
{
printf("Yes\n");
}
else
{
printf("No\n");
}
free(arr);
}
}
int main()
{
func();
return 0;
}
无排序:
#include <bits/stdc++.h>
#define ll long long
#define ld long double
using namespace std;
void func()
{
int T;
cin >> T;
for (int i = 0; i < T; i++)
{
int n;
cin >> n;
int ans1 = 0;
int ans2 = 0;
map<int, int>mp;
int* arr = (int*)malloc(n*sizeof(int));
for (int j = 0; j < n; j++)
{
cin >> arr[j];
mp[arr[j]]++;
}
int crr[10] = { 0 };
int k = 0;
if (mp.size() != 2)
{
printf("No\n");
}
else
{
for (map<int, int>::iterator it = mp.begin(); it != mp.end(); it++)
{
crr[k]=it->second;
k++;
}
if (crr[0] == crr[1])
{
printf("Yes\n");
}
else
{
printf("No\n");
}
}
free(arr);
}
}
int main()
{
func();
}
G 井然有序之衡
链接: https://ac.nowcoder.com/acm/contest/95323/G
知识点:贪心、排序
难度: 932
同样是签到题,思路也很好想,我们需要找出TA不变的是什么.是sum!只需要动态开2个数组,一个输入(要排序),一个校对.
比较2个数组相同位置元素的差的绝对值,由于统计2次,所以得除以2.
注意范围:int会爆得开long long
#include <bits/stdc++.h>
#define ll long long
#define ld long double
using namespace std;
void func()
{
int n;
cin >> n;
int* arr = (int*)malloc(n*sizeof(int));
int* arr1 = (int*)malloc(n * sizeof(int));
ll sum1 = 0;
ll sum2 = 0;
for (int i = 0; i < n; i++)
{
cin >> arr[i];
sum1 += arr[i];
}
sort(arr, arr + n);
for (int i = 0; i < n; i++)
{
sum2 += i+1;
arr1[i] = i+1;
}
int ans = 0;
for (int i = 0; i < n; i++)
{
if (sum1 != sum2)
{
printf("-1\n");
ans = 1;
break;
}
}
ll sum = 0;
if (ans == 0)
{
for (int i = 0; i < n; i++)
{
if (arr1[i] != arr[i])
{
sum += fabs(arr1[i] - arr[i]);
}
}
sum = sum / 2;
printf("%lld", sum);
}
free(arr);
free(arr1);
}
int main()
{
func();
}
H 井然有序之窗
链接: https://ac.nowcoder.com/acm/contest/95323/H
知识点:贪心,优先队列
难度: 1603
上难度了,不会做,就算在补题时写出来依旧困难.关键是怎么最优化排列,这么想?
拿样例来说:
4
3 4
1 4
2 3
1 3
这样看,毫无章法,给TA排序下:
4
1 3
1 4
2 3
3 4
这样看是不是舒服多了?我们排列两次,先按左端点升序,再按右升序,实际上本题的核心就是按左端点且区间min放这n个数.
考虑数据进出,优先队列.
#include <bits/stdc++.h>
#define ll long long
#define ld long double
using namespace std;
struct range
{
int l, r, pos;
bool operator<(const range& other)const
{
return (l < other.l) || (l == other.l && r < other.r);
}//重载,先基于左端点排序,相等则基于右端点排序.
};
struct CompareR
{
bool operator()(const range& a, const range& b)
{
return a.r > b.r;
}//比较函数对象,用于比较两个range右端点.
};
int main()
{
int n;
cin >> n;
vector<range> ranges;//存在向量ranges中
for (int i = 0; i < n; i++)
{
int l, r;
cin >> l >> r;
ranges.push_back({ l,r,i });
}//存在向量ranges中
sort(ranges.begin(), ranges.end());//先排序
priority_queue<range, vector<range>, CompareR>pq;
vector<int>res(n);
int index = 0;//定义了一个最大堆pq,使用CompareR作为比较标准.还定义了一个结果向量res,用于存储每个区间的代表点,以及一个索引index用于遍历ranges.
for (int k = 1; k <= n; k++)
{
while (index < n && ranges[index].l <= k)
{
pq.push(ranges[index++]);
}
while (pq.empty() == 0 && pq.top().r < k) pq.pop();
if (pq.empty())
{
cout << -1;
return 0;
}
auto [l, r, pos] = pq.top();
pq.pop();
res[pos] = k;
}
//这个循环遍历从1到n的每个点k,尝试为每个区间找到一个代表点.
//它首先将所有左端点小于等于k的区间加入堆中.然后移除所有右端点小于k的区间(因为它们不包含k).
//如果堆为空,意味着没有区间包含当前的k,程序输出-1并结束.否则,取出堆顶元素(即右端点最大的区间),将k作为该区间的代表点存储在res中.
for (int x : res) cout << x << " ";
//最后遍历结果向量res,输出每个区间的代表点
//等价于:
// for (size_t i = 0; i < res.size(); ++i)
// {
// int x = res[i];
// cout << x << " ";
// }
return 0;
}
E 双生双宿之错
链接: https://ac.nowcoder.com/acm/contest/95323/E
知识点:排序，中位数定理
难度: 1782
知道或者能推出结论就不难,本质上是数学的一条线段上一个动点到多定点的距离和最小,只不过此题先二分,分别求其到中位数的距离.
但要考虑两段中位数相等时的问题,要分两种情况:
1.前面一半集体到中位数-1的距离,后一半到中位数的距离
2.前一半集体到中位数的距离,后一半到中位数-1的距离
二者要取min
#include <bits/stdc++.h>
#define ll long long
#define ld long double
using namespace std;
ll calculate_cost(const vector<int>& arr, int start, int end, int target)
{
ll cost = 0;
for (int i = start; i < end; i++)
{
cost += fabs(arr[i]-target);
}
return cost;
}
void func()
{
int T;
cin >> T;
for (int i = 0; i < T; i++)
{
int n;
cin >> n;
vector<int>arr(n);
for (int i = 0; i < n; i++)
{
cin >> arr[i];
}
sort(arr.begin(),arr.end());
int half = n / 2;
int a, b;
if (half % 2 == 0)
{
a = (arr[half / 2 - 1] + arr[half / 2]) / 2;
}
else
{
a = arr[half / 2];
}
if (half % 2 == 0)
{
b = (arr[half+half / 2 - 1] + arr[half+half / 2]) / 2;
}
else
{
b = arr[half+half / 2];
}
if (a != b)
{
ll cost = calculate_cost(arr, 0, half, a) + calculate_cost(arr, half, n, b);
cout << cost << "\n";
}
else
{
int option1_x = a - 1;
int option1_y = a;
ll cost1 = calculate_cost(arr, 0, half, option1_x) + calculate_cost(arr, half, n, option1_y);
int option2_x = a;
int option2_y = a + 1;
ll cost2 = calculate_cost(arr, 0, half, option2_x) + calculate_cost(arr, half, n, option2_y);
cout << min(cost1, cost2) << "\n";
}
}
}
int main()
{
func();
return 0;
}
M 数值膨胀之美
链接: https://ac.nowcoder.com/acm/contest/95323/M
知识点: 贪心,模拟,线段树,ST表.
难度: 1274
数据弱了,可以混过去,但现在不行(沮丧).出的非常好,成功使我被击败…
官方思路:
如果区间只有一个数,一定会选择min * 2, min * 2之后区间极差有哪些可能?
1.Max-2*Min(2Min还是最小值)
2.2Min-次小值(2Min比Max大)
3.Max-次小值(2Min比Max小,比次小值大)
已知:极差唯一有可能减小的,就是Min*2但怎么维护 *2区间的mzx,min和剩下的max,min?
ST表,线段树.
可发现,变化完次小值成了有决定的值,那么就又有方案给次小值乘2.
次小值要乘2,那就是最小值到次小值的区间一起乘2.
这个区间乘2以后,最小值可能会变成第三最小值,也可能是最小值乘2,最大值有可能是原来的最大值,也有可能是这个区间的最大值乘2
所以,极差是”乘2的区间的最大值和剩下的最大值取最大”–”乘2的区间的最小值与剩下的最小值取最小”
剩下的区间的max–就用原数组的max,如果TA被乘2了,那么乘2区间的max才是答案,剩下的区间真的max也不管用.
剩下的区间min:
1.先结构体排序,指针指向还没乘2的最小数–如果指向的数在乘2的区间中,指针++
2.开个容器记录还没被乘2的数–求最小值,删除指定的数,有重复值–multiset
#include <bits/stdc++.h>
#define ll long long
#define ld long double
using namespace std;
pair<int, int>a[150000];
int b[150000];
void func()
{
int n;
cin >> n;
for (int i = 0; i < n; i++)
{
cin >> a[i].first;
a[i].second = i;
b[i] = a[i].first;
}
a[n].first = 2e9;
sort(a, a + n);
int l = a[0].second, r = a[0].second;
int ma = max(a[0].first * 2, a[n - 1].first);
int res = ma - min(a[0].first * 2, a[1].first);
// 遍历处理每个元素
for(i=1; i<n; i++){
// 扩展左边界到包含当前元素的原始位置
while(a[i].second < l) {
l--;
ma = max(ma, b[l]*2); // 更新最大值（可能与区间代价相关）
}
// 扩展右边界到包含当前元素的原始位置
while(a[i].second > r) {
r++;
ma = max(ma, b[r]*2); // 更新最大值
}
// 更新最优解：当前最大值 - 下一元素的值的两倍（或哨兵值）
res = min(res, ma - min(a[0].first*2, a[i+1].first));
}
cout << res;
}
int main()
{
func();
return 0;
}
J 硝基甲苯之袭
链接: https://ac.nowcoder.com/acm/contest/95323/J
知识点:位运算,数论
难度:1567
在解决此题之前我们先了解一个性质:
a ^ b = c <=> a ^ c = b
那么对于本题:
ai^gcd=aj
设gcd是x
cnt[ai]*cnt[aj]是满足ai ^ x=aj的对数
但是x可未必是ai,aj的gcd,需要验证,是ans就加,不是continue
x枚举 2-sqrt(a) ai%x==0
求ai ^ x = d ->cnt[d]
#include<bits/stdc++.h>
using namespace std;
int main()
{
const int N = 2e5 + 1;
int n;
cin >> n;
vector<int> a(N * 2 + 1);//开一个比较大的数组
for(int i = 1; i <= n; i++)
{
int x;
cin >> x;
a[x]++;//hash计数
}
auto ans = 0ll;//ans用于累加满足条件的整数对的总次数.
auto get = [&](int x, int y)//get函数接收参数x和y,计算y += x得到k = x + y,然后检查x ^ k是否等于gcd(x,k).若成立,则累加a[x] * a[k]到ans.
{
y += x;
if((x ^ y) == gcd(x, y)) ans += 1ll * a[x] * a[y];
};
for(int i = 2; i <= N; i += 2){
for(int j = 1; j * j <= i; j++){
if(i % j) continue;
get(i, j);
if(j * j != i) get(i, i / j);//将一个定为偶数,另一个在此操作变为奇数,可枚举出所有情况.
}遍历偶数 i,枚举其因数 j.对每个因数 j,调用 get(i,j) 和 get(i, i/j).
}
cout << ans << endl;
}
C 兢兢业业之移
链接: https://ac.nowcoder.com/acm/contest/95323/C
知识点: 模拟/最短路,超大模拟.
难度: 1952
考查代码量
#include <bits/stdc++.h>
#define ll long long
#define ld long double
using namespace std;
int main()
{
int T = 1;
cin >> T; // 输入测试用例数量
while (T--)
{
int n;
cin >> n; // 输入网格大小n
// 初始化网格，周围填充'1'作为边界
std::vector<std::string> s(n + 2, std::string(n + 2, '1'));
for (int i = 1; i <= n; i++)
{
cin >> s[i]; // 输入每行原始数据
s[i] = "1" + s[i] + "1"; // 左右添加边界'1'
}
vector<vector<int>> ans; // 存储操作记录
// 定义移动函数
auto go = [&](int x, int y, char c)
{
int dx = x, dy = y; // 计算移动后的坐标
dx -= (c == 'U'); // 向上移动行号-1
dx += (c == 'D'); // 向下移动行号+1
dy -= (c == 'L'); // 向左移动列号-1
dy += (c == 'R'); // 向右移动列号+1
swap(s[x][y], s[dx][dy]); // 交换元素
ans.push_back({x, y, dx, dy}); // 记录操作
};
// 第一阶段：垂直方向整理（向上推）
for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= n; j++)
{
// 从当前位置向上遍历
for (int k = i; k >= 1; k--)
{
if (s[k][j] == '1' && s[k-1][j] == '0')
{
go(k, j, 'U'); // 将'1'向上移动到'0'的位置
} else break; // 遇到障碍停止
}
}
}
// 第二阶段：水平方向整理（向左推）
for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= n; j++)
{
// 从当前位置向左遍历
for (int k = j; k >= 1; k--)
{
if (s[i][k] == '1' && s[i][k-1] == '0')
{
go(i, k, 'L'); // 将'1'向左移动到'0'的位置
} else break;
}
}
}
// 第三阶段：处理右上区域
for (int i = n/2; i >= 1; i--)
{ // 从中间行向上
for (int j = n; j > n/2; j--)
{ // 右侧列向左
if (s[i][j] == '0') continue; // 跳过空位
// 在左上区域寻找空位
int x = 0, y = 0;
for (int k = 1; k <= n/2; k++)
{
for (int l = 1; l <= n/2; l++)
{
if (s[k][l] == '1') continue;
x = k; y = l;
break;
}
if (x) break;
}
// 垂直向下移动
for (int k = i; k < x; k++) go(k, j, 'D');
// 水平向左移动
for (int k = j; k > y; k--) go(x, k, 'L');
}
}
// 第四阶段：处理右下区域
for (int i = n; i > n/2; i--)
{ // 从底部行向上
for (int j = n/2; j >= 1; j--)
{ // 中间列向左
if (s[i][j] == '0') continue;
// 在左上区域寻找空位
int x = 0, y = 0;
for (int k = 1; k <= n/2; k++)
{
for (int l = 1; l <= n/2; l++)
{
if (s[k][l] == '1') continue;
x = k; y = l;
break;
}
if (x) break;
}
// 水平向右移动（实际是向左填充）
for (int k = j; k < y; k++) go(i, k, 'R');
// 垂直向上移动
for (int k = i; k > x; k--) go(k, y, 'U');
}
}
// 输出操作步骤
cout << ans.size() << endl;
for (auto& i : ans)
{
for (auto& j : i) cout << j << " ";
cout << endl;
}
}
}
F.双生双宿之探
知识点: 双指针,前缀和,逻辑,线段树,ST表
难度: 2213
难题,首先考虑暴力n^3肯定超时.
稍微优化一下,l到r中数的个数＞2了,r就不要往后走了
优化的基本思路:1.<循环优化>(1)变成区间端点 (2)拆成多个小区间 //一重一重去看能丢掉哪个不(l,r同理,得去掉某一个)
2.<计数优化>前缀和
先把每一个符合条件的LR最大范围求出来(知道最左边在哪最右边在哪),然后在这个区间里去找符合条件的区间有多少对
#include <bits/stdc++.h>
#define ll long long
#define ld long double
using namespace std;
void func() {
int T;
cin >> T;
for(int i=0; i<T; i++) { // 处理每个测试用例
int n;
cin >> n;
vector<int> a(n + 1); // 数组从索引1开始
for (int i = 1; i <= n; i++) {
cin >> a[i];
}
vector<int> f(n + 1); // 前缀和数组
ll ans = 0;
for (int i = 1; i <= n; i++)
{
set<int> st; // 记录当前窗口内的不同元素
map<int, int> mp; // 统计前缀和出现次数
mp[0]++; // 初始前缀和为0的情况
f[i-1] = 0; // 初始化前缀和
for (int j = i; j <= n; j++)
{
st.insert(a[j]);
if (st.size() > 2)
{ // 元素超过2种，调整窗口
i = j;
st.clear();
for (; i >= 1; i--)
{
st.insert(a[i]);
if (st.size() > 2) break;
}
break; // 退出内层循环
}
// 更新前缀和
f[j] = f[j-1] + (a[j] == a[i] ? 1 : -1);
ans += mp[f[j]]; // 累加当前前缀和的出现次数
mp[f[j]]++; // 记录当前前缀和
if (j == n) i = n; // 强制退出外层循环
}
}
cout << ans << endl;
}
}
int main()
{
func();
return 0;
}
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来源 一位元宇宙爱好者的随笔！
