南联企业网站建设,广州低成本网络营销,吉安手机网站建设,小影 wordpress改造序列
题目描述
给定长度为 n n n的序列 a 1 , a 2 , . . . , a n a_1,a_2,...,a_n a1,a2,...,an#xff0c;你可以从中删除一些数#xff0c;使得删完以后的序列中#xff0c;所有相邻元素之和均为偶数。请问最少需要删除多少个数#xff1f;
输入格式
第一行…改造序列
题目描述
给定长度为 n n n的序列 a 1 , a 2 , . . . , a n a_1,a_2,...,a_n a1,a2,...,an你可以从中删除一些数使得删完以后的序列中所有相邻元素之和均为偶数。请问最少需要删除多少个数
输入格式
第一行一个整数 T T T表示测试数据组数 T T T
接下来 T T T组数据每组数据第一行一个整数 n n n第二行 n n n个整数空格分开
输出格式 T T T行每行一个整数表示相应数据的答案
样例 #1
样例输入 #1
2
5
2 4 3 6 8
6
3 5 9 7 1 3样例输出 #1
1
0提示
记 ∑ n \sum n ∑n为一个数据点中所有 n n n之和
对于 100 % 100\% 100%的数据 1 ⩽ T ⩽ 100 1\leqslant T\leqslant 100 1⩽T⩽100 3 ⩽ n ⩽ 1 0 5 3\leqslant n\leqslant 10^5 3⩽n⩽105 1 ⩽ a i ⩽ 1 0 9 1\leqslant a_i\leqslant 10^9 1⩽ai⩽109 1 ⩽ ∑ n ⩽ 1 0 5 1\leqslant \sum n\leqslant 10^5 1⩽∑n⩽105
这道题很简单只需要判断奇数和偶数的的个数输出最小的那个数就行了核心代码如下
while(t--)
{int n,ansa0,ansb0; //一定要附初值不然后面的值不对for(int i1;in;i){cina[i];if(a[i]%20) //判断奇数偶数的个数{ansa;}else{ansb;}/*这里也个可以怎么写int x;cinx;if(x%20){ansa;}else{ansb;}*/}printf(%d\n,min(ansa,ansb));
}非倍数求和
题目描述
给定 n , a , b n,a,b n,a,b求 1 1 1至 n n n之间所有既不是 a a a的倍数也不是 b b b的倍数的数之和。
输入格式
一行三个整数 n , a , b n,a,b n,a,b
输出格式
一行一个整数表示答案
样例 #1
样例输入 #1
10 3 5样例输出 #1
22提示
对于 30 % 30\% 30%的数据$1\leqslant n,a,b\leqslant 10^3 $
对于 60 % 60\% 60%的数据 1 ⩽ n , a , b ⩽ 1 0 6 1\leqslant n,a,b\leqslant 10^6 1⩽n,a,b⩽106
对于 100 % 100\% 100%的数据 1 ⩽ n , a , b ⩽ 1 0 9 1\leqslant n,a,b\leqslant 10^9 1⩽n,a,b⩽109
这道题是一道典型的数论题代码如下
#include bits/stdc.h
using namespace std;
long long gcd(int a,int b)
{if(b0){return a;}return gcd(b,a%b);
}
long long lcm(int a,int b)
{return (long long)a*b/gcd(a,b);/*这道题也可以怎么写:return (long long)a*b/__gcd(a,b);这是直接调用库里的gcd手写的gcd表示那我走*/
}
int main()
{long long n,a,b,ans0,tota,totb,tott,t;scanf(%lld%lld%lld,n,a,b);ans(long long)(1n)*n/2; //高斯求和tota(long long)(an/a*a)*(n/a)/2;totb(long long)(bn/b*b)*(n/b)/2;tlcm(a,b);tott(tn/t*t)*(n/t)/2;printf(%lld,ans-tota-totbtott); //全部-a的倍数-b的倍数a和b的倍数这里因为a和b的倍数剪了两遍所以要把那一遍加回来return 0;
}三数不同
题目描述
给定长度为 n n n的序列 a i a_i ai请计算所有满足以下条件的三元组 ( i , j , k ) (i,j,k) (i,j,k)的个数 i j k ijk ijk a i a_i ai、 a j a_j aj和 a k a_k ak互不相同
输入格式
第一行一个整数 n n n
第二行 n n n个整数 a i a_i ai
输出格式
一个整数表示答案
样例 #1
样例输入 #1
4
3 1 4 1样例输出 #1
2提示
对于 30 % 30\% 30%的数据 n ⩽ 2 × 100 n\leqslant 2\times 100 n⩽2×100$a_i\leqslant 2\times 100 $
对于 60 % 60\% 60%的数据 n ⩽ 2 × 1 0 3 n\leqslant 2\times 10^3 n⩽2×103 a i ⩽ 2 × 1 0 3 a_i\leqslant 2\times 10^3 ai⩽2×103
对于 100 % 100\% 100%的数据 3 ⩽ n ⩽ 2 × 1 0 5 3\leqslant n\leqslant 2\times 10^5 3⩽n⩽2×105 1 ⩽ a i ⩽ 2 × 1 0 5 1\leqslant a_i\leqslant 2\times 10^5 1⩽ai⩽2×105
这道题是要找出有多少对 三元组 这道题的代码如下
#include bits/stdc.h
using namespace std;
const int N2e6;
int h[N10];
long long c(int n,int m) //查找函数
{if(m2){return (long long)n*(n-1)/2;}else if(m3){return (long long)n*(n-1)*(n-2)/6;}
}
int main()
{int n,ans0;scanf(%d,n);for(int i1;in;i){int x;scanf(%d,x);h[x];}long long totc(n,3); //找zzz的情况for(int i1;iN;i){if(h[i]2){tot-c(h[i],2)*(n-h[i]); //找zzy的情况前两个找到了最后一个随便找一个就行了}if(h[i]3){tot-c(h[i],3); //找zzz的情况}}printf(%lld,tot);return 0;
}
