题目: According to the Wikipedia's article: "The Game of Life, also known simply as Life, is a cellular automaton devised by the British mathematician John Horton Conway in 1970." Given a board w
E. Pashmak and Graph 题意:一个带权有向图,没有重边,没有自环。求图的最长路径长度,使得该路径每一条边权都严格递增。 思路:先排序,然后dp。dp[u]表示以u为起点的最长递增路径长度,len[u]表示以u为起点的最长递增路径的第一条边权。权值递减扫描所有边,状态转移:dp[u]=max(dp[u],dp[v]+1)(存在边uv且权w
D. Pashmak and Parmida's problem 题意:n个整数a1~an。1<=i<j<=n,问有多少组i,j满足这样的情况:a1~ai中值为ai的数的个数大于aj~an中值为aj的数的个数。。是不是有点绕。。 思路:树状数组。为了做这题,恶补了一下线段树,树状数组,逆序数对的知识。。虽然搞了好久,也算值了。先统计f(1, i, ai)
C. Pashmak and Buses 题意:有n个学生,k辆车,出去玩d天(也就是有d次乘车)。问是否可能任两个人至少一天没有乘坐相同的车。 思路:先自己造几组小数据人脑解一下,看看应该怎样安排。不难发现其实用k进制可以解,d位的k进制可以表示k^d个不同的值。每个值实际上代表了某个学生全部d天的乘车情况。 比如输入27 3 3,那
B. Pashmak and Flowers 题意:有许多花,每朵花有一个value,选出value相差最大的两朵花,输出value的差和有多少种选法。 思路:排序,差值就是最后一个的value减去第一个的value。然后选法种数根据乘法原理可得,注意爆int和value全部一样的情况。比赛的时候我逗比了,n*(n-1)/2写成了n/2*(n-1)。。还