2016寒假训练2

题目链接

A CodeForces 361A Levko and Table

题意:构造出一个大小为n的矩阵,使得每一行,每一列的和均为k

做法:直接构造一个对角线为k,其他元素均为0的矩阵即可

B CodeForces 361B Levko and Permutation

题意:有n个数1,2,3~n,要求我们求出一个序列,使其满足恰好有k个美丽数。美丽数的定义是 gcd( i , pi ) >1,也就是这个位置上的数和这个位置编号的gcd>1

做法:很显然gcd(1,n)=1,无论如果操作,第一个数必定不符合要求。所以如果n=k,无论怎么操作都不可能可以,直接输出-1.

正解就是直接构造:

在1~n-k-1号位置上依次放上i+1,因为gcd(i,i+1)=1,不会影响答案

在第n-k号位置上放上1

然后在n-k+1~n号位置上放下和编号相同的数即可

C CodeForces 361C Levko and Array Recovery

题意:告诉我们序列长度n和一系列操作,问我们是否可以得到一个满足条件的原数列。操作分为查询区间最大值和区间整体加上一个值

做法:按照已知的操作,求出原数列每一个位置上的值的最大值,然后检查是否合法

D CodeForces 361D Levko and Array

题意:给定n个数和k,求改变这n个数中的k个使得c值尽量小。 c=max ( abs(a[i+1] – a[i]) )

做法:二分答案。 f[i]表示第i个数不修改,前i个数符合答案为c值的最小修改次数。那么我们可以枚举上一次没有修改过的位置j

if (abs(a[i]-a[j])<=(i-j)*x)
  f[i]=min(f[i],f[j]+(i-j-1));

如果 abs (a[i]-a[j])<=x*(i-j) 那么我们可以通过修改i~j-1中的所有数,使得他们满足要求

F CodeForces 358A Dima and Continuous Line

题意:给出n个一维坐标点(xi,0) 判断线段是否相交

做法:直接枚举。判断两线段是否相交条件是

 if  ((x2>x1 && x2<y1 && y2>y1)
  || (x2<x1 && y2>x1 && y2<y1))

G CodeForces 358B Dima and Text Messages

题意:给定n个字符串,每一个字符串前后加上“❤️” 得到新的字符串s。再输入一个字符串t,询问t是否可以由s插入某些字符得到

做法:直接模拟

H CodeForces 358C Dima and Containers

整题的难度就在于读懂题目。。

做法就是贪心

I CodeForces 358D Dima and Hares

题意:有n只兔子站成一排,我们需要安排一个喂兔子的顺序,使得所有兔子的happy值总和最大。以下的3种情况happy值不同:

1.这只兔子左右都还没有吃过(1号和n号兔子只有一侧)

2.这只兔子左右一个吃过,一个没吃过

3.这只兔子左右都吃过

做法:DP。

f[i][0]表示先喂了i-1 再喂i号兔子前i只兔子的最大happy值

f[i][1]表示先喂了i 再喂i-1号兔子前i只兔子的最大happy值

转移不难想到

题目+简要题解+代码

原文地址:https://www.cnblogs.com/Coolaaa/p/5177476.html