Codeforces Round #153 (Div. 2)

<a target="_blank" href="http://codeforces.com/contest/252">点击打开链接cf #153</a>

A

思路：暴力

分析：

1 题目给定n个数 n&lt;=100，要求一个区间内做^能够得到的最大值

2 n最大为100，暴力枚举区间即可。

代码：

B

法一

1 题目问能否找到两个不同的位置i , j.使得i 和 j交换后序列不是有序的。如果找不到输出-1

2 很明显n&lt;=2时是不可能找到的，输出-1；还有一中特殊的情况就是num[1]=num[2]=...=num[n]，这种也是输出-1.

3 接下来就是暴力枚举i个j的值，然后找到满足的即可。

4 注意如果没有找到应该输出-1，这里不能漏了。

法二

思路：分类模拟

1 题目要求找到两个位置交换这两个位置的数，使得序列不是单调的。如果没有输出-1

2 如果n&lt;=2，肯定是不可能找到满足的位置的。

3 那么我们可以通过分析序列总共有几个不同的数字。

   如果只有1个就是类似1 1 1...这样的肯定找不到输出-1；

   如果是2个那么我们一个for循环找到num[i] != num[i-1]，然后交换它判断是否满足即可。2个的情况可能会有不满足情况，如果都不满足那么就输出-1；

   如果是大于等于3个，那么我们只要找出三个不同的数然后交换。但是这三个数原先的排列情况有4种(/，/\，\，\/ 表示增减)。那么我们只要去判断最大值的位置就可以。有三个不同的数那么肯定是可以找到两个位置的。

C

思路：1 枚举起点，维护一个末尾指针。2 另外一种做法是把维护的指针 j 改成二分查找

1 题目给定一个n个数的有序序列，要求找到最多的方法满足题目要求。

2 我们知道一个有序的序列是很特殊的，假设现在我们的起点是num[i]，那么我们维护一个指针j，使得num[j]-num[i] &gt; d。那么我们知道[i,j)就有j-i-1个数，所以知道了起点那么满足的个数就是C(j-i-1,2){组合公式}。那么我们接下来起点变成了num[i+1]，这个时候正常的做法是j 从 i+2开始，但是由于这个序列是有序的序列有num[i]&gt;num[i-1]，那么肯定 j 之前的数都满足num[j-1]-num[i+1] &lt;= d，所以 j 不用回溯这样就不是O(n^2)而是接近O(n)的复杂度。

3 注意：假设int n = 100000 ， long long  ans = n*(n-1)*(n-2)；这个运算实际是得不到ans的，由于n是int,所以运算的时候超出了int范围，所以得到的ans是错误的。应该注意ans是long long 的情况下 n 也要改为 long long.  

4 对于一个有序的序列进行二分的时候是可以利用STL的lower_bound() 和 upper_bound()函数的。

D

1 题目的意思给定一个序列p初始为1,2,3....n。再给定一个序列q和一个序列s，做k次的变换

2 每一次的变换有两种可能，第一种是生成一个新的序列p且newp[i] = p[q[i]]，第二种是生成一个新的序列p且newp[q[i]] = p[i]

3 现在题目要问的是把初始化的序列p做k次的变换，能否前k-1次都没有出现序列s，最后一次序列正好为s

4 根据第2点，我们可以推出第一种变换和第二种变换是逆的。也就是说做一次的第一种和一次的第二种变换得到的原来的序列。

5 如果我们执行m1次第一种变换可以使得序列p等于序列s，那么我们先执行(k - m1) / 2次的(第一种变换、第二种变换)组合，再执行m1次第一种变换 即可。

   如果我们执行m2次 第二种变换可以使得序列p等于序列s，那么我们先执行(k - m2) / 2次的(第一种变换、第二种变换)组合，再执行m2次第二种变换即可。

   所以只要求出其中的m1、m2再判断一下k - m1，k - m2是否是偶数就行了。