韩山师范学院2024年度天梯赛选拔赛题解

1.空月祝福
#

解法：签到题。考察数学公式推算，先算一下给定的数字d能经历几个月，不难发现就是（d+29）/30，接着就可以带入计算了。

根据数据范围，也只有一个月，也可以直接输出\(300+d*90\) 代码如下：

#include<bits/stdc++.h>
using namespace std;
int main()
{
        int t;
        cin>>t;
        while(t--){
                int d;
                cin>>d;
                cout<<((d+30-1)/30)*300 + d*90<<endl;
        } 
}

2.叫“到”
#

解法：（ps:据说图中喊到的人曾经是蓝桥杯国一大哥）

考察数据结构-哈希表的使用，把输入的n个名字直接加入哈希表中，然后对于后面的m个查询，只需要判断名字在不在哈希表里即可。

#include<bits/stdc++.h>

using namespace std;
unordered_map<string,int>hashs;
int main()
{
        int n,m;
        cin>>n>>m;
        while(n--)
        {
                string str;
                cin>>str;
                hashs[str]++;
        }
        while(m--)
        {
                string str;
                cin>>str;
                if(hashs[str])cout<<"dao"<<endl;
                else cout<<"bu zai"<<endl;
         } 
}

3.找次品
#

解法：一道有点难的数学归纳题。可以发现把球分成三份算是比较快的，如果能是均等的，那每次分为三份，如果天平不平衡，轻的就是有次品的；如果天平平衡，没被称的就有次品的，所以能够排除掉两份。

总结出一个规律，当球的数量是3的整数次方是，答案就是log以3为底的n。

如果不是整数次方，就是log以3为底的n 向上取整。

这里枚举3的整数次方，如果有刚好等于3的整数次方就减1.

#include <bits/stdc++.h>
using namespace std;
#define el '\n'
const int N=1e3+4;
#define ll long long
#define vi vector<int>
ll pow3(ll k){
    int base=1;
    while (k--) base*=3;
    return base;
}
void solve(){
    ll n;
    cin>>n;
    ll res=0;
    if(n==2){
        cout<<1<<el;
        return;
    }
    for (int i = 1; i < 100000; ++i) {
        if(pow3(i)>n){
            res=i;
            if(pow3(i-1)==n){
                res=i-1;
            }
            break;
        }
    }
    cout<<res<<el;
}
int main() {
    int T=1;
    cin>>T;while (T--)
    solve();
    return 0;
}

4.新疗法
#

解法：先计算出旧疗法的有效率，接着把每个新疗法的有效率计算出来，然后按题意进行比较就可以了。

#include<bits/stdc++.h>

using namespace std;

int main()
{
        int n;
        cin>>n;
        double mx,my;
        cin>>mx>>my;
         mx = my/mx;
        for(int i =1;i<=n-1;i++)
        {
                double newm,newy;
                cin>>newm>>newy;
                double sum = newy/newm;
                if(sum-mx>0.05)cout<<"better"<<endl;
                else if(mx-sum>0.05)cout<<"worse"<<endl;
                else cout<<"same"<<endl;       
        } 
}

5.特立独行的字母
#

解法：把每个字母出现的次数记录一下，然后从头开始遍历字符串，找到第一个出现次数为1的字符打印出来break即可。

#include<bits/stdc++.h>

using namespace std;

int a[26];
int main()
{
        string str;
        cin>>str;
        for(int i = 0;i<str.size();i++)a[str[i]-'a']++;
        for(int i = 0; i< 26;i++)
                if(a[i]==1){
                        cout<<(char)(i+'a')<<endl;
                        break;
                }
}

6.世界商店·雅利洛-VI
#

解法：对价格从大到小排个序，然后一直买买买买到不能买为止。

#include<bits/stdc++.h>

#define x first
#define y second
using namespace std;

typedef pair<int,int>PII;
const int N= 100010;

int n,m;
PII p[N];

int main()
{
        cin>>n>>m;
        for(int i =1 ;i<=n;i++)
        {
                cin>>p[i].x>>p[i].y;
        }
        sort(p+1,p+n+1,[&](PII x, PII y){
                return x.x>y.x;
        });
        for(int i = 1;i<=n;i++)
        {
                if(m >= p[i].x)
                {
                        if(p[i].y == 0)
                        {
                                m = m -(m/p[i].x * p[i].x);
                        }
                        else
                        {
                                m = m -( min(m/p[i].x,p[i].y)*p[i].x);
                        }
                }
        }
        cout<<m<<endl;
        
}

7.艾丝妲的行星观测
#

解法：用单调栈来维护即可，对于每个正数，找到右边第一个负数，然后对栈顶的正数进行比较，判断谁会爆炸即可。

#include<bits/stdc++.h>

using namespace std;

//对于每一个行星，找到右边第一个和他相反符号的行星 （单调栈） 

const int N= 100010;
stack<int>st;

int nums[N];
int main()
{
        int n;
        cin>>n;
        for(int i =1;i<=n;i++)
        {
                cin>>nums[i];
        }

        int index = 1;
        for(int i =1;i<=n;i++)
        {
                if(nums[i]>0){
                        index =i;
                        break;
                }
        }
        
        for(int i =index;i<=n;i++)
        {
                //异号碰撞
                while(!st.empty()&& nums[st.top()]>0 && nums[i]<0 )
                {
                                int ti = abs(nums[i]);
                                if(ti > nums[st.top()])
                                {
                                        st.pop();
                                }
                                else if(ti == nums[st.top()])
                                {
                                        nums[i]=0;
                                        st.pop();                                }
                                else
                                {
                                        nums[i]=0;
                                }                }                if(nums[i]!=0)st.push(i);
        }
        cout<<st.size() + index - 1 <<endl;
        vector<int>ans;
        for(int i = 1;i<index;i++)ans.push_back(nums[i]);
        vector<int>res;
        while(st.size())
        {
                res.push_back(nums[st.top()]);
                st.pop();
        }
        for(int i = res.size()-1;i>=0;i--)ans.push_back(res[i]);
        if(ans.size()!=0){
                for(int i =0;i<ans.size()-1;i++)cout<<ans[i]<<" ";
                cout<<ans[ans.size()-1]<<endl;
        }
        return 0;
}

8.模拟宇宙
#

解法：题目实际题意就是要找从根节点到叶子结点的最大距离，dfs从根节点开始跑一遍到叶子结点就可以了。

#include<bits/stdc++.h>

using namespace std;

const int N = 10010;

int h[N],e[N],ne[N],idx;
int ans = 2e9;
unordered_map<int,int>hashs;
bool st[N];
int n,root;
void add(int a,int b)
{
        e[idx] = b;
        ne[idx]=h[a];
        h[a]=idx++;
}
void dfs(int root,int cur)
{
        cur +=hashs[root];
        //到叶子结点了
        if(h[root]==-1)
        {
                ans = min(ans,cur);
                return;
        }
        for(int i =h[root]; ~i ; i =ne[i])
        {
                int j = e[i];
                dfs(j,cur);
        }
}
int main()
{
        memset(h,-1,sizeof h);
        cin>>n;
        for(int i =1;i<=n;i++)
        {
                int x;
                cin>>x;
                hashs[i]=x;
        }
        for(int i = 1; i<=n -1 ;i++)
        {
                int a,b;
                cin>>a>>b;
                add(a,b);
                st[b]=true;
        }
        for(int i =1;i<=n;i++)
        {
                if(!st[i]){
                        root = i;
                }
        }
        dfs(root,0);
        cout<<ans<<endl;
        return 0;
}

9.下棋
#

解法：bfs模板题，先记录能跑的12个坐标（日和田），然后bfs跑一遍就可以了。

#include<bits/stdc++.h>

using namespace std;

typedef pair<int,int>PII;
const int N = 120;
int dx[12]={-2,-1,-1,-2,1,1,2,2,-2,-2,2,2},dy[12]={-1,-2,2,1,2,-2,-1,1,-2,2,2,-2};

bool st[N][N];
int cnt[N][N];
int bfs(int x,int y)
{
        //1到100
        memset(st,false,sizeof st);
        memset(cnt,0x3f,sizeof cnt);
        queue<PII>q;
        q.push({x,y});
        cnt[x][y]=0;
        st[x][y]=true;
        while(q.size())
        {
                auto t = q.front();
                q.pop();
                if(t.first==1 && t.second ==1)return cnt[1][1];
                for(int i =0;i<12;i++)
                {
                        int nx = t.first + dx[i];
                        int ny = t.second +dy[i];
                        if(nx<1||nx>100||ny<1||ny>100||st[nx][ny])continue;
                        if(cnt[nx][ny]>cnt[t.first][t.second]+1)
                        {
                                q.push({nx,ny});
                                st[nx][ny]=true;
                                cnt[nx][ny]=cnt[t.first][t.second]+1;
                        }
                }
        }
        return -1;
        
}
int main()
{
        int x1,y1,x2,y2;
        cin>>x1>>y1>>x2>>y2;
        cout<<bfs(x1,y1)<<endl;
        cout<<bfs(x2,y2)<<endl;        
}

10.赶路
#

迪杰斯特拉 dijkstra模板题。

#include<bits/stdc++.h>
#define x first
#define y second
using namespace std;

typedef pair<int,int>PII;
const int N = 30010;

int h[N], e[N],ne[N],w[N], idx;

int n,m;

int dist[N];

bool st[N];
void add(int a,int b,int c)
{
        e[idx]=b;
        w[idx]=c;
        ne[idx]=h[a];
        h[a]=idx++;
}

int dijsktra()
{
        dist[1]=0;
        priority_queue<PII,vector<PII>,greater<PII>>heap;
        heap.push({0,1});
        while(heap.size())
        {
                auto t = heap.top();
                heap.pop();
                int distance = t.first;
                int v = t.second;
                if(st[v])continue;
                st[v]=true;
                for(int i = h[v]; ~i; i =ne[i])
                {
                        int j = e[i];                        
                        if(dist[j]>distance+w[i]){
                                dist[j]=distance+w[i];
                                heap.push({distance+w[i],j});
                        }
                }
        }

        if(dist[n]==0x3f3f3f3f)return -1;
        return dist[n];
}
int main()
{
        memset(h,-1,sizeof h);
        memset(dist,0x3f,sizeof dist);
        memset(st,false,sizeof st);
        scanf("%d%d",&n,&m);
        for(int i = 1; i <=m;i++)
        {
                int a,b,c;
                cin>>a>>b>>c;
                add(a,b,c);
                add(b,a,c);
        }        cout<<dijsktra()<<endl;
}

11.雾雨魔理沙的魔法
#

假设不是循环数组注意到要子数组和相等，就满足如下条件

\(a[0]=a[k]=a[2k]=...\)

\(a[1]=a[k+1]=a[2k+1]=...\)

\(a[2]=a[k+2]=a[2k+2]=...\)

\( \cdots \) 然后可以把目标大小相同的数归在一类，最小的施法次数就是把这些数的变成它们的中位数。

回到循环数组的情况

既有n的循环，又有k的循环，根据裴蜀定理，就有\(gcd(n,k)\)的循环，就可以分成\(gcd(n,k)\)组，这样就转换成了不是循环数组的情况。

#include<bits/stdc++.h>
using namespace std;
long long makeSubKSumEqual(vector<int> &arr, int k) {
        int n = arr.size();
        k = __gcd(k, n);
        vector<vector<int>> g(k);
        for (int i = 0; i < n; ++i)
            g[i % k].push_back(arr[i]);

        long long ans = 0;
        for (auto &b: g) {
            nth_element(b.begin(), b.begin() + b.size() / 2, b.end());
            for (int x: b)
                ans += abs(x - b[b.size() / 2]);
        }
        return ans;
    }


int main()
{
   int n,k;
   cin>>n>>k;
   vector<int> a(n);
   for(int i=0;i<n;i++){
        cin>>a[i];
   }
   long long res=makeSubKSumEqual(a,k);
   cout<<res;
}

12.朋友还是敌人
#

使用并查集

将每个点x拆成两个：x和x+n（分别表示x的朋友和敌人）
如果x和y是朋友，就将x和y合并
如果x和y是敌人，就将x和y+n合并，将y和x+n合并
注意朋友的敌人不一定是敌人，因此如果x和y是朋友，不能将x+n和y+n合并

#include<bits/stdc++.h>
const int MAXN=4010;
using namespace std;
int n,m,siz[MAXN],fa[MAXN],vis[MAXN];
struct DSU{
    void SET(int nn){
        for(int i=1;i<=nn;i++)siz[i]=1, fa[i]=i;
    }
    int find(int x){
        if(!fa[x]||fa[x]==x)
            return fa[x]=x;
        return fa[x]=find(fa[x]);
    }
    void Union(int x,int y){
        int fax=find(x),fay=find(y);
        if(fax!=fay){
            if(siz[fax] > siz[fay])swap(fax, fay);
            fa[fax]=fay;
            siz[fay]+=siz[fax];
        }
    }
}dsu;//并查集，将朋友合并在一起
int main(){
    scanf("%d%d",&n,&m);
    char s[10];int xx,yy;
    dsu.SET(2*n);//初始化
    for(int i=1;i<=m;i++){
        scanf("%s%d%d",s,&xx,&yy);
        if(s[0]=='E'){
            dsu.Union(xx+n,yy),dsu.Union(xx,yy+n);//如果x，y是敌人，把x和y的敌人合并，把y和x的敌人合并。x+n是虚的敌人
        }else dsu.Union(xx,yy);//，如果是朋友，直接合并
    }
    int ans=0;
    for(int i=1;i<=n;i++){
        int p=dsu.find(i);//寻找每个人的祖先
        if(!vis[p]){//如果没有新的祖先，就是新的团伙
            vis[p]=true;
            ans++;
            }
    }
    printf("%d\n",ans);
    return 0;
}

1.空月祝福 #

2.叫“到” #

3.找次品 #

4.新疗法 #

5.特立独行的字母 #

6.世界商店·雅利洛-VI #

7.艾丝妲的行星观测 #

8.模拟宇宙 #

9.下棋 #

10.赶路 #

11.雾雨魔理沙的魔法 #

12.朋友还是敌人 #