890 . 彩色紙帶（除蟲題）

Submit
Status
Discussion / Solution
Ranklist
Back to Problems List

TopCoder

餘切
$\huge\text{owoovo is 8}$

User's AC Ratio

100.0% (4/4)

Submission's AC Ratio

100.0% (4/4)

Tags

ioicamp ioicamp-2025

Description

巴已己很喜歡各式各樣的演算法，例如幾何摺紙演算法。

今天，巴已己帶來了一條右至左切成 $n$ 等分的彩色紙帶，紙帶由右到左編號為 $1$ 至 $n$ 的正整數。一開始每一格都塗著顏色是 $c$ 的顏料。

巴已己很喜歡各種五顏六色的圖形，一個圖形越對稱，在巴已己心目中價值就會越高。雖然同樣顏色的紙帶一定是對稱的，不過巴已己覺得這樣實在過於單調，因此他決定動手修改上面的圖案。

具體來說，總共有 $q$ 件事情發生，每件事不外乎是下面的兩種之一：

  1. 巴已己塗色！第 $p_i$ 格的顏料被顏色 $c_i$ 的顏料蓋過去了。
  2. 巴已己摺紙！巴已己把位置 $p_i$ 作為中心點，看看整張紙有多麼對稱。

對於第二種事件，巴已己想知道整張紙不對稱的程度。他想，如果從中心點的一半折下去，如果有兩種不同顏色的顏料混在一起，等到整張紙要攤開的時候就會髒掉！
因此，不對稱的程度被定義為有多少對格子 $i, j$ 滿足他們與中心點的距離（編號差的絕對值）相同但顏色不同。

巴已己耽溺於藝術與對稱之中，只好請來己已巴幫他紀錄紙帶的顏色與計算不對稱的程度。
不過顯然己已巴是巴已己的相反，所以他一點也不喜歡演算法，自然寫出來的程式漏洞百出。

你能幫幫他在 edit distance 9 以內修好這段程式碼嗎？

Code 
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define N 2001

char *allocate() {
    return (char *)malloc((6 + 1) * sizeof(char));
}

int main() {
    int n, q;
    // who cares about memory leak?
    char *init_color = allocate();
    scanf("%d%6s%d", &n, init_color, &q);

    char *tape[n + 1] = {init_color};

    for (int i = 1; i <= q; ++i) {
        char op;
        scanf(" %c", &op);
        if (op == 'c') {
            int position;
            char *color = allocate();
            scanf("%d%6s", &position, color);
            tape[position] = color;
        } else if (op == 'f') {
            int center, ans = 0;
            scanf("%d", &center);
            for (int j = 1; j < center; j++)
                if (2 * center - j <= n)
                    ans += (strncmp(tape[j], tape[2 * center - j], 6) != 0);
            printf("%d\n", ans);
        }
    }
}

Input Format

輸入第一行有兩個正整數 $n, c$，依序代表紙帶的長度與初始紙帶的顏色。
第二行只有一個整數 $q$，代表事件的數量。

接下來的 $q$ 行會是兩種可能之一：

  • c $p_i$ $c_i$，代表「巴已己塗色！」
  • f $p_i$，代表「巴已己摺紙！」
  • $2 \leq n, q \leq 2000$
  • $1 \leq p_i \leq n$
  • $c, c_i$ 為恰好 6 位數的十六進位數字。

Output Format

對於每一次發生「巴已己摺紙！」，請輸出整張紙不對稱的程度。

Sample Input 1

9 1f1e33
5
c 1 114514
f 5
c 3 114514
f 2
f 3

Sample Output 1

1
0
1

Hints

數學上己已巴比巴已己還要大。

Problem Source

Subtasks

No. Testdata Range Constraints Score
1 0 範例測資 0
2 0~11 無額外限制 200

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 1000 262144 65536 1 2
1 1000 262144 65536 2
2 1000 262144 65536 2
3 1000 262144 65536 2
4 1000 262144 65536 2
5 1000 262144 65536 2
6 1000 262144 65536 2
7 1000 262144 65536 2
8 1000 262144 65536 2
9 1000 262144 65536 2
10 1000 262144 65536 2
11 1000 262144 65536 2
Submit
Back to Top