Codeforces Beta Round 9 D How many trees? (Div.2 Only)

题目

源地址:

http://codeforces.com/problemset/problem/9/D

理解

神DP,给战斗民族的数学功底跪了。 一个二叉搜索树,要求左子树的和小于右子树,问存在多少个这样的数。由题意可以推出这样一个结论:左子树的和小于右子树,只要左子树的最大值小于右子树的最大值即可,因为2^0+2^1+2^p-1<2^p。 所以在求dp[i][j]~(dp[i][j]表示i个点组成高度小于等于j的树的总数)~的时候,有两种情况: 1. 子树的中n-1个点权在左子树,要么全在右子树,这样的话就没有条件限制了。 2. 如果左右子树都有,那么最大的肯定要放在右子树上,所以除了当前根和最大的点,其他点(总共i-2个)随便取 ,枚举左子树最多放几个,右子树最多放几个就可以推出来。 转移转移方程为:dp[i][j]+=dp[k][j-1]*dp[i-k-1][j-1]

Read More

Codeforces Beta Round 7 D Palindrome Degree

题目

源地址:

http://codeforces.com/problemset/problem/7/D

理解

被引入的新概念吓到了= =,其实这道题就是一个求最大回文串的问题。 不过按照这个数据量,每一次都进行strcmp肯定不现实,所以我们需要一个好的字符串hash(的板子)。预处理之后,分别计算前缀和后缀的hash值。如果hash值相等,说明前缀和后缀相同,它们的度数就是长度/2再加上一。然后结果就是度数的和。

字符串hash的时候那个素数开大一点比较好,不用去处理hash冲突,23333。

Read More

Codeforces Beta Round 8 B Obsession with Robots

题目

源地址:

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

理解

在那遥远的地方有位好姑娘 ,人们走过她的帐篷都要留恋的张望 23333,不逗比了,真正的题解开始。 在一个无穷大的平面上,有一个机器人可以自由地上下左右移动。然后在它移动的路径上,你可以给它设置任意个障碍。如果存在一种障碍的设计,使得机器人的移动路径是最短路径,则OK;如果不存在,则存在BUG。 这道题写得很逗= =。一开始作死用switch来写,不过在字符的判断上好像写搓了,怎么写都是BUG。后来想到可以用一个vis来标记机器人走过的路径,如果存在一个点被访问过两次,那么这个路径一定不是最短路径。不过这份代码挂了,原因是还存在另外一种可能,比如:URD。也就是说,只要形成一个类似于U的结构,也一定不是最短路径。一时半会儿没想出来什么高效的方案,干脆暴力敲了一个。设一个flag出来,然后每走一个点,就四个方向判断一下是否访问过,如果flag>=2,说明一定是BUG。 多亏了CF机子好,居然过了,也是RP好。

Read More

Codeforces Beta Round 9 C Hexadecimal's Numbers (Div.2 Only)

题目

源地址:

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

理解

题意不难理解。给定一个n,要你求出从0到n有多少个仅用0和1能表示出来的数。 想法很简单,我们先来处理最为简化的情况,如果给定一个二进制数,我们要求出比这个小的二进制数的个数有多少。小脑一动,我们就能知道,这个个数就是这个二进制数转化为十进制数的大小。 那么问题来了,给定一个十进制数,我们怎样才能求出这个最大的二进制数呢?其实我们可以这样来处理:每一位都有三种情况,0或者1或者大于1。0和1不需要进行任何操作,如果大于1,我们则把从这一位起的每一位都变成1。这样处理之后,我们就得到了最大的二进制数。然后就是一个简单的进制转换问题。

其实当天晚上的BestCoder 18的1003题跟这个有点像,不过做BC的时候,我没有捋清楚思路,最后还是没有敲出来。不过多亏被虐了一发,这道题才顺利地推出了结论。

Read More

UVa 1025 A Spy in the Metro

题目

源地址:

http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=3466

理解

其实题目还是蛮吓人的= =,因为上来就是Line1~7的输入。其实题意不难,有从左到右编号为1~n的车站,有m1辆车从第1站往右开,有m2辆车从第2站往左开。主角在t=0的时候从第1站出发,要在t时刻遇见车站n的一个间谍。要求求出最短的等待时间,没有的话就输出impossible。 小脑一动,可以知道,每一次有三个选择:等待,向左,向右。我们可以用dp[t][i]来表示第t时刻在第i个车站,然后用vis[t][i][sta]来表示三种选择。全部预处理一遍之后,dp求解最短时间即可。

Read More

Codeforces Beta Round 7 A Kalevitch and Chess

题目

源地址:

http://codeforces.com/problemset/problem/7/A

理解

同样是理解题- -。 给定一个被黑白棋子占满的棋盘,能进行的操作为将一行或者一列由黑色变白色,问最少需要多少步,能将棋盘全都变为白色。 一开始感觉应该用DFS来做,但是想了想,其实用模拟就能搞定。思路很简单,只要用两层循环,由上到下,由左到右,判断是否为B。如果是B,则有tmp++;如果不是,则继续。再然后,判断tmp是不是等于8,如果是,则进行一次行的翻转,如果不是,则列的翻转数为tmp。

Read More

CF拉练第二场

比赛地址 http://acm.hust.edu.cn/vjudge/contest/view.action?cid=62027#overview 比赛总结 水掉A和B之后,就卡在了C和D上。C只是一个变形的最长上升子序列,却没有敲出来;D题是卡了半天,输出各种理解错,一直到还有20分钟结束的时候才过,这时候已经没有时间看E了。不过赛后了看,反正我也过不了E,23333。 分题讲解 A题(模拟) 没啥好说的,其实根本就不用判断人名是否相同。 http://xuanwo.org/2014/11/05/CF-5A/ B题(模拟,字符串) 注意理解题意,是左右摆动以保持平衡。 http://xuanwo.org/2014/11/05/CF-5B/ C题(LIS) 稍微变形一下的最长上升子序列就写不出来,说明做题太死板,不懂变通,要加强。 http://xuanwo.org/2014/11/07/CF-4D/ D题(贪心) 小心输出上的trick= =。 http://xuanwo.org/2014/11/07/CF-3B/ E题(几何) 论开脑洞的重要性,没有完善的证明。 http://xuanwo.org/2014/11/06/CF-2C/ 更新日志 2014年11月7日 完成题解。

Read More