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的矩阵，初始全是 000，
现在文文手上有 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;
}