时间戳

首页 > 技术文章 > “科大讯飞杯”第十七届同济大学程序设计预选赛暨高校网络友谊赛(部分题解)

“科大讯飞杯”第十七届同济大学程序设计预选赛暨高校网络友谊赛(部分题解)

blogxsc 2020-05-11 20:18 原文

A 张老师和菜哭武的游戏

题意：天才程序员菜哭武和张老师有一天到一个城市旅游，旅途中菜哭武觉得无聊就想和张老师玩一个游戏。菜哭武有n个石子，每个石子都标有1到n之间到数，且各不相同，一开始他们会随机从这堆石子选一个石子放置到一个集合中，张老师选的数是a，菜哭武选的是b（a和b不相同）。接下来菜哭武和张老师轮流按照如下规则拿走一个石子：当石子x能被拿走时，当且仅当集合存在y和z，满足x等于y+z或者y-z，当x被拿走时，把它放到集合中。谁完成最后一轮操作时，谁获胜。张老师总是先手，于是张老师就好奇当决定好a和b时，他是否总是能获胜，你能帮助一下张老师吗？

题解：这一题比较坑，要过样例很简单，但要过这道题有点难，这里涉及到一个“裴蜀定理”，如果能理解这个这一题就比较简单了，理解之后，我们需要统计出区间[1,n]可以取出的数据个数，判断奇偶性即可，这里需要说明的一点是，当你按p=x*a+b*y(a,b题目给出)时候，第三个数也符合这个等式，这样就不难理解为什么之后取出的数都符合这个等式了。这样我们就只需要判断它的奇偶性就可以了。

代码：

#include<iostream>
#include<algorithm>
using namespace std;
int main(){
    int T,n,a,b;
    cin>>T;
    while(T--){
        cin>>n>>a>>b;
        int num=n/__gcd(a,b);
        if(num%2!=0){
            cout<<"Yes"<<endl;
        } else{
            cout<<"No"<<endl;
        }
    } 
    return 0;
}

个人感想：当第一次看到这一题的时候以为是个博弈（其实也可以归为“博弈”这一类吧），好不容易找到一个判断a,b奇偶性的方法，没有想到还是个错的，还是太嫩了。

B 伤害计算

题意：勇士菜哭武获得了一把新的武器，武器有特殊的伤害计算方式。武器的伤害计算方式由若干个部分的和组成,用+号连接。每一部分可以是一个整数a，或者是一个公式ndx。其中a表示固定伤害a点；ndx表示掷n个x面骰子，伤害是所有骰子点数的和。总伤害是每一部分伤害的和。比如2d6+1d70+3，表示掷两个6面骰子和一个70面骰子（不一定实际存在70面骰子，可以理解成1到70当中随机选择一个整数），再加上固定伤害3点。

      他正准备挑选一把好武器，需要计算新武器的伤害期望值，想让你帮他计算一下。

题解：这一题总的来说不难，你只要模拟这个过程就可以了，关键看你对字符串怎样处理，还有注意对浮点数的计算，这里可能会产生精度丢失

代码：

#include<iostream>
#include<vector>
using namespace std;
string ve[500000];
int main() {
    string ptr;
    cin>>ptr;
    int t=0;
    for(int i=0; i<ptr.length(); i++) {
        if(ptr[i]=='+') {
            t++;
        } else {
            ve[t]=ve[t]+ptr[i];
        }
    }
    //遍历每个部分
    double sum=0;
    for(int i=0; i<=t; i++) {
        if(ve[i].find('d')==-1) { //没找到
            int num=0;
            for(int j=0; j<ve[i].length(); j++) {
                num=num*10+(ve[i][j]-'0');
            }
            sum=sum+num;
        } else { //找到  算每一部分的期望值
            int t1=0,t2=0;
            for(int j=0; j<ve[i].find('d'); j++) {
                t1=t1*10+(ve[i][j]-'0');
            }//几颗骰子
            for(int j=ve[i].find('d')+1; j<ve[i].length(); j++) {
                t2=t2*10+(ve[i][j]-'0');
            }//是几面的
            double m1=(1+t2)*1.0/2;
            m1=m1*t1;
            sum=sum+m1;
        }
    }
    int S=int(sum);
    if(S==sum){
        cout<<S<<endl;
    }else{
        printf("%.1f\n",sum);
    }
    return 0;
}

个人感想：我感觉这一题挺简单的，有一个坑点比价坑：当sum为整数的时候，直接输出sum会WA，要将它转为int在输出，太坑了（我太菜了）。

F 排列计算

题意：天才程序员菜哭武和石头组队参加一个叫做国际排列计算竞赛 (International Competition of Permutation Calculation, ICPC) 的比赛，这个比赛的规则是这样的：

一个选手给出一个长度为 n 的排列，另一个选手给出 m 个询问，每次询问是一个形如 (l, r) 的数对，查询队友给出的排列中第 l 个数到第 r 个数的和，并将查询到的这个区间和加入总分，最后总分最高的队伍就能获胜。

石头手速很快，在比赛一开始就给出了 m 个询问；菜哭武也很强，他总是能找到最合适的排列，使得他们队的总分尽可能高。

在看比赛直播的你看到了石头给出的 m 个询问，聪明的你能不能预测出他们队伍最终的得分呢？

一个排列是一个长度为 n 的数列，其中 1 ~ n 中的每个数都在数列中恰好出现一次。比如 [1, 3, 2] 是一个排列，而 [2, 1, 4] 和 [1, 2, 3, 3] 不是排列。 

题解：这一题整体来说也算是一个比较简单的题，要使所得总分最大，我们就要使查询次数多的位置上放数值大的数据，但你直接统计每个数的查询次数的话会TLE，这个点应该卡了不少人，我们需要使用差分+前缀和来统计查询的次数。

代码：

#include<iostream>
#include<algorithm>
using namespace std;
int a[200005]={0},b[200005]={0};
int main(){
    int n,m;
    cin>>n>>m;
    int l,r;
    while(m--){
        cin>>l>>r;
        a[l]++;
        a[r+1]--;
    }
    for(int i=1;i<=n;i++){
        a[i]=a[i-1]+a[i];
    }
    sort(a+1,a+1+n);
    long long ans=0;
    for(long long i=1;i<=n;i++){
        ans=ans+i*a[i];
    }
    cout<<ans<<endl;
    return 0;
}

个人感想：这一题的关键是要知道怎样快速统计每一个数据的查询次数，不然肯定过不了。下面解释一下用“差分+前缀和”统计查询次数的方法：

我们初始化数组a[maxn]={0},假设我们只查询一个区间[1,3],按照步骤，a[1]++,a[3+1]--,之后我们就进前缀和处理，a[1]=a[0]+a[1]=1,这1查询的次数，a[2]=a[1]+a[2]=1,这是2查询的次数，a[3]=a[2]+a[3]=1,这3查询的次数，巧妙的是，这个时候a[4],在进行前缀和之后为0，它的查询次数也是0。这样我们就可以将一个查询区间推广到多个区间，原理是一样的。

 

推荐阅读