Hướng dẫn giải của Cân bằng
Chỉ dùng lời giải này khi không có ý tưởng, và đừng copy-paste code từ lời giải này. Hãy tôn trọng người ra đề và người viết lời giải.
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.
Tác giả:
txhai12
#include <bits/stdc++.h>
using namespace std;
#define show(x) cout << (#x) << " is " << (x) << endl
#define ll long long
#define len(s) (int)s.length()
#define epb emplace_back
#define fir first
#define sed second
#define sz(ds) (int)ds.size()
#define all(arr) arr.begin(), arr.end()
int main() {
//ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
int t;
cin >> t;
while (t--) {
int n;
cin >> n;
map<int,ll> cnt;
ll ans = 0;
ll pre = 0;
for(int i = 0 ; i < n ; i++){
int tmp;cin>>tmp;
ll cur = pre + cnt[tmp];
ans+=cur;
pre = cur;
cnt[tmp]+=i+1;
}
cout<<ans<<endl;
}
}
Bình luận
Fan MU có thể nói là lại chui vào hang và xuống đáy xã hội ?
Khi vào hang cùng fan MU, mình đã lướt qua những kiến thức của các bậc hiền nhân VOZER về bài Cân Bằng này.
Giải thích ý tưởng:
Các vozer nhận thấy rằng:
Mỗi lần thêm một số mà số này đã có trong dãy (Gọi các số đã có trong dãy là số cũ và số mới thêm là số mới).
Thì giá trị cân bằng sẽ được cộng thêm một lượng bằng với tổng chỉ số của các số cũ (Không tính chỉ số của số mới).
Cộng các giá trị cân bằng vào là chúng ta sẽ có kết quả cuối cùng.
Minh họa ý tưởng:
P/s: Cảm ơn mọi người vì đã xem. Trên đây là ý hiểu của mình nếu có sai sót gì mong mọi người góp ý ?