给你一个数组 a1,a2…an 。请计算有多少个图元 (i,j,k,l)符合以下条件:
· \(1\) \(\le\) \(i\)<\(j\)<\(k\)\(<\)\(l\)\(\le\)n
· a\(i\)\(=\) a\(k\) 和 a\(j\) \(=\) a\(l\)
\(Input\)
The first line contains a single integer \(t\) (\(1\)≤\(t\)≤\(100\)) — the number of test cases.
The first line of each test case contains a single integer \(n\) (\(4\)≤\(n\)≤\(3000\)) — the size of the array a.
The second line of each test case contains n integers a\(1\),a\(2\),…,a\(n\)(\(1\)≤a\(i\)≤\(n\)) — the array a.
It's guaranteed that the sum of n in one test doesn't exceed 3000.
\(Output\)
For each test case, print the number of described tuples.
题目链接:https://codeforces.com/contest/1400/problem/D
哈希一下其实可以更快,但是数据量不大,n方解决即可;
AC代码:
#include"bits/stdc++.h"
using namespace std;
using ll=long long;
#define int long long
const int Mod=998244353;
void save_the_people(){
int n,ans{0};
cin>>n;
vector<int> a(n);
for(int i{0};i<n;i++){
cin>>a[i];
a[i]--;
}
vector<int> c1(n),c2(n);
for(int i{0};i<n;i++){
fill(c1.begin(), c1.end(),0);
fill(c2.begin(), c2.end(),0);
for(int l{i+1};l<n;l++){
c2[a[l]]++;
}
int res{0};
for(int k{i+1};k<n;k++){
res-=c1[a[k]];
c2[a[k]]--;
if(a[i]==a[k])
ans+=res;
res+=c2[a[k]];
c1[a[k]]++;
}
}
cout<<ans<<"\n";
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int t{1};
cin>>t;
while(t--) {
save_the_people();
}
}
题目链接:https://codeforces.com/contest/1934/problem/D1
一道位运算的题,只要找出初始数n转为二进制后第一二个1的位置和目标数第一个1的位置的关系即可解决;
/***
* author: touirst
* created: now
***/
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
const int N=1e9+5;
void save_the_newnew() {
ll n,m;
cin>>n>>m;
//cout<<n<<"\n";
//cout<<(n^m)<<"\n";
if((n^m)<n){cout<<1<<"\n"<<n<<" "<<m<<"\n";return;}
ll lim{0},bn{63},bm{63};
vector<int> a(65),b(65);
//cout<<n<<"\n";
while(!((n>>bn)&1)){
bn--;
}
//cout<<bn<<"\n";
bn--;
//cout<<bn<<"\n";
while(!((n>>bn)&1)){
bn--;
}
//cout<<bn<<"\n";
lim=(1ll<<(bn+1))-1;
//cout<<lim<<"\n";
while(!((m>>bm)&1)){
bm--;
}
if(lim==m){
cout<<1<<"\n"<<n<<" "<<m<<"\n";return;
}else if(lim<m||lim>=n){
cout<<"-1\n";return;
}else{
cout<<2<<"\n"<<n<<" "<<lim<<" "<<m<<"\n";
}
//cout<<bm<<"\n";
//cout<<((7>>0)&1)<<" "<<((7>>1)&1)<<" "<<((7>>2)&1);
}
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
int ttt{1};
cin>>ttt;
while(ttt--){
save_the_newnew();
}
}
标签:10,2024.3,cout,int,manjuan,long,--,test,save
From: https://www.cnblogs.com/manjuan/p/18064870