以HDU 2089 不要62 为例的数位DP小结

题意不多说,不知道自己去看http://acm.hdu.edu.cn/showproblem.php?pid=2089

 

HDU 6156 Palindrome Function 数位DP

 问题主要是求$k$进制下小于等于$n$的回文串的个数。

用$dp[base][start][cur]$表示在base进制下,从第start位开始填写,当前填到了第cur位,往后继续填能构成回文的方案数。如果填写的长度超过了一半,就不需要继续DFS了。

 

HDU 6155 Subsequence Count 线段树维护矩阵DP转移

http://acm.hdu.edu.cn/showproblem.php?pid=6155

给一个01序列,有区间反转操作,询问区间内本质不同的子序列的个数 $%10^9+7$

写出dp转移方程,用$dp[i][j]$表从起点到第$i$个点,最后一位是$j$的方案数。

当第$i$位是$0$的时候:

$$dp[i][0] = dp[i-1][0] + dp[i-1][1] + 1$$

$$dp[i][1] = dp[i-1][1] $$

当第$i$位是$1$的时候:

$$dp[i][0] = dp[i-1][0] $$

$$dp[i][1] = dp[i-1][0] + dp[i-1][1] + 1$$

写成矩阵的形式进行转移

如果这一位是$0$

$$\begin{bmatrix} dp[i+1][0]\\ dp[i+1][1]\\1 \end{bmatrix} = \begin{bmatrix} 1 & 1 & 1\\ 0 & 1 &0\\0 & 0 & 1 \end{bmatrix}\begin{bmatrix} dp[i][0]\\ dp[i][1]\\1 \end{bmatrix}$$

如果这一位是$1$

$$\begin{bmatrix} dp[i+1][0]\\ dp[i+1][1]\\1 \end{bmatrix} = \begin{bmatrix} 1 & 0 & 0\\ 1 & 0 &0\\0 & 0 & 1 \end{bmatrix}\begin{bmatrix} dp[i][0]\\ dp[i][1]\\1 \end{bmatrix}$$

可以用线段树维护任意区间内的转移方程。

考虑反转,会发现把$0$矩阵交换$r_1,r_2$和$c_1,c_2$就能变成$1$矩阵,反之亦然。令$T=\begin{bmatrix} 0 & 1& 0\\ 1 & 0 &0\\0 & 0 & 1 \end{bmatrix}$,可知$TT=E$

交换行,可以在矩阵前乘以个 $T$,交换列,可以在矩阵后乘以一个$T$。假设$C=AB$ ,那么$TCT = TABT = TATTBT$。意味着,进行区间反转的时候,将维护的转移矩阵进行交换行列就好了,并打上延时标记。

 

HDU 6052 To my boyfriend 询问分块 容斥 单调栈

http://acm.hdu.edu.cn/showproblem.php?pid=6052

To my boyfriend

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)



Problem Description

Dear Liao
I never forget the moment I met with you. You carefully asked me: "I have a very difficult problem. Can you teach me?". I replied with a smile, "of course". You replied:"Given a matrix, I randomly choose a sub-matrix, what is the expectation of the number of **different numbers** it contains?"
Sincerely yours,
Guo

Input

The first line of input contains an integer T(T≤8) indicating the number of test cases.
Each case contains two integers, n and m (1≤n, m≤100), the number of rows and the number of columns in the grid, respectively.
The next n lines each contain m integers. In particular, the j-th integer in the i-th of these rows contains g_i,j (0≤ g_i,j < n*m).

Output

Each case outputs a number that holds 9 decimal places.

Sample Input

1
2 3
1 2 1
2 1 2

Sample Output

1.666666667

Hint

6(size = 1) + 14(size = 2) + 4(size = 3) + 4(size = 4) + 2(size = 6) = 30 / 18 = 6(size = 1) + 7(size = 2) + 2(size = 3) + 2(size = 4) + 1(size = 6)

Source

题意

给定一个$n*m$的矩阵,矩阵内每个点有个颜色。现任选一个子矩阵,问这个子矩阵包含的不同颜色个数的期望。

思路

单独求每种颜色对答案的贡献,对于一种颜色来说,如果点的个数超过了7个,直接使用单调栈来维护不含这个颜色的子矩阵的个数,否则使用容斥来算。对于单调栈维护来说,枚举每一行,算出这一行的每一个点往上多高不会包含这种颜色,分别用单调栈维护以每个点作为右下角的方案即可。容斥的计算总方案数-至少包含一个点的+至少包含两个点的-……

 

 
 

CodeForces 632E FFT 二分优化多次卷积


http://codeforces.com/problemset/problem/632/E

E. Thief in a Shop

time limit per test 5 seconds
memory limit per test 512 megabytes
 
 

A thief made his way to a shop.

As usual he has his lucky knapsack with him. The knapsack can contain k objects. There are n kinds of products in the shop and an infinite number of products of each kind. The cost of one product of kind i is ai.

The thief is greedy, so he will take exactly k products (it's possible for some kinds to take several products of that kind).

Find all the possible total costs of products the thief can nick into his knapsack.

Input

The first line contains two integers n and k (1 ≤ n, k ≤ 1000) — the number of kinds of products and the number of products the thief will take.

The second line contains n integers ai (1 ≤ ai ≤ 1000) — the costs of products for kinds from 1 to n.

Output

Print the only line with all the possible total costs of stolen products, separated by a space. The numbers should be printed in the ascending order.

Examples

input

output

input

output

input

output

题意

有$n$种物品,每种物品有无限多个,每种物品的单个价值分别为$a_i$,问取$k$个物品能取到那些价值。$1\leq a_i,n \leq 1000$

思路

构造多项式$A(x) = \sum x^{a_i}$,其中 $x^{a_i}$的系数为0或者1,表示是否存在价值为$a_i$的物品。领$B(x) = (A(x))^k$,$B(x)$的各项系数是否为大于0即是否有得到对应价值的方案。考虑乘法满足结合律,可以采用二分幂的方式进行多次多项式乘法。每次多项式乘法后,把不为零的系数赋为1,可避免精度丢失(毕竟只是问有无方案,不是求方案数)。多项式乘法用FFT优化。

代码

 

 

CodeForces 756B Travel Card 二分 DP

http://codeforces.com/problemset/problem/756/B

B. Travel Card

time limit per test

2 seconds

memory limit per test

256 megabytes

input

standard input

output

standard output

A new innovative ticketing systems for public transport is introduced in Bytesburg. Now there is a single travel card for all transport. To make a trip a passenger scan his card and then he is charged according to the fare.

The fare is constructed in the following manner. There are three types of tickets:

  1. a ticket for one trip costs 20 byteland rubles,
  2. a ticket for 90 minutes costs 50 byteland rubles,
  3. a ticket for one day (1440 minutes) costs 120 byteland rubles.

Note that a ticket for x minutes activated at time t can be used for trips started in time range from t to t + x - 1, inclusive. Assume that all trips take exactly one minute.

To simplify the choice for the passenger, the system automatically chooses the optimal tickets. After each trip starts, the system analyses all the previous trips and the current trip and chooses a set of tickets for these trips with a minimum total cost. Let the minimum total cost of tickets to cover all trips from the first to the current is a, and the total sum charged before is b. Then the system charges the passenger the sum a - b.

You have to write a program that, for given trips made by a passenger, calculates the sum the passenger is charged after each trip.

Input

The first line of input contains integer number n (1 ≤ n ≤ 105) — the number of trips made by passenger.

Each of the following n lines contains the time of trip ti (0 ≤ ti ≤ 109), measured in minutes from the time of starting the system. All ti are different, given in ascending order, i. e. ti + 1 > ti holds for all 1 ≤ i < n.

Output

Output n integers. For each trip, print the sum the passenger is charged after it.

Examples

input

output

input

output

Note

In the first example, the system works as follows: for the first and second trips it is cheaper to pay for two one-trip tickets, so each time 20 rubles is charged, after the third trip the system understands that it would be cheaper to buy a ticket for 90 minutes. This ticket costs 50 rubles, and the passenger had already paid 40 rubles, so it is necessary to charge 10 rubles only.

题意

有一个乘车的收费系统,出售单次票20元,90分钟票50元,1440分钟票120元。当有人来购票的时候,系统会统计前面已经买票的人,然后让总价格最少的方式,要求现在的人补足差价即可。问每个人需要补多少钱。

样例1的解释,3个人,分别在第10分钟、20分钟、30分钟来乘车。第一个人系统买了单次票,第二个人也是单次票,第三个人,由于前两个人已经一共付了40元,且第一个人和第三个人没有超过90分钟,所有系统选择了90分钟票,所以补了10元。

思路

用dp[i]来表示前i个人最少需要花多少钱。很明显,dp是单调递增的。每次算dp[i]的时候,将买单次票、90分钟票,120分钟票的三种情况分别算出后取最小值即可。对于算90分钟和120分钟的,进行二分查找,找到第一个tp>ti-90(或者120)的人,补差价即可。

 

HDU 5951 Winning an Auction 博弈论DP


http://acm.hdu.edu.cn/showproblem.php?pid=5951

Winning an Auction

Problem Description

Alice and Bob play an auction game. Alice has A dollars and Bob has B dollars initially. There are N items on sale. In each round, an item will be sold by the following way. Alice writes down an integer a (0 ≤ a ≤ A) and Bob writes down an integer b (0 ≤ b ≤ B), which are the amount of dollars they want to pay for the item. If a > b, then Alice gets the item and pays a dollars to the seller. If a < b, then Bob gets the item and pays b dollars to the seller. If a = b, then for the 1st, 3rd, 5th, 7th ... round, Alice gets the item and pays a dollars; for the 2rd, 4th, 6th, 8th ... round, Bob gets the item and pays b dollars. Since all the items have the same value, the goal of the auction game is to get as many items as possible. Both Alice and Bob know the values of N,A and B. Your task is to calculate how many items they will get if both of them play optimally.

Input

The first line is the number of test cases.
Each test case contains 3 integers N,A and B, which are no larger than
255.

Output

For each test case, output the number of items
Alice and Bob will get if both of them play optimally.

Sample Input

3
1 1 2
2 4 2
3 3 3

Sample Output

Alice 0 Bob 1
Alice 1 Bob 1
Alice 2 Bob 1

Source

 
题意
两个人竞拍n个物品,A有a元钱,B有b元钱。出价高的人获得该物品,如果出价相同,奇数轮物品A获得,否则B获得,两人都以最优策略获得尽量多的物品进行竞拍,问最后这两个人各获得了多少物品。
思路
很容易想到一点,如果要放弃这个物品,那么竞拍的时候出价0元就好了。采用到倒推的方法,用dp[o][p][a][b]表示开始的时候是物品的奇偶性(o=1为奇数)为o,剩余p个物品,A有a元钱,B有b元钱,A最多能获得的物品的个数。当A占优势的时候(为奇数轮的时候),假设A出了u元,那么B想要获得这个物品,必须要出u+1的钱,但是如果出了之后,并没有让A的收益变少,就可以舍弃这个物品了(出价0元)。这时,如果B竞拍这个物品成功会使A的收益减少,A就会继续加价,如果加价之后并不会让A的收益变多,那么A就放弃……如此循环下去直到B的钱不够竞拍或者满足上述的要求。B占优势的时候也是类似的。最后预处理一下这个dp就可以了。

 

 

HDU 5981 Guess the number DP决策

http://acm.hdu.edu.cn/showproblem.php?pid=5981


Guess the number

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 160000/160000 K (Java/Others)

Problem Description

AOA just met a problem when he attended an interview, as shown below:
A and B two people play guessing games. A thinks of a number x between a and b randomly in his mind, and he lets B to guess this number. A will say too small if B’s guess is less than x and A will say yes if B’s guess is just x.Once B’sguess is bigger than x,A won't speak any more.After that,A just nods his head if B’s guess is just x,otherwise shakes his head.The problem is that how many kinds of best guess strategies to make the least number of guesses in the worst situation?

Input

Input contains multiple sets of test data and each of them occupies one line,including two integersa, b(1≤a≤b≤5 * 10^6),on behalf of range of the number.Input to the end of the file.

Output

For each set of input, output one line containing two integers. The first one represents the least number of times of guessing in the worst situation. The second one represents the number of best guess method modulo 100000073.

Sample Input

1 5

Sample Output

3 3

Hint

B can guess the number in A's mind up to 3 times in the worst case. The first method,B can guess in the order of (2,4,5) The second method,B can guess in the order of (3,4,5) The third method,B can guess in the order of (3,5) Each method is up to three times.

Source

题意

猜一个[a,b]区间内的数,如果猜小了会被告知小了,相等会被告知对了,但是猜大了之后,只会被告知对还是不对。问最优策略在最坏情况的猜的次数,以及最优策略的方案数。

思路

可以将猜区间[a,b]看作猜区间[1,b-a+1],即长度为b-a+1。设dp[i]猜长度i在最优策略下最坏情况所需的步数,则dp[i] = $min_{j}(max(j-1, dp[i-j]) + 1$,枚举第一次猜的数为j,如果大了,那么就是只能暴力地猜[1,j-1]里面的数,最坏情况就是j-1次,否则就是已最优策略猜后面的i-j个数,步数为dp[i-j],取一个最小值,就是最优策略。可以观察到,当j在一个连续区间[L,R]内,都是最优的决策点,找到L和R,最优策略的方案数就是 $\sum\limits_{j=L}^{R} s[j]$。其中s[j]为长度j的段的最优策略的方案数。维护一下s[i]的前缀和,这个求和就能O(1)算出来了。当i+1的时候,L,R的变化不会很大,暴力一下就好了。

 

 

HDU 5956 树上进行斜率优化DP + 记录操作并撤销

http://acm.hdu.edu.cn/showproblem.php?pid=5956

The Elder

Time Limit: 8000/4000 MS (Java/Others)    Memory Limit: 65536/65536 K (Java/Others)


Problem Description

Once upon a time, in the mystical continent, there is a frog kingdom, ruled by the oldest frog, the Elder. The kingdom consists of N cities, numbered from east to west. The 1-th city, which is located to the east of others, is the capital. Each city, except the capital, links none or several cities to the west, and exactly one city to the east.
There are some significant news happening in some cities every day. The Elder wants to know them as soon as possible. So, that is the job of journalist frogs, who run faster than any other frog. Once some tremendous news happen in a city, the journalist in that city would take the message and run to the capital. Once it reach another city, it can either continue running, or stop at that city and let another journalist to transport. The journalist frogs are too young and simple to run a long distance efficiently. As a result, it takes $L^2$ time for them to run through a path of length L. In addition, passing message requires P time for checking the message carefully, because any mistake in the message would make the Elder become extremely angry.
Now you are excited to receive the task to calculate the maximum time of sending a message from one of these cities to the capital.

Input

The first line of input contains an integer t, the number of test cases. t test cases follow. For each test case, in the first line there are two integers N (N ≤ 100000) and P (P ≤ 1000000). In the next N-1 lines, the i-th line describes the i-th road, a line with three integers u,v,w denotes an edge between the u-th city and v-th city with length w(w ≤ 100).

Output

For each case, output the maximum time.

Sample Input

3
6 10
1 2 4
2 3 5
1 4 3
4 5 3
5 6 3
6 30
1 2 4
2 3 5
1 4 3
4 5 3
5 6 3
6 50
1 2 4
2 3 5
1 4 3
4 5 3
5 6 3

Sample Output

51
75
81

Hint

In the second case, the best transportation time is: • The 2-th city: 16 = 4^2 • The 3-th city: 72 = 4^2 + 30 + 5^2 • The 4-th city: 9 = 3^2 • The 5-th city: 36 = (3 + 3)^2 • The 6-th city: 75 = (3 + 3)^2 +30 + 3^2 Consequently, the news in the 6-th city requires most time to reach the capital.

Source

题目翻译

从前,在神秘的大陆,有一个青蛙王国,由最年长的青蛙——长者统治着。这个王国由N座城市组成,从东到西编号。第一座城市是首都,座落在最东边。每一个城市,连接者几个或者没有连接几个西边的城市,并且只连接了一个东边的城市。
每天,都有一些大新闻发生在一些城市。长者想尽快地知道。所以,青蛙新闻工作者的工作就是,跑得比其他青蛙都快。当有巨大新闻发生在某座城市的时候,这座城市的新闻工作者将会携带信息,跑向首都。当到达另一个城市的时候,他可以继续跑,也可停下来让其他的新闻工作者传输信息。这些新闻工作者由于太年轻并且简单,不能有效的跑很长的距离。结果,他们需要 $L^2$的时间来跑一条长度为L的路径。除此之外,传达信息需要P的时间,是为了检查传达信息是否有误,因为信息的误差会使长者极度的生气。
现在你高兴的收到一个任务:计算从所有城市发送信息到首都的所需的最长的时间。
 

思路

可以将图看成一个由1点为根的树,每个点到根结点为路径是唯一的。设dp[u]为u点传输信息到根节点的所需时间。a[u]为u点到根节点的距离。很明显,dp[u] = min{dp[k]+$(a[u]-a[k])^2$+P | k是u的祖先)。用斜率优化优化DP转移即可。但是不同的点路径不同,所以这里还需要记录在这个点对于斜率优化的队列操作了什么,回溯离开这个点的时候,需要撤销这些操作,操作每个点有一个栈记录即可。对于从根节点转移吃出来,可以考虑单独转移,也可设置dp[1]=-P
 

 

 

Codeforces 754C Vladik and chat 字符串处理+DP

http://codeforces.com/problemset/problem/754/C

C. Vladik and chat

time limit per test

2 seconds

memory limit per test

256 megabytes

input

standard input

output

standard output

Recently Vladik discovered a new entertainment — coding bots for social networks. He would like to use machine learning in his bots so now he want to prepare some learning data for them.

At first, he need to download t chats. Vladik coded a script which should have downloaded the chats, however, something went wrong. In particular, some of the messages have no information of their sender. It is known that if a person sends several messages in a row, they all are merged into a single message. It means that there could not be two or more messages in a row with the same sender. Moreover, a sender never mention himself in his messages.

Vladik wants to recover senders of all the messages so that each two neighboring messages will have different senders and no sender will mention himself in his messages.

He has no idea of how to do this, and asks you for help. Help Vladik to recover senders in each of the chats!

Input

The first line contains single integer t (1 ≤ t ≤ 10) — the number of chats. The t chats follow. Each chat is given in the following format.

The first line of each chat description contains single integer n (1 ≤ n ≤ 100) — the number of users in the chat.

The next line contains n space-separated distinct usernames. Each username consists of lowercase and uppercase English letters and digits. The usernames can't start with a digit. Two usernames are different even if they differ only with letters' case. The length of username is positive and doesn't exceed 10 characters.

The next line contains single integer m (1 ≤ m ≤ 100) — the number of messages in the chat. The next m line contain the messages in the following formats, one per line:

  • <username>:<text> — the format of a message with known sender. The username should appear in the list of usernames of the chat.
  • <?>:<text> — the format of a message with unknown sender.

The text of a message can consist of lowercase and uppercase English letter, digits, characters '.' (dot), ',' (comma), '!' (exclamation mark), '?' (question mark) and ' ' (space). The text doesn't contain trailing spaces. The length of the text is positive and doesn't exceed 100 characters.

We say that a text mention a user if his username appears in the text as a word. In other words, the username appears in a such a position that the two characters before and after its appearance either do not exist or are not English letters or digits. For example, the text "Vasya, masha13 and Kate!" can mention users "Vasya", "masha13", "and" and "Kate", but not "masha".

It is guaranteed that in each chat no known sender mention himself in his messages and there are no two neighboring messages with the same known sender.

Output

Print the information about the t chats in the following format:

If it is not possible to recover senders, print single line "Impossible" for this chat. Otherwise print m messages in the following format:

<username>:<text>

If there are multiple answers, print any of them.

Examples

Input

Output

Input

Output

Input

Output

 题意:

给一段聊天记录,每条形如<username>:<text>或者<?>:<text>。其中<username>代表发出这条消息的人,<?>代表发消息的人未知。发话内容是由一些由逗号、句号、感叹号、问号和空格隔开的单词,并且每个人发话的单词中,不包含自己的名字。问给定的所有发话人的名单后,能不能将<?>确定下来。

思路:

先将每条记录处理出能发出这条记录的人,当然,已经确定<username>的就只有一个人,否则就是所有的未出现在这条消息中的单词的人。然后用dp[i][j]表示第i条记录由第j个人发出是否可行。记录一下dp的前驱,最后输出即可。