首页 > 代码库 > Codeforces 461C Appleman and a Sheet of Paper(模拟)

Codeforces 461C Appleman and a Sheet of Paper(模拟)

题目链接:Codeforces 461C Appleman and a Sheet of Paper

题目大意:就是一个叠被子的过程,穿插着询问一段区间上被子的单位厚度。

解题思路:用前缀和数组模拟即可。因为对于折超过一半的处理为将令一半叠上来,所以需要变量记录当前被子的正反状态。处理好下标关系即可。

#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;
const int maxn = 1e6+5;

int N, Q, W[maxn];

int main () {
    scanf("%d%d", &N, &Q);
    for (int i = 1; i <= N; i++)
        W[i] = i;

    bool flag = false;
    int k, l, r;
    int n = N, bw = 0;

    while (Q--) {
        scanf("%d%d", &k, &l);

        if (k == 1) {
            if (l > n - l) {
                flag = !flag;
                l = n - l;
            }

            if (flag) {

                for (int i = 0; i < l; i++)
                    W[bw + n - l - i] += N - W[bw + n - l + i];

            } else {
                bw += l;
                for (int i = 0; i < l; i++)
                    W[bw + i] -= W[bw - i];
            }
            n -= l;

        } else {
            scanf("%d", &r);
            if (flag) {
                int tmp = n - r;
                r = n - l;
                l = tmp;
            }
            printf("%d\n", W[bw + r] - W[bw + l]);
        }
    }
    return 0;
}

Codeforces 461C Appleman and a Sheet of Paper(模拟)