牛客小白月赛95

本文主要是介绍牛客小白月赛95，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

c相助

题目描述

此题为E题的easy版，只有aia_iai​的数据范围不同。

给你一个 nnn 个正整数组成的数组 a ，你每次操作可以选择一对 (i,j)( i, j )(i,j)，满足 1≤i<j≤n1 \leq i < j \leq n1≤i<j≤n，且 ai=aja_{i} = a_{j}ai​=aj​ ，将 { ai,ai+1,...,aj−1,aja_{i} , a_{i+1} , ... , a_{j-1} , a_{j}ai​,ai+1​,...,aj−1​,aj​ } 这段数删除，操作之后数组变为 { a1,a2,...,ai−1,aj+1,...,an−1,ana_{1},a_{2}, ..., a_{i-1},a_{j+1}, ...,a_{n-1},a_{n}a1​,a2​,...,ai−1​,aj+1​,...,an−1​,an​ }。文文想知道最少要做多少次操作，才能将数组变为空。

输入描述:

第一行一个正整数输入 nnn (1≤n≤5×105)( 1 \leq n \leq 5 \times 10^5 )(1≤n≤5×105)。

第二行依次输入 nnn 个正整数 a1,a2,...,an−1,ana_{1},a_{2},...,a_{n-1},a_{n}a1​,a2​,...,an−1​,an​，每个数之间以空格分开。(0≤ai≤1)( 0 \leq a_i \leq 1 )(0≤ai​≤1)

输出描述:

输出一行，代表最少的操作次数，如果无论如何都无法使数组为空就输出 -1。

示例1

输入

5
0 1 0 1 1

输出

2

说明

例如，n 为 5，数组为{0,1,0,1,1}\{0, 1, 0, 1, 1\}{0,1,0,1,1}，第一次操作我们可以选择 i=1i = 1i=1，j=3j = 3j=3，把这一段删除后数组变为 {1,1}\{1, 1\}{1,1}，第二次操作我们可以选择 i=1i = 1i=1，j=2j = 2j=2，把这一段删除后数组变为空，操作了两次。

示例2

输入

5
1 1 1 1 0

输出

-1

做法

答案只有-1，1，2三种。当头尾元素相同时一次就可以消除；若有一个下标满足a[i]=a[1]，且a[i+1]=a[n]，则需要消除两次。其他情况则无法完全消除。

#include<bits/stdc++.h>
using namespace std;
int n;
int a[500010];
int cnt0,cnt1;
int main(){scanf("%d",&n);for(int i=1;i<=n;i++) cin>>a[i];if(a[1]==a[n]){if(n==1)cout<<-1;else cout<<1;return 0;}for(int i=1;i<=n;i++){if(i==1||i+1==n) continue;if(a[1]==a[i]&&a[i+1]==a[n]){cout<<2;return 0;}}cout<<-1;
}

D异或炸弹（easy）

题目描述

此题为F题的easy版本，与F题仅有m的取值范围不同

给定一个n∗nn*nn∗n的矩阵，初始全是 ​0​0​0，

现在文文手上有 mmm 个炸弹,

对于每一个炸弹，都有自己的 爆炸中心(x,y) 和 爆炸半径 r.

当矩阵内某个位置与爆炸中心的 曼哈顿距离 小于等于 r 时，该位置就会收到爆炸的影响， 爆炸的影响就是给这个位置上的数异或 1.

文文给你这 mmm 个炸弹的爆炸位置和爆炸半径，你需要回答文文这个矩阵中 1 的个数

如果不明白 异或操作 和 曼哈顿距离，请看最后的提示

输入描述:

第一行给定两个正整数 n,mn ,mn,m, 分别表示矩阵大小和炸弹数量 

接下来mmm行，每行333个正整数其中第 iii 行的前2个正整数 xi,yix_i ,y_ixi​,yi​ 表示第 iii 个炸弹的爆炸中心最后一个正整数 rir_iri​ 表示第 iii 个炸弹的爆炸半径

1≤n≤3000,1≤m≤60001 \leq n \leq 3000, 1\leq m \leq 60001≤n≤3000,1≤m≤6000

1≤xi,yi≤n1 \leq x_i, y_i \leq n1≤xi​,yi​≤n

0≤ri≤60000 \leq r_i \leq 60000≤ri​≤6000

输出描述:

输出被轰炸后的矩阵中 111 的个数

示例1

输入

5 1
3 3 1

输出

5

说明

案例解释

0 0 0 0 0

0 0 1 0 0

0 1 1 1 0

0 0 1 0 0

0 0 0 0 0

共有5个1 

备注:

关于异或的运算

0 ^ 1 = 1

1 ^ 1 = 0

1 ^ 0 = 1

0 ^ 0 = 0

关于曼哈顿距离的运算如果两个点的坐标分别是(x1,y1),(x2,y2)(x1,y1),(x2,y2)(x1,y1),(x2,y2) 那么两个点的曼哈顿距离d=∣x1−x2∣+∣y1−y2∣d = |x1-x2|+|y1-y2|d=∣x1−x2∣+∣y1−y2∣.

做法

#include<bits/stdc++.h>
using namespace std;
int n,m;
int cf[3010][3010];
int main(){scanf("%d%d",&n,&m);while(m--){int x,y,r;scanf("%d%d%d",&x,&y,&r);for(int i=x-r;i<=x+r;i++){//枚举行数if(i<1||i>n) continue;int l=r-abs(x-i);//距离cf[i][max(1,y-l)]++;//差分（异或次数）cf[i][min(n+1,y+l+1)]--;}}int cnt=0;for(int i=1;i<=n;i++){int a=0;//还原数组的值for(int j=1;j<=n;j++){a+=cf[i][j];cnt+=a%2;//异或次数为奇数则最终值是1，偶数则是0}}cout<<cnt;
}

E相依

#include<bits/stdc++.h>
using namespace std;
int n;
int a[500010],dp[500010],mn[500010];
int main(){scanf("%d",&n);memset(mn,0x3f,sizeof(mn));for(int i=1;i<=n;i++) scanf("%d",&a[i]);for(int i=1;i<=n;i++){dp[i]=mn[a[i]]+1;mn[a[i]]=min(mn[a[i]],dp[i-1]);}if(dp[n]>=1e6) cout<<-1<<endl;else cout<<dp[n]<<endl;
}

这篇关于牛客小白月赛95的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---