4945: [Noi2017]游戏

观察d的数据范围为8
然后考虑暴力枚举x的取值…
一开始我暴力令x = ‘a’ ,’b’,’c’则为3^n
但是发现其实因为最后每个位置只用一个取值,那么只要保证x能取’A’ ‘B’ ‘C’即可。
也就是x = ‘a’ ,’b’, 复杂度2^n
接下来容易发现是个2-sat问题…
建边以后跑tarjan,
然后根据belong 的大小来确定是选的第一个数还是第二个..

c++代码如下:

注意上面这份代码并不能过uoj 100的数据…
uoj ac代码:

 

1 + 7 =