The race portal

A. Display The Number

The question ：

Here you are. $n(2⩽n⩽10^5)$ A match , Ask the largest number you can spell .
 

Ideas ：

Because matches with other numbers have to $4$ More than , except $1$ need $2$ root ,$7$ need $3$ root , So if you spell other numbers, you might as well spell two $1$, and $3$ When you put a match together $1$ It's better to spell $7$.
So when $n$ For even when , Spell it all $1$;
When $n$ In an odd number of , Come out more $3$ Root spell $7$, All the others $1$.
 

Code ：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=1000000007;
 
int main()
{
    
    ll T;
    cin>>T;
    while(T--)
    {
    
        ll n;
        cin>>n;
        if(n%2==0)
        {
    
            for(int i=1;i<=n/2;i++)putchar('1');
            putchar('\n');
        }
        else
        {
    
            putchar('7');
            for(int i=1;i<=n/2-1;i++)putchar('1');
            putchar('\n');
        }
    }
    return 0;
}

 
 

B. Infinite Prefixes

I was B The question card is out , A little speechless , Later, I thought about it .

The question ：

Give you a length of $n(1⩽n⩽10^5)$ String of $s$, Define string $t$ yes $s$ Infinite cycle of .
Define the balance value of a prefix as $0$ Number of minus $1$ The number of , An empty string is a prefix .
Given a $x(-10^9⩽x⩽10^9)$.
Ask how many prefixes have a balanced value equal to $x$.
 

Ideas ：

Let's deal with the whole string first $s$ The equilibrium value of $p$.
Definition $s$ The length in the string is $i$ The balance value of the prefix of is $w_i$.
So what we need is the equation $kp+w_i=x$ in ,$k$ How many natural number solutions are there .
The first $p=0$ In the case of , Go through it. If it exists $w_i=x$ There are infinite , Otherwise, $0$ individual .
When $p\ne 0$ when , Got it. $k=\frac{x-w_i}{p}$.
Then traverse $i$, For each of these $w_i$, if $x-w_i$ Can be $p$ to be divisible by , And calculated $k$ For natural Numbers , Add... To the answer $1$.
Last $x=0$ when , Because empty strings need to be considered , So add $1$.
 

Code ：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=1000000007;
 
 
string s;
int main()
{
    
    int T;
    cin>>T;
    while(T--)
    {
    
        ll n,x;
        cin>>n>>x>>s;
        ll p=0;
        for(ll i=0;i<s.size();i++)
        {
    
            if(s[i]=='0')p++;
            else p--;
        }
        if(p==0)
        {
    
            ll ans=0,w=0;
            for(ll i=0;i<s.size();i++)
            {
    
                if(s[i]=='0')w++;
                else w--;
                if(w==x)ans++;
            }
            if(ans)cout<<-1<<endl;
            else cout<<0<<endl;
            continue;
        }
        ll ans=0,w=0;
        for(ll i=0;i<s.size();i++)
        {
    
            if(s[i]=='0')w++;
            else w--;
            if((x-w)%p==0&&(x-w)/p>=0)ans++;
        }
        if(x==0)ans++;
        cout<<ans<<endl;
    }
    return 0;
}

 

C. Obtain The String

The question ：

Given a string $s$ and $t$, The length range is $1e5$.
You have an empty string , You want to construct a string $t$.
Every time you operate , You can start your $s$ Select a subsequence , Add to your string .
Ask how many operations you need , You can construct a string $t$.
If it cannot be constructed, output $-1$.
 

Ideas ：

First , The situation that cannot be constructed can be judged directly , namely $s$ Does not exist in the $t$ A letter in .
Let's set a subscript to indicate $s$ Location currently found in .
Then go through $t$ Every single letter of , To be in $s$ Quickly find the letter after the current position .
Then just preprocess out $s$ At every position in the , The next position of each letter , You can find that letter quickly , Overall complexity $o(26\times n)$.
It's not easy to make it clear , See the code .
 

Code ：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=1000000007;
 
string s,t;
int dp[100005][26];
int has[26];
int main()
{
    
    int T;
    cin>>T;
    while(T--)
    {
    
        cin>>s>>t;
        for(int i=0;i<26;i++)
        {
    
            has[i]=0;
            dp[s.size()][i]=-1;
            for(int j=s.size()-1;j>=0;j--)
            {
    
                has[s[j]-'a']=1;
                if(s[j]=='a'+i)
                {
    
                    dp[j][i]=j;
                }
                else dp[j][i]=dp[j+1][i];
            }
        }
        int times=1,cur=0,ok=1;
        for(int i=0;i<t.size();i++)
        {
    
            if(has[t[i]-'a']==0)
            {
    
                ok=0;break;
            }
            cur=dp[cur][t[i]-'a'];
            if(cur==-1)
            {
    
                times++;
                cur=dp[0][t[i]-'a']+1;
            }
            else
            {
    
                cur=dp[cur][t[i]-'a']+1;
            }
        }
        if(ok==0)cout<<-1<<endl;
        else cout<<times<<endl;
    }
    return 0;
}

 
 

D. Same GCDs

The question ：

Given two numbers $a$ and $m$.$(1⩽a<m⩽10^{10})$
How many $x$ Satisfy $0⩽x<m$, And $gcd(a,m)=gcd(a+x,m)$.
 

Ideas ：

There was a loophole in the previous solution , So a new one .

So the final answer is $\frac{m}{gcd(a,m)}$ The value of Euler's function ,$\phi (\frac{m}{gcd(a,m)})$.
 

Code ：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=1000000007;
 
ll getPhi(ll n)
{
    
    ll ans=n;
    for(ll i=2;i*i<=n;i++)
    {
    
        if(n%i==0)
        {
    
            ans=ans/i*(i-1);
            while(n%i==0)n/=i;
        }
    }
    if(n>1)ans=ans/n*(n-1);
    return ans;
}
 
ll gcd(ll a,ll b)
{
    
    return b?gcd(b,a%b):a;
}
 
int main()
{
    
    ll T;
    scanf("%lld",&T);
    while(T--)
    {
    
        ll a,m;
        scanf("%lld%lld",&a,&m);
        ll w=gcd(a,m);
        ll ans=getPhi(m/w);
        printf("%lld\n",ans);
    }
    return 0;
}

 
 

E. Permutation Separation

It's a little late to think of it , Just give me a little more time .

The question ：

Given a $1$ To $n$ Permutation $p_1,p_2\dots p_n$, And the cost of moving each location $a_i$.
$(2⩽n⩽2\times 10^5,1⩽a_i⩽2\times 10^9)$
Now you are required to divide it into two non empty sets , namely $p_1{p}_2\dots p_k$ and $p_{k+1}{p}_{k+2}\dots p_n$.
Then select some elements on the left and move them to the right , Then select some elements on the right and move to the left , Finally, make any element on the right larger than any element on the left , If one side is empty, you can also .
Moving elements costs , Namely $a_i$.
Now ask how much you need at least , To meet the conditions .
 

Ideas ：

I thought about it for a long time .
First first , Our answer takes a minimum value on the far left and right .
First , Now that you spend money to move , Then it doesn't matter , So instead, delete , The effect is the same .
Then we have to decide on a plan , There are two things to enumerate .
One is the boundary of segmentation , That is, the set boundary of the partition .
One is the divided number , That is, the maximum number on the left and the minimum number on the right have a boundary . let me put it another way , Anything larger than this on the left should be deleted , Anything smaller than this on the right should be deleted .
 
Obviously, the complexity of violent enumeration of these two is not enough , So let's consider enumerating one of them , Then quickly solve another .
Then you will find that the other one does not satisfy the dichotomy property .
Until I drew this picture on the draft book .

This picture actually gives a good solution to calculate the answer .
The numbers in the upper row represent the numbers divided into the set on the left .
A row of numbers divided on the right represents the set below .
Then we're going to enumerate $1$ To $2$ The gap between ,$3$ To $4$ The gap between …… Calculate the smallest answer . And the calculation for each void is , The sum of the number in the upper row on the right of the gap plus the sum of the number in the lower row on the left of the gap .
Then for all the voids , We require a minimum .
So we need to use segment tree to maintain these gaps , And the update is also carried out in the interval .
 
Let's see how to update .
At first, the left set was only $1$ Elements , On the right is $n-1$ Elements .
Then we consider moving an element from the right to the left .
such as $3$ Moved from the right set to the left set . We found that $3$ When gathering on the right , The gap on the left will be added $a_3$, Now I've taken it from the right collection , So let him lose . And after moving to the left , Just give it to $3$ Add... To the gap on the right $a_3$.
 
thus , Is a segment tree interval update , The template question of the most valuable query .
 

Code ：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod = 1e9+7;
 
ll tree[800005],laz[800005];
 
void push_down(ll k,ll l,ll r)
{
    
    if(l==r)
    {
    
        tree[k]=tree[k]+laz[k];
        laz[k]=0;
        return ;
    }
    laz[2*k+1]=laz[2*k+1]+laz[k];
    laz[2*k+2]=laz[2*k+2]+laz[k];
    tree[k]=tree[k]+laz[k];
    laz[k]=0;
}
 
void update(ll k,ll l,ll r,ll x,ll y,ll a)
{
    
    push_down(k,l,r);
    if(x<=l&&r<=y)
    {
    
        laz[k]=laz[k]+a;
        return ;
    }
    ll mid=(l+r)/2;
    if(x<=mid)update(2*k+1,l,mid,x,y,a);
    if(y>=mid+1)update(2*k+2,mid+1,r,x,y,a);
    push_down(2*k+1,l,mid);
    push_down(2*k+2,mid+1,r);
    tree[k]=min(tree[2*k+1],tree[2*k+2]);
}
 
ll query(ll k,ll l,ll r,ll x,ll y)
{
    
    push_down(k,l,r);
    if(x<=l&&r<=y)
    {
    
        return tree[k];
    }
    ll ans=1e18,mid=(l+r)/2;
    if(x<=mid)ans=min(ans,query(2*k+1,l,mid,x,y));
    if(y>=mid+1)ans=min(ans,query(2*k+2,mid+1,r,x,y));
    return ans;
}
ll p[200005];
ll a[200005];
int main()
{
    
    ll n;
    scanf("%lld",&n);
    for(ll i=1;i<=n;i++)scanf("%lld",&p[i]);
    for(ll i=1;i<=n;i++)scanf("%lld",&a[i]);
    ll ans=min(a[1],a[n]);
    if(p[1]!=1)update(0,1,n-1,1,p[1]-1,a[1]);
    for(ll i=2;i<=n;i++)if(p[i]!=n)update(0,1,n-1,p[i],n-1,a[i]);
    ans=min(ans,query(0,1,n-1,1,n-1));
    for(ll i=2;i<=n-1;i++)
    {
    
        if(p[i]!=n)update(0,1,n-1,p[i],n-1,-a[i]);
        if(p[i]!=1)update(0,1,n-1,1,p[i]-1,a[i]);
        ans=min(ans,query(0,1,n-1,1,n-1));
    }
    printf("%lld\n",ans);
    return 0;
}

 
 

F. Good Contest

I didn't even look .