“蔚来杯“2022牛客暑期多校训练营1

准大二弱队第一次和大佬们打的比赛：

出题人标解pdf

G. Lexicographical Maximum（签到）

给出一个数字，找到1到该数中所有数字典序最大的那个数。

思路：注意数字范围，所以只能用字符串表示，字典序最大的一定是靠前9最多的那个，比如1034的话，输出999。但是注意，若是9998，则答案应该是9998，而不是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：签到，还因为这个特殊情况WA了一发，菜炸了。

A. Villages: Landlines（思维）

给出一个发电站的坐标，再给出建筑的坐标，只有在发电站和建筑物的半径范围内的中转站才能接收到信号，我们现在要在某些位置建若干中转站，将电从发电站中转至建筑物，而发电站之间需要电线相连，问最短需要连接的电线长度是多少。

思路：因为所有坐标都是一维的，可以画一个图，我们发现，最优的方案是在某一个点的半径位置建造中转站，这样才使得连接所需的电线最短。而最终中转站连接所需要的电线，就是没有相交的半径之间的距离，如下图红色线段长度：

具体做法可以将每个点按照其左边界和右边界排序，扫一遍找出红色区域长度即可。

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（计算几何）

给出一个圆的半径，和圆内一点Q，AB是以Q为圆心，r为半径的直径，但是这个直径方向任意，问圆上投影到直径AB上的弧最长是多少。

思路：如下图：

赛时我们队是直接猜的结论。

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（期望DP）

 给出这么一些牌，每种牌有4张，现在给出原来手中的13张牌，可以从牌堆中摸一张，从手中选一张扔掉，问在最优策略下最后凑齐七个对子的期望轮数。

思路：（1）标程是用DP求期望。很显然，最优策略是摸到一张牌可以和手中的单牌组成对子，扔掉某张单牌，若组不成对子，则扔掉摸的这张牌。令f[s][r]为当前手中有s张单牌且牌堆中剩余r张牌时达成七对子的期望轮数，转移方程为：

 我的理解是：s==1时，期望有两种情况，取到三张可以配对的牌中任意一张，都是游戏成功，轮数+1；其他情况概率是(r-3)/r，乘上手中有1张单牌且从牌堆中任意取一张牌的期望轮数。s!=1时，两种情况的概率乘结果，还要加上这一次的一轮。因为情况很少，直接预处理所有可能情况的f数组，每次数一下单牌的张数即可，注意求逆元，这里使用费马小定理求逆元。

（2）因为情况数是很少的，可以直接打表，具体见大佬的博客

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（树，结论，并查集）

 给出n个点，m条边的无重边无自环有向图，初始时可以选择一个点染黑，对于一个点来说，如果该点所有入边都是黑色的话，这个点也会变黑，怎样最大化黑色点的个数。

思路：搞懂了再写吧，树的性质啥的太不会了QWQ

C. Grab the Seat!（计算几何）

给出屏幕的坐标，和每个人的坐标，每次询问增加一个人的位置坐标，问还有多少不被人挡住的座位。

思路：对于垂直屏幕边缘的两条线上来说，每个人只会挡住右边的人；对于其他地方的人来说，该位置与(0,1)，(0,m)连线之间右侧的空间都会被挡住。不难想象，这个可行的区域是个由2k条线段组成的折线图，可以将所有的折线分为与(0,1)相连的及与(0,m)相连的，而且斜率大的必回覆盖斜率小的，这样对于每个y来说，计算x最小的即可，(0,1)和(0,m)同理。

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;
}

蒟蒻不会了，，补不动了QWQ

若有错误请指教，谢谢！