💻 ACM金牌团队🏅️ | 多次AK大厂笔试 ｜ 大厂实习经历

👏 感谢大家的订阅➕ 和 喜欢💗 和 手里的小花花🌸

✨ 笔试合集传送们 -> 🧷学长刷题笔记

🍒 本专栏已收集 140+ 套题 🍄 题面描述等均已改编，如果和你实际看到的题面描述不一样请理解，做法和题目本质基本不变。

🍹 感谢各位朋友们的订阅，你们的支持是我们创作的最大动力 💞

🎀 01.K小姐的生日派对

题目描述

K小姐即将迎来自己的生日,为了庆祝这个特殊的日子,她邀请了 位朋友参加生日派对。朋友们围坐在一张大圆桌周围,我们按照顺时针的方向将他们编号为 。

现在,K小姐想在朋友中选出一些人组成一个小组,并为这个小组拍照留念。为了照片的和谐美观,小组中的所有人必须坐在一起。K小姐想知道,一共有多少种不同的选择方案呢?

注意:

1. 由于圆桌的特殊性,编号为 的朋友同时与编号为 和 的朋友相邻。
2. 两个方案不同,当且仅当选出的朋友个数不同或者选出的朋友编号不完全相同。

输入格式

输入一个正整数 ,表示朋友的人数。

输出格式

输出一个整数,表示总的方案数。

样例输入

4

样例输出

13

数据范围

• 对于 的数据,。
• 对于 的数据,。
• 对于 的数据,。
• 对于 的数据,。

题解

本题可以通过数学分析的方法求解。我们将所有可能的方案分为两类:

1. 普通方案:即选出的朋友不是圆桌上所有人。在这种情况下,我们可以从任意一位朋友开始选择,然后再选出其之后(顺时针方向)连续的 到 位朋友,共 种方案。

2. 特殊方案:选出圆桌上所有的朋友。这种情况只有 种方案。

因此,总的方案数为 。

时间复杂度 ,空间复杂度 。

参考代码

• Python

n = int(input())
print(n * (n - 1) + 1)

• Java

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        System.out.println(n * (n - 1) + 1);
    }
}

• Cpp

#include <iostream>
using namespace std;

int main() {
    int n;
    cin >> n;
    cout << n * (n - 1) + 1 << endl;
    return