Cowdriver Little White Moon Race 41

A. Xiao Hong's Check-in Title

meaning of the title

A total of a questions and b participants are known to have changed the version of the Little White Moon Contest. The total number of questions passed by all participants is c. Ask how many ak are there at most?

thinking
Check in the title, just c/a

Code

#include<bits/stdc++.h>
using namespace std;
#define IOS std::ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
const int N=110;

typedef long long LL;

int main()
{
    IOS;
    int a,b,c;
    cin>>a>>b>>c;
    cout<<c/a<<endl;
    return 0;
}

B. Small Red's ABC

meaning of the title

Xiao Hong gets a string that contains only three characters:'a','b','c'.
Xiao Hong wants to know, what is the length of the shortest palindrome substring that is longer than 1?

thinking
There are only three possibilities for a palindrome substring with a minimum length of more than 1, nonexistent, 2 or 3, so traversing directly will give you an answer.

Code

#include<bits/stdc++.h>

using namespace std;

#define IOS std::ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)

const int N=110;
typedef long long LL;
string s;

int main()
{
    cin>>s;
    int i=0,j=1;
    int flag=false,flag1=false; //Do 2 and 3 occur?
    for(int i=0;i<s.length();i++)
    {
        if(s[i]==s[i+1])
            flag=true;
        if(s[i]==s[i+2])
            flag1=true;
    }
        
    if(flag)
        cout<<2<<endl;
    else if(flag1)
        cout<<3<<endl;
    else 
        cout<<-1<<endl;
    return 0;
}

C. Small red mask

meaning of the title

Xiao Hongwang bought n masks.
As we all know, it is uncomfortable to wear a mask. Xiao Hong wears each mask for the first day with an initial discomfort of ai
Xiao Hong sometimes reuses the mask (Note: This is very hygienic!), and the discomfort of the mask doubles each time it is reused.
Xiao Hong wants to know how many days can she spend with an existing mask if her total discomfort does not exceed k?

thinking
Each time you choose the mask with the least comfort and then double and reorder it, it's clear that we can solve this problem with a little root heap.

Code

#include<bits/stdc++.h>

using namespace std;

#define IOS std::ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)

const int N=1e5+10;

priority_queue<int ,vector<int> ,greater<int> >q;


typedef long long LL;

LL a[N];
int cnt;
int main()
{
    int n,k;
    cin>>n>>k;
    for(int i=0;i<n;i++){  //Input data
        int x;
        cin>>x;
        q.push(x);
    }
    
    while(k>=0)
    {
        int x=q.top();
        if(k>=x)  
        {
            k-=x;
            x*=2;   //Rejoin the team after doubling comfort
            q.pop();
            q.push(x);
            cnt++;
        }
        else  
            break;
    }
    cout<<cnt<<endl;
    return 0;
}

D. Small Red Array

meaning of the title

Xiao Hong gets an array of length n, in which the elements are positive integers.
Xiao Hong wants you to answer the following three questions: the number of scenarios whose product of two numbers is greater than k, the number of scenarios whose product of two numbers is equal to k, and the number of scenarios whose product of two numbers is less than k.

thinking
Binary
There are three cases of traversing an array after sorting:
1. If a[i]*a[i+1]>k, there will be n-i-1 multiplier a[i] from i+1~n > K.
2. If a[i]*a[n]<k, there is also a n-i-1 multiplier a[i] from i+1~n that will be <k.
3. If a[i]*a[i+1]=k or a[i]*a[n]=k, first we have to divide the left boundary L to find the first number of >=k/a[i] and the right boundary R to >k/a[i], i n which we have to distinguish between two cases:

• A: If k%a[i]=0:
  Then multiply the number from I-1 to L by a[i]<k, the number of LR by a[i]=k, and the number of Rn by a[i]>k
• b: if k%a[i]!= 0:
  So there won't be a case equal to k, so there are Rn numbers multiplied by a[i]>k,i-1R numbers multiplied by a[i]<k

Code

#include<bits/stdc++.h>

using namespace std;

#define IOS std::ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)

const int N=3e5+10;

typedef long long LL;

LL n,k;
LL  a[N];
LL k1,k2,k3;

int main()
{
    cin>>n>>k;
    for(int i=0;i<n;i++)  cin>>a[i];

    sort(a,a+n);

    for(int i=0;i<n-1;i++)
    {
        if(a[i]*a[i+1]>k) k1+=n-i-1;
        else if(a[i]*a[n-1]<k)  k3+=n-i-1;
        else {
            int p=lower_bound(a+i+1,a+n,k/a[i])-a;
            int q=upper_bound(a+i+1,a+n,k/a[i])-a;
            
            if(k%a[i]!=0)
            {
                k1+=n-q;
                k3+=q-i-1;
            }
            else
            {
                k3+=p-i-1;
                k1+=n-q;
                k2+=q-p;
            }
        }
    }
    cout<<k1<<' '<<k2<<' '<<k3<<endl;
    return 0;
}

QAQ~Sleepy