xp04 - day03 考试
2025-08-14 20:55:28
发布于：浙江
30阅读
0回复
0点赞
坤坤爱喝可乐2
#include <iostream>
using namespace std;
int main(){
int n,m,cnt;//m代表空瓶子，cnt喝了多少瓶
cin >> n;
cnt = n;
m = n;
while(m >= 3){
cnt+=m/3;
m=m%3+m/3;
}
if(m==2) cnt++;
cout << cnt;
return 0;
}
图腾
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 200010;
int n;
int a[N];
int tr[N];
int Greater[N], lower[N];
int lowbit(int x){
return x & -x;
}
void add(int x, int c){
for (int i = x; i < N; i += lowbit(i)) tr[i] += c;
}
int sum(int x){
int res = 0;
for (int i = x; i; i -= lowbit(i)) res += tr[i];
return res;
}
int main(){
cin>>n;
for (int i = 1; i <= n; i ++ ) cin>>a[i];
for (int i = 1; i <= n; i ++ ){
int y = a[i];
Greater[i] = sum(n) - sum(y);
lower[i] = sum(y - 1);
add(y, 1);
}
for (int i = 1; i <= n; i ++ )tr[i]=0;
LL res1 = 0, res2 = 0;
for (int i = n; i; i -- ){
int y = a[i];
res1 += Greater[i] * (LL)(sum(n) - sum(y));
res2 += lower[i] * (LL)(sum(y - 1));
add(y, 1);
}
cout<<res1<<" "<<res2;
return 0;
}
奶牛的秘密
#include <bits/stdc++.h>
using namespace std;
const int N = 300010;
int n;
int h[N];
int ans[N];
int tr[N];
int lowbit(int x){
return x & -x;
}
void add(int x, int c){
for (int i = x; i <= n; i += lowbit(i)) tr[i] += c;
}
int sum(int x){
int res = 0;
for (int i = x; i; i -= lowbit(i)) res += tr[i];
return res;
}
int main(){
cin>>n;
for (int i = 2; i <= n; i ++ ) cin>>h[i];
for (int i = 1; i <= n; i ++ ) tr[i] = lowbit(i);
for (int i = n; i; i -- ){
int k = h[i] + 1;
int l = 1, r = n;
while (l < r)
{
int mid = l + r >> 1;
if (sum(mid) >= k) r = mid;
else l = mid + 1;
}
ans[i] = r;
add(r, -1);
}
for (int i = 1; i <= n; i ++ ) cout<<ans[i]<<endl;
return 0;
}
有帮助，赞一个