马蹄集oj赛（双周赛第二十三次）

2024-03-22 22:28
文章标签 oj 第二十三 双周 马蹄

本文主要是介绍马蹄集oj赛（双周赛第二十三次），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

目录

数列分割

小码哥的地毯

小码哥的三色墙

palace

高数考试

新全排列

黑白双煞

等差

数三角形

区间修改

相对马高

小码哥剪绳子

数列分割


难度:黄金 时间限制:1秒巴 占用内存:64 M
小码哥给你一个长度为n的数列，求将该数列分割成两个左右两个部分且两个部分内数字的和相等的方案数。
格式
输入格式:给定一整数n;
接下来有 n 个数 a[i]。
其中:1≤n≤ 105,ai]的绝对值不大于 10000。
输出格式:输出一行表示答案。

//
// Created by abner on 2024/3/22.
//
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
long long n,a[N],sum [N],ans;int main() {cin >> n;for (int i = 1; i <= n; i++) {cin >> a[i];sum[i] = sum[i - 1] + a[i];}for (int i = 2; i <= n; i++) {if (sum[n] - sum[i - 1] == sum[i - 1])ans++;}cout << ans;return 0;
}

小码哥的地毯


少 难度:黄金·时间限制:1秒四占用内存:128M
小码哥的房间要铺上地毯。房间大小为几*几，小码哥有m 块矩形地毯，给出每块地毯放置的两个对角的坐标。问每个点被多少个地毯覆盖
格式
输入格式:今第一行，两个整数n，m;接下来 m 行，每行两个坐标(1,y)和(2,y) 代表一块地毯，左上角是(1,y)，右下角是(2,y2)。
输出格式:输出n行，每行几个整数;

//
// Created by abner on 2024/3/22.
//
#include <bits/stdc++.h>
using namespace std;
#define N 1005
int n,m;
int a[N][N],sub[N][N];
int main(){cin >>n >>m;for(int i=1;i<=m;++i){int x1,y1,x2,y2;cin >>x1 >>y1 >>x2 >>y2;sub[x1][y1] += 1;sub[x1][y2+1] -= 1;sub[x2+1][y1] -= 1;sub[x2+1][y2+1] += 1;
}
for (int i=1;i<=n;++i){
for (int j=1;j <= n;++j){
a[i][j]=sub[i][j]+a[i-1][j]+a[i][j-1]-a[i-1][j-1];cout <<a[i][j]<<" ";
}
puts("");
}
return 0;
}

小码哥的三色墙


难度:黄金时间限制:1秒巴 占用内存:128 M
小码哥的房间墙要重新刷漆。墙面大小可以看成几*m个小方块，每个方块初始颜色为W,B或R，小码哥对于刷漆的要求是:
1.从最上方若干行(至少一行)的格子全部是W色的;
2.接下来若干行(至少一行)的格子全部是B色的;
3.剩下的行(至少一行)全部是 色的。
小码哥想要更改最少的格子数来满足要求。请你帮他算算最少的更改数。

//
// Created by abner on 2024/3/22.
//
#include <bits/stdc++.h>
using namespace std;
#define N 1005
int n,m,w[N],b[N],r[N];
int ans = 0x3f3f3f3f;
string s;
int cal(char c) {
//某一行全部刷成某种颜色的代价int t = 0;for (int i = 0; i < m; ++i)if (s[i] != c)t++;return t;
}
int main() {cin >> n >> m;for (int i = 1; i <= n; ++i) {cin >> s;w[i] = w[i - 1] + cal('W');b[i] = b[i - 1] + cal('B');r[i] = r[i - 1] + cal('R');}for (int i = 1; i < n - 1; ++i)for (int j = i + 1; j < n; ++j)ans = min(ans, w[i] + b[j] - b[i] + r[n] - r[j]);cout << ans;return 0;
}

palace


难度:钻石时间限制:1秒巴 占用内存:128 M。
小码哥准备给自己盖一座很华丽的宫殿。于是，他看中了一块NxM 的矩形空地。
空地中每个格子都有自己的海拔高度。小码哥想让他的宫殿的平均海拔在海平面之上(假设海平面的高度是0，平均数都会算吧?)。而且，小码哥希望他的宫殿尽量大，能够容纳更多的人来膜拜他。请问小码哥的宫殿最后会有多大?
格式
输入格式:第一行两个整数 n,m;
之后 n 行，每行 m 个数，描述的空地的海拔。

//
// Created by abner on 2024/3/22.
//
#include <bits/stdc++.h>
using namespace std;
const int N = 210;
int n,m,a[N][N],sum [N][N],ans;int main(){cin >>n >>m;for (int i=1;i <=n;i++)for (int j =1;j <=m;j++) {cin >> a[i][j];sum[i][j] =sum[i - 1][j] + sum[i][j - 1] + a[i][j] - sum[i - 1][j - 1];}for (int i=1;i<=n;i++)for (int j =1;j <= m;j++)for (int k=i;k <= n;k++)for (int l=j;l <= m;l++) {int tmp = (k - i + 1) * (l - j + 1);int tmp2 = sum[k][l] - sum[i - 1][l] - sum[k][j - 1] +sum[i - 1][j - 1];if (tmp > ans && tmp2 > 0)ans = tmp;}cout << ans;return 0;
}

高数考试


黄金!巴 占用内存:128 M子难度:时间限制:1秒
高数考完了，又到了数学老师难办的时候。数学老师想捞同学一把，她总是要一遍遍地给某些同学增加分数(均为正整数)，又要注意最低分是多少。由于工作量很大，你能帮帮她吗?
格式
输入格式:第一行有两个整数n，p，代表学生数与增加分数的次数第二行有 n 个数，a1~ an ，代表各个学生的初始成绩;接下来p行，每行有三个数 ，y，z，代表给第  个到第y个学生每人增加z分。

/*MT2068 高数考试 
*/#include<bits/stdc++.h> 
using namespace std;const int MAX = 5e6+5;
int ary[MAX], sub[MAX];int main( )
{// 录入数据 int n,p,x,y,z,minScore=MAX; cin>>n>>p; // 录入分数时同时记录差分数组 for(int i=1;i<=n;i++){cin>>ary[i];sub[i] = ary[i] - ary[i-1];}// 录入操作时只需要对差分数组进行修改 while(p--){cin>>x>>y>>z;sub[x] += z;sub[y+1] -=z;}// 还原数组并找出最小值 for(int i=1;i<=n;i++){ary[i] = ary[i-1] + sub[i];minScore = min(minScore, ary[i]);}// 输出最低分数 cout<<minScore<<endl;return 0;
}

新全排列


 时间限制:2秒难度:钻石四:占用内存:256 M
列数组 P1,P2,?3,..,?n 被称作一个全排列当且仅当1到n所有数都出现一次。现有一个n的全排列 p1,p2,p3,·..,pn ，仅知道 q1,q2,3,·..,qn-1的序列，其中 qi=pi+1-Pi。
要求求出原序列。
格式
输入格式:第一行输入 n(2 <n<2*105)原序列长度;第二行输入 q1, 92, q3,·..,qn-1(-n < qi< n)。

//
// Created by abner on 2024/3/22.
//
#include <bits/stdc++.h>
using namespace std;
const int N =2e5+ 7;int n,p[N],q[N],tmp[N];
bool flag;
int main() {cin >> n;for (int i = 1; i <= n - 1; i++)cin >>q[i];//差分数组前缀和就是原数组int minn = 0;for (int i=2;i<=n;i++){p[i]=p[i-1]+q[i-1];if (p[i] < minn)minn = p[i];
}
for (int i=1;i<=n;i++) {p[i] = p[i] - minn + 1;tmp[i] = p[i];if (tmp[i] > n || tmp[i] < 1) {cout << -1;return 0;}
}
sort(tmp + 1,tmp +n + 1);
for (int i=1;i<=n-1;i++)
if (tmp[i]==tmp[i + 1]){cout<<-1;return 0;
}for (int i=1;i<=n;i++)cout << p[i] <<" ";return 0;
}

黑白双煞


难度:钻石时间限制:1秒巴:占用内存:128 M
小码哥现在手里一个环(首尾相连)，环上有(2<n<100000)个点，每个点必定是两种颜色之一(黑色或白色)。
现在他想请你进行一些操作，每次交换两个点的位置，求最少操作次数使得黑白色的几个点分离成两个部分，每个部分只含一种颜色。
格式
输入格式:第-行-个正整数n(2≤n≤ 100000);
接下来一行一个字符串 S ，长度为 n ，第讠位为 H 则表示黑点，T 则表示白点。

//
// Created by abner on 2024/3/22.
//
#include <bits/stdc++.h>
using namespace std;
const int N=1e5 + 10;
int a[N << 1],sum[N << 1];
int n,cnt,ans;//cnt表示黑色的个数，ans表示cnt长的区间内，最多多少个黑色
char ch;
int main(){cin >> n;for (int i=1;i<=n;i++) {cin >> ch;if (ch == 'H')//黑色为1a[i + n] = a[i] = 1, cnt++;}for (int i=1;i<=n * 2;i++)sum[i]=sum[i-1]+a[i];//前缀和，前面有多少个黑色for (int i=1;i <=n;i++)ans = max(ans,sum[i+cnt - 1] - sum[i-1]);cout <<cnt - ans;return 0;}

等差


难度:钻石时间限制:1秒四: 占用内存:256 M
学完等差数列的小码哥神清气爽，他想在一长串数中找到等差的部分。
他给你一个整数数组nums，要求该数组中所有为等差数组的子数组个数(等差数组子数组，指的是至少3个数的连续数组成等差数列)。
格式
输入格式:一个整数数组。
输出格式:返回一个非负整数。

//
// Created by abner on 2024/3/22.
//
#include <bits/stdc++.h>
using namespace std;
const int N = 5010;
int nums [N],sub[N],n,ans;int main(){int x;while (cin >>x){n++;nums[n] = x;sub[n] = nums[n] - nums[n - 1];}for (int i=2;i<n;i++){int tmp = sub[i],index = i+1,t=0;while (sub [index]==tmp) {t++;index++;}ans +=t;}cout <<ans;return 0;}

数三角形


时间限制:1秒难度:钻石巴: 占用内存:128 M
给出四个整数 A, B,C,D ，其中 1< A≤B<C<D<5.105
求三边长分别为 æ, y,z(㎡,y,z为整数)并且満足 A≤æ≤B≤y≤C≤z≤D 的非退化三角形(三顶点不共线)的个数。
格式
输入格式:第一行为 A,B,C,D
输出格式:输出一个整数为答案。

//
// Created by abner on 2024/3/22.
//
#include <bits/stdc++.h>
using namespace std;
const int N=5e5 +5;
long long a[N],sum[N],A,B,C,D,ans;
int main(){cin >>A >>B>>C>>D;for (int i=A;i<=B;i++)for (int j=B;j<=C;j++)a[i+j]++;for (int i=A+B;i <= B+C;i++)sum[i] = sum[i -1] + a[i];for(int i=C;i <= min(D,B+C);i++)ans += sum[B + C] - sum[i];cout <<ans;return 0;
}

区间修改


难度:黄金
时间限制:1秒巴:占用内存:128 M
小码哥有几个手下,他们的编号为1,n。小码哥想要给他们发放工资，用一个长度为n的数列ai,表示编号为i的手下初始收到的工资，但发工资时没有计算好，导致每个人到手的工资不-样，为了使他们的工资相同，现在小码哥可以使得编号在区间,中的手下，收到1或上交1的工资。即工资+1或工资-1;
求至少需要多少次操作才能使所有人的工资相同都一样?
工资可以暂时为负数，小码哥可以压榨他的手下，让手下暂时垫付部分钱，之后再还;小码哥也可以多付一些钱给手下，也可以少给一些(自己贪污一点)，即工资总数不要求一定是初始手下的工资之和。只要他们每个人的工资一样就可以。

//
// Created by abner on 2024/3/22.
//
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
int n,a[N],sub[N],num1,num2;
int main(){int ans =0,buf =0;cin >>n;for (int i=1;i<=n;i++)cin >>a[i];for (int i=2;i<=n;i++){sub[i] = a[i]-a[i-1];if (sub[i] > 0)num1 += sub[i];else num2 += sub[i];}cout <<max(num1,-num2);return 0;
}

相对马高


少难度:黄金时间限制:1秒四: 占用内存:128 M
小码哥有几头马，他们站作一排，由于马的身高不同，如果马A和B能够相互看见，那么，在(a,b)区间的马的身高都小于 a，b马。
现在给出最高的马的身高h。之后小码哥将给出f组数据，表示马A，B可以相互看见，请你推出小码哥的马们的最大的可能的身高,由于小码哥工作向来随性，马的区间顺序关系可能写错(数据不确保 a<b)。
格式
输入格式:第 1 行输入 n,h,f;
第 2 行到第 f+1 行 输入两个数据 a,b，以空格分隔

//
// Created by abner on 2024/3/22.
//
#include <bits/stdc++.h>
using namespace std;
const int N = 1e4 + 10;
int n,h,f,g[N],sub[N],a,b;
int main() {cin >> n >> h >> f;sub[1] = h;while (f--) {cin >> a >> b;if (a == b)continue;if (a > b)swap(a, b);sub[a + 1] -= 1;sub[b] += 1;}for (int i = 1; i <= n; i++) {g[i] = g[i - 1] + sub[i];cout << g[i] << endl;}return 0;
}

小码哥剪绳子


时间限制:1秒巴 占用内存:128 M了 难度:黄金
马上就要到文化节了，小码哥身为学生会的一员需要参与到道具制作。
由于被分配到趣味拔河，小码哥需要切绳子，有N 条绳子，它们的长度分别为,n。
如果从它们中切割出 K 条长度相同的绳子，这条绳子每条最长能有多长?
格式
输入格式:第一行两个整数 N 和K;
接下来 N 行，每行一个整数代表每条绳子的长度 工。

//
// Created by abner on 2024/3/22.
//
#include <bits/stdc++.h>
using namespace std;
const int M = 1e5 + 10;
int L[M],N,K,l,r,mid,ans;bool check(int num){int tmp =0;for (int i =1;i<=N;i++) {tmp += L[i] / num;}if (tmp >=K)return true;elsereturn false;}int main(){cin >>N>>K;for (int i=1;i<=N;i++) {cin >> L[i];r = max(r, L[i]);}while (l <=r){mid = l+(r-l)/2;if (check(mid))l=mid + 1,ans = mid;elser = mid - 1;}cout <<ans;return 0;}

这篇关于马蹄集oj赛（双周赛第二十三次）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/836329。

相关文章

哈理工OJ 2179(深搜)

哈理工OJ 2179(深搜)

组合 Time Limit: 1000 MSMemory Limit: 32768 K Total Submit: 7(5 users)Total Accepted: 6(5 users)Rating: Special Judge: No Description 给出一个正整数N，从集合{1,2,3..N} 中找出所有大小为k的子集, 并按照字典序从小到大输出。 Input 第一行是一个整
阅读更多...
每日OJ_牛客_求和（递归深搜）

每日OJ_牛客_求和（递归深搜）

目录 牛客_求和（递归深搜） 解析代码 牛客_求和（递归深搜） 求和_好未来笔试题_牛客网 解析代码         递归中每次累加一个新的数，如果累加和大于等于目标，结束递归。此时如果累加和正好等于目标，则打印组合。向上回退搜索其它组合。此题本身就是一个搜索的过程，找到所有的组合。 #include <iostream>#include <cmath>#in
阅读更多...
OJ-0905

OJ-0905

题目 示例1： 输入：10 10 56 34 99 1 87 8 99 3 255 6 99 5 255 4 99 7 255 2 99 9 255 213 4输出：99 示例2： 输入：10 10 255 34 0 1 255 8 0 3 255 6 0 5 255 4 0 7 255 2 0 9 255 213 5输出：255 import java.util.
阅读更多...
每日OJ_牛客_Emacs计算器（逆波兰表达式）

每日OJ_牛客_Emacs计算器（逆波兰表达式）

目录 牛客_Emacs计算器（逆波兰表达式） 解析代码 牛客_Emacs计算器（逆波兰表达式） Emacs计算器__牛客网 解析代码 逆波兰表达式(后缀表达式)求值，需要借助栈，思路： 循环输入，获取逆波兰表达式，然后进行以下补助，直到测试完所有的测试用例： 遇到数字字符串，将该数字字符串转化为数字然后入栈。遇到操作符时，从栈顶取两个数字，然后进行该运算符所对应运算
阅读更多...
西北工业大学oj题-兔子生崽

西北工业大学oj题-兔子生崽

题目描述： 兔子生崽问题。假设一对小兔的成熟期是一个月，即一个月可长成成兔，每对成兔每个月可以生一对小兔，一对新生的小兔从第二个月起就开始生兔子，试问从一对兔子开始繁殖，一年以后可有多少对兔子？ 这道题目一眼看过去就是典型的递归问题，代码如下 public class RabbitReproduction {public static void main(String[] args) {in
阅读更多...
★ 算法OJ题 ★ 力扣209 - 长度最小的子数组

★ 算法OJ题 ★ 力扣209 - 长度最小的子数组

Ciallo～(∠・ω< )⌒☆ ~ 今天，简将和大家一起做一道滑动窗口算法题--长度最小的子数组~ 目录 一  题目 二  算法解析 解法⼀：暴力求解 解法二：滑动窗口 三  编写算法 一  题目 209. 长度最小的子数组 - 力扣（LeetCode） 二  算法解析 解法⼀：暴力求解 算法思路： 从前往后枚举数组中的任意⼀个元素，把它当成起始位置
阅读更多...
OJ-0903

OJ-0903

题目 示例1 输入：30 12 25 8 19输出：15 示例2 输入：10 12 25 8 19 8 6 4 17 19 20 30输出：-1 题解 import java.util.ArrayList;import java.util.List;import java.util.Scanner;public class Main {public static
阅读更多...
Leetcode - 138双周赛

Leetcode - 138双周赛

目录 一，3270. 求出数字答案 二，3271. 哈希分割字符串 三，3272. 统计好整数的数目 四，3273. 对 Bob 造成的最少伤害 一，3270. 求出数字答案 本题数据范围小，可以将数字转换成字符串来做，这里教一种更省空间的做法。我们可以从后往前求出每一个数位的最小值min(a % 10， b  % 10，c % 10)，a /= 10，b /= 10，c
阅读更多...
【负载均衡式在线OJ】Compile_server 模块

【负载均衡式在线OJ】Compile_server 模块

文章目录 程序源码compile_server整体思路编译(compile.hpp)运行模块编译运行模块编译运行服务 程序源码 https://gitee.com/not-a-stupid-child/online-judge compile_server 整体思路 这个服务要对oj_server 发送过来的代码进行编译和运行，最后把结果返回给oj_server。 所以我
阅读更多...
★ 算法OJ题 ★ 力扣18 - 四数之和

★ 算法OJ题 ★ 力扣18 - 四数之和

Ciallo～(∠・ω< )⌒☆ ~ 今天，爱丽速子将和大家一起做一道双指针算法题--四数之和~ 目录 一  题目 二  算法解析 三  编写算法  做此题前最好先看一下前两篇博客~： ★ 算法OJ题 ★ 力扣 LCR179 - 和为 s 的两个数字-CSDN博客 ★ 算法OJ题 ★ 力扣15 - 三数之和-CSDN博客 一  题目 18. 四数之和 - 力扣（Lee
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2