2023杭电多校第五场

Typhoon

题目大意

一个二维平面上，给你m个台风的坐标和n个避难所坐标，台风会从$(x_1,y_1)$到$(x_2,y_2)$…直到$(x_m,y_m)$，影响半径恒定为r的进行移动，问你每个避难所被台风影响到的最小的r。

解题思路

求每个避难所到每两个连续台风位置连成的线段的最小值即可。

直接套一个求点到线段的距离的板子。

时间复杂度：$O(nm)$

参考代码

#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
#define debug(a) cout<<#a<<"="<<a<<endl;
#define int long long
// #define x first
// #define y second
typedef long long LL;
typedef pair<int,int> PII;
typedef pair<double,double> PDD;
const double eps=1e-8;
bool multi=0;
const int N=1e4+10;
int m,n;

struct Point
{
    double x, y;
    Point(double x = 0, double y = 0) : x(x), y(y) { }
}p[N],P[N];


int sign(double x)  // 符号函数
{
    if (fabs(x) < eps) return 0;
    if (x < 0) return -1;
    return 1;
}

int cmp(double x, double y)  // 比较函数
{
    if (fabs(x - y) < eps) return 0;
    if (x < y) return -1;
    return 1;
}
Point operator + (Point A, Point B) {return Point(A.x + B.x, A.y + B.y);}

Point operator - (Point A, Point B) {return Point(A.x - B.x, A.y - B.y);}

Point operator * (Point A, double p) {return Point(A.x * p, A.y * p);}

Point operator / (Point A, double p) {return Point(A.x / p, A.y / p);}


double dot(Point a, Point b)
{
    return a.x * b.x + a.y * b.y;
}

double get_length(Point a)
{
    return sqrt(dot(a, a));
}


double cross(Point a, Point b)
{
    return a.x * b.y - b.x * a.y;
}

double distance_to_line(Point p, Point a, Point b)
{
    Point v1 = b - a, v2 = p - a;
    return fabs(cross(v1, v2) / get_length(v1));
}

double distance_to_segment(Point p, Point a, Point b)
{
    if (cmp(a.x,b.x)==0&&cmp(a.y,b.y)==0) return get_length(p - a);
    Point v1 = b - a, v2 = p - a, v3 = p - b;
    if (sign(dot(v1, v2)) < 0) return get_length(v2);
    if (sign(dot(v1, v3)) > 0) return get_length(v3);
    return distance_to_line(p, a, b);
}

void solve(){
    cin>>m>>n;
    for(int i=1;i<=m;i++){
        cin>>P[i].x>>P[i].y;
    }
    for(int i=1;i<=n;i++){
        cin>>p[i].x>>p[i].y;
    }
    for(int i=1;i<=n;i++){
        double ans=1e18;
        for(int j=1;j<=m-1;j++){
            ans=min(ans,distance_to_segment(p[i],P[j],P[j+1]));
        }
        cout<<fixed<<setprecision(4)<<ans<<endl;
    }

}

signed main(){
    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    int TTT=1;
    if(multi) cin>>TTT;
    while(TTT--){
        solve();
    }

    return 0;
}

Touhou Red Red Blue

题目大意

你将依次获得n个带有R、G、B颜色的飞行物，每次你可以选择丢弃或者存储。

记该飞行物为U

当你决定存储时，如果袋子1是空的，则将U放进袋子1；若袋子1不空而袋子2是空的，则装进袋子2；

若没有袋子是空的，那么我们考虑两个袋子中的飞行物颜色和当前的飞行物颜色，若三种颜色不同，这三个飞盘消失，你将获得1分数，你的包1将出现一个你自己决定颜色的飞行物；如果三个颜色都不同，这三个飞行物都消失，你的包1和包2都分别出现一个你自己决定颜色的飞行物；否则你将丢弃包1中的飞行物，把包2的飞行物移到包1，然后把U存到包2。

问收到这n个飞行物后，你可以获得的最高积分是多少？

解题思路

定义$dp[i][j][k]$为取完前i-1个飞行物，包1的颜色为j，包2的颜色为k的状态的最高积分。

其中j和k表示相同，0表示空，1表示R，2表示G，3表示B，4表示你可以自己选择的颜色，可以当成任意颜色来使用。

接下来考虑状态转移，考虑从当前状态往下一个状态转移。

首先，每个U都可以选择丢弃，直接转移到下一个状态即可。

若选择存储，则有以下情况：

（代码处直接循环i,j,k)

令当前即第i个得到的飞盘为cur。

包1为空时，装入包1，$dp[i][j][k]$转移到$dp[i+1][cur][j]$

否则，若包2为空，装入包2，$dp[i][j][k]$转移到$dp[i+1][j][cur]$

若都不为空，

判断$j,k,cur$三个量的关系：

若三个颜色可以相同，$dp[i][j][k]$转移到$dp[i+1][4][0]$，注意这里获得了1分数

若三个颜色可以都不同，$dp[i][j][k]$转移到$dp[i+1][4][4]$

否则，$dp[i][j][k]$转移到$dp[i+1][k][cur]$

最后的答案就是$i=n+1$的所有状态中取最大值

（取完前n个飞行物的状态）

时间复杂度：$O(n*5*5)$

参考代码

#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
#define debug(a) cout<<#a<<"="<<a<<endl;
//#define x first
//#define y second
typedef long long LL;
typedef pair<int,int> PII;
typedef pair<double,double> PDD;
const double eps=1e-8;
bool multi=1;
const int N=1e5+10;
char s[N];
int dp[N][5][5];
const int INF=0x3f3f3f3f;
int mp[120];
int a[4];

void solve(){
    scanf("%s",s+1);
    int n=strlen(s+1);
    for(int i=0;i<=n+1;i++){
        for(int j=0;j<5;j++){
            for(int k=0;k<5;k++){
                dp[i][j][k]=-INF;
            }
        }
    }
    dp[1][0][0]=0;
    for(int i=1;i<=n;i++){
        int cur=mp[s[i]];
        for(int j=0;j<5;j++){
            for(int k=0;k<5;k++){
                dp[i+1][j][k]=max(dp[i+1][j][k],dp[i][j][k]);
                if(j==0){
                    dp[i+1][cur][k]=max(dp[i+1][cur][k],dp[i][j][k]);
                    continue;
                }else if(k==0){
                    dp[i+1][j][cur]=max(dp[i+1][j][cur],dp[i][j][k]);
                    continue;
                }else{

                    int cnt1=0;
                    int cnt2=0;
                    memset(a,0,sizeof a);
                    if(j==4) cnt1++;
                    else{
                        if(!a[j]) cnt2++;
                        a[j]++;
                    }
                    if(k==4) cnt1++;
                    else{
                        if(!a[k]) cnt2++;
                        a[k]++;
                    }
                    if(!a[cur]) cnt2++;
                    a[cur]++;
                    if((int)cnt2<=1){
                        dp[i+1][4][0]=max(dp[i+1][4][0],dp[i][j][k]+1);
                    }
                    if(cnt1+cnt2==3){
                        dp[i+1][4][4]=max(dp[i+1][4][4],dp[i][j][k]);
                    }
                    if(cnt1!=0||cnt1==0&&cnt2==2){
                        dp[i+1][k][cur]=max(dp[i+1][k][cur],dp[i][j][k]);
                    }

                }
            }
        }
    }

    int ans=0;
    for(int i=0;i<5;i++){
        for(int j=0;j<5;j++){
            ans=max(ans,dp[n+1][i][j]);
        }
    }
    printf("%d\n",ans);
}

signed main(){
    mp['R']=1,mp['G']=2,mp['B']=3;
    int TTT=1;
    if(multi) cin>>TTT;
    while(TTT--){
        solve();
    }

    return 0;
}

Expectation (Easy Version)

题目大意

进行n次比赛，赢的概率是$a/b$，每次赢获得的分数为$1^m+2^m+...+k^m$，其中k表示你总共赢的次数，输了不减分。

问你最后的得分的期望值对998244353取模的结果。

解题思路

假设这n场比赛赢了i次，即①$C_n^i$，概率应该是②$(b/a)^i*((a-b)/b)^i$，赢得分数为③$1^m+2^m+...+i^m$

最后的得分期望值就是$C_n^i(b/a)^i*((a-b)/b)^i(1^m+2^m+...+i^m)$

分①②③，三部分进行递推预处理，最后相乘，可以使得最后的复杂度为$nlogn$，1e7的数据4s的时限不会超。

时间复杂度：$O(nlogn)$

参考代码

#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
#define debug(a) cout<<#a<<"="<<a<<endl;
#define int long long
//#define x first
//#define y second
typedef long long LL;
typedef pair<int,int> PII;
typedef pair<double,double> PDD;
const double eps=1e-8;
bool multi=1;
const int mod=998244353;

//a ^ b mod p
int qpow(int a,int b,int p){
    long long res=1%p;
    while(b){
        if(b&1) res=res*a%p;
        a=(long long)a*a%p;
        b>>=1;
    }
    return res;
}
const int N=1e6+10;

int sum[N];
int C[N];
int s[N];

void solve(){
    int n,m,a,b;
    cin>>n>>m>>a>>b;
    for(int i=1;i<=n;i++){
        sum[i]=(sum[i-1]+qpow(i,m,mod)%mod)%mod;
    }
    int invab=a*qpow(b,mod-2,mod)%mod;
    int invbab=(b-a)*qpow(b,mod-2,mod)%mod;
    // pow[0]=qpow(invab,n);
    // for(int i=1;i<=n;i++){
    //     pow[i]=pow[i-1]*qpow(invb,mod-2,mod)
    // }
    int inva=qpow(a,mod-2,mod);
    int invba=qpow(b-a,mod-2,mod);
    s[0]=qpow(b-a,n,mod)*qpow(qpow(b,mod-2,mod),n,mod)%mod;
    for(int i=1;i<=n;i++){
        s[i]=s[i-1]*a%mod*invba%mod;
    }
    C[0]=1;
    int invbb=qpow(qpow(b,mod-2,mod),n,mod);
    for(int i=1;i<=n;i++){
        C[i]=(C[i-1]*(n-i+1)%mod*qpow(i,mod-2,mod))%mod;
    }
    int ans=0;
    for(int i=1;i<=n;i++){
        ans=(ans+C[i]*s[i]%mod*sum[i]%mod)%mod;
    }
    cout<<ans%mod<<endl;
}

signed main(){
    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    int TTT=1;
    if(multi) cin>>TTT;
    while(TTT--){
        solve();
    }

    return 0;
}

Tree

题目大意

给定一个有根树，其中指定某些边是重边，一组最大重边构成一个重链，单个顶点也形成一个重链。

对于每个重链，构造深度为$\lceil log_22k \rceil$（k表示这条重链的结点数量）的二叉树维护它，段树的每个叶子结点表示重链上的一个顶点，该二叉树的根节点的父节点为这条重链的顶端结点的父节点。

问这棵搜索树的深度。

解题思路

正解是用树形dp做的，因为我赛时的第一想法就是带权并查集而且我感觉这种方法可做，但赛时权值数组的更新出现了一点问题，赛后也是又想了很久终于写出来了。

对于带权并查集的框架这里就不详细讲了。

首先，我们可以把每个重链想成是一个集合，而重链对应的搜索树连向另一个搜索树就相当于集合的合并。那么本题就是要对所有搜索树进行合并。

起初，每个集合的权值是$\lceil log_22k \rceil$（k表示这条重链的结点数量），记并查集中的权值数组为d[]，开始的d数组应该都为0，因为并查集的值存的是相对关系，d为该点与它的祖宗结点的相对距离。

合并操作中，当a为重链顶点时，将这个重链合并到它的父节点b上，即a为这个集合的祖宗结点，此时a与pa(pa=find(a))等价,d[pa]=depth[pa]+d[b]，然后再把a的祖宗结点赋值为b，此时的情况是d[a]为a到b的距离，a集合中的其它结点如c,由于没改变它的值，初始状态d[c]=0，那么相当于将a集合中的值都加了a重链的书高和b与b的祖宗结点的距离，这样就合并了两个集合。

最后就是d[i]-d[root]即i到i祖宗的相对距离加上root的深度，因为root不会成为其它结点的根节点，所以它的搜索树的深度不会在合并中被加上，我们在最后加上。

时间复杂度：$O(n)$

参考代码

#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
#define debug(a) cout<<#a<<"="<<a<<endl;
#define int long long
//#define x first
//#define y second
typedef long long LL;
typedef pair<int,int> PII;
typedef pair<double,double> PDD;
const double eps=1e-8;
bool multi=1;
const int N=1e6+10;
int n;
int p[N],sz[N],fa[N],d[N];
int depth[N];
int root;
int ans;

inline int find(int x){//带权并查集模板
    if(p[x]!=x){
        int rt=find(p[x]);
        d[x]+=d[p[x]];
        p[x]=rt;
    }
    return p[x];
}

void solve(){
    ans=0;
    cin>>n;
    for(int i=1;i<=n;i++){
        int x;
        cin>>x;
        fa[i]=x;
        if(x==0){
            root=i;
        }
    }
    for(int i=1;i<=n;i++){//初始化
        p[i]=i;
        sz[i]=1;
        depth[i]=0;
        d[i]=0;
    }
    
    for(int i=1;i<=n;i++){
        int x;
        cin>>x;
        if(x==0){
            continue;
        }
        int px=find(x),pi=find(i);
        if(px!=pi){//这里还不需要d的概念，我们要合并重链间的
        //点以及合并成的重链内部结点的数量
            p[px]=pi;
            sz[pi]+=sz[px];
        }
    }

    for(int i=1;i<=n;i++){//对于每条重链计算它的搜索树的高度
        int pi=find(i);
        depth[i]=(int)ceil(log2(2*sz[pi]));
    }

    for(int i=1;i<=n;i++){//将重链合并，即将搜索树合并
        if(p[i]==i&&fa[i]!=0){
            int a=i,b=fa[i];
            int pa=find(a),pb=find(b);
            if(pa!=pb){
                d[pa]=depth[pa]+d[b];
                p[pa]=pb;
            }
        }
    }
    for(int i=1;i<=n;i++){
        find(i);//这里find(i)是为了更新一下i这个结点d数组，
        //进行路径压缩得到跟真正的根节点的距离
        ans=max(ans,d[i]-d[root]+depth[root]);
        //记得补上根节点所在重链的搜索树的树高
    }
    cout<<ans<<endl;
}

signed main(){

    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    int TTT=1;
    if(multi) cin>>TTT;
    while(TTT--){
        solve();
    }

    return 0;
}

Counting Stars

题目大意

给定一个n个点m条边的无向图，令连向一个点的边的数量为i的总和为$cnt_i$，问$cnt_2$一直异或到$cnt_{n-1}$取模1e9+7的值。

解题思路

记录每个点的度，累加$i=2,3,...,dgr[u]$对$cnt$的贡献$C_{dgr[u]}^i$

最后异或每个$cnt_i$即可。

对于求组合数操作，可以先预处理出$1\times 2\times ...\times n$的前缀积，以及用逆元预处理出$1^{-1}\times 2^{-1}\times ...\times n^{-1}$的前缀积，然后O(1)得到组合数。

**时间复杂度：$O(n+m)$

参考代码

#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
#define debug(a) cout<<#a<<"="<<a<<endl;
#define int long long
//#define x first
//#define y second
typedef long long LL;
typedef pair<int,int> PII;
typedef pair<double,double> PDD;
const double eps=1e-8;
const int mod=1e9+7;
bool multi=1;
int n,m;
const int N=1e6+10;
int dg[N];
int cnt[N];
int fac[N],infac[N];

//a ^ b mod p
int qpow(int a,int b,int p){
    long long res=1%p;
    while(b){
        if(b&1) res=res*a%p;
        a=(long long)a*a%p;
        b>>=1;
    }
    return res;
}

inline int C(int a,int b){
    return fac[a]*infac[a-b]%mod*infac[b]%mod;
}

void solve(){
    cin>>n>>m;
    memset(dg,0,(n+1)*sizeof(int));
    memset(cnt,0,(n+1)*sizeof(int));
    for(int i=1;i<=m;i++){
        int u,v;
        cin>>u>>v;
        dg[u]++;
        dg[v]++;
    }
    for(int i=1;i<=n;i++){
        for(int j=2;j<=dg[i];j++){
            cnt[j]=(cnt[j]+C(dg[i],j))%mod;
        }
    }
    int ans=0;
    for(int i=0;i<n;i++){
        ans^=cnt[i];
    }
    cout<<ans<<endl;
}

signed main(){
    fac[0]=infac[0]=1;
    for(int i=1;i<N;i++){
        fac[i]=fac[i-1]*i%mod;
        infac[i]=infac[i-1]*qpow(i,mod-2,mod)%mod;
    }
    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    int TTT=1;
    if(multi) cin>>TTT;
    while(TTT--){
        solve();
    }

    return 0;
}