标签: 状压DP

「CodeForces 1215E」 Marbles

Monocarp has arranged 𝑛 colored marbles in a row. The color of the 𝑖-th marble is 𝑎𝑖. Monocarp likes ordered things, so he wants to rearrange marbles in such a way that all marbles of the same color form a contiguos segment (and there is only one such segment for each color).

In other words, Monocarp wants to rearrange marbles so that, for every color 𝑗, if the leftmost marble of color 𝑗 is 𝑙-th in the row, and the rightmost marble of this color has position 𝑟 in the row, then every marble from 𝑙 to 𝑟 has color 𝑗.

To achieve his goal, Monocarp can do the following operation any number of times: choose two neighbouring marbles, and swap them.

You have to calculate the minimum number of operations Monocarp has to perform to rearrange the marbles. Note that the order of segments of marbles having equal color does not matter, it is only required that, for every color, all the marbles of this color form exactly one contiguous segment.

「SDOI2009」学校食堂

小F 的学校在城市的一个偏僻角落,所有学生都只好在学校吃饭。学校有一个食堂,虽然简陋,但食堂大厨总能做出让同学们满意的菜肴。当然,不同的人口味也不一定相同,但每个人的口味都可以用一个非负整数表示。 由于人手不够,食堂每次只能为一个人做菜。做每道菜所需的时间是和前一道菜有关的,若前一道菜的对应的口味是a,这一道为b,则做这道菜所需的时间为(a or b)-(a and b),而做第一道菜是不需要计算时间的。其中,or 和and 表示整数逐位或运算及逐位与运算,C语言中对应的运算符为“|”和“&”。

「CodeForces 1234F」Yet Another Substring Reverse

You are given a string 𝑠 consisting only of first 20 lowercase Latin letters ('a', 'b', ..., 't').

Recall that the substring 𝑠[𝑙;𝑟] of the string 𝑠 is the string 𝑠𝑙𝑠𝑙+1…𝑠𝑟. For example, the substrings of "codeforces" are "code", "force", "f", "for", but not "coder" and "top".

「CodeForces 1238E」Keyboard Purchase

You have a password which you often type — a string 𝑠 of length 𝑛. Every character of this string is one of the first 𝑚 lowercase Latin letters.

Since you spend a lot of time typing it, you want to buy a new keyboard.

A keyboard is a permutation of the first 𝑚 Latin letters. For example, if 𝑚=3, then there are six possible keyboards: abc, acb, bac, bca, cab and cba.

「2017 四川省赛」2017 Revenge

Bobo has n integers a1,a2,,ana_1, a_2, \dots, a_n
He would like to choose some of the integers and calculate their product (the product of the empty set is defined as 1).

Bobo would like to know the number of products whose remainder divided by 2017 is r. As the exact number is too large, he only asks for the number modulo 2.

「SCOI2008」奖励关

你正在玩你最喜欢的电子游戏,并且刚刚进入一个奖励关。在这个奖励关里,系统将依次随机抛出k次宝物,每次你都可以选择吃或者不吃(必须在抛出下一个宝物之前做出选择,且现在决定不吃的宝物以后也不能再吃)。

宝物一共有n种,系统每次抛出这n种宝物的概率都相同且相互独立。也就是说,即使前k-1 次系统都抛出宝物1(这种情况是有可能出现的,尽管概率非常小),第k次抛出各个宝物的概率依然均为1/n。

「SCOI2005」 互不侵犯

在N×N的棋盘里面放K个国王,使他们互不攻击,共有多少种摆放方案。国王能攻击到它上下左右,以及左上左下右上右下八个方向上附近的各一个格子,共8个格子。

「AHOI2009」 中国象棋

这次小可可想解决的难题和中国象棋有关,在一个N行M列的棋盘上,让你放若干个炮(可以是0个),使得没有一个炮可以攻击到另一个炮,请问有多少种放置方法。大家肯定很清楚,在中国象棋中炮的行走方式是:一个炮攻击到另一个炮,当且仅当它们在同一行或同一列中,且它们之间恰好 有一个棋子。你也来和小可可一起锻炼一下思维吧!

「NOI2001」 炮兵阵地

司令部的将军们打算在NM的网格地图上部署他们的炮兵部队。一个NM的地图由N行M列组成,地图的每一格可能是山地(用“H” 表示),也可能是平原(用“P”表示),如下图。在每一格平原地形上最多可以布置一支炮兵部队(山地上不能够部署炮兵部队);一支炮兵部队在地图上的攻击范围如图中黑色区域所示: