A little question every day at the Blue Bridge, ta and you in the national game

Table of contents

The first question is a clever row of poker

💒Title description

original title portal

🌟 Problem solving report

I don’t know how to implement this problem into the code. I don’t know if there are any friends who can give me some pointers on the implementation of the code. I will do the calculation directly on the scratch paper, and then output the result directly.

The derived diagram is as follows:

a[0] ~ a[12] respectively represent the 13 poker cards in hand

At this point, you can clearly see how many cards correspond to a[0] to a[12].

🌻 Reference code (C++ version)

#include <cstdio>

int  main ()
 {
 //I feel the pit is that the title doesn't seem to say there is a space between them.... 
  printf ( "7, A, Q, 2, 8, 3, J, 4, 9, 5, K, 6, 10" );
   return  0 ;
}

The second question is prime number split

💒Title description

original title portal

🌟 Problem solving report

The only thing I want to say about this question is to be careful when reading the question.
I originally thought it was very cute to add two prime numbers to equal 2019. They are all ready to take out the dual pointers they have just learned to practice their hands, and then they are WA.

The title is about a number of different prime numbers. It means to use many prime numbers to combine, but each prime number is unique and can only be used once. Now let’s find an optimal solution, then this is the lovely 01 backpack .

Take out our lovely Yan-style DP analysis method

Status indicates:

set: f [i] [ j ] f[i][j] f [ i ] [ j ] means the first i i The sum of i prime numbers can be formed to be j j The number of solutions for j
Attribute: C o u n t Count Count

Because this collection f[i][j]is still a piece of storage space in the end, to store a piece of data, we generally refer to this data as f[i][j]an attribute

State calculation:

The essence of state calculation is to divide the currently determined set f[i][j] with the last difference.
For the 01 backpack, the division of this question is still whether the current prime number is selected or not.

To sum up, you can get this lovely DP analysis graph

What is written here is two-dimensional DP, it can be optimized to one-dimensional, because there is more content later, I will not talk about optimization, and I will post a blog about optimization in the future~

🌻 Reference code (C++ version)

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <iostream>

using namespace std;
typedef long long LL;

const int N = 2030;
bool st[N];
int primes[N],cnt;
LL f[N][ 4200 ]; //f[i][j] indicates the number of schemes that can be formed with the sum of j in the first i prime numbers



//The linear sieve gets the prime numbers out 
void  get_primes ( int n)
 {
     for ( int i = 2 ;i <= n;i++)
    {
        //If it is a prime number, add it to the array 
        if (!st[i]) primes[++cnt] = i;
         //Enumerate all prime numbers from small to large 
        for ( int j = 0 ; primes[j ] <= n/i;j++)
        {
            //Filter out prims[j] * i 
            st[primes[j] * i] = true ;
        }
    }
}

int  main ()
 {
     //Use the sieve method to sieve out all the prime numbers from 
    2-2019 get_primes( 2019 );

    //Each number can only be used once, then you can find the cute 01 backpack

    //initialize 
    f[ 0 ][ 0 ] = 1 ;

    for(int i = 1; i <= cnt;i++)
        for(int j = 0;j <= 2019;j++)
        {
            f[i][j] += f[i-1][j];
            if(j >= primes[i]) f[i][j] +=  f[i-1][j-primes[i]];
        }

    cout << f[cnt][2019] << endl;

    return 0;
}

The third question log statistics

💒Title description

original title portal

🌟 Problem solving report

The label it gives is greedy, but I’m just learning about double pointers, so let’s write with double pointers. It just so happens that I’m not too greedy~, in fact, I’m not very good at double pointers, damn it.

Two pointer arithmetic: let a pointer i i i is ahead, walking slowly, another pointer j j j , go fast, and i i The i pointer forms an interval.

For this question: Take each liked post first and save it.
Then go to check whether the post is within the specified time difference d d get K K under dK likes. If so, then this post is a hot post,

🌻 Reference code (C++ version)

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>


#define x first
#define y second

using namespace std;

typedef pair< int , int > PII; //When the input information is a two-tuple, either use pair or define the structure yourself

const int N = 100010;

int n,d,k;
PII logs[N];; //Used to store logs ts, id 
int cnt[N]; //Used to mark the id number of the post 
bool st[N]; //Used to record the number of likes obtained by an id number, The representation is cnt[id]++;

int main()
{
    scanf("%d%d%d",&n,&d,&k);
    for(int i = 0; i < n;i++) scanf("%d%d",&logs[i].x,&logs[i].y);


    // sort in chronological order
    sort(logs,logs+n);

    // enumerate each post 
    for ( int i = 0 ,j = 0 ; i < n; i++)
    {
        int id = logs[i].y; //Save the id of each liked post 
        cnt[id] ++;; //Get a like, so now ++

        while(logs[i].x - logs[j].x >= d)
        {
            cnt[logs[j].y] --; //Deduct this unqualified post from 
            j++; //move the pointer j backwards
        }

        if(cnt[id] >= k) st[id] = true;
    }

   // Print the id of the hot post 
    for ( int i = 0 ;i <= 100000 ;i++)
         if (st[i]) printf ( "%d\n" ,i);

    return 0;

}

Question 4 Incremental triples

💒Title description

original title portal

🌟 Problem solving report

If the direct triple loop enumeration, then it is 1 0 15 10^{15} 1015 operations are far greater than the 100 million operations that C++ can perform in one second, so it must be timed out.

Combining with the algorithm I put in Yizhixing based on the data range determination, we can see that if the data range is 1 0 5 10^5 105 , then we can only do one layer of loops at most.

According to the requirements of the title,
we need to find A A The ratio of B i B_i in the A sequenceBi​Small numbers, count them;
find C C The ratio of B i B_i in the C sequenceBi​Big ones, count them.
Finally, according to the cute multiplication principle (primary mathematics content), you can get the result

I’m afraid everyone forgot primary school math…

In order to count B i B_i smaller than B i in the A sequenceBi​The number of , in the C sequence is greater than B i B_i Bi​number of.

**It can be sorted first, and then combined with binary search.

Statistics A sequence is less than B i B_i Bi​ , then it is equivalent to finding 0 0 in the prefix sum array0 ~ B i − j B_i-j Bi​−How many numbers does j have.
Statistical B sequence greater than B i B_i Bi​ , then it is equivalent to looking up B i B_i in the prefix sum arrayBi​ ~ N − 1 N-1 N−How many numbers are there in 1 .

🌻 Reference code (C++ version)

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

typedef long long LL;
const int N = 100010;

int n;
 int a[N],b[N],c[N];
 int a_b[N]; //a_bi] indicates how many numbers in A[] are less than b[i] 
int c_b[ N]; //c_b[i] indicates how many numbers in C[] are greater than the number of b[i]

int cnt[N],s[N];   //The cnt array for statistics and the s array for calculating the prefix sum

int  main ()
 {
     scanf ( "%d" ,&n);
     //Read in three triples 
    //Because the knowledge of the prefix sum is used, there will be a subtraction operation in the prefix sum, in order to avoid array corners Out of bounds, all results that require +1 to the input 
    for ( int i = 0 ; i < n;i++) scanf ( "%d" ,&a[i]),a[i] ++; 
     for ( int i = 0 ; i < n;i++) scanf ( "%d" ,&b[i]),b[i] ++;
     for ( int i = 0 ; i < n;i++) scanf ( "%d" ,&c[ i]),c[i]++;

    //Seek as[] 
    //First count the number of occurrences of this a[i] 
    for ( int i = 0 ; i < n;i++) cnt[a[i]] ++; //Use the cnt array to count, which means , if it appears, it is 1, if it does not appear, it is 0 
    for ( int i = 1 ; i < N;i++) s[i] = s[i -1 ] +cnt[i]; //Initialize the prefix sum 
    for ( int i = 0 ; i < n;i++) a_b[i] = s[b[i] -1 ]; //Count the prefix sum of (0, to Bj-1), because this prefix sum records the number, just The query can be implemented in O(1)

    //Seek cs[] 
    //First clear both the cnt and s arrays 
    memset (cnt, 0 , sizeof cnt);
     memset (s, 0 , sizeof s);

    for ( int i = 0 ; i < n;i++ ) cnt[c[i]] ++;
     for ( int i = 1 ; i < N;i++) s[i] = s[i -1 ] + cnt[ i];
     for ( int i = 0 ; i < n;i++) c_b[i] = s[N -1 ] - s[b[i]]; i] job

    //According to the data range algorithm here we have determined that we can only enumerate one number 
    //enumerate each b[i] 
    LL res = 0 ;
     for ( int i = 0 ; i < n; i++) res += ( LL)a_b[i] * c_b[i];

    cout << res << endl;
    return 0;

}

Question 5: Priority of takeaway points

💒Title description

original title portal

🌟 Problem solving report

The idea of ​​dealing with discrete data – because for a store, there may be orders for a period of time, and there may be no orders for a period of time.
So the data is discrete. The processing method can ignore the moment when there is no order in a row, and put it into processing after there is an order.

Problem solving idea:

This simulation problem is a bit complicated. If your friends have the habit of writing pseudo-code, you can be more comfortable when solving more complex simulation problems.

1. Sort all orders by time

2. Then enumerate each order from front to back

Pure brute force is to enumerate every moment, time complexity is O ( N 2 ) O(N^2) O ( N2 ), it will time out.
In the loop, the same batch of orders is processed each time (it can be understood that as long as this time point and the corresponding store Id are the same, they are regarded as a whole, and a batch of orders can be processed each time)

Suppose the current order is the ith i , use the loop to determine whether there arethe same orders(that is, at the same order time t t t , the number id id of the storeid is the same).
When the j jth When there are j orders, the orders are different, then the quantity of this batch of orders should be c n t = j − i cnt= j – i cnt=j−i
lower order f o r for The f o r loop starts at j to process the next batch of orders

Record t and id at this time, and calculate the priority of id. There are two parts to be processed.

Part 1:
Calculate the priority, if it is negative at this time, then Reset priority to 0.
If the priority is less than or equal to 3, remove the store from the priority cache, that is: s t [ i d ] = f a l s e st[id] = false st[id]=false**

Part II:
t t Get the order at time t , and the quantity is c n t cnt c n t , the priority of this store is to add 2 ∗ c n t 2*cnt 2∗c n t .
Calculate the priority, if it is greater than 5, put it into the priority cache, that is: s t [ i d ] = t r u e st[id] = true st[id]=true;

Because the same order has already been processed, there is no need to calculate it again, and a new cycle starts at the position j, where the next batch of orders appears.

for(int i = 0; i < m;)
......
i = j;

Loop to the end, the last time the order was received last [ d ] last[id] l a s t [ i d ] is updated to t t t

3. Final processing

If the time of the last order is T, then it does not need to be processed.
If it is not T, then the subtraction of the priority deduction from the last order to the time T needs to be supplemented.
That is, subtract the difference between the last order moment and T. Because there is no order at time T, there is no need to reduce it by one.
Judging the priority, if it is less than or equal to 3, clear it out of the priority cache. Finally, traverse the priority cache, and the number obtained is the answer to the question

🌻 Reference code (C++ version)

#include <iostream>
#include <cstring>
#include <iostream>
#include <algorithm>

#define x first
#define y second

using namespace std;

typedef pair<int,int> PII;
const int N = 100010;

int n,m,T;
 int score[N]; //indicates the priority of the i-th store 
int last[N]; //indicates the last time the i-th store had no orders 
bool st[N]; // Indicates whether the i-th store is currently in the priority cache

PII order[N];

int  main ()
 {
     scanf ( "%d%d%d" ,&n,&m,&T);
     //Because the order information is a two-tuple, so use pair to read a two-tuple 
    for ( int i = 0 ; i < m; i++) scanf ( "%d %d" ,&order[i].x,&order[i].y);

    //One-step sorting: pair has its own comparison function, which is performed according to the first keyword first. If the first keyword is the same, the second keyword is considered
    sort(order,order+m);

    // enumerate each order 
    for ( int i = 0 ; i < m;)
    {
        int j = i;
         //find m orders, the same order 
        while (j < m && order[j] == order[i]) j++;
         int t = order[i].x; //get order time 
        int id = order[i].y; //get order id 
        int cnt = ji; //get quantity

        i = j; //Assign j to i, process the next batch of orders

        score[id] -= t - last[id] - 1 ; //Deduct the priority when there is no order at time t 
        if (score[id] < 0 ) score[id] = 0 ; //If the priority The deduction is negative, reset to 0 
        if (score[id] <= 3 ) st[id] = false ; // pull this store out of the priority cache

        //The above is the information before time t

        score[id] += cnt * 2;
        if(score[id] >  5) st[id] = true;

        //Update last[id]
        last[id] = t;
    }

    //Enumerate each store 
    for ( int i = 1 ; i <= n;i++)
         if (last[i] < T) //If there is no order in the last period of time, deduct the corresponding
        {
            score[i] -= T - last[i];
            if(score[i] <= 3) st[i] = false;
        }

    int res = 0 ;
     //Finally count how many stores are in the priority cache 
    for ( int i = 1 ;i <= n;i++) res += st[i];

    //output result 
    printf ( "%d\n" ,res);
     return  0 ;
}

Struggling for a day, hard…

Leave a Comment

Your email address will not be published. Required fields are marked *