改造序列

題目描述

給定長度為$n$的序列$a_1,a_2,...,a_n$，你可以從中刪除一些數(shù)，使得刪完以后的序列中，所有相鄰元素之和均為偶數(shù)。請(qǐng)問最少需要?jiǎng)h除多少個(gè)數(shù)？

輸入格式

第一行一個(gè)整數(shù)$T$，表示測試數(shù)據(jù)組數(shù)$T$

接下來$T$組數(shù)據(jù)，每組數(shù)據(jù)第一行一個(gè)整數(shù)$n$，第二行$n$個(gè)整數(shù)，空格分開

輸出格式

$T$行，每行一個(gè)整數(shù)，表示相應(yīng)數(shù)據(jù)的答案

樣例 #1

樣例輸入 #1

2
5
2 4 3 6 8
6
3 5 9 7 1 3

樣例輸出 #1

1
0

提示

記$\sum n$為一個(gè)數(shù)據(jù)點(diǎn)中所有$n$之和

對(duì)于$100\%$的數(shù)據(jù)，$1?T?100$，$3?n?10^5$，$1?a_i?10^9$，$1?\sum n?10^5$

這道題很簡單，只需要判斷奇數(shù)和偶數(shù)的的個(gè)數(shù)，輸出最小的那個(gè)數(shù)就行了，核心代碼如下：

while(t--)
{int n,ansa=0,ansb=0;	//一定要附初值，不然后面的值不對(duì)for(int i=1;i<=n;i++){cin>>a[i];if(a[i]%2==0)	//判斷奇數(shù)偶數(shù)的個(gè)數(shù){ansa++;}else{ansb++;}/*這里也個(gè)可以怎么寫：int x;cin>>x;if(x%2==0){ansa++;}else{ansb++;}*/}printf("%d\n",min(ansa,ansb));
}

非倍數(shù)求和

題目描述

給定$n,a,b$，求$1$至$n$之間所有既不是$a$的倍數(shù)也不是$b$的倍數(shù)的數(shù)之和。

輸入格式

一行，三個(gè)整數(shù)$n,a,b$

輸出格式

一行，一個(gè)整數(shù)，表示答案

樣例 #1

樣例輸入 #1

10 3 5

樣例輸出 #1

22

提示

對(duì)于$30\%$的數(shù)據(jù)，$1\leqslant n,a,b\leqslant 10^3 $

對(duì)于$60\%$的數(shù)據(jù)，$1?n,a,b?10^6$

對(duì)于$100\%$的數(shù)據(jù)，$1?n,a,b?10^9$

這道題是一道典型的數(shù)論題，代碼如下：

#include <bits/stdc++.h>
using namespace std;
long long gcd(int a,int b)
{if(b==0){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);這是直接調(diào)用庫里的gcd手寫的gcd表示：那我走*/
}
int main()
{long long n,a,b,ans=0,tota,totb,tott,t;scanf("%lld%lld%lld",&n,&a,&b);ans=(long long)(1+n)*n/2;	//高斯求和tota=(long long)(a+n/a*a)*(n/a)/2;totb=(long long)(b+n/b*b)*(n/b)/2;t=lcm(a,b);tott=(t+n/t*t)*(n/t)/2;printf("%lld",ans-tota-totb+tott);	//全部-a的倍數(shù)-b的倍數(shù)+a和b的倍數(shù)（這里因?yàn)閍和b的倍數(shù)剪了兩遍，所以要把那一遍加回來）return 0;
}

三數(shù)不同

題目描述

給定長度為$n$的序列$a_i$，請(qǐng)計(jì)算所有滿足以下條件的三元組$(i,j,k)$的個(gè)數(shù)

• $i<j<k$
• $a_i$、$a_j$和$a_k$互不相同

輸入格式

第一行，一個(gè)整數(shù)$n$

第二行$n$個(gè)整數(shù)$a_i$

輸出格式

一個(gè)整數(shù)，表示答案

樣例 #1

樣例輸入 #1

4
3 1 4 1

樣例輸出 #1

2

提示

對(duì)于$30\%$的數(shù)據(jù)，$n?2\times 100$，$a_i\leqslant 2\times 100 $

對(duì)于$60\%$的數(shù)據(jù)，$n?2\times 10^3$，$a_i?2\times 10^3$

對(duì)于$100\%$的數(shù)據(jù)，$3?n?2\times 10^5$，$1?a_i?2\times 10^5$

這道題是要找出有多少對(duì) 三元組 ，這道題的代碼如下：

#include <bits/stdc++.h>
using namespace std;
const int N=2e6;
int h[N+10];
long long c(int n,int m)	//查找函數(shù)
{if(m==2){return (long long)n*(n-1)/2;}else if(m==3){return (long long)n*(n-1)*(n-2)/6;}
}
int main()
{int n,ans=0;scanf("%d",&n);for(int i=1;i<=n;i++){int x;scanf("%d",&x);h[x]++;}long long tot=c(n,3);	//找zzz的情況for(int i=1;i<=N;i++){if(h[i]>=2){tot-=c(h[i],2)*(n-h[i]);	//找zzy的情況，前兩個(gè)找到了，最后一個(gè)隨便找一個(gè)就行了}if(h[i]>=3){tot-=c(h[i],3);	//找zzz的情況}}printf("%lld",tot);return 0;
}