数量
给定一个正整数 n，请你计算[1,n]范围内一共有多少个正整数满足能被 2整除，但不能被 3整除。
输入格式
一个正整数 n。
输出格式
一个整数，表示满足条件的整数的数量。
数据范围
前 3个测试点满足 1≤n≤100。
所有测试点满足 1≤n≤10000。
思路:
一个比较简单的模拟
代码:
#include<bits/stdc++.h>
using namespace std;
int main(){
int n;
cin>>n;
int ans=0;
for(int i=1;i<=n;i++){
if(i%2==0&&i%3!=0){
ans++;
}
}
cout<<ans<<endl;
return 0;
}
三元组
给定一个长度为 n的正整数数组 a1,a2,…,an。
请你计算，一共有多少个三元组 (i,j,k)（1≤i<j<k≤n），使得 ai⋅aj⋅ak为最小可能值。
输入格式
第一行包含整数 n。
第二行包含 n个正整数 a1,a2,…,an。
输出格式
一个整数，表示满足条件的三元组的数量。
数据范围
前 3个测试点满足，3≤n≤6。
所有测试点满足，3≤n≤105，1≤ai≤109。
思路:
也是一个比较简单的模拟,注意一下数据范围就好了
代码:
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e5+10;
ll a[N];
ll deshu(ll x,ll y){
ll ans=1;
for(int i=x;i>=x-y+1;i--){
ans*=i;
}
for(int i=1;i<=y;i++){
ans/=i;
}
return ans;
}
int main(){
int n;
cin>>n;
// std::vector<int> a(n+1);
for(int i=1;i<=n;i++){
cin>>a[i];
}
sort(a+1,a+n+1);
// int ans1,ans2,ans3;
// ans1=ans2=ans3=0;
ll x=a[1];
int flag=1;
int y=0;
std::vector<int> ans;
for(int i=1;i<=n;i++){
if(flag==4){
break;
}
if(a[i]==x){
y++;
}
else{
x=a[i];
ans.push_back(y);
y=1;
flag++;
}
}
if(flag<=3){
ans.push_back(y);
}
// for(int i=0;i<ans.size();i++){
// cout<<ans[i]<<" ";
// }
// cout<<endl;
if(ans[0]>=3){
cout<<deshu(ans[0],3)<<endl;
}
else if(ans[0]+ans[1]> =3){
cout<<deshu(ans[0],ans[0])*deshu(ans[1],3-ans[0])<<endl;
}
else{
cout<<deshu(ans[0],ans[0])*deshu(ans[1],ans[1])*deshu(ans[2],3-ans[1]-ans[0])<<endl;
}
return 0;
}
删除元素
给定一个长度为 n的整数序列 a1,a2,…,an，这恰好是一个 1∼n 的排列。
在一个序列中，如果一个元素满足位于它前面的所有元素均严格小于它，那么就称该元素是一个有价值元素。
特别规定，位于序列首位的元素视为有价值元素。
现在，请你删除给定序列中的一个元素，使得新序列中有价值元素的数量尽可能多。
如果可以删除的元素不唯一，则优先删除其中最小的元素。
输入格式
第一行包含整数 n。
第二行包含 n个整数 a1,a2,…,an。
输出格式
一个整数，表示要删除的元素的值。
数据范围
前 3 个测试点满足 1≤n≤5。
所有测试点满足 1≤n≤105，1≤ai≤n，保证 a1∼an 是一个 1∼n 的排列。
思路:
f[i]表示删去值为i的元素后，有价值的数增加的个数,如果我们当前考虑的数字之前有两个比他大的数字,那样删除他对其他的造不成影响,如果前面只有一个比他大的数字,那样可以把前面大的数字删除,这样多一个有价值的,如果本身就是有价值的,那样删了就少了,所以我们只需要保留最大值和次大值就行.
代码
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
// int a[N];
int f[N];
void solve(){
int n;
cin>>n;
int maxn1=0,maxn2=0;
for(int i=1;i<=n;i++){
int x;
cin>>x;
if(x>maxn2){
f[x]-=1;
}
else if(x>maxn1&&x<maxn2){
f[maxn2]+=1;
}
if(x>maxn2){
maxn1=maxn2;
maxn2=x;
}
else if(x>maxn1){
maxn1=x;
}
}
int flag=1;
// int x=f[1];
for(int i=2;i<=n;i++){
if(f[i]>f[flag]){
flag=i;
}
}
cout<<flag<<endl;
}
int main(){
int t=1;
while(t--){
solve();
}
return 0;
}