题目描述

时间限制：C/C++ 1秒，其他语言2秒

空间限制：C/C++ 256M，其他语言512M

一球从100米高度自由落下，每次落地后反跳回原高度的一半；再落下，求它在第n次落地时，共经过多少米？第n次反弹多高？（n<=10）

输入描述:

一行，一个整数n (1<=n<=10)。

输出描述:

输出两个浮点数ans1,ans2。ans1为第n次落地时，共经过的距离；ans2为第n次反弹的高度。答案应与标准答案误差小于1e-5。两个数间以空格相间。

输入例子1:

1

输出例子1:

100.000000 50.000000

输入例子2:

10

输出例子2:

299.609375 0.097656

思路描述

  • 输入的n比较小，不用做太多考虑；输出结果的格式是小数点后保留6位；输出以空格分隔
  • 每一次落地都包含一次反弹，ans1记录第n次落地时经过的距离，则不算最后一次反弹
  • ans2为第n次反弹后的高度，每次落地后更新其数值即可
#include <iostream>
#include <iomanip>
using namespace std;

int main(int argc, char *argv[]){
    cout << fixed << setprecision(6);
    int n;
    cin >> n;
    if(n < 1)return 0;
    double all = 0, end = 100;
    for(int i = 0; i < n; i++){
        all += end;
        end /= 2;
        all += end;
    }
    cout << all-end << ' ' << end;
    return 0;
}

题目描述

时间限制：C/C++ 1秒，其他语言2秒

空间限制：C/C++ 256M，其他语言512M

有n个人围成一圈，顺序排号。从第一个人开始报数（从1到3报数），凡报到3的人退出圈子，问最后留下的是原来第几号的那位。

输入描述:

一行，一个正整数n（1<=n<=1000000）。

输出描述:

输出答案。

输入例子1:

5

输出例子1:

4

例子说明1:

出局的编号依次为3,1,5,2，最后留下的是4

思路描述

典型的环形链表，处理约瑟夫环问题

  • 构建循环链表，使用双指针逐个剔除，运行超时

    #include <iostream>
using namespace std;
struct Node{
    int n;
    Node* next;
    Node(int i):n(i){}
};
int main(){
    int n;
    cin >> n;
    if(n == 1)return n;
    Node *head = new Node(1);
    Node *cur = head;
    
    //构建循环链表
    for(int i = 2; i <= n; i++){
        cur->next = new Node(i);
        cur = cur->next;
    }
    cur->next = head;
    
    Node *pre = nullptr;
    cur = head;
    int count = 1;
    
    while(cur != pre){
        if(count % 3 == 0){
            Node *temp = cur;
            cur = temp -> next;
            pre -> next = cur;
            delete temp;
        }
        else{
            pre = cur;
            cur = cur -> next;
            count++;
        }
    }
    cout << cur->n;
    delete cur;
    return 0;
}

  • 数学公式（递推推导）

    将数组看成环形的，使用一个指针指向环的起始（帮助理解）

    推理过程：每退出一个人，将重新开始计数 ---> 可以看成每退出一个人，指针指向退出位置的后一个，也就是起始位置后移M（相对的最终保留者的位置相对就前移M）

    将推理过程反过来，则可以得出状态公式：$F(N) = (F(N-1) + M) % N$，N个人时的胜利者的位置是N-1个人时胜利者的位置后移M位

    • F(N)表示N个人时，胜利者的位置
    • M表示每次相对偏移的个数
    • 环形数组，防止溢出，最后需要整除N
    理解示例：
问：假设，当有11个人时，胜利者的下标位置为6。那下一轮10个人时，胜利者的下标位置为多少？
答：第一轮删掉编号为3的人后，之后的人都往前面移动了3位，胜利这也往前移动了3位，所以他的下标位置由6变成3
问2：假设，当有10个人时，胜利者的下标位置为3。那下一轮11个人时，胜利者的下标位置为多少？
答：这可以看错是上一个问题的逆过程，大家都往后移动3位，所以f(11)=f(10)+3。不过有可能数组会越界，所以最后模上当前人数的个数，f(11,3)=（f(10,3)+3）%11

    因为求出的结果是数组中的下标，最终的编号还要加1

    #include <iostream>
using namespace std;

int main(){
    int n;
    cin>>n;
    int pos=0;
    for(int i=2;i<=n;i++)
    {
        pos=(pos+3)%i;
    }
    cout<<pos+1;
    return 0;
}

题目描述

时间限制：C/C++ 1秒，其他语言2秒

空间限制：C/C++ 256M，其他语言512M

小陆每天要写一份工作日报，日报标题含有日期。几年后，他翻开以前的日报，想知道两份日报的日期是否同为星期几，请编程帮助他判断。

输入描述:

第一行一个正整数T(1<=T<=100)。表示有T个测试样例。
接下来T行，每一行有6个正整数y1,m1,d1,y2,m2,d2,（以空格相间）。其中y1-m1-d1分别为第一个日期的年月日，y2-m2-d2分别为第二个日期的年月日。（满足1970<=y1,y2<=9999, 1<=m1,m2<=12, 1<=d1,d2<=31,且保证两个日期是合法的）。

输出描述:

输出T行，对应T个答案。对于每一行，如果两个日期在同一周，输出“True”；否则输出“False”（输出内容不含双引号）。

输入例子1:

2
1970 1 2 2020 2 7
2020 1 1 2020 1 2

输出例子1:

True
False

例子说明1:

1970-01-2和2020-02-7同为星期五；
2020-01-1为星期三，2020-01-2为星期四。

思路描述

计算两个日期之间的天数，

我们以题目样例1970-01-2星期五为的前一天1970-01-1为基准，这也是题目给的日期范围

需要注意每个月的天数、闰年等情况。

#include <stdio.h>
 
int CaculateWeekDay(int y,int m, int d)
{
    if(m==1||m==2) {
        m+=12;
        y--;
    }
    int iWeek=(d+2*m+3*(m+1)/5+y+y/4-y/100+y/400)%7;
      return iWeek + 1;
} 
 
int main(){
    int T;
    scanf("%d", &T);
    for(int i = 0; i < T; i++){
        int y1, m1, d1, y2, m2, d2;
        scanf("%d %d %d %d %d %d", &y1, &m1, &d1, &y2, &m2, &d2);
        if(CaculateWeekDay(y1, m1, d1) == CaculateWeekDay(y2, m2, d2)){
            printf("True\n");
        }else{
            printf("False\n");
        }
    }
    return 0;
}

基姆拉尔森计算公式

  1. 用途：给你年月日，计算今天星期几

  2. 公式：Week = (d+2m+3(m+1)/5+y+y/4-y/100+y/400+1) mod 7；

    1. d为几号
    2. m为月份
    3. y为年份

  3. 注：把一月和二月看为是上一年的十三月和十四月！！

  4. 样例：

    int Date(int y,int m,int d)
{
    if(m==1||m==2){//一二月换算
        m+=12;
        y--;
    }
    int week = (d + 2*m +3*(m+1)/5 + y + y/4 - y/100 + y/400 + 1)%7;
    return week;//其中1~7表示周一到周日
}

题目描述

时间限制：C/C++ 1秒，其他语言2秒

空间限制：C/C++ 256M，其他语言512M

段誉身具凌波微波，动无常则，若危若安，一次能走一级台阶或者两级台阶，他要爬一段30级的山路，问有多少种走法？分析如何计算，然后编程解答。 进阶问题：当他轻功熟练度提升，一次最多可以走三级，那就结果有什么变化？后来走火入魔了，不能走一级，只能走二或三级，又有什么变化？

输入描述:

输入一个数n（1<=n<=30），代表段誉要爬一段n级的山路。

输出描述:

输出三个整数a,b,c（以空格相间）。其中a为段誉一次能走一级或两级台阶的走法；b为段誉一次能走一级、二级或三级台阶的走法；c为段誉一次能走二级或三级台阶的走法。

输入1

3

输出1

3 4 1

思路描述

爬楼梯问题，动态规划，当前楼梯的可能情况由可以到当前楼梯的楼梯的可能情况决定。

状态方程：

  • 情况1：$a[n] = a[n-1] + a[n-2]$，a[1] = 1, a[2] = 1, a[3] = 3
  • 情况2：$b[n] = b[n-1] + b[n-2] + b[n-3]$，b[1] = 1, b[2] = 2, b[3] = 4;
  • 情况3：$c[n] = c[n-2] + c[n-3]$，c[1] = 0, c[2] = 1, c[3] = 1
#include <iostream>
using namespace std;
int a[31];
int b[31];
int c[31];
int main(){
    int n;
    cin >> n;
    b[1] = a[1] = 1;
    b[2] = a[2] = 2;
    a[3] = 3;
    b[3] = 4;
    c[1] = 0;
    c[2] = 1;
    c[3] = 1;
    for(int i = 4; i <= n; i++){
        a[i] = a[i-2] + a[i-1];
        b[i] = b[i-3] + b[i-2] + b[i-1];
        c[i] = c[i-3] + c[i-2];
    }
    cout << a[n] << ' ' << b[n] << ' ' << c[n];
    return 0;
}

第一题： 输入说明： 第一行输入n代表队伍中的人数 第二行输入队伍中每个人的身高（用空格隔开）

比如输入： 5 2 3 1 5 4 6 5 4 1 6 8 2

输出说明： 如果现在所在位置之前没有比自己身高高的，数值变为-1，如果现在所在位置之前有比自己身高高的，数值变为所在位置之前那个离自己最近的且比自己高的那个人的身高

上例的输入对应输出： 5 -1 -1 3 -1 5 6 -1 5 4 -1 -1 8

思路：使用一个数组存放身高，因为每个人都要和前面所有人比较，所以从最后一个人开始，使用二层循环，从后往前修改不影响前面数值的比较。

#include <iostream>

using std::cin;
using std::cout;
using std::endl;


int main(int argc, char* argv[]){
    int n;
    while(cin >> n){
        int *a = new int[n];
        for(int i = 0; i < n; i++){
            cin >> a[i];
        }
        for(int i = n-1; i >= 0; i--){
            int k = -1;
            for(int j = i - 1; j >= 0; j--){
                if(a[i] < a[j]){
                    k = j;
                    break;
                }
            }
            if(k == -1)a[i] = -1;
            else a[i] = a[k];
        }
        for(int i = 0; i < n; i++)cout << a[i] << ' ';
        cout << endl;
        delete[] a;
    }
    
    return 0;
}