1 条题解

  • 0
    @ 2025-11-18 15:42:50

    题目分析

    这是一个关于二进制表示和压缩形式的数学问题。我们需要计算从1到n的所有数的二进制表示中UFO的总数，并输出结果的压缩形式。

    关键概念

    1. UFO定义：序列中第一个1或最后一个1，且不和任何1相邻
    2. 压缩形式：用连续相同数位的数量表示二进制数
    3. 问题规模：n的二进制位数可达10^9，必须使用特殊算法

    UFO计数规律

    通过分析可以发现：

    • 对于二进制数，UFO出现在：
      • 最高位的1（总是UFO）
      • 最低位的1（如果是孤立的）
      • 中间孤立的1（前后都是0）

    核心思路

    题目给出的代码实现了一个巧妙的数学公式：

    sks(n) = ls + ps - cs

    其中：

    • ps = floor(n/2) + count1Groups(n)
    • cs = floor(log₂n) + 1
    • ls 是一个与n的最高几位相关的值

    代码解析

    数据结构设计

    class BigBin {
    vector<char> bVal;  // 每块的值(0或1)
    vector<int> bLen;   // 每块的长度
    int blockCount;     // 块数
    int capacity;       // 容量
};

    这种设计高效地表示了压缩形式的二进制数。

    主要算法步骤

    1. 读取输入：解析压缩形式的n
    2. 计算ps：floor(n/2) + 1的块数
    3. 计算cs：二进制位数
    4. 计算ls：根据n的最高位模式选择不同公式
    5. 最终计算：sks(n) = ls + ps - cs

    关键函数

    // 大数加法
BigBin* iterAdd(BigBinIter* it1, BigBinIter* it2);

// 大数减法  
BigBin* iterSub(BigBinIter* it1, BigBinIter* it2);

// 计算2的幂次
BigBin* powOfTwo(int k);

// 统计1的块数
int count1Groups(BigBin* b);

    完整代码

    #include <iostream>
#include <vector>
#include <cassert>
#include <cstdlib>
#include <memory>

using namespace std;

const int MAX_BLOCK_LEN = 1000000000;

class BigBin {
public:
    vector<char> bVal;
    vector<int> bLen;
    int blockCount;
    int capacity;

    BigBin(int blockCapacity = 0) : capacity(blockCapacity) {
        if (capacity > 0) {
            bVal.reserve(capacity);
            bLen.reserve(capacity);
        }
        blockCount = 0;
    }

    BigBin(const BigBin& other) {
        bVal = other.bVal;
        bLen = other.bLen;
        blockCount = other.blockCount;
        capacity = other.capacity;
    }

    BigBin& operator=(const BigBin& other) {
        if (this != &other) {
            bVal = other.bVal;
            bLen = other.bLen;
            blockCount = other.blockCount;
            capacity = other.capacity;
        }
        return *this;
    }
};

class BigBinIter {
public:
    BigBin* bigBin;
    int countLeft;
    char value;
    int nextBlock;

    BigBinIter(BigBin* b) : bigBin(b), countLeft(0), value(0), nextBlock(0) {
        rewindIterator();
    }

    bool atEnd() const {
        return countLeft == 0 && nextBlock == bigBin->blockCount;
    }

    void rewindIterator() {
        if (atEnd()) return;

        if (countLeft == 0) {
            countLeft = bigBin->bLen[nextBlock];
            assert(nextBlock == 0 || (1 - value) == bigBin->bVal[nextBlock]);
            value = bigBin->bVal[nextBlock];
            nextBlock++;
        }
    }

    void nextBlockInfo(int* length, int* val) {
        if (atEnd()) {
            *length = -1;
        } else {
            rewindIterator();
            *length = countLeft;
            *val = value;
        }
    }

    void step(int len) {
        while (true) {
            if (len == 0) return;
            if (atEnd()) return;
            
            rewindIterator();

            if (countLeft > len) {
                countLeft -= len;
                len = 0;
            } else {
                len -= countLeft;
                countLeft = 0;
            }
        }
    }
};

BigBinIter* getIterator(BigBin* b) {
    return new BigBinIter(b);
}

bool atEnd(BigBinIter* it) {
    return it->atEnd();
}

void rewindIterator(BigBinIter* it) {
    it->rewindIterator();
}

void nextBlock(BigBinIter* it, int* length, int* value) {
    it->nextBlockInfo(length, value);
}

void step(BigBinIter* it, int length) {
    it->step(length);
}

void stepCommonBlock(BigBinIter* it1, BigBinIter* it2, int* length,
                     int* value1, int* value2) {
    int l1, l2;
    nextBlock(it1, &l1, value1);
    nextBlock(it2, &l2, value2);

    if (l1 == -1 && l2 == -1) {
        *length = -1;
        return;
    }

    if (l1 == -1) {
        l1 = l2;
        *value1 = 0;
    }

    if (l2 == -1) {
        l2 = l1;
        *value2 = 0;
    }

    *length = (l1 < l2 ? l1 : l2);
    step(it1, *length);
    step(it2, *length);
}

void append(BigBin* b, int length, char value) {
    if (length == 0) return;
    
    if (b->blockCount != 0 && b->bVal[b->blockCount - 1] == value) {
        b->bLen[b->blockCount - 1] += length;
    } else {
        if (static_cast<int>(b->bVal.size()) <= b->blockCount) {
            b->bVal.push_back(value);
            b->bLen.push_back(length);
        } else {
            b->bVal[b->blockCount] = value;
            b->bLen[b->blockCount] = length;
        }
        b->blockCount++;
    }
}

BigBin* iterAdd(BigBinIter* it1, BigBinIter* it2) {
    BigBin* b = makeBigBin(2 * (it1->bigBin->blockCount + it2->bigBin->blockCount));
    int r = 0;

    while (true) {
        int len, val1, val2;
        stepCommonBlock(it1, it2, &len, &val1, &val2);

        if (len == -1) break;

        if (val1 == 0 && val2 == 0) {
            if (r == 0)
                append(b, len, 0);
            else {
                append(b, 1, 1);
                append(b, len - 1, 0);
                r = 0;
            }
        } else if (val1 + val2 == 1) {
            append(b, len, 1 - r);
        } else if (val1 == 1 && val2 == 1) {
            if (r == 0) {
                append(b, 1, 0);
                append(b, len - 1, 1);
            } else {
                append(b, len, 1);
            }
            r = 1;
        }
    }

    if (r == 1)
        append(b, 1, 1);

    fixLead(b);
    assertCorrect(b);
    
    delete it1;
    delete it2;
    return b;
}

BigBin* iterSub(BigBinIter* it1, BigBinIter* it2) {
    BigBin* b = makeBigBin(2 * (it1->bigBin->blockCount + it2->bigBin->blockCount));
    int r = 0;

    while (true) {
        int len, val1, val2;
        stepCommonBlock(it1, it2, &len, &val1, &val2);

        if (len == -1) break;

        if (val1 == 0 && val2 == 0) {
            append(b, len, r);
        } else if (val1 == 1 && val2 == 0) {
            if (r == 0)
                append(b, len, 1);
            else {
                append(b, 1, 0);
                append(b, len - 1, 1);
                r = 0;
            }
        } else if (val1 == 1 && val2 == 1) {
            append(b, len, r);
        } else if (val1 == 0 && val2 == 1) {
            if (r == 0) {
                append(b, 1, 1);
                append(b, len - 1, 0);
                r = 1;
            } else {
                append(b, len, 0);
            }
        }
    }

    assert(r == 0);
    fixLead(b);
    assertCorrect(b);
    
    delete it1;
    delete it2;
    return b;
}

BigBin* ofInt(int n) {
    BigBin* b = makeBigBin(32);

    while (n != 0) {
        append(b, 1, (n & 1));
        n /= 2;
    }

    assertCorrect(b);
    return b;
}

BigBin* powOfTwo(int k) {
    BigBin* b = makeBigBin(2);

    if (k > 0)
        append(b, k, 0);

    append(b, 1, 1);
    assertCorrect(b);
    return b;
}

BigBin* makeBigBin(int blockCount) {
    BigBin* b = new BigBin(blockCount);
    b->bVal.resize(blockCount);
    b->bLen.resize(blockCount);
    b->capacity = blockCount;
    b->blockCount = 0;
    return b;
}

BigBin* readBigBin() {
    int n;
    assert(cin >> n);
    BigBin* b = makeBigBin(n);
    b->blockCount = n;
    
    int val = 1;
    for (int i = n - 1; i >= 0; i--) {
        assert(cin >> b->bLen[i]);
        b->bVal[i] = val;
        val = 1 - val;
    }
    
    assertCorrect(b);
    return b;
}

void writeBigBin(BigBin* b) {
    assertCorrect(b);
    cout << b->blockCount << endl;
    for (int i = b->blockCount - 1; i >= 0; i--) {
        cout << b->bLen[i];
        if (i > 0)
            cout << " ";
        else
            cout << endl;
    }
}

int length(BigBin* b) {
    int cnt = 0;
    for (int i = 0; i < b->blockCount; i++) {
        cnt += b->bLen[i];
    }
    return cnt;
}

int bit(BigBin* b, int k) {
    int block = 0;

    while (true) {
        if (block >= b->blockCount)
            return 0;
        else if (k < b->bLen[block])
            return b->bVal[block];
        else {
            k -= b->bLen[block];
            block++;
        }
    }
}

void clearFirstBit(BigBin* b) {
    assert(b->bLen[b->blockCount - 1] > 0);
    assert(b->bVal[b->blockCount - 1] == 1);
    b->bLen[b->blockCount - 1]--;
    fixLead(b);
    assertCorrect(b);
}

int count1Groups(BigBin* b) {
    return (b->blockCount + 1) / 2;
}

void fixLead(BigBin* b) {
    while (b->blockCount > 0 && (b->bVal[b->blockCount - 1] == 0 || b->bLen[b->blockCount - 1] == 0)) {
        b->blockCount--;
    }
}

void assertCorrect(BigBin* b) {
#ifndef NDEBUG
    assert(b->blockCount <= b->capacity);

    if (b->blockCount == 0) return;

    assert(b->bVal[b->blockCount - 1] == 1);
    assert(b->bLen[b->blockCount - 1] > 0);
    
    for (int i = b->blockCount - 2; i >= 0; i--) {
        assert(1 - b->bVal[i + 1] == b->bVal[i]);
        assert(b->bLen[i] > 0);
        assert(b->bLen[i] <= MAX_BLOCK_LEN);
    }
#endif
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    BigBin* N = readBigBin();

    // ps = floor(N / 2) + count1Groups(N)
    BigBinIter* hN = getIterator(N);
    step(hN, 1);
    BigBin* ps = iterAdd(hN, getIterator(ofInt(count1Groups(N))));

    // cs = floor(lg(N)) + 1
    BigBin* cs = ofInt(length(N));

    // ls = 2 ^ (k-1) + (n mod 2^k), n=(10...)
    //      2 ^ k, n=(11...)
    BigBin* ls;
    int k = length(N) - 1;

    if (bit(N, k - 1) == 0) {
        clearFirstBit(N);
        BigBinIter* iter1 = getIterator(powOfTwo(k - 1));
        BigBinIter* iter2 = getIterator(N);
        ls = iterAdd(iter1, iter2);
        
        BigBinIter* iter3 = getIterator(ls);
        BigBinIter* iter4 = getIterator(ofInt(1));
        ls = iterAdd(iter3, iter4);
    } else {
        ls = powOfTwo(k);
    }

    BigBinIter* iter5 = getIterator(ls);
    BigBinIter* iter6 = getIterator(ps);
    BigBin* temp = iterAdd(iter5, iter6);
    
    BigBinIter* iter7 = getIterator(temp);
    BigBinIter* iter8 = getIterator(cs);
    BigBin* result = iterSub(iter7, iter8);
    
    writeBigBin(result);
    
    delete N;
    delete ps;
    delete cs;
    delete ls;
    delete temp;
    delete result;
    
    return 0;
}

    总结

    这道题的难点在于：

    1. 理解UFO的数学规律：需要发现二进制数中UFO出现的模式
    2. 处理超大整数：n的二进制长度可达10^9位，必须使用压缩表示
    3. 设计高效算法：直接在压缩形式上进行运算，避免解压缩
    4. 数学推导：找到计算sks(n)的闭式表达式

    代码通过精心设计的数据结构和算法，成功解决了这个看似不可能的问题，体现了数学建模和算法优化的完美结合。

    • 1

    「POI2010」01 序列计数 Ones

    信息

    ID
    4981
    时间
    1000ms
    内存
    256MiB
    难度
    10
    标签
    递交数
    4
    已通过
    1
    上传者
    1. 评测队列
    2. 服务状态
    3. 兼容模式
    4. 主题
    2. 黔ICP备2023002402号-2
    3. Worker 0, 34ms
    4. Powered by Hydro v4.19.1 Community, Modified by 33DAI