A. median
Title:
Given the array a1,a2,..., an with length n, do exactly k operations. Each operation selects two different positive integers i,j so that ai=ai+aj, and deletes aj from the array.
What is the minimum median of the sequence after k operations?
Median: a sequence with a length of M. its median is the number of floor ⌊ 2m+1 ⌋ after arranging the M numbers in ascending order.
Enter Description:
The input contains T groups of test cases, and the first line contains an integer t
The first line of each test case contains two integers n,k
The second line of each test case contains n integers A1, A2... an
Output Description:
Output the answers of the i-th group of test cases in line T.
Example 1
input
1
5 1
4 3 5 1 2
output
2
remarks:
1≤T≤5,1≤ai≤200000,2≤n≤200000,1≤k<n
Investigation: greed.
Idea:
Ask what is the minimum median after k operations. Consider two cases.
If there is only one number left after k operations, then this number is the median and it is equal to the sum of all numbers.
else, the greedy strategy is to sort from small to large, and always keep the first half. By operating the number of the second half, you can always maintain the median. The number in the previous smaller original number series is the median.
Then the median after K operations is the median of the first half of the length n-k!
The code is as follows:
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 200010;
int t,n,k,a[N];
ll sum;
int main(){
cin>>t;
while(t--){
cin>>n>>k;
sum=0;
for(int i=1;i<=n;i++) cin>>a[i],sum+=a[i];
sort(a+1,a+n+1);
n-=k;//Get the sequence length after k operations
if(n==1) cout<<sum<<endl;//There is only one number left after k operations, so this number is the sum of all numbers
else cout<<a[(n+1)/2]<<endl;//The smallest median is the number in the original sequence, so directly take the (n + 1) / 2nd number of the original sequence
}
return 0;
}
B.k decimal query
Title Description
Niuniu learned to persist the line segment tree, so he began to show off to niumei. Niu Mei disdains it. Can you solve the following k{k}k decimal query problem:
Given the sequence a1, a2,..., an with length n{n}n, how many pairs of different integer pairs (l,r)(l ≤ r)(l,r) satisfy r − l+1 ≥ K and the smallest number k in al,al+1,..., ar is x?
Enter Description:
The first line contains three integers n,x,k.
The second line n{n}n integers A1, A2... an
Output Description:
An integer on a line represents the answer.
Example 1
input
5 3 2
1 2 3 4 5
output
copy
3
explain
The second smallest number in the interval [2,3], [2,4], [2,5] is 3.
remarks:
1≤x,k≤n≤200000
a1, a2,..., an is an arrangement of 1,2,..., n.
**Investigation: * * prefix and, left and right extension
Idea:
To make x the k-th decimal in the sequence, it is necessary to ensure that the number of k-1 in this sequence is less than x.
Take x as the center, expand left and right, and calculate the number less than x on the left and right sides, which is in the range of 0-k-1,
The number of each position meeting the requirements is calculated by product (both left and right contribute), and then accumulated.
The code is as follows:
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define N 200010
int n,x,k,a[N],pos;
ll l[N],r[N],ans;
int main(){
scanf("%d%d%d",&n,&x,&k);
for(int i=1;i<=n;i++){
scanf("%d",&a[i]);
if(a[i]==x) pos=i;//Record the position of x
}
l[0]=1,r[0]=1;//Itself, when k=1 and there is only x in the sequence, it is the first decimal
int num=0;
for(int i=pos-1;i>=1;i--){
if(a[i]<x) num++;//Num represents the number of num smaller than x on the left of X
l[num]++;//Update the interval length satisfying num
}
num=0;
for(int i=pos+1;i<=n;i++){
if(a[i]<x) num++;
r[num]++;
}
for(int i=0;i<=k-1;i++){//Left and right contribution multiplication
ans+=l[i]*r[k-1-i];
}
cout<<ans<<endl;
return 0;
}
C. Boss Niu
**Investigation: * * greedy, DFS
Idea:
First, several simple cases are cited, and complex cases are calculated recursively with simple cases.
If the denomination is less than 6, it can only be paid for one yuan, and x sheets are required.
If it happens to be 6 or 9, it's 1.
We map x to at least how many face values are needed. If it is calculated, it is output directly.
If you can't divide a number, first calculate the multiple of the number divided by 6 (or the multiple of 9. As for who to take, see who is the best),
Then the divisible part only needs one,
This is the optimal solution that can divide the part. Next, recursively calculate the number of sheets required for the remainder part, and finally add up the face values required for the integer part and the remainder part,
Take the best value in two cases (6i or 9i first).
Key:
This problem needs to map x to the required number of sheets, so you need map or unordered_map, but since this problem will appear in the recursive calculation and calculate the number of other X sheets, we don't need to recalculate, just take the result directly. unordered_map provides an MP The count (x) function returns the number of key value pairs if the key is x, and returns 0.5 if it does not exist Therefore, if(mp.count(x)) is generally used. Unordered in terms of search and insertion_ Map is more efficient than hash_map, better than map; In terms of spatial complexity, hash_map lowest, unordered_map takes the second place and map is the largest. hash_ The map is a little complex, so unordered is preferred when searching_ map.
The code is as follows:
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
unordered_map<ll,ll> mp;
ll qk(ll a,ll b){
ll ans=1;
while(b){
if(b&1) ans=ans*a;
a=a*a;
b>>=1;
}
return ans;
}
ll cal(ll x){
if(x<6) return x;//6 ^ 0 = 1, x 1 required
if(x==6||x==9) return 1;
if(mp.count(x)) return mp[x];//If there is a face value of x, return it directly
ll num1=0,num2=0;
ll i=1;
while(i<=x){
i*=6;
num1++;
}
num1--;
i=1;
while(i<=x){
i*=9;
num2++;
}
num2--;
mp[x]=min(cal(x-qk(6,num1))+1,cal(x-qk(9,num2))+1);
return mp[x];
}
int main(){
int t;
cin>>t;
while(t--){
ll x;
cin>>x;
printf("%d\n",cal(x));
}
return 0;
}