P2930 [USACO09HOL]假期绘画Holiday Painting

    • 39通过
    • 83提交
  • 题目提供者 FarmerJohn2
  • 评测方式 云端评测
  • 标签 USACO 2009 高性能
  • 难度 省选/NOI-
  • 时空限制 1000ms / 128MB

题解

  • 提示:收藏到任务计划后,可在首页查看。
  • 体验新版界面

    最新讨论 显示

    推荐的相关题目 显示

    题目描述

    To show their spirit for the holidays, the cows would like to paint a picture! Their picture will be represented as an R x C (1 <= R <= 50,000; 1 <= C <= 15) grid of unit squares, each of which is either 0 or 1. The grid rows are conveniently numbered 1..R; the columns are numbered 1..C.

    Being pressed for time, the cows have asked their neighbors north of the border for help. Under the very helpful supervision of Canmuu the moose, they constructed a machine to throw paint at the picture in entire buckets! Beginning with all 0's in the picture grid, the machine splashes a certain paint color (either 0 or 1) over a

    rectangle in the grid. In particular, Canmuu suggested that they perform Q (1 <= Q <= 10,000) operations; operation i consists of five integers R1_i, R2_i, C1_i, C2_i, and X_i (1 <= R1_i <= R2_i <= R; 1 <= C1_i <= C2_i <= C; 0 <= X_i <= 1), meaning that the cows will paint each unit square with a row index between R1_i and R2_i, inclusive, and a column index between C1_i and C2_i, inclusive, with color X_i.

    However, painting a picture like this is quite prone to mistakes. So Canmuu has enlisted you to determine, after each operation, the number of unit squares in the grid which are the correct color.

    MEMORY LIMIT: 64 MB

    TIME LIMIT: 1.5 seconds

    [USACO09HOL]假期绘画Holiday Painting

    为了表达假日的激情,奶牛们要画一幅巨大的画.画布可以分成R*C个方格,从上到下编为1到R行,从左到右编为1到C列.作画的颜色有两种,白色(用0)或者黑色(用1表).

    由于时间紧迫,奶牛们不得不请教北面的邻居,卡门.卡门送给她们一台机器,一次操作只输入5个参数R1_i, R2_i, C1_i, C2_i, and X_i (1 <= R1_i <= R2_i <= R; 1 <= C1_i <= C2_i <= C; 0 <= X_i <= 1),

    把R1行到行R2,列C1到列C2的一个大长方形涂成色.在所有操作还未进行的时候,画 布是白色的.

    奶牛们一共要进行Q次操作.因为这样的画法总要出些差错,所以奶牛们想 请你算算,每一次操作过后,一共有多少个方格与她们的目标画里对应的方格是同色的.

    输入输出格式

    输入格式:

    * Line 1: Three space-separated integers: R, C, and Q

    * Lines 2..R+1: Line i+1 contains C characters, each '0' or '1', denoting the i-th row of the grid in the obvious way.

    * Lines R+2..R+Q+1: Line R+i+1 contains five space-separated integers representing a paint operation: R1_i, R2_i, C1_i, C2_i, and X_i

    输出格式:

    * Lines 1..Q: On line i+1, print a single integer representing the number of matching unit squares after the i-th operation.

    输入输出样例

    输入样例#1: 复制
    17 15 10 
    111111101111111 
    111111000111111 
    111110000011111 
    111100000001111 
    111000000000111 
    111100000001111 
    111000000000111 
    110000000000011 
    111000000000111 
    110000000000011 
    100000000000001 
    110000000000011 
    100000000000001 
    000000000000000 
    111111000111111 
    111111000111111 
    111111000111111 
    5 8 2 14 1 
    8 17 3 7 1 
    4 5 10 15 0 
    7 16 12 14 1 
    2 17 13 14 0 
    2 6 2 3 1 
    13 14 4 8 1 
    3 6 6 7 1 
    1 16 10 11 0 
    7 16 10 10 0 
    
    输出样例#1: 复制
    113 
    94 
    95 
    91 
    87 
    93 
    91 
    87 
    93 
    93 
    

    说明

    The cows want to paint a picture of a holiday tree

    After the first operation, the picture grid looks as follows:

    000000000000000

    000000000000000

    000000000000000

    000000000000000

    011111111111110

    011111111111110

    011111111111110

    011111111111110

    000000000000000

    000000000000000

    000000000000000

    000000000000000

    000000000000000

    000000000000000

    000000000000000

    000000000000000

    000000000000000

    There are 113 unit squares which match the corresponding square in the tree image; they are denoted below by an 'x' (the other bits are shown as they appear after the first paint splash):

    0000000x0000000

    000000xxx000000

    00000xxxxx00000

    0000xxxxxxx0000

    0xx111111111xx0

    0xxx1111111xxx0

    0xx111111111xx0

    0x11111111111x0

    000xxxxxxxxx000

    00xxxxxxxxxxx00

    0xxxxxxxxxxxxx0

    00xxxxxxxxxxx00

    0xxxxxxxxxxxxx0

    xxxxxxxxxxxxxxx

    000000xxx000000

    000000xxx000000

    000000xxx000000

    提示
    标程仅供做题后或实在无思路时参考。
    请自觉、自律地使用该功能并请对自己的学习负责。
    如果发现恶意抄袭标程,将按照I类违反进行处理。