A-Villages: Landlines

来源: 牛客多校训练营1 算法: 区间合并题目链接: https://ac.nowcoder.com/acm/contest/33186/A 补完: Yes 完成时间: August 19, 2022

题解

本题求各个区间之间的空隙, 第五场F题同样使用到了这种操作, 可以抽象化保存一下.

代码

#include<bits/stdc++.h>

using namespace std;

// 区间
struct Interval{
    int start;
    int finish;
    bool operator<(const Interval other) const {
        return start<other.start||(start==other.start&&finish>other.finish);
    }
};

// 给区间数组, 返回区间间隙
int rest(vector<Interval> intervals){
    // 若域边界大于始末区间, 可再加两区间扩充边界
    // intervals.pop_back({left , left });
    // intervals.pop_back({right, right});
    sort(intervals.begin(),intervals.end());
    int lim = intervals[0].start, temp = 0;
    for (auto interval : intervals) {
        if (lim < interval.start) {
            temp += interval.start - lim;
        }
        lim = max(lim, interval.finish);
    }
    return temp;
}

void solve() {
    int n;
    cin>>n;
    vector<Interval> build;
    int center, radius;
    for (int i = 1; i <= n; i++) {
        cin>>center>>radius;
        build.push_back({center-radius,center+radius});
    }
    cout<<rest(build);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int T = 1;
    // cin>>T;
    while (T--) {
        solve();
    }
    return 0;
}

C-Grab the Seat!

来源: 牛客多校训练营1 算法: 计算几何, 贪心补完: Yes 完成时间: August 25, 2022

题目链接

题意简述

一间教室，有\(n*m\)个座位，即座位在整数点坐标\(（i,j）\)上，\(i\)的取值是\([1,n]\)，\(j\)的取值是\([1,m]\)。

\((0,1)−(0,m)\)（包含边界）区域是屏幕。

一个能清楚地看见整块屏幕，即到屏幕所有连线构成区域里没有其他人的座位的位置是好座位。

每个人都可能换座位，求每次有人改变座位后的好座位数量。

（黑色粗线是屏幕，绿色点是好座位，红色点是有人的座位。）

题目分析

本题很关键的一个思考方向是转换参考对象（是这么说吗）

总之，每个好座位到\(（0，1）\)和\(（0，m）\)点连成的三角区域里没有被占用的座位，这是很好理解到的。但凭借这个做题会非常复杂。~~所以赛时很不聪明的我跑路了。~~

我们把目光移动到，每次询问会变化的被占用座位。类似好座位的连线连一下，靠近屏幕那侧的三角区域是会挡住视线的区域，换个方向看，远离屏幕那侧的自然是能挡住别人的区域。

在每次变动之后处理（或者更新）被占用座位的占用数量，显然比每次遮挡者变化后处理每个位置是否被遮挡容易得多。

那么我们开始考虑处理这个遮挡区域：

一个位置正后方的所有位置会被遮挡是很显然的。我们面向屏幕看。那么在座位左后方的位置可能看不见部分的偏右的屏幕，右后方的位置可能看不见部分偏左的屏幕。左右侧后关心的屏幕范围是可以比较独立的来看的。

画一画图，大概是这样：三角遮挡区被正后方这条线割裂开。可以看出不同区域关心的范围是不一样的。（题目的图，旋转了）

并且，一个很朴素的认知：在非阶梯教室里，越前面的位置能挡住越多人。

这在这里依然适用。在进行了区域分割后更加明显。

两个方向上，靠前的点的覆盖区域都能把同一行靠后的点的覆盖区域包含。

而在不同的行上，大概表现出了一个补充的关系：

对于从\(（0，1）\)点连线考虑的情况，处在更上方的点，虽然可能相对更靠后，但它的覆盖区域在它那行以上的地方，对原来的点的覆盖区域有一个补充的范围。

也就是我们处理这部分答案的时候，从下向上跑是可以获得更新的。

同理，处理另一个部分的时候，从\(（0，m）\)连来的点也表现出了类似的性质，不过是下方的点可能对上方的点进行补充，所以这部分答案从上往下跑可能获得答案更新。

即，我们在预先存好初始的占有座位的点情况之后，对于每次询问，先更新点，然后再找到每一行最前面的点（也就是对于每个y最小的x），每行记录被遮住的点的数量，从下向上更新一次\(（0，1）\)点的答案，从上向下更新一次\(（0，m）\)的答案即可。

每行覆盖了多少点可以使用斜率计算获得。但注意，由于屏幕边界也要看见，所以正好被屏幕边缘连线覆盖的点是不作数的，也就是类似开区间那个意思。

在处理这个问题的时候，如果使用的是\(double\)类型计算，可以在答案里扣掉一个很小的数字来进行补正后，再转换成int类型。（比如2.000000转int是2，1.9999999转int是1）

本题评测环境里，这个数字的范围在\(1e-6\)到\(1e-10\)均可。这里使用了\(1e-9\)。

完整代码

#include<iostream>
using namespace std;
struct point{
	int x;
	int y;
}pt[200005];
int min_x[200005];
int ans[200010];
int main(){
	int n,m,k,q;
	cin>>n>>m>>k>>q;
	for(int i=1;i<=k;++i) cin>>pt[i].x>>pt[i].y;
	while(q--){
		int p;
		cin>>p;
		cin>>pt[p].x>>pt[p].y;
		for(int i=1;i<=m;++i) min_x[i]=n+1;
		for(int i=1;i<=k;++i) min_x[pt[i].y]=min(min_x[pt[i].y],pt[i].x); 
		double EPS=1e-9;
		double k=0;
		for(int i=1;i<=m;i++){
			k=max(k,double(i-1)/min_x[i]); 
			if(k==0) ans[i]=min_x[i]-1; 
			else ans[i]=(int)(i-1)/k-EPS; 
		} 
		k=0;
		for(int i=m;i>=1;i--){
			k=min(k,double(i-m)/min_x[i]); 
            int cmp1=(int)(min_x[i]-1);
			int cmp2=(int)((i-m)/k-EPS); 
			if(k==0) ans[i]=min(ans[i],cmp1);
			else ans[i]=min(ans[i],cmp2); 
		}
		long long anss=0;
		for(int i=0;i<=m;i++)anss+=ans[i];
		cout<<anss<<'\n';
	}
}

D-Mocha and Railgun

来源: 牛客多校训练营1 算法: 计算几何题目链接: https://ac.nowcoder.com/acm/contest/33186/D 补完: Yes 完成时间: July 18, 2022

题解

找最长弧

发现当发射方向垂直于发射点与圆心的连线时,破坏圆弧最长

分类讨论

每个样例给发射点\(Q\)点坐标\((x,y)\),发射半径\(d\)

可求得发射点到圆心的圆心距\(L=\sqrt{x^2+y^2}\)

几何画板

当原点在发射半径外时

\(L>d\)

在三角形\(AOE\)上,可求得\(\alpha=\arcsin(L+d)\)

在三角形\(IOJ\)上,可求得\(\beta=\arcsin(L-d)\)

对所求圆弧有\(弧长=r*(\alpha-\beta)\)

当原点在发射半径内时

\(L<d\)

在三角形\(AOE\)上,可求得\(\alpha=\arcsin(d+L)\)

在三角形\(IOJ\)上,可求得\(\beta=\arcsin(d-L)\)

对所求圆弧有\(弧长=r*(\alpha+\beta)\)

代码

由上述逻辑得

#include<bits/stdc++.h>
using namespace std;
int T;
int main(){
    cin>>T;
    double r,x,y,d,L;
    while(T--){
        cin>>r>>x>>y>>d;
        L=sqrt(x*x+y*y);
        if(L>d){
            printf("%.8lf\n",r*(asin((L+d)/r)-asin((L-d)/r)));
        }
        else{
            printf("%.8lf\n",r*(asin((d+L)/r)+asin((d-L)/r)));
        }
    }
    return 0;
}

然而其实有\(\arcsin(-x)=-\arcsin(x)\),故可以化简

#include<bits/stdc++.h>
using namespace std;
int T;
int main(){
    cin>>T;
    double r,x,y,d,L;
    while(T--){
        cin>>r>>x>>y>>d;
        L=sqrt(x*x+y*y);
        printf("%.8lf\n",r*(asin((L+d)/r)-asin((L-d)/r)));
    }
    return 0;
}

G-Lexicographical Max

来源: 牛客多校训练营1 算法: 字典序题目链接: https://ac.nowcoder.com/acm/contest/33186/G 补完: Yes 完成时间: July 28, 2022

题意

给定一个整数n，输出1到这个数字中所有数字字符串中字典序最大值； 容易知道：

字典序排序是先比最高位再比第二位，因此字典序中9比19大，90比9大； 因此我们可以：

求出n的长度len，并判断n的数字组成，若除了个位数都是9，则直接输出n；否则输出len-1个9

代码如下

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

I-Chiitoitsu

来源: 牛客多校训练营1 算法: 动态规划, 概率DP 题目链接: https://ac.nowcoder.com/acm/contest/33186/I 补完: Yes 完成时间: July 22, 2022

解题

最优策略相当于开了透视,保留的手牌一定是最快凑成对子的,把第二张牌来得晚的丢掉.

所以我们具体手牌是什么不重要,只要知道已经凑齐了几个对子就好了

此时对于保留在手上的待匹配牌,还有三张牌在牌池里.

设牌池还剩\(i\)张牌,还有\(j\)张牌需要凑对子,\(f[i][j]\)为距结束步数

则有摸下一张牌时,可以匹配的概率为\(\frac{3*j}{i}\),不可以匹配的概率为\(\frac{i-3*j}{i}\)

因为初始手牌为\(13\)张,其中有\(13-j\)张牌是对子,则在游戏结束前\(j\)只能为奇数

当\(j=0\)时,

所有牌都得到匹配,游戏结束,距游戏结束还有 \(0\)回合

\[ \begin{align} f[i][0]=0 \end{align} \]

当\(j=1\)时,

摸完一张牌之后牌池还剩\(i-1\)张牌,

若匹配则消不匹配的牌,还有\(j-1\)张待匹配的牌,

若不可以匹配则丢摸到的这张牌,还有\(j\)张待匹配的牌

\[ \begin{align} f[i][j]&=1\\ &+\frac{3*j}{i}*f[i-1][j-1]&匹配\\ &+\frac{i-3*j}{i}*f[i-1][j]&不匹配 \end{align} \]

当\(j>1\)时,

摸完一张牌之后牌池还剩\(i-1\)张牌,

若匹配则消不匹配的牌同时丢一张不能匹配的牌,还有\(j-2\)张待匹配的牌,

若不可以匹配则丢摸到的这张牌,还有\(j\)张待匹配的牌

\[ \begin{align} f[i][j]&=1\\ &+\frac{3*j}{i}*f[i-1][j-2]&匹配\\ &+\frac{i-3*j}{i}*f[i-1][j]&不匹配 \end{align} \]

跑完之后直接拿数据访问\(f[i][j]\)即可

代码

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll P = 1e9+7;
int t=1;
ll f[137][14];
ll qpow(ll x,ll a){
    ll res=1;
    while(a){
        if(a&1)res=res*x%P;
        x= x*x%P;
        a>>=1;
    }
    return res;
}
void Init() {
    for(int j=1;j<=13;j+=2){
        for(int i=1;i<=136;i++){
            if(j==1)f[i][j]=(1+(3*j)*qpow(i,P-2)%P*f[i-1][j-1]%P+(i-3*j)*qpow(i,P-2)%P*f[i-1][j]%P)%P;
            else    f[i][j]=(1+(3*j)*qpow(i,P-2)%P*f[i-1][j-2]%P+(i-3*j)*qpow(i,P-2)%P*f[i-1][j]%P)%P;
        }
    }
}
void solve(){
    char s[26];
    scanf("%s",&s);
    int pp[5][10];
    for(int i=1;i<5;i++){
        for(int j=1;j<10;j++){
            pp[i][j]=0;
        }
    }
    int cnt=0;
    for(int i=0;i<26;i+=2){
        switch(s[i+1]){
        case 'm':pp[1][s[i]-'0']++;break;
        case 'p':pp[2][s[i]-'0']++;break;
        case 's':pp[3][s[i]-'0']++;break;
        case 'z':pp[4][s[i]-'0']++;break;
        default:break;
        }
    }
    for(int i=1;i<5;i++){
        for(int j=1;j<10;j++){
            if(pp[i][j]>1)cnt++;
        }
    }
    printf("Case #%d: %lld\n",t++,f[123][13-cnt*2]);
}
int main(){
    Init();
    int T;
    cin>>T;
    while(T--)solve();
    return 0;
}

J-Serval and Essay

来源: 牛客多校训练营1 算法: set, 启发式合并, 并查集, 数论题目链接: https://ac.nowcoder.com/acm/contest/33186/J 补完: Yes 完成时间: August 23, 2022

完完全全的补题，题解参考雨巨的讲解

题意

有一张\(n\) 个点\(m\)条边的无重边无自环的有向图
初始时可以选择一个点染黑，其余均为白点
若某个点所有入边的起点均为黑点，则该点可以被染黑
选择一点染黑使得图中黑点数量最大化

解

从图中所有没有访问过的点出发，把所有入度为1的点和它的前面的那一部分合并，合并后要把重复的边去掉。对于可以合成一堆的块来说，只需要把起始点染黑，那么这个整块都会变成黑的，而我们要找的就是经过合并操作之后，哪一整块会最大，然后这块是多大。

处理

用set存储集合连出去的边指向的点，再将另一个集合连出去的边放置在set，所形成的新集合继续与其他集合合并。

如果一个点的入度是1，就以此为起点搜索前部分，把前部分和此点所在集合进行合并，把边数小的集合合并到边数大的集合上，在这个过程中入度也要处理。 ## 代码

#include <iostream>
#include <bits/stdc++.h>
using namespace std;
const int N=1e6+10;
set<int>to[N],from[N];
int fa[N],sz[N];
int find(int i)
{
	if(i==fa[i]){
		return i;
	}
	else {
		fa[i]=find(fa[i]);
		return fa[i];
	}
}

void _Merge(int x,int y){
	//得到这两点的并查集 
	x=find(x);
	y=find(y);
	if(x==y)   //已经在一个集合里了，说明已经被合并过 
		return;
	if(to[x].size()<to[y].size())  //找指出去少的边来遍历 
		swap(x,y);
	fa[y]=x;  //合并 
	sz[x]+=sz[y];  //大小更新 
	vector<pair<int,int> >mg; 
	for(auto t : to[y]){      // 把y指出去的边都遍历一遍 
		to[x].insert(t);  //让x指向t 
		from[t].erase(y); //消去t从y连过来的边 
		from[t].insert(x);//加上x指向t的边 
		if(from[t].size()==1){
			mg.push_back(make_pair(t,x));  //可合并 
		}
	} 
	for(auto [x,y]:mg){
		_Merge(x,y);
	}
}

int main(){
	int t;
	cin>>t;
	int p=1;
	while(t--){
		int n;
		cin>>n;
		for(int i=1;i<=n;i++){
			fa[i]=i;  //并查集的父亲 
			sz[i]=1;  // 表示集合大小的数组 
		}
		for(int i=1;i<=n;i++){  //读入边 
			int k;
			cin>>k;
			for(int j=1;j<=k;j++){
				int a;
				cin>>a;
				to[a].insert(i);
				from[i].insert(a);
			}  //建立双向边 
		}
		for(int i=1;i<=n;i++){
			if(from[i].size()==1){  //遍历所有size等于1的点 
				_Merge(*from[i].begin(),i);   //把它和前部分合并 
			}
		}
		int ans=0;
		for(int i=1;i<=n;i++){   //找到最大块集合
			ans=max(ans,sz[i]);
		} 
		printf("Case #%d: %d\n",p++,ans);
		for(int i=1;i<=n;i++){    //清空
			to[i].clear();
			from[i].clear();
		}
	}
	return 0; 
}

Shelter

2022牛客多校训练营01