2021 ICPC 沈阳站 D题 Journey to Un‘Goro (打表+找规律)

2021 ICPC 沈阳站 D.Journey to Un'Goro

【链接】http://codeforces.com/gym/103202/problem/D

【题意】

Recently, you’ve taken a trip to Un’Goro.
A small road in Un’Goro has attracted your eyes. The road consists of n steps, each colored either red or blue.
When you go from the ith step to the jth, you count the number of red steps you’ve stepped. You will be satisfied if the number is odd.
“What is the maximum number of pairs ( i , j ) ( 1 ≤ i ≤ j ≤ n ) (i,j) (1≤i≤j≤n) (i,j)(1≤i≤j≤n), such that I’ll be satisfied if I walk from the ith step to the j j j th?” you wonder. Also, how to construct all colorings such that the number of pairs is maximized?
构造长度为 n n n的一条路,每一块的颜色为red或者blue。
红色块数为奇数的区间为满意。
现要求输出最大的满意区间个数,并构造出符合最大值的全部路径。

【输入】

The only line contains an integer n ( 1 ≤ n ≤ 1 0 5 ) n (1≤n≤10^5) n(1≤n≤105), indicating the number of steps of the road.

【输出】

Output an integer in the first line, denoting the maximum number of pairs that make you satisfied.
Each of the following several lines contains a string with length n that represents a coloring scheme, in lexicographically ascending order. The ith character is the color of the ith step, where r is for red and b for blue.
If there are more than 100 different colorings, just find the lexicographically smallest 100 colorings.
Note that in lexicographical order, b is ordered before r.
(按字典序取前 100 100 100种)

【思路】

最大的满意区间个数应该不必多说了,随便模几组样例,很好发现,当道路每一块都是红色的时候一定最优: a n s 奇 = ( n + 1 ) 2 2 , a n s 偶 = n 2 + 2 × n 2 ans_{奇}=\frac{(n+1)^2}{2},ans_{偶}=\frac{n^2+2 \times n}{2} ans奇​=2(n+1)2​,ans偶​=2n2+2×n​。
因为只输出前100组解,我们自然会想到,能否暴力,于是先敲一个暴力的打表程序。

n=7,这个时候,看不出什么规律
all_num=8     num=1   bbbrbbb
all_num=17    num=2   bbrbbbr
all_num=19    num=3   bbrbbrr
all_num=22    num=4   bbrbrrb
all_num=28    num=5   bbrrrbb
all_num=34    num=6   brbbbrb
all_num=37    num=7   brbbrbr
all_num=39    num=8   brbbrrr
all_num=42    num=9   brbrbrb
all_num=45    num=10  brbrrbr
all_num=47    num=11  brbrrrr
all_num=52    num=12  brrbrbb
all_num=57    num=13  brrrbbr
all_num=59    num=14  brrrbrr
all_num=62    num=15  brrrrrb
all_num=68    num=16  rbbbrbb
all_num=73    num=17  rbbrbbr
all_num=75    num=18  rbbrbrr
all_num=78    num=19  rbbrrrb
all_num=82    num=20  rbrbbrb
all_num=85    num=21  rbrbrbr
all_num=87    num=22  rbrbrrr
all_num=90    num=23  rbrrbrb
all_num=93    num=24  rbrrrbr
all_num=95    num=25  rbrrrrr
all_num=100   num=26  rrbbrbb
all_num=105   num=27  rrbrbbr
all_num=107   num=28  rrbrbrr
all_num=110   num=29  rrbrrrb
all_num=114   num=30  rrrbbrb
all_num=117   num=31  rrrbrbr
all_num=119   num=32  rrrbrrr
all_num=122   num=33  rrrrbrb
all_num=125   num=34  rrrrrbr
all_num=127   num=35  rrrrrrr
n=8时,依旧看不出什么
all_num=8     num=1   bbbbrbbb
all_num=16    num=2   bbbrbbbb
all_num=17    num=3   bbbrbbbr
all_num=19    num=4   bbbrbbrr
all_num=22    num=5   bbbrbrrb
all_num=28    num=6   bbbrrrbb
all_num=33    num=7   bbrbbbbr
all_num=34    num=8   bbrbbbrb
all_num=35    num=9   bbrbbbrr
all_num=37    num=10  bbrbbrbr
all_num=38    num=11  bbrbbrrb
all_num=39    num=12  bbrbbrrr
all_num=42    num=13  bbrbrbrb
all_num=44    num=14  bbrbrrbb
all_num=45    num=15  bbrbrrbr
all_num=47    num=16  bbrbrrrr
all_num=52    num=17  bbrrbrbb
all_num=56    num=18  bbrrrbbb
all_num=57    num=19  bbrrrbbr
all_num=59    num=20  bbrrrbrr
all_num=62    num=21  bbrrrrrb
all_num=66    num=22  brbbbbrb
all_num=68    num=23  brbbbrbb
all_num=69    num=24  brbbbrbr
all_num=71    num=25  brbbbrrr
all_num=73    num=26  brbbrbbr
all_num=74    num=27  brbbrbrb
all_num=75    num=28  brbbrbrr
all_num=77    num=29  brbbrrbr
all_num=78    num=30  brbbrrrb
all_num=79    num=31  brbbrrrr
all_num=82    num=32  brbrbbrb
all_num=84    num=33  brbrbrbb
all_num=85    num=34  brbrbrbr
all_num=87    num=35  brbrbrrr
all_num=89    num=36  brbrrbbr
all_num=90    num=37  brbrrbrb
all_num=91    num=38  brbrrbrr
all_num=93    num=39  brbrrrbr
all_num=94    num=40  brbrrrrb
all_num=95    num=41  brbrrrrr
all_num=100   num=42  brrbbrbb
all_num=104   num=43  brrbrbbb
all_num=105   num=44  brrbrbbr
all_num=107   num=45  brrbrbrr
all_num=110   num=46  brrbrrrb
all_num=113   num=47  brrrbbbr
all_num=114   num=48  brrrbbrb
all_num=115   num=49  brrrbbrr
all_num=117   num=50  brrrbrbr
all_num=118   num=51  brrrbrrb
all_num=119   num=52  brrrbrrr
all_num=122   num=53  brrrrbrb
all_num=124   num=54  brrrrrbb
all_num=125   num=55  brrrrrbr
all_num=127   num=56  brrrrrrr
all_num=132   num=57  rbbbbrbb
all_num=136   num=58  rbbbrbbb
all_num=137   num=59  rbbbrbbr
all_num=139   num=60  rbbbrbrr
all_num=142   num=61  rbbbrrrb
all_num=145   num=62  rbbrbbbr
all_num=146   num=63  rbbrbbrb
all_num=147   num=64  rbbrbbrr
all_num=149   num=65  rbbrbrbr
all_num=150   num=66  rbbrbrrb
all_num=151   num=67  rbbrbrrr
all_num=154   num=68  rbbrrbrb
all_num=156   num=69  rbbrrrbb
all_num=157   num=70  rbbrrrbr
all_num=159   num=71  rbbrrrrr
all_num=162   num=72  rbrbbbrb
all_num=164   num=73  rbrbbrbb
all_num=165   num=74  rbrbbrbr
all_num=167   num=75  rbrbbrrr
all_num=169   num=76  rbrbrbbr
all_num=170   num=77  rbrbrbrb
all_num=171   num=78  rbrbrbrr
all_num=173   num=79  rbrbrrbr
all_num=174   num=80  rbrbrrrb
all_num=175   num=81  rbrbrrrr
all_num=178   num=82  rbrrbbrb
all_num=180   num=83  rbrrbrbb
all_num=181   num=84  rbrrbrbr
all_num=183   num=85  rbrrbrrr
all_num=185   num=86  rbrrrbbr
all_num=186   num=87  rbrrrbrb
all_num=187   num=88  rbrrrbrr
all_num=189   num=89  rbrrrrbr
all_num=190   num=90  rbrrrrrb
all_num=191   num=91  rbrrrrrr
all_num=196   num=92  rrbbbrbb
all_num=200   num=93  rrbbrbbb
all_num=201   num=94  rrbbrbbr
all_num=203   num=95  rrbbrbrr
all_num=206   num=96  rrbbrrrb
all_num=209   num=97  rrbrbbbr
all_num=210   num=98  rrbrbbrb
all_num=211   num=99  rrbrbbrr
all_num=213   num=100 rrbrbrbr
n=20的情况,这个时候会发现,打出来的图案开始有了规律,我们按照第一个r出现的位置,可以对其进行分块
分块后发现,对于20的情况,可以分成4个块:
all_num=512   num=1   bbbbbbbbbbrbbbbbbbbb //①第一个块单独一列,r在中间
all_num=1024  num=2   bbbbbbbbbrbbbbbbbbbb //②第二个块r往前挪后,后半部分每次最多出现两个r
all_num=1025  num=3   bbbbbbbbbrbbbbbbbbbr //并成表现成梯状
all_num=1027  num=4   bbbbbbbbbrbbbbbbbbrr
all_num=1030  num=5   bbbbbbbbbrbbbbbbbrrb
all_num=1036  num=6   bbbbbbbbbrbbbbbbrrbb
all_num=1048  num=7   bbbbbbbbbrbbbbbrrbbb
all_num=1072  num=8   bbbbbbbbbrbbbbrrbbbb
all_num=1120  num=9   bbbbbbbbbrbbbrrbbbbb
all_num=1216  num=10  bbbbbbbbbrbbrrbbbbbb
all_num=1408  num=11  bbbbbbbbbrbrrbbbbbbb
all_num=1792  num=12  bbbbbbbbbrrrbbbbbbbb
all_num=2049  num=13  bbbbbbbbrbbbbbbbbbbr //③第三块形状和第二块相近
all_num=2050  num=14  bbbbbbbbrbbbbbbbbbrb //但是多行拼接成的形状犹如下降的格子
all_num=2051  num=15  bbbbbbbbrbbbbbbbbbrr //但是直接分析出它规律还是比较困难
all_num=2053  num=16  bbbbbbbbrbbbbbbbbrbr
all_num=2054  num=17  bbbbbbbbrbbbbbbbbrrb
all_num=2055  num=18  bbbbbbbbrbbbbbbbbrrr
all_num=2058  num=19  bbbbbbbbrbbbbbbbrbrb
all_num=2060  num=20  bbbbbbbbrbbbbbbbrrbb
all_num=2061  num=21  bbbbbbbbrbbbbbbbrrbr
all_num=2063  num=22  bbbbbbbbrbbbbbbbrrrr
all_num=2068  num=23  bbbbbbbbrbbbbbbrbrbb
all_num=2072  num=24  bbbbbbbbrbbbbbbrrbbb
all_num=2073  num=25  bbbbbbbbrbbbbbbrrbbr
all_num=2075  num=26  bbbbbbbbrbbbbbbrrbrr
all_num=2078  num=27  bbbbbbbbrbbbbbbrrrrb
all_num=2088  num=28  bbbbbbbbrbbbbbrbrbbb
all_num=2096  num=29  bbbbbbbbrbbbbbrrbbbb
all_num=2097  num=30  bbbbbbbbrbbbbbrrbbbr
all_num=2099  num=31  bbbbbbbbrbbbbbrrbbrr
all_num=2102  num=32  bbbbbbbbrbbbbbrrbrrb
all_num=2108  num=33  bbbbbbbbrbbbbbrrrrbb
all_num=2128  num=34  bbbbbbbbrbbbbrbrbbbb
all_num=2144  num=35  bbbbbbbbrbbbbrrbbbbb
all_num=2145  num=36  bbbbbbbbrbbbbrrbbbbr
all_num=2147  num=37  bbbbbbbbrbbbbrrbbbrr
all_num=2150  num=38  bbbbbbbbrbbbbrrbbrrb
all_num=2156  num=39  bbbbbbbbrbbbbrrbrrbb
all_num=2168  num=40  bbbbbbbbrbbbbrrrrbbb
all_num=2208  num=41  bbbbbbbbrbbbrbrbbbbb
all_num=2240  num=42  bbbbbbbbrbbbrrbbbbbb
all_num=2241  num=43  bbbbbbbbrbbbrrbbbbbr
all_num=2243  num=44  bbbbbbbbrbbbrrbbbbrr
all_num=2246  num=45  bbbbbbbbrbbbrrbbbrrb
all_num=2252  num=46  bbbbbbbbrbbbrrbbrrbb
all_num=2264  num=47  bbbbbbbbrbbbrrbrrbbb
all_num=2288  num=48  bbbbbbbbrbbbrrrrbbbb
all_num=2368  num=49  bbbbbbbbrbbrbrbbbbbb
all_num=2432  num=50  bbbbbbbbrbbrrbbbbbbb
all_num=2433  num=51  bbbbbbbbrbbrrbbbbbbr
all_num=2435  num=52  bbbbbbbbrbbrrbbbbbrr
all_num=2438  num=53  bbbbbbbbrbbrrbbbbrrb
all_num=2444  num=54  bbbbbbbbrbbrrbbbrrbb
all_num=2456  num=55  bbbbbbbbrbbrrbbrrbbb
all_num=2480  num=56  bbbbbbbbrbbrrbrrbbbb
all_num=2528  num=57  bbbbbbbbrbbrrrrbbbbb
all_num=2688  num=58  bbbbbbbbrbrbrbbbbbbb
all_num=2816  num=59  bbbbbbbbrbrrbbbbbbbb
all_num=2817  num=60  bbbbbbbbrbrrbbbbbbbr
all_num=2819  num=61  bbbbbbbbrbrrbbbbbbrr
all_num=2822  num=62  bbbbbbbbrbrrbbbbbrrb
all_num=2828  num=63  bbbbbbbbrbrrbbbbrrbb
all_num=2840  num=64  bbbbbbbbrbrrbbbrrbbb
all_num=2864  num=65  bbbbbbbbrbrrbbrrbbbb
all_num=2912  num=66  bbbbbbbbrbrrbrrbbbbb
all_num=3008  num=67  bbbbbbbbrbrrrrbbbbbb
all_num=3328  num=68  bbbbbbbbrrbrbbbbbbbb
all_num=3584  num=69  bbbbbbbbrrrbbbbbbbbb
all_num=3585  num=70  bbbbbbbbrrrbbbbbbbbr
all_num=3587  num=71  bbbbbbbbrrrbbbbbbbrr
all_num=3590  num=72  bbbbbbbbrrrbbbbbbrrb
all_num=3596  num=73  bbbbbbbbrrrbbbbbrrbb
all_num=3608  num=74  bbbbbbbbrrrbbbbrrbbb
all_num=3632  num=75  bbbbbbbbrrrbbbrrbbbb
all_num=3680  num=76  bbbbbbbbrrrbbrrbbbbb
all_num=3776  num=77  bbbbbbbbrrrbrrbbbbbb
all_num=3968  num=78  bbbbbbbbrrrrrbbbbbbb
all_num=4098  num=79  bbbbbbbrbbbbbbbbbbrb //④第四个块由于展示不完整,就非常难以描述规律了
all_num=4100  num=80  bbbbbbbrbbbbbbbbbrbb
all_num=4101  num=81  bbbbbbbrbbbbbbbbbrbr
all_num=4103  num=82  bbbbbbbrbbbbbbbbbrrr
all_num=4105  num=83  bbbbbbbrbbbbbbbbrbbr
all_num=4106  num=84  bbbbbbbrbbbbbbbbrbrb
all_num=4107  num=85  bbbbbbbrbbbbbbbbrbrr
all_num=4109  num=86  bbbbbbbrbbbbbbbbrrbr
all_num=4110  num=87  bbbbbbbrbbbbbbbbrrrb
all_num=4111  num=88  bbbbbbbrbbbbbbbbrrrr
all_num=4114  num=89  bbbbbbbrbbbbbbbrbbrb
all_num=4116  num=90  bbbbbbbrbbbbbbbrbrbb
all_num=4117  num=91  bbbbbbbrbbbbbbbrbrbr
all_num=4119  num=92  bbbbbbbrbbbbbbbrbrrr
all_num=4121  num=93  bbbbbbbrbbbbbbbrrbbr
all_num=4122  num=94  bbbbbbbrbbbbbbbrrbrb
all_num=4123  num=95  bbbbbbbrbbbbbbbrrbrr
all_num=4125  num=96  bbbbbbbrbbbbbbbrrrbr
all_num=4126  num=97  bbbbbbbrbbbbbbbrrrrb
all_num=4127  num=98  bbbbbbbrbbbbbbbrrrrr
all_num=4132  num=99  bbbbbbbrbbbbbbrbbrbb
all_num=4136  num=100 bbbbbbbrbbbbbbrbrbbb
为了使规律更加明显,我们直接上手跑n=29的情况(①和②的规律已经很显然了,就不过多赘述)
再进行观察,发现,n=29的时候只剩下了3个块!!!
这就是说,我们可以直接忽视第4个块。
然后再打一发n=30的表,会发现,它们的第三个块的形状大体一致。
再对n=27/28打表观察,n同奇同偶时,后半部分的内容时一致的,只有第一个r的位置有所变化。

那么本题的一种解法就显然了:
先把n=29/30的后半段(16位)打表存起来,用于拼接。
对于n<=30(可以是其他的值,只要不出现第4块的内容就行),直接用暴力程序求解
对于n>30的情况,先根据规律输出前两个块和第三个块的前半截,第三个块的后半截直接取用n=29/30的后16位即可

all_num=16384 num=1   bbbbbbbbbbbbbbrbbbbbbbbbbbbbb //①
all_num=32769 num=2   bbbbbbbbbbbbbrbbbbbbbbbbbbbbr //② 
all_num=32771 num=3   bbbbbbbbbbbbbrbbbbbbbbbbbbbrr
all_num=32774 num=4   bbbbbbbbbbbbbrbbbbbbbbbbbbrrb
all_num=32780 num=5   bbbbbbbbbbbbbrbbbbbbbbbbbrrbb
all_num=32792 num=6   bbbbbbbbbbbbbrbbbbbbbbbbrrbbb
all_num=32816 num=7   bbbbbbbbbbbbbrbbbbbbbbbrrbbbb
all_num=32864 num=8   bbbbbbbbbbbbbrbbbbbbbbrrbbbbb
all_num=32960 num=9   bbbbbbbbbbbbbrbbbbbbbrrbbbbbb
all_num=33152 num=10  bbbbbbbbbbbbbrbbbbbbrrbbbbbbb
all_num=33536 num=11  bbbbbbbbbbbbbrbbbbbrrbbbbbbbb
all_num=34304 num=12  bbbbbbbbbbbbbrbbbbrrbbbbbbbbb
all_num=35840 num=13  bbbbbbbbbbbbbrbbbrrbbbbbbbbbb
all_num=38912 num=14  bbbbbbbbbbbbbrbbrrbbbbbbbbbbb
all_num=45056 num=15  bbbbbbbbbbbbbrbrrbbbbbbbbbbbb
all_num=57344 num=16  bbbbbbbbbbbbbrrrbbbbbbbbbbbbb
all_num=65538 num=17  bbbbbbbbbbbbrbbbbbbbbbbbbbbrb //③
all_num=65541 num=18  bbbbbbbbbbbbrbbbbbbbbbbbbbrbr
all_num=65543 num=19  bbbbbbbbbbbbrbbbbbbbbbbbbbrrr
all_num=65546 num=20  bbbbbbbbbbbbrbbbbbbbbbbbbrbrb
all_num=65549 num=21  bbbbbbbbbbbbrbbbbbbbbbbbbrrbr
all_num=65551 num=22  bbbbbbbbbbbbrbbbbbbbbbbbbrrrr
all_num=65556 num=23  bbbbbbbbbbbbrbbbbbbbbbbbrbrbb
all_num=65561 num=24  bbbbbbbbbbbbrbbbbbbbbbbbrrbbr
all_num=65563 num=25  bbbbbbbbbbbbrbbbbbbbbbbbrrbrr
all_num=65566 num=26  bbbbbbbbbbbbrbbbbbbbbbbbrrrrb
all_num=65576 num=27  bbbbbbbbbbbbrbbbbbbbbbbrbrbbb
all_num=65585 num=28  bbbbbbbbbbbbrbbbbbbbbbbrrbbbr
all_num=65587 num=29  bbbbbbbbbbbbrbbbbbbbbbbrrbbrr
all_num=65590 num=30  bbbbbbbbbbbbrbbbbbbbbbbrrbrrb
all_num=65596 num=31  bbbbbbbbbbbbrbbbbbbbbbbrrrrbb
all_num=65616 num=32  bbbbbbbbbbbbrbbbbbbbbbrbrbbbb
all_num=65633 num=33  bbbbbbbbbbbbrbbbbbbbbbrrbbbbr
all_num=65635 num=34  bbbbbbbbbbbbrbbbbbbbbbrrbbbrr
all_num=65638 num=35  bbbbbbbbbbbbrbbbbbbbbbrrbbrrb
all_num=65644 num=36  bbbbbbbbbbbbrbbbbbbbbbrrbrrbb
all_num=65656 num=37  bbbbbbbbbbbbrbbbbbbbbbrrrrbbb
all_num=65696 num=38  bbbbbbbbbbbbrbbbbbbbbrbrbbbbb
all_num=65729 num=39  bbbbbbbbbbbbrbbbbbbbbrrbbbbbr
all_num=65731 num=40  bbbbbbbbbbbbrbbbbbbbbrrbbbbrr
all_num=65734 num=41  bbbbbbbbbbbbrbbbbbbbbrrbbbrrb
all_num=65740 num=42  bbbbbbbbbbbbrbbbbbbbbrrbbrrbb
all_num=65752 num=43  bbbbbbbbbbbbrbbbbbbbbrrbrrbbb
all_num=65776 num=44  bbbbbbbbbbbbrbbbbbbbbrrrrbbbb
all_num=65856 num=45  bbbbbbbbbbbbrbbbbbbbrbrbbbbbb
all_num=65921 num=46  bbbbbbbbbbbbrbbbbbbbrrbbbbbbr
all_num=65923 num=47  bbbbbbbbbbbbrbbbbbbbrrbbbbbrr
all_num=65926 num=48  bbbbbbbbbbbbrbbbbbbbrrbbbbrrb
all_num=65932 num=49  bbbbbbbbbbbbrbbbbbbbrrbbbrrbb
all_num=65944 num=50  bbbbbbbbbbbbrbbbbbbbrrbbrrbbb
all_num=65968 num=51  bbbbbbbbbbbbrbbbbbbbrrbrrbbbb
all_num=66016 num=52  bbbbbbbbbbbbrbbbbbbbrrrrbbbbb
all_num=66176 num=53  bbbbbbbbbbbbrbbbbbbrbrbbbbbbb
all_num=66305 num=54  bbbbbbbbbbbbrbbbbbbrrbbbbbbbr
all_num=66307 num=55  bbbbbbbbbbbbrbbbbbbrrbbbbbbrr
all_num=66310 num=56  bbbbbbbbbbbbrbbbbbbrrbbbbbrrb
all_num=66316 num=57  bbbbbbbbbbbbrbbbbbbrrbbbbrrbb
all_num=66328 num=58  bbbbbbbbbbbbrbbbbbbrrbbbrrbbb
all_num=66352 num=59  bbbbbbbbbbbbrbbbbbbrrbbrrbbbb
all_num=66400 num=60  bbbbbbbbbbbbrbbbbbbrrbrrbbbbb
all_num=66496 num=61  bbbbbbbbbbbbrbbbbbbrrrrbbbbbb
all_num=66816 num=62  bbbbbbbbbbbbrbbbbbrbrbbbbbbbb
all_num=67073 num=63  bbbbbbbbbbbbrbbbbbrrbbbbbbbbr
all_num=67075 num=64  bbbbbbbbbbbbrbbbbbrrbbbbbbbrr
all_num=67078 num=65  bbbbbbbbbbbbrbbbbbrrbbbbbbrrb
all_num=67084 num=66  bbbbbbbbbbbbrbbbbbrrbbbbbrrbb
all_num=67096 num=67  bbbbbbbbbbbbrbbbbbrrbbbbrrbbb
all_num=67120 num=68  bbbbbbbbbbbbrbbbbbrrbbbrrbbbb
all_num=67168 num=69  bbbbbbbbbbbbrbbbbbrrbbrrbbbbb
all_num=67264 num=70  bbbbbbbbbbbbrbbbbbrrbrrbbbbbb
all_num=67456 num=71  bbbbbbbbbbbbrbbbbbrrrrbbbbbbb
all_num=68096 num=72  bbbbbbbbbbbbrbbbbrbrbbbbbbbbb
all_num=68609 num=73  bbbbbbbbbbbbrbbbbrrbbbbbbbbbr
all_num=68611 num=74  bbbbbbbbbbbbrbbbbrrbbbbbbbbrr
all_num=68614 num=75  bbbbbbbbbbbbrbbbbrrbbbbbbbrrb
all_num=68620 num=76  bbbbbbbbbbbbrbbbbrrbbbbbbrrbb
all_num=68632 num=77  bbbbbbbbbbbbrbbbbrrbbbbbrrbbb
all_num=68656 num=78  bbbbbbbbbbbbrbbbbrrbbbbrrbbbb
all_num=68704 num=79  bbbbbbbbbbbbrbbbbrrbbbrrbbbbb
all_num=68800 num=80  bbbbbbbbbbbbrbbbbrrbbrrbbbbbb
all_num=68992 num=81  bbbbbbbbbbbbrbbbbrrbrrbbbbbbb
all_num=69376 num=82  bbbbbbbbbbbbrbbbbrrrrbbbbbbbb
all_num=70656 num=83  bbbbbbbbbbbbrbbbrbrbbbbbbbbbb
all_num=71681 num=84  bbbbbbbbbbbbrbbbrrbbbbbbbbbbr
all_num=71683 num=85  bbbbbbbbbbbbrbbbrrbbbbbbbbbrr
all_num=71686 num=86  bbbbbbbbbbbbrbbbrrbbbbbbbbrrb
all_num=71692 num=87  bbbbbbbbbbbbrbbbrrbbbbbbbrrbb
all_num=71704 num=88  bbbbbbbbbbbbrbbbrrbbbbbbrrbbb
all_num=71728 num=89  bbbbbbbbbbbbrbbbrrbbbbbrrbbbb
all_num=71776 num=90  bbbbbbbbbbbbrbbbrrbbbbrrbbbbb
all_num=71872 num=91  bbbbbbbbbbbbrbbbrrbbbrrbbbbbb
all_num=72064 num=92  bbbbbbbbbbbbrbbbrrbbrrbbbbbbb
all_num=72448 num=93  bbbbbbbbbbbbrbbbrrbrrbbbbbbbb
all_num=73216 num=94  bbbbbbbbbbbbrbbbrrrrbbbbbbbbb
all_num=75776 num=95  bbbbbbbbbbbbrbbrbrbbbbbbbbbbb
all_num=77825 num=96  bbbbbbbbbbbbrbbrrbbbbbbbbbbbr
all_num=77827 num=97  bbbbbbbbbbbbrbbrrbbbbbbbbbbrr
all_num=77830 num=98  bbbbbbbbbbbbrbbrrbbbbbbbbbrrb
all_num=77836 num=99  bbbbbbbbbbbbrbbrrbbbbbbbbrrbb
all_num=77848 num=100 bbbbbbbbbbbbrbbrrbbbbbbbrrbbb

【代码】

存后16位的打表代码:

#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll n,ans;
string sta[100];
void init()
{
}
string getpath(int x)//构造字符串
{
    string res="";
    for(int i=1;i<=n;i++)res+="b";
    int i=n-1;
    while(x)
    {
        if(x&1)res[i]='r';
        x>>=1;
        --i;
    }
    return res;
}
void solve()
{
    int cnt=0;
    int id=0;
    for(int i=0;i<(1<<n);i++)//
    {
        int sum=0,t;
        string path=getpath(i);

        for(int j=0;j<n;j++)//n^2暴力check当前道路满意区间数
        {
            t=0;
            for(int k=j;k<n;k++)
            {
                if(path[k]=='r')t++;
                if(t&1)sum++;
            }
        }

        if(sum==ans)//当前道路满意区间为最大值则输出
        {
            ++cnt;
            if(cnt<n-12)continue;//前面两组解直接略过
            ++id;
            cout<<"stb["<<id<<"]="<<'"';
            for(int j=n-16;j<n;j++)cout<<path[j];//只取最后16位就可以了
            cout<<'"'<<';';
            cout<<endl;
            if(cnt==100)break;
        }
    }
}
void work()
{

}
int main()
{
    freopen("data.out","w",stdout);//文件输出,方便复制粘贴结果
    cin>>n;//输入n=29/30,分别跑出奇偶两组的解
    
    if(n&1)ans=(n+1)*(n+1)/4;//计算最大满意区间数
    else ans=(n*n+2*n)/4;
    cout<<ans<<endl;
    
    init();
    if(n<=30)solve();
    else work();
    return 0;
}

AC代码

#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll n,ans;//注意!!! 因为n是1e5,ans是n^2级别的,会爆int
//现在赛就是思路出的还算顺利,结果因为疏忽了这个,疯狂找bug待机了半天,QwQ
string sta[100],stb[100];//sta,stb分别记录n=29、30时第三部分的后16位
void init()
{
    sta[1]="bbbbbbbbbbbbbbrb";
    sta[2]="bbbbbbbbbbbbbrbr";
    sta[3]="bbbbbbbbbbbbbrrr";
    sta[4]="bbbbbbbbbbbbrbrb";
    sta[5]="bbbbbbbbbbbbrrbr";
    sta[6]="bbbbbbbbbbbbrrrr";
    sta[7]="bbbbbbbbbbbrbrbb";
    sta[8]="bbbbbbbbbbbrrbbr";
    sta[9]="bbbbbbbbbbbrrbrr";
    sta[10]="bbbbbbbbbbbrrrrb";
    sta[11]="bbbbbbbbbbrbrbbb";
    sta[12]="bbbbbbbbbbrrbbbr";
    sta[13]="bbbbbbbbbbrrbbrr";
    sta[14]="bbbbbbbbbbrrbrrb";
    sta[15]="bbbbbbbbbbrrrrbb";
    sta[16]="bbbbbbbbbrbrbbbb";
    sta[17]="bbbbbbbbbrrbbbbr";
    sta[18]="bbbbbbbbbrrbbbrr";
    sta[19]="bbbbbbbbbrrbbrrb";
    sta[20]="bbbbbbbbbrrbrrbb";
    sta[21]="bbbbbbbbbrrrrbbb";
    sta[22]="bbbbbbbbrbrbbbbb";
    sta[23]="bbbbbbbbrrbbbbbr";
    sta[24]="bbbbbbbbrrbbbbrr";
    sta[25]="bbbbbbbbrrbbbrrb";
    sta[26]="bbbbbbbbrrbbrrbb";
    sta[27]="bbbbbbbbrrbrrbbb";
    sta[28]="bbbbbbbbrrrrbbbb";
    sta[29]="bbbbbbbrbrbbbbbb";
    sta[30]="bbbbbbbrrbbbbbbr";
    sta[31]="bbbbbbbrrbbbbbrr";
    sta[32]="bbbbbbbrrbbbbrrb";
    sta[33]="bbbbbbbrrbbbrrbb";
    sta[34]="bbbbbbbrrbbrrbbb";
    sta[35]="bbbbbbbrrbrrbbbb";
    sta[36]="bbbbbbbrrrrbbbbb";
    sta[37]="bbbbbbrbrbbbbbbb";
    sta[38]="bbbbbbrrbbbbbbbr";
    sta[39]="bbbbbbrrbbbbbbrr";
    sta[40]="bbbbbbrrbbbbbrrb";
    sta[41]="bbbbbbrrbbbbrrbb";
    sta[42]="bbbbbbrrbbbrrbbb";
    sta[43]="bbbbbbrrbbrrbbbb";
    sta[44]="bbbbbbrrbrrbbbbb";
    sta[45]="bbbbbbrrrrbbbbbb";
    sta[46]="bbbbbrbrbbbbbbbb";
    sta[47]="bbbbbrrbbbbbbbbr";
    sta[48]="bbbbbrrbbbbbbbrr";
    sta[49]="bbbbbrrbbbbbbrrb";
    sta[50]="bbbbbrrbbbbbrrbb";
    sta[51]="bbbbbrrbbbbrrbbb";
    sta[52]="bbbbbrrbbbrrbbbb";
    sta[53]="bbbbbrrbbrrbbbbb";
    sta[54]="bbbbbrrbrrbbbbbb";
    sta[55]="bbbbbrrrrbbbbbbb";
    sta[56]="bbbbrbrbbbbbbbbb";
    sta[57]="bbbbrrbbbbbbbbbr";
    sta[58]="bbbbrrbbbbbbbbrr";
    sta[59]="bbbbrrbbbbbbbrrb";
    sta[60]="bbbbrrbbbbbbrrbb";
    sta[61]="bbbbrrbbbbbrrbbb";
    sta[62]="bbbbrrbbbbrrbbbb";
    sta[63]="bbbbrrbbbrrbbbbb";
    sta[64]="bbbbrrbbrrbbbbbb";
    sta[65]="bbbbrrbrrbbbbbbb";
    sta[66]="bbbbrrrrbbbbbbbb";
    sta[67]="bbbrbrbbbbbbbbbb";
    sta[68]="bbbrrbbbbbbbbbbr";
    sta[69]="bbbrrbbbbbbbbbrr";
    sta[70]="bbbrrbbbbbbbbrrb";
    sta[71]="bbbrrbbbbbbbrrbb";
    sta[72]="bbbrrbbbbbbrrbbb";
    sta[73]="bbbrrbbbbbrrbbbb";
    sta[74]="bbbrrbbbbrrbbbbb";
    sta[75]="bbbrrbbbrrbbbbbb";
    sta[76]="bbbrrbbrrbbbbbbb";
    sta[77]="bbbrrbrrbbbbbbbb";
    sta[78]="bbbrrrrbbbbbbbbb";
    sta[79]="bbrbrbbbbbbbbbbb";
    sta[80]="bbrrbbbbbbbbbbbr";
    sta[81]="bbrrbbbbbbbbbbrr";
    sta[82]="bbrrbbbbbbbbbrrb";
    sta[83]="bbrrbbbbbbbbrrbb";
    sta[84]="bbrrbbbbbbbrrbbb";

    stb[1]="bbbbbbbbbbbbbbbr";
    stb[2]="bbbbbbbbbbbbbbrb";
    stb[3]="bbbbbbbbbbbbbbrr";
    stb[4]="bbbbbbbbbbbbbrbr";
    stb[5]="bbbbbbbbbbbbbrrb";
    stb[6]="bbbbbbbbbbbbbrrr";
    stb[7]="bbbbbbbbbbbbrbrb";
    stb[8]="bbbbbbbbbbbbrrbb";
    stb[9]="bbbbbbbbbbbbrrbr";
    stb[10]="bbbbbbbbbbbbrrrr";
    stb[11]="bbbbbbbbbbbrbrbb";
    stb[12]="bbbbbbbbbbbrrbbb";
    stb[13]="bbbbbbbbbbbrrbbr";
    stb[14]="bbbbbbbbbbbrrbrr";
    stb[15]="bbbbbbbbbbbrrrrb";
    stb[16]="bbbbbbbbbbrbrbbb";
    stb[17]="bbbbbbbbbbrrbbbb";
    stb[18]="bbbbbbbbbbrrbbbr";
    stb[19]="bbbbbbbbbbrrbbrr";
    stb[20]="bbbbbbbbbbrrbrrb";
    stb[21]="bbbbbbbbbbrrrrbb";
    stb[22]="bbbbbbbbbrbrbbbb";
    stb[23]="bbbbbbbbbrrbbbbb";
    stb[24]="bbbbbbbbbrrbbbbr";
    stb[25]="bbbbbbbbbrrbbbrr";
    stb[26]="bbbbbbbbbrrbbrrb";
    stb[27]="bbbbbbbbbrrbrrbb";
    stb[28]="bbbbbbbbbrrrrbbb";
    stb[29]="bbbbbbbbrbrbbbbb";
    stb[30]="bbbbbbbbrrbbbbbb";
    stb[31]="bbbbbbbbrrbbbbbr";
    stb[32]="bbbbbbbbrrbbbbrr";
    stb[33]="bbbbbbbbrrbbbrrb";
    stb[34]="bbbbbbbbrrbbrrbb";
    stb[35]="bbbbbbbbrrbrrbbb";
    stb[36]="bbbbbbbbrrrrbbbb";
    stb[37]="bbbbbbbrbrbbbbbb";
    stb[38]="bbbbbbbrrbbbbbbb";
    stb[39]="bbbbbbbrrbbbbbbr";
    stb[40]="bbbbbbbrrbbbbbrr";
    stb[41]="bbbbbbbrrbbbbrrb";
    stb[42]="bbbbbbbrrbbbrrbb";
    stb[43]="bbbbbbbrrbbrrbbb";
    stb[44]="bbbbbbbrrbrrbbbb";
    stb[45]="bbbbbbbrrrrbbbbb";
    stb[46]="bbbbbbrbrbbbbbbb";
    stb[47]="bbbbbbrrbbbbbbbb";
    stb[48]="bbbbbbrrbbbbbbbr";
    stb[49]="bbbbbbrrbbbbbbrr";
    stb[50]="bbbbbbrrbbbbbrrb";
    stb[51]="bbbbbbrrbbbbrrbb";
    stb[52]="bbbbbbrrbbbrrbbb";
    stb[53]="bbbbbbrrbbrrbbbb";
    stb[54]="bbbbbbrrbrrbbbbb";
    stb[55]="bbbbbbrrrrbbbbbb";
    stb[56]="bbbbbrbrbbbbbbbb";
    stb[57]="bbbbbrrbbbbbbbbb";
    stb[58]="bbbbbrrbbbbbbbbr";
    stb[59]="bbbbbrrbbbbbbbrr";
    stb[60]="bbbbbrrbbbbbbrrb";
    stb[61]="bbbbbrrbbbbbrrbb";
    stb[62]="bbbbbrrbbbbrrbbb";
    stb[63]="bbbbbrrbbbrrbbbb";
    stb[64]="bbbbbrrbbrrbbbbb";
    stb[65]="bbbbbrrbrrbbbbbb";
    stb[66]="bbbbbrrrrbbbbbbb";
    stb[67]="bbbbrbrbbbbbbbbb";
    stb[68]="bbbbrrbbbbbbbbbb";
    stb[69]="bbbbrrbbbbbbbbbr";
    stb[70]="bbbbrrbbbbbbbbrr";
    stb[71]="bbbbrrbbbbbbbrrb";
    stb[72]="bbbbrrbbbbbbrrbb";
    stb[73]="bbbbrrbbbbbrrbbb";
    stb[74]="bbbbrrbbbbrrbbbb";
    stb[75]="bbbbrrbbbrrbbbbb";
    stb[76]="bbbbrrbbrrbbbbbb";
    stb[77]="bbbbrrbrrbbbbbbb";
    stb[78]="bbbbrrrrbbbbbbbb";
    stb[79]="bbbrbrbbbbbbbbbb";
    stb[80]="bbbrrbbbbbbbbbbb";
    stb[81]="bbbrrbbbbbbbbbbr";
    stb[82]="bbbrrbbbbbbbbbrr";
    stb[83]="bbbrrbbbbbbbbrrb";
}
string getpath(int x)//构造字符串
{
    string res="";
    for(int i=1;i<=n;i++)res+="b";
    int i=n-1;
    while(x)
    {
        if(x&1)res[i]='r';
        x>>=1;
        --i;
    }
    return res;
}
void solve()//暴力求解
{
    int cnt=0;
    int id=0;
    for(int i=0;i<(1<<n);i++)
    {
        int sum=0,t;
        string path=getpath(i);//二进制枚举状态

        for(int j=0;j<n;j++)//n^2暴力check当前道路满意区间数
        {
            t=0;//t:区间red的个数
            for(int k=j;k<n;k++)
            {
                if(path[k]=='r')t++;
                if(t&1)sum++;//t为奇数,当前区间符合要求
            }
        }

        if(sum==ans)//当前道路满意区间为最大值则输出
        {
            ++cnt;
            //if(cnt<n-12)continue;
            //++id;
            //cout<<"sta["<<id<<"]="<<'"';
            for(int j=0;j<n;j++)cout<<path[j];//输出结果
            //cout<<'"'<<';';
            cout<<endl;
            if(cnt==100)break;//只取前100项
        }
    }
}
void work()//规律求解
{
    int cnt=1;
    for(int i=1;i<=n/2;i++)cout<<'b';cout<<'r';for(int i=n/2+2;i<=n;i++)cout<<'b';cout<<endl;//输出第一部分
    for(int i=n/2+1;i;i--)//输出第二部分
    {
        for(int j=1;j<=n/2-1;j++)cout<<'b';cout<<'r';
        for(int j=1;j<=(n+1)/2;j++)
            if(j==i||j==i+1)cout<<'r';
            else cout<<'b';
        cout<<endl;
        ++cnt;
        if(cnt==100)break;
    }
    for(int i=cnt+1;i<=100;i++)//输出第三部分
    {
        for(int j=1;j<=n/2-2;j++)cout<<'b';cout<<'r';
        for(int j=n/2;j<=n-16;j++)cout<<'b';
        if(n&1)cout<<sta[i-cnt];
        else cout<<stb[i-cnt];
        cout<<endl;
    }
}
int main()
{
    //freopen("data.out","w",stdout);
    cin>>n;

    if(n&1)ans=(n+1)*(n+1)/4;
    else ans=(n*n+2*n)/4;
    cout<<ans<<endl;

    init();

    if(n<=30)solve();//小于30直接暴力求解
    else work();//大于30按规律求解
    return 0;
}

上一篇:2020ICPC沈阳站 D-Journey to Un'Goro


下一篇:Python Journey - Day12 -文件操作