Educational Codeforces Round 69

最近水平下降有点严重啊。。。还是多打CF熟悉手感

A. DIY Wooden Ladder

水题，给一个序列a，问最大K是多少？

条件是序列中有两个值大于k+1，其他的有k个大于等于1的值

直接排序即可，最多也就n-2条，枚举判断即可

#include<iostream>
#include<string.h>
#include<algorithm>
#include<stdio.h>
#include<queue>
#include<stack>
#include<vector>
#include<list>
#include<set>
#define LL long long
#define pii pari<int,int>
#define mp make_pair
using namespace std;
const int maxx = 1e5+6;
int a[maxx];
int main(){
  int t,n;
  scanf("%d",&t);
  while(t--){
     scanf("%d",&n);
     for (int i=1;i<=n;i++){
        scanf("%d",&a[i]);
     }
     sort(a+1,a+1+n);
     int ans=0;
     for (int i=1;i<=n-2;i++){
         if (a[n-1]>=i+1){
            ans=i;
         }else break;
     }
     printf("%d\n",ans);
  }
  return 0;
}

View Code

B. Pillars

给定一个位置，只有一个固定大小的磁盘，你只能在相邻的磁盘之间移动，问能不能移动到一个上面，并且移动的同时，只能把面积小的往面积大的上面移动，问能不能把所有的都移动到一个上面。

直接开两个队列，判断即可，如果能够移动，一定是按照降序的顺序，放入的。

#include<iostream>
#include<string.h>
#include<algorithm>
#include<stdio.h>
#include<queue>
#include<stack>
#include<vector>
#include<list>
#include<set>
#define LL long long
#define pii pari<int,int>
#define mp make_pair
using namespace std;
queue<int>s;
queue<int>ss;
int a[200005];
int main(){
  int n;
  while(~scanf("%d",&n)){
    int maxx=0,id=0;
    while(s.size())s.pop();
    while(ss.size())ss.pop();
    for (int i=1;i<=n;i++){
        scanf("%d",&a[i]);
        if (a[i]>maxx){
            maxx=a[i];
            id=i;
        }
    }
    for (int i=id-1;i>=1;i--){
          s.push(a[i]);
    }
    for (int i=id+1;i<=n;i++){
         ss.push(a[i]);
    }
    int now=n-1;
    int flag=0;
    while(now>=1){
          if (s.size() && s.front()==now){
              s.pop();
          }else if (ss.size() && ss.front()==now){
              ss.pop();
          }else {
            flag=1;
            break;
          }
          now--;
    }
    if (flag)printf("NO\n");
    else printf("YES\n");
  }
  return 0;
}

View Code

C. Array Splitting

这题想错了，我开始是直接二分每个区间的最大间距

但是这样保证了，最大的区间内部数据的极差最小，但是

这却不是这些极差和最小的，

我们这样考虑这个问题

我们吧这个序列分成1-i i+1....j j+1...n等这些区间

求的是区间内部最大值与最小值的差值和最小。

其实这个非常简单，我们发现题目数值是顺序给的。。。

这些区间的最值之差，就是差分。两个两个数字划分到不同区间

那么他们之间的差分其实就没有了。

所有要划分k个区间，等价于取消k-1个差分，而取消的这k-1必须是

最小的。从而题目迎刃而解

#include<iostream>
#include<string.h>
#include<algorithm>
#include<stdio.h>
#include<queue>
#include<stack>
#include<vector>
#include<list>
#include<set>
#define LL long long
#define pii pari<int,int>
#define mp make_pair
using namespace std;
const int maxx = 3e5+6;
int a[maxx];
int b[maxx];
int main(){
  int n,k;
  while(~scanf("%d%d",&n,&k)){
      for (int i=1;i<=n;i++){
        scanf("%lld",&a[i]);
      }
      for (int i=1;i<n;i++){
        b[i]=a[i+1]-a[i];
      }
      int ans=0;
      sort(b+1,b+n);
      for (int i=1;i<=n-k;i++){
        ans+=b[i];
      }
      printf("%d\n",ans);
  }
  return 0;
}

View Code

D. Yet Another Subarray Problem

首先拿到题目，这个m小到不科学，一看基本上确定就是DP了，那么怎么搞呢？？？

我们可以很容易知道一件事情，DP可以写成dp[i][j]，我们如何转移呢？？

这简单嘛，我们发现dp[i][0]=max(dp[i-1][m-1]+a[i]-k,a[i]-k)这个怎么理解呢？？？

也就是说，我们的右端点为i并且（区间长度-1）% m=j时候的值，为什么要减1，因为。。这样把在0的时候进行-k的操作，比较好算一点

意思就是，当前如果长度为1，那么我们应该是从上一位长度0的地方减去k并加上a[i]，这样就能算出来了，而后面的，由于不涉及-k了，那么直接加上就可以了。

转移方程

dp[i][0]=max(dp[i-1][m-1]+a[i]-k,a[i]-k)

dp[i][j]=dp[i-1][j-1]+a[i]

维护最大值即可

#include<iostream>
#include<stdio.h>
#include<algorithm>
#define LL long long
using namespace std;
const int maxx = 3e5+7;
LL a[maxx];
LL dp[maxx][15];
int n;
int main(){
   int n,m,k;
   while(~scanf("%d%d%d",&n,&m,&k)){
      for (int i=1;i<=n;i++){
          scanf("%lld",&a[i]);
      }
      for (int i=0;i<=n;i++){
        for (int j=0;j<m;j++){
            dp[i][j]=-1e18;
        }
      }
      LL ans=0;
      dp[0][m-1]=0;
      for (int i=1;i<=n;i++){
          dp[i][0]=max(dp[i-1][m-1]-k+a[i],a[i]-k);
          ans=max(ans,dp[i][0]);
          for (int j=1;j<=m-1;j++){
              dp[i][j]=dp[i-1][j-1]+a[i];
              ans=max(dp[i][j],ans);
          }
      }
      printf("%lld\n",ans);
   }
   return 0;
}