Niuke IOI weekly 27 popularity group

Cattle guest IOI Weekly game 27- Popularization group

A topic （ Small H My kitten ）

（ source ：nowcoder_ Cattle guest IOI Weekly game 27- Popularization group _A topic ）

Topic link ：https://ac.nowcoder.com/acm/contest/19151/A

Title Description

Small H There is a kitten , This kitten is at the origin (0,0) The location of . We will x Axis and y The positive half axis of the axis is regarded as two walls , origin (0,0) The position of is regarded as a corner . Now? , In the first quadrant 、x Axis and y There is n A stake , These stakes are seen as dots of no size , Small H These wooden stakes can be connected by a fence .

Please find out the small H Can you fence the kitten around the corner . If possible , Please output small H The shortest total length of fence needed to surround the kitten , And keep the answer after the decimal point 10 position , Otherwise output “Poor Little H!”.

The definition surrounding the corner ： That is, these fences and coordinate axes form a polygon .

Topic analysis

With x Axis and y Axis is wall , The origin is the corner , The kitten is in the corner , Give several points , Ask if you can surround the kitten in the corner with a fence , Find the shortest total length of the fence .

Their thinking

Build a structure , Store coordinates inside x,y And the distance from the coordinate to the origin （ It's easy to find the shortest coordinate point later ）, Create a sort function customized by the structure cmp（ Sort according to the distance from the origin from small to large ）, After arranging the order, traverse to find x by 0 Subscript sum of y by 0 The subscript . The distance between the coordinates corresponding to the two subscripts is the shortest distance （ The shortest line between two points ）.

Code implementation

#include<bits/stdc++.h>
using namespace std;
int n,m,l,k,c1=-1,c2=-1;
double ans;
struct zuobiao{
    
    double x,y,len;
}a[10000010];
bool cmp(zuobiao a,zuobiao b){
    
    return a.len<b.len;
}
int main(){
    
    cin>>n;
    for(int i=0;i<n;i++){
    
        scanf("%lf%lf",&a[i].x,&a[i].y);       
        a[i].len=sqrt(a[i].x*a[i].x+a[i].y*a[i].y);
    }
    sort(a,a+n,cmp);
    for(int i=0;i<n;i++){
    
        if(a[i].x==0&&c1==-1)c1=i;
        if(a[i].y==0&&c2==-1)c2=i;
        if(c1!=-1&&c2!=-1) break;
    }
    if(c1!=-1&&c2!=-1){
    
        ans+=sqrt((a[c2].x-a[c1].x)*(a[c2].x-a[c1].x)+(a[c2].y-a[c1].y)*(a[c2].y-a[c1].y));
        printf("%.10lf\n",ans);
    }else{
    
        cout<<"Poor Little H!"<<endl;
    }
    return 0;
}

B topic （ Small H Sequence of numbers ）

（ source ：nowcoder_ Cattle guest IOI Weekly game 27- Popularization group _B topic ）

Topic link ：https://ac.nowcoder.com/acm/contest/19151/B

Title Description

Small H There is a sequence , This sequence satisfies $a_1=1,4a_{i-1}{a}_i=(a_{i-1}+a_i-1{)}^2,a_{i-1}<a_i(i\ge 2)$. And ensure that none of them is 0. Now here you are n, Please find out $a_n$ Value .

Topic analysis

Find the sequence of equal ratio n term

Their thinking

First, the given formula is transformed into the form of standard proportional sequence ：
Push to formula ：

From the recurrence formula :
${a_{n+1}}^2-2(a_n+1)a_{n+1}+(a_n-1{)}^2=0（1）$

use $n-1$ Instead of $n+1$, have to
${a_{n-1}}^2-2(a_n+1)a_{n-1}+(a_n-1{)}^2=0（2）$

from （1）（2） know $a_{n+1}and{a}_{n-1}$ It's the equation $x^2-2(a_n+1)x+(a_n-1{)}^2=0$ Two of them .

From Weida theorem ：
$a_{n+1}+a_{n-1}=2a_n+2（3）$

from （3） Formula ：
$a_{n+1}-a_n=a_n-a_{n-1}+2$

therefore { $a_{n+1}-a_n$} The general term of can be obtained by cumulative addition , namely $a_{n+1}-a_n=2n+1$

In addition by superposition , have to $a_n=n^2$

Big data , A high-precision template that multiplies two numbers .

Code implementation

#include<bits/stdc++.h>
using namespace std;
vector<int>ma,mb;
int n;
string s1,s2;
vector<int> hqa(const vector<int>&a,const vector<int>&b){
    
    vector<int>mc(a.size()+b.size(),0);
    for(int i=0;i<a.size();i++) for(int j=0;j<b.size();j++) mc[i+j]+=a[i]*b[j];
    for(int i=0;i<mc.size();i++) n+=mc[i],mc[i]=n%10,n/=10;
    while(mc.size()>1&&mc.back()==0) mc.pop_back();
    return mc;
}
int main()
{
       
    cin>>s1;s2=s1;
    for(int i=s1.size()-1;i>=0;i--) ma.push_back(s1[i]-'0');
    for(int i=s2.size()-1;i>=0;i--) mb.push_back(s2[i]-'0');
    auto mc=hqa(ma,mb);
    for(int i=mc.size()-1;i>=0;i--)cout<<mc[i];
    return 0;
}

C topic （ Small H Of candy ）

（ source ：nowcoder_ Cattle guest IOI Weekly game 27- Popularization group _C topic ）

Topic link ：https://ac.nowcoder.com/acm/contest/19151/C

Title Description

Small H Birthday day , Someone gave it to Xiao H 1 Candy . Small H I think I have too little candy , So he learned two kinds of magic ：
Count the sweets +1.
Let every candy split into k Candy , Multiply the total number of sweets by k
Small H Want to know , How many times does he need to use magic at least to make the number of sweets just equal to small H The lucky number of n.

Topic analysis

Given n, Two kinds of operations , operation 1：n Divide k（ If you can divide ）, operation 2： subtract 1, Please make n Turn into 1 The minimum number of operands .

Their thinking

1. The first n Become able to be k Divisible number （ By manipulating the 2）
2. Regrouping k, Simulation is enough

Code implementation

#include<bits/stdc++.h>
using namespace std;
long long n,k,s,t;
int main(){
    
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    cin>>t;
    for(long long i=0;i<t;i++){
    
        cin>>k>>n;s=0;
        if(k==1){
    cout<<n-1<<"\n";continue;}
        while(n>=k)s+=n%k,s++,n/=k;
        cout<<s+n-1<<"\n";
    }
    return 0;
}

D topic （ tourism ）

（ source ：nowcoder_ Cattle guest IOI Weekly game 27- Popularization group _D topic ）

Topic link ：https://ac.nowcoder.com/acm/contest/19151/D

Title Description

A holiday , Small L Plan your holiday arrangements happily .

She decided to go n Play in scenic spots . And these tourist attractions have reached cooperation , There will be a fixed price direct bus between two scenic spots （ There will be no parking in other scenic spots ）. therefore , Small L Decide to take the direct bus to and from various tourist attractions during the tourism , And she hopes to spend the least every time she goes to another scenic spot .
As we are now in the epidemic period , Every scenic spot should be disinfected according to regulations . Because small L Very afraid of infection , So she decided , Only take the bus that has been disinfected at least once at the starting point and destination .

Topic analysis

Given a picture , Only when the starting point and the ending point meet the conditions, can the edge be connected , Given multiple inquiries , Find the shortest path

Their thinking

Because the points passed must be disinfected , That is, we can consider only the disinfected points , To maintain the shortest circuit , Then judge whether the end point is disinfected and whether it can be reached .

Code implementation

#include<bits/stdc++.h>
using namespace std;
int dis[310][310],xd[310];//dis Store weights in the array ,xd Which nodes stored in the array are put into 
int n,m,s,q,f,x,c,a,b;
void floyd(int x){
    
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            dis[i][j]=min(dis[i][j],dis[i][x]+dis[x][j]); // Update the weight of the array to minimize 
}
int main(){
    
    memset(dis,0x3f,sizeof(dis));f=dis[1][1];// Set the number in the two-dimensional array to the maximum , It is convenient to use the minimum replacement later 
    cin>>n>>m>>s>>q;
    for(int i=1;i<=n;i++)dis[i][i]=0;xd[s]=1;
    for(int i=1;i<=m;i++){
    
        cin>>a>>b>>c;
        dis[a][b]=min(dis[a][b],c);
    }
    floyd(s);
    while(q--){
    
        cin>>c>>x;
        if(c==1){
    
            if(!xd[x])floyd(x);
            xd[x]=1;
        }else{
    
            if(xd[x]==0||dis[s][x]==f){
    cout<<-1<<endl;continue;}
            else {
    cout<<dis[s][x]<<endl;s=x;}
        }
    }
    return 0;
}