CodeForces 660E – Different Subsets For All Tuples [DP]


Link 传送门 Problem For a sequence a of n integers between 1 and m, inclusive, denote f(a) as the number of distinct subsequences of a (including the empty subsequence). You are given two positive integers n and m. Let S be the set of all sequenc...

CodeForces 660E – Different Subsets For All Tuples [DP]

Link 传送门 Problem For a sequence a of n integers between 1 and m, inclusive, denote f(a) as the number of distinct subsequences of a (including ...
阅读全文 0

HDU 5642 – King’s Order [数位DP]


Link 传送门 Problem After the king’s speech , everyone is encouraged. But the war is not over. The king needs to give orders from time to time. But sometimes he can not speak things well. So in his order there are some ones like this: “...

HDU 5642 – King’s Order [数位DP]

Link 传送门 Problem After the king’s speech , everyone is encouraged. But the war is not over. The king needs to give orders from time to tim...
阅读全文 0

UVa 12174 – Shuffle [滑动窗口]


Link 传送门 Problem You are listening to your music collection using the shuffle function to keep the music surprising. You assume that the shuffle algorithm of your music player makes a random permutation of the songs in the playlist and plays th...

UVa 12174 – Shuffle [滑动窗口]

Link 传送门 Problem You are listening to your music collection using the shuffle function to keep the music surprising. You assume that the shuffle...
阅读全文 0

ZOJ 2317 – Nice Patterns Strike Back [DP+矩阵+Java大数]


Link 点击打开zoj题目链接 Problem You might have noticed that there is the new fashion among rich people to have their yards tiled with black and white tiles, forming a pattern. The company Broken Tiles is well known as the best tiling company in o...

ZOJ 2317 – Nice Patterns Strike Back [DP+矩阵+Java大数]

Link 点击打开zoj题目链接 Problem You might have noticed that there is the new fashion among rich people to have their yards tiled with black and wh...
阅读全文 0

CodeForces 288B – Polo the Penguin and Houses [推公式]


点击打开codeforces题目链接 题意 有N个店铺,每个店铺门牌上都写着一个数字x,表示某人到此的下一站是x。 求满足下列条件的情况数: ① 从1~K的某个店铺出发能够回到1 ② 从1号回到1号时,中间必须经过其他店铺 ③ 从K+1~N号店铺走必须回不到1号店铺. 分析 现在想想...

CodeForces 288B – Polo the Penguin and Houses [推公式]

点击打开codeforces题目链接 题意 有N个店铺,每个店铺门牌上都写着一个数字x,表示某人到此的下一站是x。 求满足下列条件的情况数: ① 从1~K的某个店铺出发...
阅读全文 0

UVa 1646 – Edge Case [规律+大数]


点击打开vjudge题目链接 题意:n个节点组成一个圈,求匹配(即没有公共点的边集)个数。 分析:找规律,n=3时答案是4,n=4时答案是7,画画图递推一下发现n=5时答案是11,n=6时答案是18…类似于斐波那契数列。因为并没有取模,需要大数,直接上java. import ja...

UVa 1646 – Edge Case [规律+大数]

点击打开vjudge题目链接 题意:n个节点组成一个圈,求匹配(即没有公共点的边集)个数。 分析:找规律,n=3时答案是4,n=4时答案是7,画画图递推一下发现n=5...
阅读全文 0

HDU 1165 – Eddy’s research II [推公式]


vjudge题目连接 Description As is known, Ackermann function plays an important role in the sphere of theoretical computer science. However, in the other hand, the dramatic fast increasing pace of the function caused the value of Ackermann functio...

HDU 1165 – Eddy’s research II [推公式]

vjudge题目连接 Description As is known, Ackermann function plays an important role in the sphere of theoretical computer science. However, in the...
阅读全文 0

FZU 2056 – 最大正方形 [二分+递推]


vjudge链接:http://acm.hust.edu.cn/vjudge/problem/viewProblem.action?id=29392 Description 现在有一个n*m的矩阵A,在A中找一个H*H的正方形,使得其面积最大且该正方形元素的和不大于 limit。 Input 第一行一个整数T,表示有T组数据。 每组数据 第一...

FZU 2056 – 最大正方形 [二分+递推]

vjudge链接:http://acm.hust.edu.cn/vjudge/problem/viewProblem.action?id=29392 Description 现在有一个n*m的矩阵A,在A中找一个H*H的正方形,使得...
阅读全文 0

POJ 2229 – Sumsets [动规]


比较好的动规思路题,要根据奇偶找出递推式来。 对于dp[i],当i为奇数时,相当于在dp[i-1]的每种情况前面都加上1,即dp[i] = dp[i-1] 当i为偶数时,对每种拆分,分为前面带1和不带1两种情况。带1时,可变为dp[i] = dp[i-1](或dp[i] = dp[i-2...

POJ 2229 – Sumsets [动规]

比较好的动规思路题,要根据奇偶找出递推式来。 对于dp[i],当i为奇数时,相当于在dp[i-1]的每种情况前面都加上1,即dp[i] = dp[i-1] 当i为偶数...
阅读全文 0