博客第一周小结&&SSL暑假训练第二周小结  写这个主要是因为过几天要写暑假训练总结，做个准备。 学习内容 首先，我们学了高精度、搜索、动规。几次测试让我真正的意识到我的舍友有多么强，特别是myd和wcr这两个巨佬，几乎每次测试都AK，弄得我心态都炸裂了，感觉自己就是个菜鸡，和我个人标签一模一样。Orzzzzzz 关于博客 不过终于有一个玩意儿让我找回了自信——博客！。嘿嘿嘿，虽然说我写的博客比较少，但我访问量比他们多。好了，说正经的。博客真是个好东西，比如在写博客时，有些程序没有理解，在写注释和思路时就可以让我理解更深，因为要思考什么语句表达什么意思啊，为什么要这样做啊等等，...

叠放箱子  Description 某港口有一批集装箱，将其编号，分别为1至N。每一个箱子的外型尺寸都是一样的，现在要将其中某些集装箱叠放起来，集装箱叠放的规则如下：   1)每个集装箱上最多只能直接叠放一个集装箱。   2)编号较小的集装箱不能放在编号较大的集装箱之上。   3)每个集装箱都给出了自身的重量和可承受的重量，每个集装箱之上的所有集装箱重量之和不得超过该集装箱的可承受的重量。 现在要求你编程，从中选出最多个集装箱，使之在满足以上条件的情况下叠放起来，即要求叠得尽可能地高。 Input 第一行是一个正整数N，表示共有N个集装箱（1≤ N ≤1000）。   以下共有N行，每行两个正...

没有上司的舞会  Description Ural大学有N个职员，编号为1~N。他们有从属关系，也就是说他们的关系就像一棵以校长为根的树，父结点就是子结点的直接上司。每个职员有一个快乐指数。现在有个周年庆宴会，要求与会职员的快乐指数最大。但是，没有职员愿和直接上司一起与会。 Input 第一行一个整数N。(1<=N<=6000) 接下来N行，第i+1行表示i号职员的快乐指数Ri。(-128<=Ri<=127) 接下来N-1行，每行输入一对整数L,K。表示K是L的直接上司。 最后一行输入0,0。 Output 输出最大的快乐指数。 Sample Input 7 1 1 1...

SSL暑假训练第一周总结  第一周学习内容 第一天来ssl，觉得有点陌生，到宿舍布置好床铺收拾好东西，认识了一下舍友们（wj是小学同学），第一天训练，感觉还挺不错，学习了高精度，这玩意儿在小学就学了，感觉还挺简单，当然，只是感觉。 测试也挺简单的 满分700，我得了200，还有一个dalao室友wcr直接AK，我当场裂开了。 过了几天，学习了深度搜索，好像找到了感觉，分数开始上涨，最近一次测试满分1000我终于AK了。感觉还不错吧，期待下一周。  谢谢阅读

加法最大  Description 设有一个长度为n的数字字符串，分成k+1个部份，使其k+1部份相加的和为最大。例如：数字串’340670’，k=1，其加法有   3+40670=40673 34+0670=704 340+670=1010 3406+70=3476 34076+0=34076 其最大和为40676。 问题：当数字串和k给出后，找出一个分法使和为最大。 Input Output Sample Input 6 1 340670  Sample Output 40673  解题思路 这道题看似简单，但实际上也很简单。这道题不需要用到高精度，只用使用 l o n g long lo...

乘积最大  Description 今年是国际数***盟确定的“2000——世界数学年”，又恰逢我国著名数学家华罗庚先生诞辰90周年。在华罗庚先生的家乡江苏金坛，组织了一场别开生面的数学智力竞赛的活动，你的一个好朋友XZ也有幸得以参加。活动中，主持人给所有参加活动的选手出了这样一道题目： 设有一个长度为N的数字串，要求选手使用K个乘号将它分成K+1个部分，找出一种分法，使得这K+1个部分的乘积能够为最大。 同时，为了帮助选手能够正确理解题意，主持人还举了如下的一个例子： 有一个数字串：312， 当N=3，K=1时会有以下两种分法： 1) 312=36   2) 312=62 这时，符合题目要求...

SSL暑假训练总结  第一周 第一周过的还算好吧，觉得饭堂伙食也挺好的，同学也挺好。学习的东西感觉比小学难好多，有种觉得以前学的东西太简单了的感觉，但多亏了小学的时候基础打得还算扎实，学得还行，但总是感觉自己就是个菜鸡，就是一个蒟蒻，哎，室友真的太强了。 第一周总结  第二周 第二周自我感觉挺不错的，总算追上了部分室友，成绩也开始上涨（这一切都亏了姜老师和各位神仙学长们的帮助），而且注册了博客，也发了好几篇，对自己挺有帮助的，加油。 第二周总结 学习内容 第一周学了高精度、深度搜索，第二周学习了排列组合初步、动态规划初步，难度还可以，学得也算不错吧。 总结 总之，这两周的训练让我熟悉了初中的学...

电子眼  Description 中山市石一个环境优美、气候宜人的小城市。因为城市的交通并不繁忙，市内的道路网很稀疏。准确地说，中山市有N-1条马路和N个路口，每条马路连接两个路口，每两个路口之间最多只有一条马路。作为一条交通网络，显然每两个路口之间都是可达的。为了更好地管理中山市的交通，市长决定在一些路口加装电子眼，用来随时监视路面情况。这些装在路口的电子眼能够监视所有连接到这个路口的马路。现在市长想知道最少需要在多少个路口安装电子眼才能监视所有的马路。市长已经把所有的路口都编上了1～N的号码。 给你中山市的地图，你能帮忙吗？ Input 输入文件traffic.in的第1行包括一个数字N(...

矩阵乘积  Description  Input n表示矩阵的个数(<=100) n+1个数,表示矩阵(<=100) Output 最小的乘法次数 Sample Input 5 5 10 4 6 10 2  Sample Output 348  解题思路 这道题的动态转移方程:  c [ j ] [ i ] = m i n ( c [ j ] [ i ] , c [ j + k ] [ i − k ] + c [ j ] [ k ] + a [ j ] ∗ a [ i + j ] ∗ a [ j + k ] ) ; c[j][i]=min(c[j][i],c[j+k][i-k]+c...

苹果  Description 农场的夏季是收获的好季节。在Farmer John的农场，他们用一种特别的方式来收苹果：Bessie摇苹果树，苹果落下，然后Farmer John尽力接到尽可能多的苹果。   作为一个有经验的农夫， Farmer John将这个过程坐标化。他清楚地知道什么时候(1<=t<=1,000,000)什么位置(用二维坐标表示，-1000<=x,y<=1000)会有苹果落下。他只有提前到达那个位置，才能接到那个位置掉下的苹果。   一个单位时间，Farmer John能走s(1<=s<=1000)个单位。假设他开始时(t=0)站在(0,...

书的复制  Description 现在要把m本有顺序的书分给k个人复制（抄写），每个人的抄写速度都一样，一本书不允许分给两个或两个以上的人抄写，分给每个人的书，必须是连续的，比如不能把第一、第三、第四本书给同一个人抄写。 现在请你设计一种方案，使得复制时间最短。复制时间为抄写最多的人用去的时间。 Input 第一行两个整数，m,k(k<=m<=500) 第二行为m个整数，第i个数表示第i本书的页数。 Output 最短时间 Sample Input 9 3 1 2 3 4 5 6 7 8 9  Sample Output 17  解题思路 这道题没什么思路，直接进入主题——状态转...

能量项链  Description 在Mars星球上，每个Mars人都随身佩带着一串能量项链。在项链上有N颗能量珠。能量珠是一颗有头标记与尾标记的珠子，这些标记对应着某个正整数。并且，对于相邻的两颗珠子，前一颗珠子的尾标记一定等于后一颗珠子的头标记。因为只有这样，通过吸盘（吸盘是Mars人吸收能量的一种器官）的作用，这两颗珠子才能聚合成一颗珠子，同时释放出可以被吸盘吸收的能量。如果前一颗能量珠的头标记为m，尾标记为r，后一颗能量珠的头标记为r，尾标记为n，则聚合后释放的能量为（Mars单位），新产生的珠子的头标记为m，尾标记为n。   需要时，Mars人就用吸盘夹住相邻的两颗珠子，通过聚合得到...

CIM  Description 给出一个1到n的排列，每次可以移动一个数到一个任意位置。问要达到状态1,2,3……n至少移动多少次？ Input n （１<=n<=100000） n个数 Output 移动次数！ Sample Input 5 2 1 4 5 3  Sample Output 2  解题思路 这道题其实就是求n-最长上升子序列的长度。动态转移方程：  i f ( a [ i ] > = f [ m ] ) m + + ; f [ m ] = a [ i ] ; if(a[i]>=f[m]){m++;f[m]=a[i];} if(a[i]>=f[m...

取数字问题  Description 给定M*N的矩阵，其中的每个元素都是-10到10之间的整数。你的任务是从左上角（1，1）走到右下角（M，N），每一步只能向右或向下，并且不能走出矩阵的范围。你所经过的方格里面的数字都必须被选取，请找出一条最合适的道路，使得在路上被选取的数字之和是尽可能小的正整数。 Input 第一行两个整数M，N，（2<=M,N<=10），分别表示矩阵的行和列的数目。接下来的M行，每行包括N个整数，就是矩阵中的每一行的N个元素。 Output 仅一行一个整数，表示所选道路上数字之和所能达到的最小的正整数。如果不能达到任何正整数就输出-1。 Sample Inp...