牛客编程巅峰赛S1赛季第8场题解(钻石场)

牛牛的分配

思路:贪心。我们发现,为了使可以达到要求的瓶子尽可能地多的话,我们就要把原来已经达到要求的,而且多出来的水先收集起来,然后,按目前未达到的要求的瓶子的水量从少到多进行分配,直到把所有的多出来的水都被用完了或者已经不能再使得任何一个瓶子达到要求或者我们能把所有的瓶子都达到要求。
代码:

class Solution {
public:
    /**
     * 返回重新分配后,满足牛牛要求的水量的瓶子最多的数量
     * @param n int整型 瓶子的数量
     * @param x int整型 牛牛的对瓶中的水量要求
     * @param a int整型vector 每个瓶子中的含水量
     * @return int整型
     */
    int solve(int n, int x, vector<int>& a) {
        // write code here
        sort(a.begin(),a.end());
        long long sum=0;
        int k=-1;
        for(int i=n-1;i>=0;i--){
            if(a[i]<x){
                k=i;
                break;
            }
            else{
                long long tmp=a[i]-x;
                sum+=tmp;
            }
        }
        int ans=n;
        for(int i=k;i>=0;i--){
            long long tmp=x-a[i];
            if(sum<tmp){
                ans=n-i-1;
                break;
            }
            else  sum-=tmp;
        }
        return ans;
    }
};

playfair

思路:模拟+STL。这个题目有点复杂,关键是要先读懂题目来。我们首先要处理的问题是先根据输入的密钥求出相应的密码表,然后才好进行相应的查询操作。加密过程中的j都由i来代替。playfair加密算法首先需要绘制密码表,密码表是一个5*5的矩阵,开始由密钥按顺序排列,其余按照未出现的字母顺序。若密钥中含有重复字母需要将重复字母去掉,若有j用i来代替。这些话十分关键,它给了我们以下信息:
1、密码表肯定是5x5的,那么我们就可以开一个矩阵进行存储密码表。
2、如果密钥里面有j,就要用i来替换掉,也就是可以先把密钥的j都换成i,然后再转成密码表。
3、如果待加密的字符串里面有j,也要用i先进行替换,然后再根据密码表进行转换。
然后,介绍几个比较好的小技巧,我们对于每一个位置,假如我们想要快速的知道给位置在密码表中的具体的坐标的话,可以用一个map来进行映射,然后该字符的坐标用一个node结构体进行存储。这样,我们在比较相邻字符改如何进行转化的时候就可以比较快速的查询到每个字符的具体的坐标了。
代码:

class Solution {
public:
    /**
     * playfair加密算法
     * @param key string字符串 密钥
     * @param str string字符串 明文
     * @return string字符串
     */
   char c[6][6];
    bool inq[1000]={false};
    struct node{
        int x,y;
    };
    map<char,node> mp;
    string Encode(string key, string str) {
        // write code here
        int len=key.size();
        string rk;
        for(int i=0;i<len;i++){
            if(inq[key[i]]==false){
                if(key[i]=='j'){
                    rk+='i';
                    inq['j']=true;
                    inq['i']=true;
                    continue;
                }
                if(key[i]=='i')  inq['j']=true;
                rk+=key[i];
                inq[key[i]]=true;
            }
        }
        for(int i='a';i<='z';i++){
            if(inq[i]==false){
                if(i=='j') continue;
                rk+=i;
                inq[i]=true;
            }
        }
    //    cout<<rk<<endl;
        int k=0;
        for(int i=1;i<=5;i++){
            for(int j=1;j<=5;j++){
                c[i][j]=rk[k++];
                node Node;
                Node.x=i,Node.y=j;
                mp[c[i][j]]=Node;
            }
        }
        string ans;
        len=str.size();
        int x1,x2,y1,y2;
        for(int i=0;i<len;i++){
            if(str[i]=='j')  str[i]='i';
        }
        for(int i=0;i<len;i++){
            x1=mp[str[i]].x,y1=mp[str[i]].y;
            i++;
            if(i==len)  break;
            x2=mp[str[i]].x,y2=mp[str[i]].y;
            char s;
            //cout<<x1<<" "<<y1<<" "<<x2<<" "<<y2<<endl;
            if(x1!=x2&&y1!=y2){
                s=c[x1][y2];
                ans+=s;
                s=c[x2][y1];
                ans+=s;
            }
            else if(x1==x2&&y1==y2){
                ans+=str[i];
                ans+=str[i];
            }
            else if(x1==x2){
                if(y1==5)  y1=0;
                if(y2==5)  y2=0;
                s=c[x1][y1+1];
                ans+=s;
                s=c[x2][y2+1];
                ans+=s;
            }
            else if(y1==y2){
                if(x1==5)  x1=0;
                if(x2==5) x2=0;
                s=c[x1+1][y1];
                ans+=s;
                s=c[x2+1][y2];
                ans+=s;
            }
        }
        if(len&1)  ans+=str[len-1];
        return ans;
    }
};

牛牛摇骰子

思路:打表题。直接进行bfs肯定会被T,我们知道可以通过打表发现对于每个位置,都是在以11为周期进行变化的。然后初始的从1-11对应的答案分别为:3,2,1,2,3,2,1,2,3,2,1,但是这里有个例外就是当坐标在2的时候所需摇塞子的次数为4次,其余的就可以根据上面那个周期求得。没多出11就在原来的基础之上加上1.
代码:

class Solution {
public:
    /**
     * 把所有询问的答案按询问顺序放入vector里
     * @param arr int整型vector 要查询坐标的数组
     * @return int整型vector
     */
     //typedef long long ll;
     int a[12]={-1,3,2,1,2,3,2,1,2,3,2,1};
    vector<int> MinimumTimes(vector<int>& arr) {
        // write code here
        int len=arr.size();
        vector<int> ans;
        for(int i=0;i<len;i++){
            int num=arr[i];
            if(num==2)  ans.push_back(4);
            else{
                int cnt,id;
                if(num%11==0){
                    cnt=num/11-1;
                    id=11;
                }
                else{
                    cnt=num/11;
                    id=num%11;
                }
                int tmp=a[id]+cnt;
                ans.push_back(tmp);
            }
        }
        return ans;
    }
};
全部评论

相关推荐

07-07 12:25
门头沟学院 Java
程序员牛肉:你这个智邮公司做的就是那个乐山市税务系统的服务吗?
点赞 评论 收藏
分享
06-27 12:54
已编辑
门头沟学院 Java
累了,讲讲我的大学经历吧,目前在家待业。我是一个二本院校软件工程专业。最开始选专业是觉得计算机感兴趣,所以选择了他。本人学习计算机是从大二暑假结束开始的,也就是大三开始。当时每天学习,我个人认为Java以及是我生活的一部分了,就这样持续学习了一年半,来到了大四上学期末,大概是在12月中旬,我终于找的到了一家上海中厂的实习,但我发现实习生的工作很枯燥,公司分配的活也不多,大多时间也是自己在自学。就这样我秋招末才找到实习。时间来到了3月中旬,公司说我可以转正,但是转正工资只有7000,不过很稳定,不加班,双休,因为要回学校参加答辩了,同时当时也是心高气傲,认为可以找到更好的,所以放弃了转正机会,回学校准备论文。准备论文期间就也没有投递简历。然后时间来到了5月中旬,这时春招基本也结束了,然后我开始投递简历,期间只是约到了几家下场面试。工资也只有6-7k,到现在我不知道该怎么办了。已经没有当初学习的心劲了,好累呀,但是又不知道该干什么去。在家就是打游戏,boss简历投一投。每天日重一次。26秋招都说是针对26届的人,25怎么办。我好绝望。要不要参加考公、考研、央国企这些的。有没有大佬可以帮帮我。为什么感觉别人找工作都是顺其自然的事情,我感觉自己每一步都在艰难追赶。八股文背了又忘背了又忘,我每次都花很长时间去理解他,可是现在感觉八股、项目都忘完了。真的已经没有力气再去学习了。图片是我的简历,有没有大哥可以指正一下,或者说我应该走哪条路,有点不想在找工作了。
码客明:太累了就休息一下兄弟,人生不会完蛋的
如果实习可以转正,你会不...
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务