"Weilai Cup" 2022 Niuke summer multi school training camp 1

Fly

G.Lexicographical Maximum

The question ：

Give me a number n（n It could be big ）, Find out 1-n The largest number in the dictionary .

Ideas ：

To maximize dictionary order , Then it must be 9 start . Consider special situations first , When there is only one digit , So it must be n.
otherwise , Set the number n The number of digits is len, So first len-1 Bit 9, Look at the numbers n Before n-1 All places are 9, Then finally add n Last digit of , It is the one with the largest dictionary order , Namely n. If not , Then output n-1 Bit 9.
because n It could be very big , So input in the form of string .

Investigate ：
Dictionary order maximum

Code ：

#include <bits/stdc++.h>
using namespace std;
int main(){
	string s;
	cin>>s;
	int len=s.size();
	if(len==1){
		cout<<s; 
		return 0;
	}
	int f=0;
	string ss="";
	for(int i=0;i<len-1;i++){
		cout<<"9";
		if(s[i]!='9') f=1;
	}
	if(f==0) cout<<s[len-1];
	return 0;
}

A.Villages: Landlines

The question ：

Give one-dimensional coordinates of a power station and multiple buildings , They all need to be connected by towers and wires , Realize the shortest wire length . At the power station / Within the radius of the building, it can be directly connected with the electric tower , The towers are connected by wires .

Ideas ：

Convert each coordinate and radius into an interval , Merge the intersecting intervals ( Sort the intervals by the left endpoint , Merge from left to right , The large intervals thus obtained must not intersect ), Finally, connect , Is the sum of the distances between each large interval . If only one interval is obtained from the final combination , Then the length of the wire used is 0.

Investigate ：
Interval merging

Notice:

because r Range bit -1e9~1e9, So the boundary is better than 2e9 Be big , I use it 3e9, And used long long. At first, the error is because only the right endpoint is considered from left to right , Instead of considering the interval , Therefore, it is easy to shorten the required distance when the back covers the front . Therefore, it is necessary to realize the merging of intervals first , Then find the distance between large intervals .

Code ：

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> PII;
vector<PII> p,q;
struct node{
	ll x,r;
}a[200005];

inline void solve(){
   ll n;
   scanf("%lld",&n);
   for(ll i=0;i<n;i++){
   	    scanf("%lld%lld",&a[i].x,&a[i].r);
   	    p.push_back({a[i].x-a[i].r,a[i].x+a[i].r});// Convert coordinates and radii into intervals 
   	    
   }
   sort(p.begin(),p.end());// Sort by left endpoint 
   
   ll st=-3e9,ed=-3e9;// Set the initial boundary 
   for(auto num:p)                   
    {
        if(ed<num.first)        // Separately segmented                     
        {
            if(ed!=-3e9) q.push_back({st,ed}) ;  // If ed<num.first  And ed!=-3e9, It shows that the intervals can no longer be merged  
            st=num.first,ed=num.second ;            // to update st and ed
        }
        
        else if(ed<num.second)  // Can merge , to update ed
            ed=num.second ;                         
    }  

    if(st!=-3e9&&ed!=-3e9) q.push_back({st,ed});// Add the last interval 
    if(q.size()==1) puts("0");// Finally, there is only one interval 
    else{// Accumulate the distance between large intervals 
    	ll ans=0;
    	ll l=q[0].second;
    	for(ll i=1;i<q.size();i++){
    		ll r=q[i].first;
    		ans+=(r-l);
    		l=q[i].second;
		}
		printf("%lld\n",ans);
	}
	
}

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);
	ll t;
	t=1;
	while(t--){
		solve();
	}
	return 0;
}

Interval consolidation template ：

 sort(p.begin(),p.end());// Sort by left endpoint 
   
   ll st=-3e9,ed=-3e9;// Set the initial boundary 
   for(auto num:p)                   
    {
        if(ed<num.first)        // Separately segmented                     
        {
            if(ed!=-3e9) q.push_back({st,ed}) ;  // If ed<num.first  And ed!=-3e9, It shows that the intervals can no longer be merged  
            st=num.first,ed=num.second ;            // to update st and ed
        }
        
        else if(ed<num.second)  // Can merge , to update ed
            ed=num.second ;                         
    }  

    if(st!=-3e9&&ed!=-3e9) q.push_back({st,ed});// Add the last interval 

D.Mocha and Railgun

The question ：
Give a circle whose center is C(0,0) Circular wall of , One point Q(x,y) and d,Q For the line segment AB Center of , The length of the segment is 2d. Find the longest length of the arc that can be mapped . Line segment AB The end point is strictly inside the circular wall .

Ideas ：
In radian system , If the central angle of the circle opposite the arc is θ, There's a formula l=Rθ.
rsinθ=L+d
θ=arcsin((L+d)/r)

Investigate ：
Plane computational geometry

Code ：

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

inline void solve(){
	double r,x,y,d;
	scanf("%lf%lf%lf%lf",&r,&x,&y,&d);
	double h=sqrt(x*x+y*y);
    printf("%.10lf\n",r*(asin((d+h)/r)-asin((h-d)/r)));
}

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);
	int t;
	scanf("%d",&t);
	while(t--){
		solve();
	}
	return 0;
}