2016寒假训练3

题目链接

A CodeForces 362A Two Semiknights Meet

题意：在一个棋盘中有两个定义了特殊走法的棋子，同时移动他们，问是否会相遇（只能在合法的位置）。

做法：直接暴力dfs处理出这两个棋子到达各个位置的时间，如果到达同一个格子的时间差％2=＝0，就可以相遇。

B CodeForces 362B Petya and Staircases

题意：跳台阶，有的位置是坏的，问是否可以跳到顶层

正解就是直接模拟

C CodeForces 362C Insertion Sort

题意：给定n个数0～n-1的数列，求逆序对以及交换该数列中任意两个数之后最小的逆序对数

做法：dp预处理之后，枚举修改的两个数。也可以用树状数组。

D CodeForces 362D Fools and Foolproof Roads

题意：给定一个n个点m条边的无向图，要求在图里面增加p条边（边权按照题目给的条件），并且这张图的连通分量数为q。

做法：贪心。每次取出连通块中最小的两块进行合并。

E CodeForces 362E Petya and Pipes

费用流模版题

F CodeForces 365A Good Number

题意：题意坑爹。能过样例基本就没问题了。给定n和k，问接下去的n个数中有哪些数字是由0~k组成的（0～k都必须出现）。

做法：直接做。。

G CodeForces 365B The Fibonacci Segment

题意：找出最长的符合斐波那契的长度。

做法：预处理之后直接做。但是要注意n＝1，n=2，以及连续0的情况。

H CodeForces 365C Matrix

题意：给定a和s，构造一个矩阵bij = si·sj，问有多少个子矩阵的和为a。

做法：先预处理出前缀和数组sum[i],然后构造times数组，times[i]表示和为i的前缀和段的出现次数。然后枚举。a＝0的情况需要特殊讨论。

I CodeForces 365D Free Market

题意：每天可以去市场上进行一次物品交换，要求交换的物品当前没有，并且价值差不小于d。求可以获得的最大价值以及天数。

做法：dp预处理出可以取到的所有价值。然后从0开始取物品，直到某一天不能进行交换为止。

题目＋简要题解＋代码