“蔚来杯“2022牛客暑期多校训练营1补题记录(ACDGIJ)

把题补了,感觉要自己梳理一下,就写一下题解.

"蔚来杯"2022牛客暑期多校训练营1_ACM/NOI/CSP/CCPC/ICPC算法编程高难度练习赛_牛客竞赛OJ牛客ACM提高训练营是面向ICPC/CCPC/CSP/NOI比赛备战的选手，由金牌选手命题，提高训练高难度的编程比赛，ACM/NOI拔高训练营。https://ac.nowcoder.com/acm/contest/33186#question

目录

A.Villages: Landlines(签到)

C.Grab the Seat!(计算几何?枚举)

D.Mocha and Railgun(计算几何,签到)

G.Lexicographical Maximum(签到)

I.Chiitoitsu(概率dp)

J.Serval and Essay(启发式合并)

---

A.Villages: Landlines(签到)

吐槽:阅读题,读完就过了.

思路:把数学模型抽象出来,就变成了一格一格的区间,我们要把它们变成连续的一个区间.直接求空区间长度即可.

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N =5e5+10,mod=998244353;
struct node
{
    int l,r;
};
vector<node>ve;
bool cmp(node a,node b)
{
    return a.l<b.l;
}
void solve()
{
    int n,ans=0;
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        int x,r;
        cin>>x>>r;
        ve.push_back({x-r,x+r});
    }
    sort(ve.begin(),ve.end(),cmp);
    int l=ve[0].l,r=ve[0].r;
    for(int i=1;i<ve.size();i++)
    {
        if(ve[i].l<=r)
        {
            r=max(ve[i-1].r,ve[i].r);
        }
        else
        {
            ans+=ve[i].l-r;
            l=ve[i].l;
            r=ve[i].r;
        }
    }   
    cout<<ans<<"\n";
    return ;
}
signed main()
{
    solve();
    return 0;
}

C.Grab the Seat!(计算几何?枚举)

思路:对于每一行我们都要找到光线的覆盖的最左边的点即可.所以我们要针对所有的光线进行讨论(太麻烦了),但是我们在这一行取一个点之后,链接这个屏幕的两段的点,所有的光线也就在这两条线的区间内,所以我们要考虑这两条线覆盖的未被覆盖的范围.当然,还有一种情况就是这一行有某个点坐了人,吧从屏幕两端射来的,被其他的掩盖的光(取最值)和这一行的"土著居民"的位置取min就行了.

(图中阴影为被遮盖的,粉色点为有人的位置,覆盖坐标最小值即为这一行覆盖值)

ps:因为计算出来的点可能是整点,但是这个点当前被影响了,所以要对求出来的坐标减去一个极小值再去取整,再求未被影响的范围的和.

#include<bits/stdc++.h>
#define int long long
#define eps 1e-6 
using namespace std;
const int N =5e5+10,mod=998244353;
int n,m,k;
struct poi
{
    int x,y;
}p[200100];
int ans[200100],xmin[200100];
void sol()
{
    for(int i=1;i<=m;i++)
        ans[i]=n,xmin[i]=n+1;
    for(int i=1;i<=k;i++)
        xmin[p[i].y]=min(xmin[p[i].y],p[i].x);
    double k=0;
    ans[1]=min(ans[1],xmin[1]-1);
    for(int i=2;i<=m;i++)
    {
        k=max(k,(double)(i-1)*1.0/xmin[i]);
        ans[i]=min(ans[i],(int)floor((i-1)*1.0/k-eps));
    }
    k=0;
    ans[m]=min(ans[m],xmin[m]-1);
    for(int i=m-1;i>=1;i--)
    {
        k=max(k,(double)(m-i)*1.0/xmin[i]);
        ans[i]=min(ans[i],(int)floor((m-i)*1.0/k-eps));
    }
    int anss=0;
    for(int i=1;i<=m;i++)
        anss+=ans[i];
    cout<<anss<<"\n";
    return ;
}
void solve()
{
    int q;
    cin>>n>>m>>k>>q;
    for(int i=1;i<=k;i++)
        cin>>p[i].x>>p[i].y;
    while (q--)
    {   
        int id,x,y;
        cin>>id>>x>>y;
        p[id].x=x;
        p[id].y=y; 
        sol();
    }
    return ;
}
signed main()
{
    solve();
    return 0;
}

D.Mocha and Railgun(计算几何,签到)

思路:对于情况分类讨论再按照公式求长度即可:

1.未碰到圆心

2.穿过圆心

3.端点为圆心

#include <bits/stdc++.h>
using namespace std;
const double eps = 1e-8;
const double pi = acos(-1.0);
double r;
void solve()
{
    double x,y,d;
    scanf("%lf%lf%lf%lf",&r,&x,&y,&d);
    double ans = r * asin(d / r) * 2;
    
    double  dis = sqrt(x*x + y*y);//Q到圆心距离
    double d1 = dis + d;
    if(d < dis)
    {
        double d2 = dis - d;
        double c1 = r * acos(d1 / r) * 2;
        double c2 = r * acos(d2 / r) * 2;
        ans = max(ans,(c2 - c1) / 2);
    }
    if(d == dis)
    {
        double c1 = r * acos(d1 / r) * 2;
        double c2 = r * pi;
        ans = max(ans,(c2 - c1) / 2);
    }
    if(d > dis)
    {
        double d3 = d - dis;
        double c1 = r * acos(d1 / r) * 2;
        double c2 = r * pi;
        double c3 = r * acos(d3 / r) * 2;
        ans = max(ans,(c2 - c1) / 2 + (c2 - c3) / 2);
    }
    printf("%.8lf\n",ans);
    return ;
}
int main()
{
    int T;
    scanf("%d",&T);
    while(T --)solve();
    return 0;
}

G.Lexicographical Maximum(签到)

#include<bits/stdc++.h>
using namespace std;
void solve()
{
    string s,s1="";
    cin>>s;
    for(int i=0;i<s.size();i++)
    {
        s1+="9";
    }
    if(s1==s)
        cout<<s1<<"\n";
    else
    {
        for(int i=1;i<s1.size();i++)
            cout<<s1[i];
        cout<<"\n";
    }
    return ;
}
signed main()
{
    solve();
    return 0;
}

I.Chiitoitsu(概率dp)

i真是我的心头恨,概率dp,没把题整明白,这题面也太长了吧...还是自己太菜了,呜呜.

先吧这个题抽象成又一个起点,很多个终点的一个有向无环图,每条边的长度就是1.每一个状态的后继状态都是进行一次摸牌打牌得来(相当于走了长度为1的路).所以求期望次数就成了期望长度(抽象了更好理解).直接就是走的长度*概率.

然后进行状态考虑,我们设计f [ i ][ j ],意思是我们手上目前有i张牌,牌堆里有j张牌我们获胜的期望.为什么这么设置,因为题目我们的最优决策就是假设我摸到一张牌能和手里的牌组成对子,我就保留并且扔掉一张单牌,摸到的如果是单牌就直接打出去,这样的话就是最优决策,然后结合题目说一开始手上相同的牌最多两张,就推出这个状态.

直接得到状态转移方程式,直接记忆化搜索即可.

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int mod=1e9+7;
int f[15][130],tot=1;
int inv[220];
map<string,int>ma;
void init()
{
    inv[0]=inv[1]=1;
    for(int i=2;i<=200;i++)
        inv[i]=(mod-mod/i)*inv[mod%i]%mod;
    return ;
}
int dfs(int sheng,int zong)
{
    if(sheng<=0||zong<=0)
        return 0;
    if(f[sheng][zong]!=-1)
        return f[sheng][zong];
    f[sheng][zong]=(1ll+(dfs(sheng-2,zong-1)*3*sheng+dfs(sheng,zong-1)*(zong-3*sheng))%mod*inv[zong])%mod;
    return f[sheng][zong]=(f[sheng][zong]%mod+mod)%mod;
}
void solve()
{
    
    ma.clear();
    string s,t="";
    cin>>s;
    for(int i=0;i<s.size();i+=2)
    {
        t="";
        t+=s[i];
        t+=s[i+1];
        ma[t]++;
    }
    int dan=0;
    for(auto &x:ma)
        if(x.second==1)
            dan++;
    cout<<"Case #"<<tot<<": "<<dfs(dan,123)<<"\n";
    tot++;
    return ;
}
signed main()
{
    memset(f,-1,sizeof f);
    ios::sync_with_stdio(false);
    init();
    int t;
    cin>>t;
    while(t--)
        solve();
    return 0;
}

J.Serval and Essay(启发式合并)

为了节约时间,该题需要对集合进行合并,采用启发式合并.

这题启发式合并的思路是:判断如果某个集合都被染黑了,那么直接将他们看做一体,染黑吧该集合自己和的未染黑的记录下来,然后一直坚信循环知道一整个相连的集合都染黑.当两个集合进行合并时,我们选择小集合起并入大集合(这里的大小是针对两者可以继续合并的边决定的).代码有注解

#include<bits/stdc++.h>
#define int long long
using namespace std;
int fa[200015],siz[200015],n,k,tot=1;
set<int>f[200015],s[200015];
typedef pair<int,int>pii;
int read() 
{
    int x=0,f=1;
    char c=getchar();
    while(c<'0'||c>'9'){if(c=='-') f=-1;c=getchar();}
    while(c>='0'&&c<='9') x=x*10+c-'0',c=getchar();
    return x*f;
}
void write(int x) 
{
     if(x<0) putchar('-'),x=-x;
     if(x>9) write(x/10);
     putchar(x%10+'0');
}
int find(int x)
{
    if(x!=fa[x])
		fa[x]=find(fa[x]);
    return fa[x];
}//并查集找父亲
void solve()
{
	int x,y;
	n=read();
	for(int i=1;i<=n;i++)
	{
		f[i].clear();
		s[i].clear();
		siz[i]=1;
		fa[i]=i;
	}//初始化
	for(int i=1;i<=n;i++)
	{
		k=read();
		for(int j=0;j<k;j++)
		{
			x=read();
			s[x].insert(i);
			f[i].insert(x);
		}
//f表示记录的父亲节点,s记录的儿子节点
	}
	queue<pii>qu;
	for(int i=1;i<=n;i++)
	{
		if(f[i].size()!=1)//说明有多个父亲,没有全被染黑
			continue;
		qu.push({*f[i].begin(),i});
//只有一个父亲,将父亲节点和当前的i节点的子节点尝试合并
		while(qu.size())
		{
			pii bef=qu.front();
			qu.pop();
			x=bef.first,y=bef.second;
			x=find(x),y=find(y);
			if(x==y)
				continue;
			if(s[y].size()>s[x].size())
				swap(x,y);
			fa[y]=x;
			siz[x]+=siz[y];
			for(auto t:s[y])
			{
				f[t].erase(y);
				f[t].insert(x);
				s[x].insert(t);
//两个集合合并,父亲节点改变,原来的父亲节点的儿子节点增加
				if(f[t].size()==1)
					qu.push({x,t});
//其实每个集合合并之后,表示的方法就是一个父亲节点加上其他的可以继续合并的节点,已经合并的中间
节点不在表示.所以我们将持续向下合并并且记录边界(还有多少点喝一喝其他进行合并)
			}
		}
	}
	int ans=-1;
	for(int i=1;i<=n;i++)
	 	ans=max(ans,siz[i]);
	printf("Case #");
	write(tot);
	printf(": ");
	write(ans);
	printf("\n");
	tot++;
	return ;
}
signed main()
{
	int t;
	t=read();
	while(t--)
	   solve();
	return 0;
}