首页 > 试题广场 >

不想出差的HR

[编程题]不想出差的HR

热度指数：1901 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 32M，其他语言64M
算法知识视频讲解

按照卡中心校园招聘的要求，HR小招和小商需要从三个科室中（分别为A、B、C）抽派面试官去往不同城市。
两名HR按照以下规定轮流从任一科室选择面试官：每次至少选择一位，至多选择该科室剩余面试官数。最先选不到面试官的HR需要自己出差。
假设HR小招和小商都不想出差且每次选择都采取最优策略，如果是小招先选，写一个函数来判断她是否需要出差。如果不需要出差，请给出第一步的最优策略。

输入描述:

输入为三个正整数，分别代表三个科室的面试官人数，用英文逗号分隔

输出描述:

若小招需要出差，则输出：1；
若小招不需要出差，则输出：第一步选择的科室名称和选择人数，用英文逗号分隔

示例1

输入

1,8,9

输出

示例2

输入

2,0,4

输出

C,2

算法知识视频讲解

garengao

  
 
  标准的博弈论NIM游戏，具体证明我就不搬运了，最简单的就是先找规律，然后发现抑或可行，然后用反证法。 
  最简单假设 1,0,0 a先手，a必赢 1,1,0 a先手，a必输， 若 1,1,1 a先手，a取最优解，a 必赢，大致所有的样例都可以归为这3种 
  既然得知 亦或和k为0时 必输，  亦或不为0时则可赢， 
  k不为0时，肯定有一个数的第（k的最高位）位 与k相同，最后这个数与K亦或的值X 一定比这个数小，再做差就能得到最优步骤了。 
  下面这个代码在判定对哪个进行选派还是有点问题的，之前过了就没管了，今天写这个解析的时候才发现有点问题，懒得改了。 
  实在想要真正100%的话，就枚举呗，两两亦或 比第三个小的 情况就选第三个，然后做差 
  嗯，第一次写解析，乱七八糟的，不清楚地留言就行。 
  代码如下 
  import java.io.BufferedReader; 
  import java.io.InputStreamReader; 
  
 
  public class Main { 
  
 
      public static void main(String[] args) throws Exception { 
          // TODO Auto-generated method stub 
          BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); 
          int keshi[] = new int[3]; 
          String[] line = br. readLine().trim().split(","); 
          keshi[0] = Integer.parseInt(line[0]); 
          keshi[1] = Integer.parseInt(line[1]); 
          keshi[2] = Integer.parseInt(line[2]); 
          int res; 
          int k = keshi[0] ^ keshi[1] ^ keshi[2]; 
          if(k==0) { 
              System.out.println(1); 
          }else { 
              int i =0; 
              for(;i<3;i++) { 
                  if(highbit(k) == highbit(keshi[i])) { 
                      break; 
                  } 
              } 
              res = keshi[i]-(keshi[i]^k); 
              System.out.println((char)('A'+i) +","+res); 
          } 
      } 
        
      public static int highbit(int n) { 
          int res =0; 
          while(n>0) { 
              n /=2; 
              res++; 
          } 
          return res; 
      } 
  } 

发表于 2018-08-29 00:33:51 回复(2)

C/C++

nbgao

#include <bits/stdc++.h>
using namespace std;

int main(){
    int n, a[3], s;
    scanf("%d,%d,%d", &a[0], &a[1], &a[2]);
    s = a[0] ^ a[1] ^ a[2];
    if(s==0)
        printf("1\n");
    else{
        for(int i=0;i<3;i++){
            int x = s ^ a[i];
            if(a[i]-x < 0)
                continue;
            printf("%c,%d\n", 'A'+i, a[i]-x);
        }
    }
    return 0;
}

发表于 2020-10-20 00:28:30 回复(0)

wylu

https://baike.baidu.com/item/Nim%E6%B8%B8%E6%88%8F

关于寻找N-position移动到某个P-position的方法，参考第二个命题的证明

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

/**
 * Nim游戏
 * @author wylu
 */
public class Main {
    static String[] room = {"A", "B", "C"};

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] strs = br.readLine().split(",");
        int[] a = new int[strs.length];
        int k = 0;
        for (int i = 0; i < strs.length; i++) {
            a[i] = Integer.parseInt(strs[i]);
            k ^= a[i];
        }

        if (k == 0) {
            //P-position，先手必败
            System.out.println(1);
        } else {
            //N-position，先手必胜
            for (int i = 0; i < a.length; i++) {
                //寻找N-position移动到某个P-position的方法
                int num = k ^ a[i];
                if (a[i] - num >= 0) {
                    System.out.println(room[i] + "," + (a[i] - num));
                    break;
                }
            }
        }
    }
}

编辑于 2020-08-06 22:12:38 回复(4)

雾非雾selina

a=list(map(int,input().split(',')))
k=a[0]^a[1]^a[2]
room=['A','B','C']
if k==0:
    print(1)
else:
    for i in range(len(a)):
        num=k^a[i]
        if a[i]-num<0:
            continue
        print(room[i]+','+str(a[i]-num))

发表于 2019-06-11 16:30:47 回复(1)

Python

牛客302131191号

异或为0则必输；则非必输的情况下，需保证取完之后剩下的均异或为0

a,b,c=[int(num) for num in input().split(',')]

if a^b^c==0:
    print(1)
    exit()
if a==1:
    print('A,{}'.format(1))
    exit()
if b==1:
    print ('B,{}'.format(1))
    exit()
if c==1:
    print ('C,{}'.format(1) )
    exit()
for i in range(1,a):
    if b^c^(a-i)==0:
        print ('A,{}'.format(i) )
        exit()
for i in range(1,b):
    if a^c^(b-i)==0:
        print ('B,{}'.format(i) )
        exit()
for i in range(1,c):
    if b^a^(c-i)==0:
        print ('C,{}'.format(i) )
        exit()

发表于 2020-10-11 14:06:46 回复(0)

海拉鲁老实人

#include<stdio.h>
#include<iostream>
using namespace std;
pair<char,int> choose(int a,int b,int c){
    if(a==0&&b==0&&c==0)
        return {'D',0};
    if(a==0&&b==0)
        return {'C',c};
    if(a==0&&c==0)
        return {'B',b};
    if(b==0&&c==0)
        return {'A',a};
    pair<char,int> tmp;
    for(int i=a;i>=1;i--){
        tmp=choose(a-i,b,c);
        if(tmp.second==0)
            return {'A',i};
    }
    for(int i=b;i>=1;i--){
        tmp=choose(a,b-i,c);
        if(tmp.second==0)
            return {'B',i};
    }
    for(int i=c;i>=1;i--){
        tmp=choose(a,b,c-i);
        if(tmp.second==0)
            return {'C',i};
    }
    return {'D',0};
}
int main(){
    int a,b,c;
    scanf("%d,%d,%d",&a,&b,&c);
    pair<char,int> tmp=choose(a,b,c);
    if(tmp.second==0)
        cout<<1<<endl;
    else
        cout<<tmp.first<<","<<tmp.second<<endl;
    return 0;
}

🤣不知道Nim游戏，只能用搜索多过点case了。搜索的顺序很重要，3个for循环的顺序从大到小比较好，这样能通过83.3%的case，如果从小到大只能通过58%的case。

遇到这样的题目能多拿点分就多拿点吧，不强求。

编辑于 2020-03-04 10:46:46 回复(0)

提交观点

问题信息

C++工程师 iOS工程师安卓工程师运维工程师前端工程师算法工程师 PHP工程师贪心模拟 2018 数学招商银行信用卡中心 Java工程师

上传者：小小

难度：

6条回答 148收藏 5127浏览

通过挑战的用户

查看代码

牛客42922...

2023-03-12 18:50:34
牛客11351...

2022-09-18 10:18:25
英俊的嘟教授上岸了

2022-09-08 10:44:40
在春招的潜伏者...

2022-09-05 16:33:32
牛客24975...

2022-09-04 11:50:35

不想出差的HR

输入描述:

输出描述:

输入

输出

输入

输出

问题信息

热门推荐

通过挑战的用户

相关试题