Teacher Ma专场补题

C：点到为止

题意：

游戏一开始有一堆含有n个石头的石子，玩家轮流进行以下操作，每次操作可以选择下列两种中的一种：
1.选择一堆石子，将石子分成两堆石子，新分的石子不能为空。
2.选择一堆石子，假设该堆有 i 个石头，当满足 gcd( i ，j ) == 1 时，可以从该堆取走 j 个石头。

不能进行操作的人判输。

Teacher Ma先手，两人都采取最优的策略，输出谁会赢得比赛。

思路：

sg函数

代码：

#include<bits/stdc++.h>

using namespace std;
int gcd(int a,int b){
    return a%b?gcd(b,a%b):b;
}
int SG[20];
int sg(int x){
    if(SG[x]!=-1) return SG[x];
    set<int> s;
    for(int i=1;i<x;i++){
        if(gcd(i,x)==1)
            s.insert(sg(x-i));
        s.insert(sg(i)^sg(x-i));
    }
    int res=0;
    while(s.count(res)) res++;
    SG[x]=res;
    return res;
}
int main(){
    int t;
    cin>>t;
    memset(SG,-1,sizeof(SG));
    SG[0]=0;SG[1]=1;
    while(t--){
        int n;
        cin>>n;
        //cout<<sg(n)<<endl;
        if(sg(n))
            cout<<"Teacher Ma"<<endl;
        else
            cout<<"Xiao Huo Zi"<<endl;
    }
}

D：混元功法

题意：

在一个二维平面上，有 n 个健身房，第 i 个健身房的坐标是（ Xi，Yi ）

满足（ X1 ，X2，X3 ... Xn ）是一个 1-n 的排列

满足（ Y1 ，Y2，Y3 ... Yn ）是一个 1-n 的排列

假设Teacher Ma现在在第 k 个健身房，他可以使用浑元功法完成下列操作任意次：

对于一个健身房 j ，如果 Xk < Xj 并且 Yk < Yj，或者 Xk > Xj 并且 Yk > Yj，那么Teacher Ma可以移动到健身房 j 。

求Teacher Ma在第i个健身房时最多可以到多少个健身房练功

思路：

并查集

代码：

#include<bits/stdc++.h>

using namespace std;
int x[1005],y[1005],n;
int father[1005];
int find(int x){
    int p=x,t;
    while(father[p]!=p) p=father[p];
    while(x!=p){t=father[x];father[x]=p;x=t;}
    return x;
}
int ans[1005];
int combine(int a,int b){
    int fa=find(a),fb=find(b);
    if(fa<fb){
        father[fb]=fa;
    }else{
        father[fa]=fb;
    }
}
void init(){
    for(int i=1;i<=n;i++)
        father[i]=i;
    for(int i=1;i<=n;i++){
        for(int j=i+1;j<=n;j++){
            if((x[i]<x[j]&&y[i]<y[j])||(x[i]>x[j]&&y[i]>y[j]))
                combine(i,j);
        }
    }
    memset(ans,0,sizeof(ans));
    for(int i=1;i<=n;i++){
        ans[find(i)]++;
    }
}
int main(){
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>x[i]>>y[i];
    }
    init();
    for(int i=1;i<=n;i++){
        cout<<ans[find(i)]<<endl;
    }
}

E：英国大力士

题意：

给定一个n

给一个数组a和一个数组b

取走第i个数的代价为a[i]+b[i-1]+b[i+1],取走左右两端合并

求最低代价

思路：

对数组a求和即为数组a的代价

对数组b区间dp求出最低代价

代码：

#include<bits/stdc++.h>

using namespace std;
int a,b[505];
int dp[505][505];
int main(){
    int n,sum=0;
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a;
        sum+=a;
    }
    memset(b,0,sizeof(b));
    for(int i=1;i<=n;i++){
        cin>>b[i];
    }
    for(int i=1;i<=n;i++){
        dp[i][i]=b[i-1]+b[i+1];
    }
    for(int len=2;len<=n;len++){
        for(int i=1;i<=n;i++){
            int j=i+len-1;
            if(j>n)break;
            dp[i][j]=0x3f3f3f3f;
            for(int k=i;k<=j;k++){
                dp[i][j]=min(dp[i][j],dp[i][k-1]+dp[k+1][j]+b[i-1]+b[j+1]);
            }
        }
    }
    cout<<dp[1][n]+sum<<endl;
    return 0;
}