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

For the first time, the weak team of the second year of quasi University played against the big guys ：

Standard solution of the author pdf

G. Lexicographical Maximum（ Sign in ）

Give me a number , find 1 To the number in which all numbers are listed in the largest order .

Ideas ： Pay attention to the number range , So it can only be represented by string , The largest dictionary order must be in the front 9 The one with the most , such as 1034 Words , Output 999. But notice , if 9998, The answer should be 9998, instead of 999.

AC Code：

#include <bits/stdc++.h>

const int N=1e5+5;
std::string s;

int main(){
	std::ios::sync_with_stdio(false);
	std::cin.tie(0);
	std::cout.tie(0);
	std::cin>>s;
	int len=s.length();
	if(len==1){
		std::cout<<s<<'\n';
		return 0;
	}
	bool flag=true;
	int pos=0;
	for(int i=0;i<len;i++){
		if(s[i]!='9'){
			flag=false;
			break;
		}
		pos++;
	}
	if(flag){
		std::cout<<s<<'\n';
		return 0;
	}
	if(pos==len-1){
		std::cout<<s<<'\n';
		return 0;
	}
	for(int i=0;i<len-1;i++){
		std::cout<<9;
	}
	std::cout<<'\n';
	return 0;
}

os： Sign in , Also because of this special situation WA A hair , The dish is fried .

A. Villages: Landlines（ thinking ）

Give the coordinates of a power station , Then give the coordinates of the building , Only transfer stations within the radius of power stations and buildings can receive signals , We are now going to build several transit stations at certain locations , Transfer electricity from the power station to the building , And power stations need to be connected by wires , Ask the shortest length of wire to be connected .

Ideas ： Because all coordinates are one-dimensional , You can draw a picture , We found that , The best solution is to build a transfer station at the radius of a certain point , Only in this way can the wires required for connection be shortest . And finally, the wires needed for connecting the transfer station , Is the distance between radius without intersection , As shown in the figure below, the length of the red line segment ：

You can sort each point according to its left boundary and right boundary , Scan once to find out the length of the red area .

AC Code： 

#include <bits/stdc++.h>

typedef long long ll;
const int N=2e5+5;
ll n,X,R,x,r;

struct node{
	ll l,r;
} e[N];

bool cmp(node a,node b){
	if(a.l<b.l) return true;
	else if(a.l==b.l&&a.r<b.r) return true;
	else return false;
}

int main(){
	std::ios::sync_with_stdio(false);
	std::cin.tie(0);
	std::cout.tie(0);
	std::cin>>n;
	std::cin>>X>>R;
	for(int i=1;i<n;i++){
		std::cin>>x>>r;
		e[i].l=x-r;
		e[i].r=x+r;
	}
	e[n].l=X-R,e[n].r=X+R;
	std::sort(e+1,e+1+n,cmp);
	ll le=e[1].r;
	ll ans=0;
	for(int i=2;i<=n;i++){
		if(e[i].l<=le){
			if(e[i].r>le)  le=e[i].r;
		}
		else ans+=e[i].l-le,le=e[i].r;
	}
	std::cout<<ans<<'\n';
	return 0;
}

D. Mocha and Railgun（ Computational geometry ）

Give the radius of a circle , And a little inside the circle Q,AB In order to Q For the center of a circle ,r Is the diameter of the radius , But this diameter direction is arbitrary , Ask the diameter projected on the circle AB What is the longest arc on .

Ideas ： Here's the picture ：

During the game, our team guessed directly .

AC Code：

#include <bits/stdc++.h>

int t;
double R,x,y,r;

int main(){
	scanf("%d",&t);
	while(t--){
		scanf("%lf%lf%lf%lf",&R,&x,&y,&r);
		double CA=sqrt(x*x+y*y)-r;
		double C=acos(CA/R);
		double ca=C*R;
		double CB=sqrt(x*x+y*y)+r;
		double CC=acos(CB/R);
		double cb=CC*R;
		printf("%.12lf\n",ca-cb);
	}
	return 0;
}

  I. Chiitoitsu（ expect DP）

  Give these cards , Each card has 4 Zhang , Now give the original 13 card , You can touch a card from the pile , Choose one from your hand and throw it away , Ask the expected number of rounds of seven pairs under the optimal strategy .

Ideas ：（1） The standard range is used DP Expect . Obviously , The best strategy is to touch a card and form a pair with the single card in your hand , Throw away a single card , If it doesn't form a pair , Then throw away the card you touched . Make f[s][r] For the current hand s A single card and remaining in the stack r The expected number of rounds to achieve seven pairs of cards , The transfer equation is ：

  My understanding is that ：s==1 when , Expect two things , Take any one of the three matching cards , All games are successful , Number of rounds +1; The probability of other cases is (r-3)/r, Multiply by having 1 The expected number of rounds of a single card and taking any card from the stack .s!=1 when , The probability multiplication result of the two cases , Plus this round . Because there are few cases , Directly preprocess all possible situations f Array , Count the number of cards placed each time , Pay attention to the inverse element , Here we use Fermat's theorem to find the inverse element .

（2） Because the number of cases is very small , You can print the meter directly , Specific view Big guy's blog

AC Code：

#include <bits/stdc++.h>

typedef long long ll;
const int N=200;
const int mod=1e9+7;
int t;
std::string s;
int mp[255],p[10][4];
ll inv[N],f[15][N];

ll pmod(ll a,ll b){
    ll res=1;
    while(b){
        if(b&1) res=res*a%mod;
        b>>=1;
        a=a*a%mod;
    }
    return res;
}

int main(){
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    std::cout.tie(0);
    int n=136-13;
    mp['m']=0,mp['p']=1,mp['s']=2,mp['z']=3;
    for(int i=1;i<=n;i++){
        inv[i]=pmod(i,mod-2);
        for(int j=1;j<=13;j++){
            f[j][i]=(1+f[std::max(0,j-2)][i-1]*(3*j)%mod*inv[i]
                    +f[j][i-1]*(i-3*j)%mod*inv[i])%mod;
        }
    }
    std::cin>>t;
    int tot=0;
    while(t--){
        std::cin>>s;
        memset(p,0,sizeof(p));
        int cnt=0;
        for(int i=0;i<26;i+=2){
            p[s[i]-'0'][mp[s[i+1]]]++;
        }
        for(int i=1;i<=9;i++){
            for(int j=0;j<4;j++){
                if(p[i][j]==1) cnt++;
            }
        }
        std::cout<<"Case #"<<++tot<<": "<<f[cnt][n]<<'\n';
    }
    return 0;
}

J. Serval and Essay（ Trees , Conclusion , Union checking set ）

  give n A little bit ,m Edge free edge free self ring digraph , Initially, you can choose a spot dyed black , For one point , If all the edges of this point are black , This dot will also turn black , How to maximize the number of black dots .

Ideas ： Write after you understand , The nature of trees is too bad QWQ

C. Grab the Seat!（ Computational geometry ）

Give the coordinates of the screen , And everyone's coordinates , Add one person's position coordinates every time you ask , Ask how many seats are there that are not blocked .

Ideas ： For two lines perpendicular to the edge of the screen , Everyone will only block the people on the right ; For people in other places , This location is the same as (0,1),(0,m) The space on the right side between the lines will be blocked . It's not hard to imagine , This feasible area is made up of 2k A line chart composed of line segments , All broken lines can be divided into and (0,1) Connected and connected with (0,m) Connected , And those with a large slope must cover those with a small slope , So for each y Come on , Calculation x The smallest one is enough ,(0,1) and (0,m) Empathy .

AC Code：

#include <bits/stdc++.h>

typedef long long ll;
#define INF 0x3f3f3f3f3f3f3f3f
const int N=3e5+5;
const int mod=1e9+7;
int n,m,k,q;
ll pos[N],x[N],y[N],h[N];

struct node{
    ll a,b;
    bool operator<(const node &v) const{
        return a*v.b<b*v.a;
    }
};

int main(){
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    std::cout.tie(0);
    std::cin>>n>>m>>k>>q;
    for(int i=1;i<=k;i++){
        std::cin>>y[i]>>x[i];
    }
    while(q--){
        int p,xx,yy;
        std::cin>>p>>xx>>yy;
        y[p]=xx,x[p]=yy;
        std::fill(h+1,h+1+m,n);
        std::fill(pos+1,pos+1+m,n+1);
        for(int i=1;i<=k;i++){
            pos[x[i]]=std::min(pos[x[i]],y[i]);
        }
        node L={INF,(ll)1};
        for(int i=2;i<=m;i++){
            if(L.a!=INF){
                ll Y=L.a,X=L.b;
                h[i]=std::min(h[i],(Y*(i-1)-1)/X);
            }
            L=std::min(L,(node){pos[i],i-1});
        }
        node R={INF,(ll)1};
        for(int i=m-1;i>=1;i--){
            if(R.a!=INF){
                ll Y=R.a,X=R.b;
                h[i]=std::min(h[i],(Y*(m-i)-1)/X);
            }
            R=std::min(R,(node){pos[i],m-i});
        }
        ll ans=0;
        for(int i=1;i<=m;i++){
            h[i]=std::min(h[i],pos[i]-1);
            ans+=h[i];
        }
        std::cout<<ans<<'\n';
    }
    return 0;
}

Konjaku won't ,, It can't be mended QWQ

If there is any mistake, please advise , thank you ！