CF 102897J - 大扫除

Rating: -
Tags: -
Solve time: 35s
Verified: yes

Solution

Problem Understanding

We are given several independent building descriptions. Each building consists of multiple floors, and each floor is represented by a string. Characters in the string describe whether a position contains trash and what type it is. A dot character represents an empty position, while any other character represents a trash item, and different characters correspond to different trash types.

For each floor, we are asked to count how many distinct trash types appear on that floor. Then we sum this value across all floors in the building. Finally, we output this total for each test case.

The key point is that distinctness is measured per floor independently. If the same trash type appears on multiple floors, it contributes separately on each floor where it appears. If a floor contains multiple occurrences of the same character, it still contributes only once for that floor.

The constraints imply a linear scan solution. The total number of characters across all floors in a test file can be up to 10^7. This immediately rules out any per-character expensive structure like sorting substrings or repeated set reinitialization with heavy overhead per query. We need an approach that processes each character essentially once, with constant-time updates.

A subtle failure case appears when one mistakenly aggregates trash types across the whole building instead of per floor. For example, consider:

Floor 1: a.a

Floor 2: aa.

Correct interpretation:

Floor 1 has {a} so contributes 1.

Floor 2 also has {a} so contributes 1.

Answer is 2.

A wrong global-set approach would treat it as one type total and output 1.

Another subtle case is repeated characters on the same floor. For example:

####

This should contribute 1, not 4.

Approaches

A straightforward interpretation is to process each floor independently, build a set of all non-dot characters in that string, and add its size to the answer. This is correct because a set naturally enforces uniqueness of trash types per floor.

However, the naive concern is performance. If we literally create a new set and insert each character, we still touch each character once, so the complexity is linear in total input size. The only potential overhead is hash set operations, but in Python this is still acceptable under the constraint of 10^7 total characters.

We can refine the implementation by avoiding repeated allocations or heavy object creation where possible. Instead of explicitly storing full sets for each floor, we can maintain a boolean marker array or a last-seen timestamp array for each character type. For each floor, we reset only the markers we used, which avoids clearing large structures.

The key observation is that we do not need to know which floors used a character, only whether it appeared on the current floor. So we can track seen characters per floor in O(1) marking operations.

Approach	Time Complexity	Space Complexity	Verdict
Per-floor set	O(total characters)	O(alphabet size)	Accepted
Timestamp / boolean array	O(total characters)	O(alphabet size)	Accepted

Algorithm Walkthrough

Read number of test cases. Each test case is independent, so we reset the accumulated answer for each one.
For each test case, initialize a global structure seen that records whether a character has already been counted on the current floor. This can be a dictionary or array depending on constraints.
Iterate over each floor string. Before processing a new floor, clear or reset only the state relevant to that floor. The important requirement is that no information from previous floors leaks into the current one.
Scan the string character by character. If the character is a dot, skip it immediately since it does not represent trash.
For any non-dot character, check whether it has already been counted for this floor. If not, mark it as seen and increase the floor contribution by 1. This ensures each trash type contributes at most once per floor.
After finishing the floor, add its contribution to the total answer.
Move to the next floor and repeat.

Why it works

Each floor is treated as an independent universe where we count distinct symbols among non-dot characters. The marking structure ensures that each symbol is counted once per floor, and the reset between floors guarantees independence. Because every character is processed exactly once and contributes at most one increment, the final sum exactly matches the definition of “sum of distinct trash types per floor”.

Python Solution

import sys
input = sys.stdin.readline

def solve():
    T = int(input())
    for _ in range(T):
        n = int(input())
        total = 0
        
        seen = set()
        
        for _ in range(n):
            s = input().strip()
            seen.clear()
            cnt = 0
            
            for ch in s:
                if ch == '.':
                    continue
                if ch not in seen:
                    seen.add(ch)
                    cnt += 1
            
            total += cnt
        
        print(total)

if __name__ == "__main__":
    solve()

The solution processes each test case independently and accumulates the answer floor by floor. The seen set is cleared for every floor, ensuring no cross-floor contamination of trash types. Each character is checked once, and insertion into a Python set guarantees uniqueness tracking in amortized constant time.

A common pitfall is forgetting to clear seen between floors, which would incorrectly merge trash types across different floors and inflate counts.

Worked Examples

Example 1

Input:

2
..#.
#...

Floor	String	Seen evolution	Floor contribution
1	`..#.`	{#, # already unique}	1
2	`#...`	{#}	1

Total answer is 2.

This confirms that identical trash types on different floors are counted separately.

Example 2

Input:

1
####
#..#

Floor	String	Seen evolution	Floor contribution
1	`####`	{#}	1
2	`#..#`	{#}	1

Total answer is 2.

This demonstrates deduplication within a floor: repeated symbols still count once.

Complexity Analysis

Measure	Complexity	Explanation
Time	O(total characters)	Each character is processed once and checked in O(1) average time in a set
Space	O(1)	At most 26 or bounded distinct symbols stored per floor

The total input size is up to 10^7 characters, and the algorithm performs a constant amount of work per character, which fits comfortably within typical 1-second limits in optimized Python with simple operations.

Test Cases

import sys, io

def run(inp: str) -> str:
    sys.stdin = io.StringIO(inp)
    from solution import solve  # assume solution is in solve()
    from contextlib import redirect_stdout
    out = io.StringIO()
    with redirect_stdout(out):
        solve()
    return out.getvalue().strip()

# provided sample style cases
assert run("""1
1
a""") == "1"

assert run("""1
2
a.a
aa.""") == "2"

# custom cases
assert run("""1
1
....""") == "0", "all empty"

assert run("""1
1
abcabc""") == "3", "dedup within floor"

assert run("""1
2
a
a""") == "2", "independent floors"

assert run("""1
3
a.b
.b.
aaa""") == "3", "mixed patterns"

Test input	Expected output	What it validates
all dots	0	no trash handling
repeated chars	3	per-floor uniqueness
same char across floors	2	independence
mixed patterns	3	general correctness

Edge Cases

One edge case is a floor with only dots, for example ".....". The algorithm clears seen, scans each character, finds no valid trash, and contributes 0. The set remains empty and the contribution is correctly zero.

Another edge case is extremely long single-floor input consisting of the same character, for example "aaaaaaaa...". The first occurrence inserts into seen, and all subsequent characters are ignored, producing a contribution of 1 regardless of length.

A third case is alternating floors with overlapping symbols, such as:

a.b
b.a

On the first floor, seen becomes {a, b} and contributes 2. On the second floor, seen is cleared and recomputed again as {a, b}, contributing 2 again. The reset ensures no carry-over, preserving correctness across floors.