P4733 纸的折痕（入门）

解题思路

把一张长方形的纸对折，每对折一次，折痕都与上次的折痕保持平行。对折 1 次得到 1 条折痕，对折 2 次得到 3 条，对折 3 次得到 7 条。问对折 n 次一共能得到几条折痕。

先观察规律：1 次得 1 条，2 次得 3 条，3 次得 7 条。细看会发现 1=2¹-1，3=2²-1，7=2³-1。也就是说，对折 n 次得到的折痕数 = 2ⁿ - 1。为什么是这个规律呢？因为每对折一次，纸变厚一层，原来已有的每条折痕都会被"复制"到纸的另一半上，折痕数大约翻一倍，再加上新压出的 1 条折痕，所以从第 1 次开始依次得到 1、3、7、15、31……正好每一项都是 2 的幂减 1。n 最大 19，2¹⁹-1=524287，完全在 long long 范围内。实现时用一个变量 r 从 1 开始连乘 n 次 2，最后输出 r-1 即可。边界情况：n=1 时循环 1 次，r=2，输出 1，正确。

参考代码

// 纸的折痕：长方纸对折n次可得到2^n-1条折痕
#include <iostream>
int main(){
  long long r=1;
  int n,i;
  std::cin>>n;
  for(i=1;i<=n;i++) r*=2;   // 每次对折折痕数翻倍再加1，正好等于2^n-1
  std::cout<<r-1;
  return 0;
}

复杂度分析

循环 n 次做乘法，时间 O(n)。空间上只用一个 long long 变量，是 O(1)。n 最多 19，循环 19 次就结束，运行飞快。