首页 > 试题广场 >

小度的部队

[编程题]小度的部队

热度指数：833 时间限制：C/C++ 2秒，其他语言4秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

小度的特种部队一共有n名士兵, 一天小度派所有士兵去探索野区。士兵们出发时沿着一条道路行进, 直到遇到三岔路口。
小度在出发前就给部队部署了部队划分规则: 当遇到三岔路口的时候, 部队若可以分为两个部分，并且两个部分的人数差恰好为k, 那么就完成部队划分, 划分的两个部分分别沿着两条路行进下去，否则该部队的所有士兵就在此位置停下扎营。
野区内有不计其数的三岔路口, 所以整个部队的每一个部分最终都会停下扎营，小度想知道最终扎营的总数为多少？

输入描述:

包括两个整数, 即部队中士兵的总人数和划分部队的参数。

输出描述:

一个整数，表示最终答案。

示例1

输入

10 2

输出

说明

10
/ \
6 4
/\ /\
4 2 3 1
/\
3 1
最终叶子节点个数即答案:5

算法知识视频讲解

JavaScript

Williammm

var lines = readline().split(" ")
var n = parseInt(lines[0])
var k = parseInt(lines[1])
var count = 0
function result(n,k){
if(n<=k||(n-k)%2){ //不能划分的话记录count次数+1
    return count+=1
}else{
    var a = result((n+k)/2,k)
    var b = result((n-k)/2,k)
}
}
result(n,k)
console.log(count)

JS代码简单明了

发表于 2021-08-25 20:55:03 回复(0)

难受啊兄弟

import java.util.Scanner;


public class Main {
    static int count = 0;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int k = sc.nextInt();
        recur(n, k);
        System.out.println(count);
    }

    private static void recur(int n, int k) {
        if (n <= 0 || (n - k) % 2 != 0 || n <= k) {
            count++;
            return;
        }
        // x + (x + k) = n ==> x = (n - k) / 2
        int x = (n - k) / 2;
        recur(x, k);
        recur(x + k, k);
    }
}

发表于 2022-09-13 01:19:31 回复(0)

寄了的喜羊羊很大胆

import java.util.Scanner;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    static int res=0;
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int a = in.nextInt();
        int b = in.nextInt();
        f(a,b);
        System.out.println(res+1);
    }

    public static void f(int count,int k){
        if(count<=k+1){
            return;
        }else{
            if((count-k)%2==0){
                res++;
                int left=(count-k)/2;
                int right=left+k;
                f(left,k);
                f(right,k);
            }
        }
    }
}

发表于 2023-10-15 19:17:46 回复(0)

quincy_sky

import java.util.Scanner;
import java.lang.Math;

public class Main{
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int n = scan.nextInt();
        int m = scan.nextInt();
        System.out.println(solve(n, m));
    }
    public static int solve(int n, int m) {
        if (n  <= m || (n - m) % 2 != 0) return 1;
        int avg = (n - m) / 2;
        int left = avg + m;
        int right = avg;
        return solve(left, m) + solve(right, m);
    }
}

编辑于 2023-03-16 16:48:18 回复(0)

gerfawilk

public class Main {
    private static int ans = 0;

    public static void dfs(int sum, int k) {
        if (sum < k + 2 || sum < k || (sum - k) % 2 != 0) {
            ans += 1;
            return;
        }
        dfs((sum - k) / 2, k);
        dfs((sum - k) / 2 + k, k);
    }
 
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int k = in.nextInt();
        dfs(n, k);
        System.out.println(ans);
    }
}

发表于 2023-03-13 15:24:02 回复(0)

细致的烤冷面在刷题

import java.util.Scanner;
import java.util.Queue;
import java.util.LinkedList;

public class Main {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int n=scanner.nextInt();
int k=scanner.nextInt();
int res=0;
Queue<Integer> queue=new LinkedList<>();
queue.add(n);
while(!queue.isEmpty()){
int e=queue.poll();
if((e-k)%2==0 && e>k){
queue.offer((e-k)/2);
queue.offer((e-k)/2+k);
}
else {
res++;
}
}
scanner.close();
System.out.println(res);
}
}

发表于 2023-03-11 14:50:23 回复(0)

聂海洲

import java.util.*;

public class Main{
public static void main(String[] args){
Scanner in = new Scanner(System.in);
int n = in.nextInt();
int k = in.nextInt();
System.out.println(fun(n, k));
}

public static int fun(int n, int k){
if(n > k + 1 && n % 2 == k % 2)
{
int h = n / 2 - k / 2;
return fun(h, k) + fun(n - h, k);
}
else
{
return 1;
}
}
}

发表于 2022-09-11 20:17:40 回复(0)

LBYW

import java.util.Scanner;
public class Main{
    public static int num = 0;
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int k = sc.nextInt();
        if(n<=k){
            System.out.println(1);
        }else{
            count(n,k);
        }
        System.out.println(num);
    }
    public static boolean isValid(int n,int k){
        if(n<=k)
            return false;
        if((n+k)%2==0)
            return true;
        return false;
    }
    public static void count(int n,int k){
        
        int x = 0;
        int y = 0;
        if(isValid(n,k)){
            x = (n+k)/2;
            y = n-x;
            //System.out.println("有效分解...."+x+" "+y);
            count(x,k);
            count(y,k);
        }else{
            num++;
            return;
        }
    }
}

发表于 2022-09-09 23:30:19 回复(0)

每天不断自我拉扯

import java.util.*;
public class Main{
public static void main(String args[]){
Deque<Integer> deque = new LinkedList<>();
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int k = sc.nextInt();
int sum = 0;
deque.push(n);
while(!deque.isEmpty()){
int[] arr = func(deque.peek(),k);
deque.pop();
if(arr.length==0){
sum++;
}else{
deque.push(arr[0]);
deque.push(arr[1]);
}
}
System.out.println(sum);
}
public static int[] func(int num,int k){
int left = 1;
int right = num-1;
while(left<right){
if(left+k==right){
return new int[]{left,right};
}else{
left++;
right--;
}
}
return new int[]{};
}
}

发表于 2022-04-19 17:38:01 回复(0)

刷题小蜜蜂

function prepost(n,k){
    let a=(n+k)/2;
    let b=(n-k)/2;
    if(a%1!=0||b%1!=0||a<=0||b<=0){
        res=res+1;
        return(res);
    }else{
    prepost(a,k);
    prepost(b,k);
    return res;}
}
 
var lines=readline().split(' ');
var n=lines[0];
var k=lines[1];
var res=0;
prepost(n,k);
console.log(res);

在本地可以成功运行，但是在牛客网上就提示：

“程序异常退出，请检查是否存在语法错误或者数组越界非法访问等情况

a.v8js:1: RangeError: Maximum call stack size exceeded

function prepost(n,k){”

到底为什么呀

发表于 2022-03-28 10:53:10 回复(0)

牛客435663740号

import java.util.Scanner;

public class Main{
    static int count=0;
    public static void main(String[] args) {
        Scanner Array=new Scanner(System.in);
        int n=Array.nextInt();
        int k=Array.nextInt();
        sprit(n,k);
        System.out.println(count);
    }
    private static void sprit(int n,int k) {
        if(n<=k||(n-k)%2!=0) {
            count++;
            return;
        }else {
            sprit((n+k)/2 ,k);
      sprit((n-k)/2, k);
      return;
        }
    }
}

发表于 2021-09-19 19:57:28 回复(0)

牛客468857724号

n, k = [int(v) for v in input().split()]
 
def separate(n, k):
    tmp = n-k
    if tmp > 0 and tmp%2 == 0:
        tmp_2 = tmp//2
        return separate(tmp_2+k, k) + separate(tmp_2, k)
    else:
        return 1
     
print(separate(n, k))

递归

发表于 2021-09-06 22:34:48 回复(0)

牛牛永不怕困难

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

public class Main {
static int count = 0;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String[] str = br.readLine().split(" ");
int n = Integer.parseInt(str[0]);
int k = Integer.parseInt(str[1]);
cal(n,k);
System.out.println(count);
}
private static void cal(int n, int k){
if( n<=k || (n-k)%2 !=0){
count++;
return;
}
cal((n+k)/2 ,k);
cal((n-k)/2, k);
return;
}
}

发表于 2021-09-06 13:33:09 回复(0)

黑莓婆婆

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

unordered_map<int, int> M;

int calc(int n, int k) {
    if (n <= k || (n - k) % 2) return 1;  // 不可再划分
    if (M.count(n)) return M[n];
    int res = calc((n - k) / 2, k) + calc((n + k) / 2, k);
    M[n] = res;
    return res;
}

int main() {
    int n, k;
    cin >> n >> k;
    cout << calc(n, k) << endl;
    return 0;
}

发表于 2021-07-17 10:31:45 回复(0)