Welcome the winter vacation multi school league game 2 partial solution (B, C, D, F, G, H)

Topic link ：https://ac.nowcoder.com/acm/contest/27740#question

B character string

Title Description

Definition A continuous number forms a string For a good string .
example ：1～7 The good string is 1234567 The length of this good string is 7.
Now let's find a way from 1～2022 The length of a good string of consecutive numbers .

Ideas

Directly traverse all numbers , Returns the sum of the lengths

Code

#include<cstdio>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#include<cmath>
#include<cstring>
#define ll long long
using namespace std;
ll solve(ll x){
    
    ll sum=0;
    while(x){
    
        x/=10;
        sum++;
    }
    return sum;
}
ll sum=0;
int main()
{
    
    /*for(int i=1;i<=2022;i++){ sum+=solve(i); }*/
    cout<<"6981";
    return 0;
}

C Approximate sum count

Title Description

Give you a positive integer nn. And give you a function F(n)F(n), The value of this function is nn All the factors of （ Not including himself ） Sum of . Now you are studying a problem to put nn Turn into 1, How many iterations are needed FF function .
When n=12 His iterative process is
12 -> 1 + 2 + 3 + 4 + 6 = 16
16 -> 1 + 2 + 4 + 8 = 15
15 -> 1 + 3 + 5 = 9
9-> 1 + 3 = 4
4-> 1 + 2 = 3
3-> 1 = 1

All his iterations are 6 Time
Please output when n=720n=720 Iterations of

Ideas

Direct violence seeks the sum of factors , Then output the result

Code

#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
const int maxn = 1e5+10;
ll n=720;
ll solve(ll x){
    
    ll sum=1;
    for(ll i=2;i*i<=x;i++){
    
        if(x%i==0&&(i*i!=x)){
    
            //cout<<i<<" "<<x/i<<endl;
            sum+=i;
            sum+=x/i;
        }else if(x%i==0){
    
            sum+=i;
        }
        //
    }
    return sum;
}
int main(){
    
    /*ll f=0; //cout<<n<<endl; while(1){ ll t=solve(n); n = t; f++; cout<<n<<" "<<f<<endl; if(n==1){ break; } }*/
    cout<<194;
    return 0;
}

D Array splitting

Title Description

Xiaosha started with an array , There is only one number in the array , Now Xiao Sha wants to do several operations . Each time he operates, he can select one of the array that is not 1 The number of xx, Split him into x/2,x-x/2 or x-x/2,x/2 Two cases , Now Xiao Sha asks you , When you can split several times , How many cases does this array have .
When the first number is 5 When , The whole array has 13 In this case , Now please answer when the first number is 1152921504606846976 when , How many situations . Because the answer is too big , You need to get the answer right 1e9+7 modulus .

remarks :

about 5 The split is as follows ：
1 1 1 1 1
1 1 1 2
1 1 2 1
1 1 3
1 2 1 1
1 2 2
2 1 1 1
2 1 2
2 2 1
2 3
3 1 1
3 2
5

Ideas

Through analysis , It will be split into two numbers each time , Finally, it is divided into 1. Divide the two numbers and multiply the number of the final respective schemes （ When writing, write it as adding, but it doesn't get the result ） Add 1（ Its own ）

Code

#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
const ll mod = 1e9+7;
ll f1=1,f2=1;
ll f3 = 0;
ll n = 1152921504606846976;
map<ll,ll> mp;
ll dfs(ll x){
    
    //cout<<x<<endl;
    if(x==1){
    
        return 1;
    }
    if(mp[x])return mp[x];
    return mp[x]=(dfs(x/2)*dfs(x-x/2)%mod+1)%mod;
}
int main(){
    
    cout<<dfs(n)<<endl;
    return 0;
}

F Complement code

Title Description

You are a supercomputer , You are very suitable for calculating the complement of a number , Now let me give you some numbers , Please output 32 Digit number 01 The number string represents his complement .
Positive numbers ：
The complement of a positive integer is its binary representation , Same as the original
negative ：
Find the complement of a negative integer , Reverse all the bits of the original code except the sign bit （0 change 1,1 change 0, Symbol bit 1 unchanged ） After add 1

Input description :

Enter a number on each line T
And then T A number in each line represents a given number

Output description :

Total output T Each line has a length of 32 A string of numbers .

Ideas

Direct simulation 32 Binary system

Code

#include<cstdio>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#include<cmath>
#include<cstring>
#define ll long long
using namespace std;
ll t,n;
char s[100];
int main()
{
    
    cin>>t;

    while(t--){
    
        memset(s,'0',sizeof(s));
        cin>>n;
        ll f=0;
        if(n<0){
    
            f = 1;
        }
        n = abs(n);
        ll k=32;
        for(int i=1;i<=32;i++){
    
            ll q=n%2;
            s[k]=q+'0';
            n>>=1;
            k--;
        }
        if(f==1){
    
            for(int i=1;i<=32;i++){
    
                if(s[i]=='0'){
    
                    s[i] = '1';
                }else{
    
                    s[i] = '0';
                }
                //cout<<s[i]<<" ";
            }
            //cout<<endl;
            ll pos=1;
            for(int i=32;i>=1;i--){
    
                if(s[i]=='1'&&pos){
    
                    s[i]='0';
                    pos=1;
                }else if(s[i]=='0'&&pos){
    
                    s[i]='1';
                    pos = 0;
                }
            }
        }
        for(int i=1;i<=32;i++){
    
            cout<<s[i];
        }
        cout<<endl;
    }
    return 0;
}

G The pain of Xiao Sha

Title Description

Xiao Sha encountered a very painful thing when he set a question , If he gives too much cancer , Then this topic will be hit back , If it's too simple , Then Xiao Sha will feel very guilty .
Xiao Sha is constantly increasing the difficulty of the problem , repulse , Reduce the difficulty of the topic , It broke out in the process of fighting back , He found the difficulty of the topic too difficult to control , So he came up with such a simple problem .
Given you nn Number , You can choose to add any two numbers , Add them together and then pp The residual value is the largest .（ Note that the value after remainder is the largest , Not before residual ）.
Now Xiao Sha wants to ask you , What is the maximum value .

Input description :

Enter two integers on the first line n,p, Represents the number and modulus of a given number
Second line input n It's an integer

Output description ：

Output a number , For the maximum .

Example

 Input 
5 7
3 3 4 4 5
 Output 
6

Ideas

First of all, this topic is to take the remainder of all the numbers , And then sort it , Convenient dichotomy . Then traverse all the numbers , Suppose that the current number of traversals is x, So if there is p-x-1, The result is p-1, Because it is the sum of two numbers to get the remainder , So there can be no other situation bigger than this , And if there is no such case, it must take a smaller value z Instead of p-x-1,（ Because when y>z when , The result is (x+y-p)=(y-(p-x)), To be greater than the above （y-(p-x)）>(x+z), namely y>（p+z+1）, It's obviously impossible ）. Another special case is that each number has no corresponding z, Of course, the result is to add the last two numbers

Code

#include<cstdio>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#include<cmath>
#include<cstring>
#include<map>
#define ll long long
using namespace std;
const ll maxn=1e6+10;
ll n,m;
ll a[maxn];
map<ll,ll> mp;
ll cnt=0;
ll b[maxn];
int main()
{
    
    scanf("%lld%lld",&n,&m);
    for(int i=0;i<n;i++){
    
        scanf("%lld",&a[i]);
        a[i] %= m;
    }
    sort(a,a+n);
    ll ma = (a[n-2]+a[n-1])%m;
    for(int i=0;i<n-1;i++){
    
        ll pos = lower_bound(a+i,a+n,m-a[i]) - a;
        //cout<<pos<<endl;
        if(pos>(i+1)){
    
            ma = max((a[pos-1]+a[i])%m,ma);
        }
    }
    cout<<ma;
    return 0;
}

H The supermarket

Topic link ： Portal

Topic ideas

It's actually an interval problem , But the interval will not be maintained . Refer to others' code , The general idea is , The discount days are l To r, stay l Time to join , stay r When it pops up , Maintenance minimum . The two methods , One is priority queue , One is the line segment tree

Code

Priority queue

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const ll maxn=1e6+10;
struct node{
    
    int val,id,ed;
    bool operator<(const node &rh)const{
    
        return val>rh.val||(val==rh.val&&id>rh.id);
    }
};
priority_queue<node> que;
vector<node>  g[maxn];
int a[maxn];
int n,m,q;
int get(ll x,ll y){
    
    if(y<10)y*=10;
    return x*y/100;
}
int main()
{
    
    cin>>n>>m>>q;
    for(int i=1;i<=n;i++){
    
        cin>>a[i];
        que.push(node{
    a[i],i,m});
    }
    for(int i=1;i<=q;i++){
    
        int x,y,l,r;
        cin>>x>>y>>l>>r;
        int t=get(a[x],y);
        g[l].push_back({
    t,x,r});
    }
    for(int i=1;i<=m;i++){
    
        for(int j=0;j<g[i].size();j++){
    
            que.push(g[i][j]);
        }
        while(!que.empty()&&que.top().ed<i)que.pop();
        cout<<que.top().id<<" ";
    }
    return 0;
}

Line segment tree

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const ll maxn=1e6+10;
const ll INF=1e9;
struct node{
    
    int x,y,d;
    bool operator<(const node &rh)const{
    
        if(d==rh.d){
    
            return y>rh.y;
        }
        return d<rh.d;
    }
}queues[maxn];
struct Node{
    
    ll l,r,v;
}tr[maxn<<2];
vector<node>  g[maxn];
int a[maxn];
int n,m,q;
int get(ll x,ll y){
    
    if(y<10)y*=10;
    return x*y/100;
}
void pushup(ll root){
    
    tr[root].v = min(tr[root*2].v,tr[root*2+1].v);
}
void build(ll root,ll l,ll r){
    
    tr[root] = {
    l,r,INF};
    if(l==r){
    
        tr[root].v=a[l];
        return ;
    }
    ll mid = (l+r)/2;
    build(root*2,l,mid);
    build(root*2+1,mid+1,r);
    pushup(root);
    return ;
}
void update(ll root,ll pos,ll y){
    
    if(tr[root].l==tr[root].r){
    
        tr[root].v=y;
        return ;
    }
    ll mid =(tr[root].l+tr[root].r)/2;
    if(pos<=mid)update(root*2,pos,y);
    else{
    
        update(root*2+1,pos,y);
    }
    pushup(root);
    return ;
}
ll query(ll root){
    
    if(tr[root].l==tr[root].r){
    
        return tr[root].l;
    }
    else if(tr[root*2].v==tr[root].v){
    
        return query(root*2);
    }else{
    
        return query(root*2+1);
    }
}
int main()
{
    
    cin>>n>>m>>q;
    for(int i=1;i<=n;i++){
    
        cin>>a[i];
    }
    build(1,1,n);
    ll idx=0;
    for(int i=1;i<=q;i++){
    
        int x,y,l,r;
        cin>>x>>y>>l>>r;
        int t=get(a[x],y);
        queues[++idx]={
    x,t,l};
        queues[++idx]={
    x,a[x],r+1};
    }
    sort(queues+1,queues+1+idx);
    for(int i=1,j=1;i<=m;i++){
    
        while(j<=idx&&queues[j].d==i){
    
            update(1,queues[j].x,queues[j].y);
            j++;
        }
        ll sum = query(1);
        cout<<sum<<" ";
    }
    return 0;
}