Problem I. Block Combination Minimal Perimeter

问题描述

给定 n 个矩形方块，其中第 i 个方块的尺寸为 (1 $\times$ i)（即宽为 1，长为i）。要求将所有方块无重叠、无空隙地组合成一个实心矩形，求出该矩形的最小周长。若无法组合（题目保证一定可以组合），无需额外处理。

输入

  • 第一行：整数 n，表示方块的数量。

约束

  • (1 $\leq n $$\leq 2 $$\times 10^5$)

输出

组合成的矩形的最小周长。

思路

1. 总面积计算

每个方块的面积为其长与宽的乘积，即第 i 个方块的面积为 (1$\times i = i$)。因此，n 个方块的总面积 S 为前 n 个正整数的和，计算公式为：(S = $\frac{n(n+1)}{2}$) 该面积也是组合后矩形的面积，即矩形的长 a 与宽 b 需满足 (a $\times$ b = S)。

2. 最小周长的核心逻辑

矩形的周长公式为 (2 $\times$ (a + b))。在面积固定时，a 与 b 越接近，(a + b) 的值越小，对应的周长也越小。因此，问题转化为寻找满足 (a $\times$ b = S) 且 (a $\leq$ b) 的整数对 ((a, b))，使得 (a + b) 最小。

3. 高效枚举因子对

为找到最优的 a 和 b，需枚举所有可能的因子：

  • 枚举范围为 1 到 ($\sqrt{S}$)，对于每个整数 a，若 a 是 S 的因子，则对应的宽为 (b = S / a)。
  • 由于最大方块的尺寸为 ($1 \times n$)，组合后的矩形至少有一边不小于 n，因此枚举时需限制范围为 1 到 ($\min(\sqrt{S}, S/n)$)，确保能容纳最大方块。
  • 跟踪所有有效因子对中 (a + b) 的最小值，其对应的周长即为结果。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include<bits/stdc++.h>
using namespace std;
#define ll long long
int main() {
    ll n;cin>>n;
    ll s=n*(n+1)/2;
    ll q=sqrt(s);
    ll a=min(q, s/n);
    ll ans=2*(s+1);
    for(ll h=1;h<=a;++h) {
        if(s%h==0) {
            ll w=s/h;
            ll t=2*(h+w);
            if(t<ans) {ans=t;}
        }
    }
    cout<<ans<<endl;
    return 0;
}

解释

  1. 总面积计算：通过公式 (S = $\frac{n(n+1)}{2}$) 计算所有方块的总面积，这是组合后矩形的面积基础。
  2. 枚举范围确定：为确保矩形能容纳最大的 (1 $\times$ n) 方块，枚举高度 h 时上限设为 ($\min$($\sqrt{S}, S/n)$)，既保证因子对的有效性，又满足尺寸约束。
  3. 因子对检查：对每个可能的高度 h，检查其是否为 S 的因子，若是则计算对应的宽度 (w = S / h)，并更新最小周长。
  4. 结果输出：最终最小周长为最小 ((h + w)) 的 2 倍，即为组合矩形的最小周长。

复杂度分析

  • 时间复杂度：O($\sqrt{S}$)

Problem E. Mysterious XOR Operation

问题描述

定义神秘异或操作 ($\oplus_{m}$) 如下：对于两个数 a 和 b，先计算常规异或结果 (c = a $\oplus$ b)，再对 c 的二进制表示按以下规则处理：从最低有效位到最高有效位扫描，初始化计数器 (count = 0)，每遇到 1 则将 count 加 1，若 count 为奇数则保留该位，为偶数则清除该位（设为 0）。

给定一个长度为 N 的数组 A，计算所有无序对 ((i, j))（(i $\neq$ j)）的神秘异或结果之和，即 ($\sum_{i=1}^{N} $$\sum_{j>i}^{N}$ A_i $\oplus_{m}$ A_j) 。

输入

  • 第一行：整数 N（(2 $\leq$ N $\leq$ $10^5$)）。
  • 第二行：N 个整数 (a_i)（(0 $\leq$ a_i $\leq$ $10^8$)）。

输出

所有无序对的神秘异或结果之和。

思路

神秘异或的结果是二进制数，每一位的贡献相互独立，因此可按位计算贡献后累加。对于第 k 位（从 0 开始计数），若能确定其在所有无序对神秘异或结果中为 1 的次数，则总贡献为该次数乘以 $2^k$。

  1. 按位分析：对于第 k 位，仅需关注常规异或结果中该位为 1，且低 (k+1) 位中 1 的总个数为奇数的情况（此时该位在神秘异或中保留为 1）。
  2. 分类计数：对每个数的低 (k+1) 位，统计两类信息：第 k 位的值（0 或 1）、低 (k+1) 位中 1 的个数的奇偶性（0 或 1），得到四类计数 (c00, c01, c10, c11)。
  3. 有效对计算：满足条件的无序对数量为 (c00 $\times$ c11 + c01 $\times$ c10)，即第 k 位为 1 的总次数，乘以 $2^k$即为该位的贡献。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main(){
    int n;cin>>n;
    vector<int> a(n);
    for(int i=0;i<n;++i)cin>>a[i];
    ll M=30;
    ll ans=0;
    for(int k=0;k<=M;++k){
        ll c00=0,c01=0,c10=0,c11=0;
        int m=(1<<(k+1))-1;
        for(int x:a){
            int v=x&m,b=(v>>k)&1,p=0,t=v;
            while(t){p^=1;t&=t-1;}
            if(b==0){if(p==0)c00++;else c01++;}
            else{if(p==0)c10++;else c11++;}
        }
        ans+=c00*c11*(1<<k)+c01*c10*(1<<k);
    }
    cout<<ans<<endl;
    return 0;
}

时间复杂度

O(N)