CF 637 div2

有空补上。

A题：

题意：t个测试数据，每个数据给出n个数,每个数在[a-b,a+b],询问n个数的和是否在[c-d,c+d]上。

分析：直接判断n个数的最大值是否小于c-d或者最小值大于c+d,满足的话输出No。否则输出Yes。

代码：

 1 #include <iostream>
 2 #include <cstdio>
 3 using namespace std;
 4 int t,n,a,b,c,d;
 5 int main(void)
 6 {
 7     scanf("%d",&t);
 8     while(t--)
 9     {
10         scanf("%d %d %d %d %d",&n,&a,&b,&c,&d);
11         if(n*(a-b)>c+d||n*(a+b)<c-d)printf("No
");
12         else printf("Yes
");
13     }
14     return 0;
15 }

B题：

题意：对每一个例给出一组数据，求该组数据中一个长度为k的区间的最大山峰数以及该区间的左下标。

分析：对每一个山峰？（英语不好）做一个标记，然后设置一个长度为k的区间，从1到k，然后将这个区间滑动到最后，过程中更新最大山峰数以及区间左下标。怎么更新呢？设置一个变量now记录当前的山峰数，向右滑动时如果加入的点是标记点的后一个，那么now++;出去的点如果是标记点的前一个, now--。最后输出即可。

代码：

 1 #include <iostream>
 2 #include <cstdio>
 3 using namespace std;
 4 int t,n,k,a[210000],f[210000];
 5 int main(void)
 6 {
 7     scanf("%d",&t);
 8     while(t--)
 9     {
10         scanf("%d %d",&n,&k);
11         for(int i=1;i<=n;i++)
12         {
13             scanf("%d",&a[i]);
14             f[i]=0;
15         }
16         for(int i=2;i<n;i++)
17         {
18             if(a[i]>a[i+1]&&a[i]>a[i-1])f[i]=1;
19         }
20         int maxx=0,now=0,left=1;
21         for(int i=2;i<k;i++)
22         {
23             if(f[i])now++;
24         }
25         maxx=maxx>now?maxx:now;
26         for(int i=k+1;i<=n;i++)
27         {
28             if(f[i-1])now++;
29             if(f[i-k+1])now--;
30             if(now>maxx)
31             {
32                 maxx=now;
33                 left=i-k+1;
34             }
35         }
36         printf("%d %d
",maxx+1,left);
37     }
38     return 0;
39 }

C题：

题意：（理解了好久）对每组排列，判断生成器能否生成该组排列，生成器生成排列规则如下：

1.对于每一个下标j,1<=j<=n,r_j等于后面最近的空位下标，否则为0。

2.对于每一个下标t,cnt_t等于r_j=t的数量（1<=j<=n），如果该位置被占用则无效。

3.生成器必须取cnt_t最大的位置存放当前的数，如果不止一个最大，那可以在这些位置中任意选择。

分析：首先存放的数对cnt和r没有影响，关键是存放的位置，容易知道一开始没有放任何数时，所有的cnt_t都等于1，假设我们第一个是存放的位置是i,那么就有两种情况：

（1）i=n，也就是放在最后一位，此时cnt n无效，而其他的所有cnt_t仍为1，因为对1<=j<=n,r_j=j;所有对1<=t<=n-1,cnt_t=1。我们接下来相当于来到把n-1个数放进n-1个位置，相比原来仅仅少了一个数。

（2）i<n，此时r_i=i+1,r_i+1=i+1,cnt_i无效，而cnt_i+1=2,其他所有cnt_t=1,因此下一个数只能存放在i+1位置，而这又导致cnt_i+2最大，从而得到结论：如果这个位置紧邻着下一个空位，那么下一个数必定存在下一个空位。

最后思路便是：对于1<=i<n,a[i+1]==a[i]+1 or a[i+1]<a[i]，否则不能生成该排列。

代码：

 1 #include <iostream>
 2 #include <cstdio>
 3 using namespace std;
 4 int t,n,p[110000];
 5 int main(void)
 6 {
 7     cin>>t;
 8     while(t--)
 9     {
10         cin>>n;
11         for(int i=1;i<=n;i++)cin>>p[i];
12         int i;
13         for(i=2;i<=n;i++)
14         {
15             if(p[i]>p[i-1]+1)break;
16         }
17         if(i<=n)printf("No
");
18         else printf("Yes
");
19     }
20     return 0;
21 }