The race portal

A. Deadline

The question ：

To give you one n and d (1≤n≤10⁹, 1≤d≤10⁹) , Ask if there are natural numbers x, bring $x+\lceil \frac{d}{x+1}\rceil ⩽n$. There is output YES, No output present NO.

Answer key ：

Save time in pushing formulas , Just wrote a o($\sqrt{n}$) The violence of , from 0 To $\sqrt{d}$ enumeration x, Then judge whether the formula is true .
 
 

B. Yet Another Meme Problem：

The question ：

Yes t(1≤t≤100) Group example , Each set of examples gives two integers A and B (1≤A,B≤10⁹), Ask how many pairs there are (a,b) Satisfy 1≤a≤A,1≤b≤B, And ab+a+b=conc(a,b). among conc(a,b) Character concatenation for numbers , Such as conc(12,23)=1223.

Answer key :

set up b The number of digits of is w, Then there are ab+a+b=a⋅10^w+b. Put it in order a⋅(10^w-b-1)=0. because a>0, obtain b=10^w-1, namely 9,99,999…… I won't say the rest .
 
 

C. Two Arrays

The question ：

Given n and m (1≤n≤1000, 1≤m≤10). Ask how many pairs of arrays there are a and b Satisfy ：
1. Array a and b The length is m.
2.a and b All of the elements are 1 To n The integer of .
3. about i from 1 To m every , Yes ai ≤ bi establish .
4. Array a Is a non decreasing group .
5. Array b Is a non incrementing array .
Answer model 1e9+7.

Answer key ：

Easy to find , As long as the last bit of the two arrays satisfies the condition 3, According to the condition 4 and 5, Conditions can be obtained 3 It must be true . So , We enumerate the last bit of two arrays in a two-layer loop , At this point, we also need to know , In order to meet the conditions 2,3,4, And the last one is given , As much as there is left , It can be used dp Array preprocessing ,dp[i][j] The length is i Array of , The rising space is j How many cases are there in the array of . Just ok 了 . The code is as follows （m by 1 The special judgment is purely because it can't be found ）：

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=1e9+7;
 
ll dp[15][1005];
 
int main()
{
    
    ll n,m;
    scanf("%lld%lld",&n,&m);
    for(int i=1;i<=n;i++)dp[1][i]=i;
    for(int i=2;i<=10;i++)
    {
    
        for(int j=1;j<=1000;j++)
        {
    
            for(int k=1;k<=j;k++)
            {
    
                dp[i][j]=(dp[i][j]+dp[i-1][k])%mod;
            }
        }
    }
    ll ans=0;
    if(m!=1)
    {
    
        for(int b=1;b<=n;b++)
        {
    
            for(int a=1;a<=b;a++)
            {
    
                ans=(ans+dp[m-1][a]*dp[m-1][n-b+1])%mod;
            }
        }
    }
    else
    {
    
        ans=n*(n+1)/2%mod;
    }
    printf("%lld\n",ans);
    return 0;
}

 
 

D. Minimax Problem

The question was hack 了 , Very angry , I won't post the code . But the idea should be ok .

The question ：

Given n An array , The length of each array is m.(1≤n≤3⋅10⁵, 1≤m≤8)
Select two of the arrays ai and aj（ It can be the same ）, Define an array b by
One of these two arrays is required , bring

Output the subscript of the selected array .

Answer key ：

First think of the maximum value of the minimum value of dichotomy , Then think about how check.
If there are two arrays , Make the maximum value on each bit greater than the current binary value , be check success .
If you enumerate two arrays , practice o(n²) Obviously not .
m Only 8, Consider converting to binary .
check Current binary value p The idea of ： Convert each array into binary numbers , The transformation mode is , If the number of current bits is greater than or equal to p, Then the bit under binary is 1, Otherwise 0. Then you will find that when there are two numbers or the value is 2^m-1, be check success . and m Only 8, Possible binary values, but 256. So you can use a length of 256 The array of records whether this number appears , Then, the two-level cycle of violence determines whether there are two numbers that meet the conditions .
 
 

E. Messenger Simulator

The question ：

This is a question with a better understanding of the background than the modeled meaning . Is that there is... In the message list n Personal news , Number from 1 To n, The order from top to bottom in the list is also 1 To n An arrangement of .
When someone sends you a message , His position in the list will jump to the first , And the people in front of him will move back one space .
From top to bottom in the initial list is 1 To n.
Now I'll give you a n and m (1≤n,m≤3⋅10⁵) Express n personal , After the initial situation, we received m Bar message .
Next m Number , Indicates who received the message .
Ask to output everyone's message at the top and bottom of the list .
Examples ：

Answer key :

First , It's easy to handle the most forward position . When this person sent a message , Then his top position is 1, Otherwise, it's his initial position .
Now think about the back most position . When a person appears , His position became first , Before he becomes number one next time , During this period , His ranking will fall back The number of people who have sent messages A place .
such as ：1 3 2 2 1,1 After becoming number one , Two positions fell back .
So what we're looking for is , about a Come on , Two a The number of species separated from each other .
Dealing with border situations , It's amazing to add... At the beginning 1 To n The reverse order of indicates the initialization . If the example becomes 5 4 3 2 1 3 5 1 4
It will be easier to handle . And like 2 This only occurs in the initial state , Then the number from its record to the end .
So the problem becomes ,n Intervals , Ask the number of types of interval numbers .
Used Mo team o(n$\sqrt{n}$) After that .
The code is as follows ：

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=1e9+7;
int ans1[300005];
int ans2[300005];
int a[600005];
vector<int>v[300005];
 
typedef struct
{
    
    int l,r,id,B;
}Query;
 
Query Q[1000005];
 
bool cmp(Query a,Query b)
{
    
    if(a.B==b.B)return a.r<b.r;
    else return a.B<b.B;
}
 
int mp[300005];
int main()
{
    
    int n,m;
    scanf("%d%d",&n,&m);
    int N=n+m;
    int B=sqrt(N);
    for(int i=1;i<=n;i++)a[i]=n-i+1,ans1[i]=i;
    for(int i=n+1;i<=n+m;i++)scanf("%d",&a[i]),ans1[a[i]]=1;
    for(int i=1;i<=N;i++)v[a[i]].push_back(i);
    int qn=0;
    for(int i=1;i<=n;i++)
    {
    
        for(int j=0;j<v[i].size();j++)
        {
    
            if(j==v[i].size()-1)Q[qn++]=Query{
    v[i][j],N,i,(v[i][j]-1)/B+1};
            else Q[qn++]=Query{
    v[i][j],v[i][j+1],i,(v[i][j]-1)/B+1};
        }
    }
    sort(Q,Q+qn,cmp);
    int l=1,r=1,ans=1;
    mp[a[1]]=1;
    for(int i=0;i<qn;i++)
    {
    
        while(r<Q[i].r){
    r++;mp[a[r]]++;if(mp[a[r]]==1)ans++;}
        while(l>Q[i].l){
    l--;mp[a[l]]++;if(mp[a[l]]==1)ans++;}
        while(r>Q[i].r){
    mp[a[r]]--;if(mp[a[r]]==0)ans--;r--;}
        while(l<Q[i].l){
    mp[a[l]]--;if(mp[a[l]]==0)ans--;l++;}
        ans2[Q[i].id]=max(ans2[Q[i].id],ans);
    }
    for(int i=1;i<=n;i++)printf("%d %d\n",ans1[i],ans2[i]);
    return 0;
}

F. Red-Blue Graph

There's no time , Can't .