Educational Codeforces Round 69 （A、B、C、D）

A. DIY Wooden Ladder

贪心水题

 1 #include<iostream>
 2 #include<sstream>
 3 #include<fstream>
 4 #include<algorithm>
 5 #include<cstring>
 6 #include<iomanip>
 7 #include<cstdlib>
 8 #include<cctype>
 9 #include<vector>
10 #include<string>
11 #include<cmath>
12 #include<ctime>
13 #include<stack>
14 #include<queue>
15 #include<map>
16 #include<set>
17 #define mem(a,b) memset(a,b,sizeof(a))
18 #define random(a,b) (rand()%(b-a+1)+a)
19 #define ll long long
20 #define ull unsigned long long
21 #define e 2.71828182
22 #define Pi acos(-1.0)
23 using namespace std;
24 const int MAXN=1e5+5;
25 int a[MAXN];
26 int n;
27 int read()
28 {
29     int s=1,x=0;
30     char ch=getchar();
31     while(!isdigit(ch)) {if(ch=='-') s=-1;ch=getchar();}
32     while(isdigit(ch)) {x=10*x+ch-'0';ch=getchar();}
33     return x*s;
34 }
35 int solve()
36 {
37     sort(a+1,a+n+1,greater<int>());
38     if(n==2) return 0;
39     int high=min(a[1],a[2]);
40     if(high==1) return 0;
41     return high-1<n-2?high-1:n-2;
42 }
43 int main()
44 {
45     int T;cin>>T;
46     while(T--)
47     {
48         cin>>n;
49         for(int i=1;i<=n;++i) cin>>a[i];
50         cout<<solve()<<endl;
51     }
52     return 0;
53 }
54

View Code

B.Pillars

找到最大值的下标，必须向两侧递减

 1 #include<iostream>
 2 #include<sstream>
 3 #include<fstream>
 4 #include<algorithm>
 5 #include<cstring>
 6 #include<iomanip>
 7 #include<cstdlib>
 8 #include<cctype>
 9 #include<vector>
10 #include<string>
11 #include<cmath>
12 #include<ctime>
13 #include<stack>
14 #include<queue>
15 #include<map>
16 #include<set>
17 #define mem(a,b) memset(a,b,sizeof(a))
18 #define random(a,b) (rand()%(b-a+1)+a)
19 #define ll long long
20 #define ull unsigned long long
21 #define e 2.71828182
22 #define Pi acos(-1.0)
23 using namespace std;
24 const int MAXN=2e5+5;
25 int imax,a[MAXN];
26 int read()
27 {
28     int s=1,x=0;
29     char ch=getchar();
30     while(!isdigit(ch)) {if(ch=='-') s=-1;ch=getchar();}
31     while(isdigit(ch)) {x=10*x+ch-'0';ch=getchar();}
32     return x*s;
33 }
34 int main()
35 {
36     int n=read();
37     for(int i=1;i<=n;++i)
38     {
39         a[i]=read();
40         if(a[i]==n) imax=i;
41     }
42     bool flag=true;
43     for(int i=1;i<=imax-1&&flag;++i)
44     if(a[i]>a[i+1]) flag=false; 
45     for(int i=imax;i<=n-1&&flag;++i)
46     if(a[i]<a[i+1]) flag=false;
47     if(flag) cout<<"YES
";
48     else cout<<"NO
";
49 }

View Code

C.Array Splitting

a[n]-a[1]=(a[n]-a[n-1])+(a[n-1]-a[n-2])+...+(a[2]-a[1])。划分k个区间相当于从(a[2]-a[1],a[3]-a[2],...,a[n]-a[n-1])中去掉k-1个值。排序后减去前k-1个打的。

 1 #include<iostream>
 2 #include<sstream>
 3 #include<fstream>
 4 #include<algorithm>
 5 #include<cstring>
 6 #include<iomanip>
 7 #include<cstdlib>
 8 #include<cctype>
 9 #include<vector>
10 #include<string>
11 #include<cmath>
12 #include<ctime>
13 #include<stack>
14 #include<queue>
15 #include<map>
16 #include<set>
17 #define mem(a,b) memset(a,b,sizeof(a))
18 #define random(a,b) (rand()%(b-a+1)+a)
19 #define ll long long
20 #define ull unsigned long long
21 #define e 2.71828182
22 #define Pi acos(-1.0)
23 using namespace std;
24 const int MAXN=3e5+5;
25 int a[MAXN],b[MAXN];
26 int read()
27 {
28     int s=1,x=0;
29     char ch=getchar();
30     while(!isdigit(ch)) {if(ch=='-') s=-1;ch=getchar();}
31     while(isdigit(ch)) {x=10*x+ch-'0';ch=getchar();}
32     return x*s;
33 }
34 int main()
35 {
36     int n=read();
37     int k=read();
38     for(int i=1;i<=n;++i)
39     a[i]=read();
40     int ans=a[n]-a[1];
41     for(int i=2;i<=n;++i)
42     b[i]=a[i]-a[i-1];
43     sort(b+2,b+n+1,greater<int>());
44     //for(int i=2;i<=n;++i) cout<<b[i]<<' ';cout<<endl;
45     for(int i=2+0;i<2+k-1;++i)
46     ans-=b[i];
47     cout<<ans<<endl;
48 }

View Code

一开始想用Dp，但复杂度不允许。令dp[i][j]表示前i个数划分成j个子数组（第j个数位于第j个子数组），那么dp[i][j]=min(dp[i-1][j-1],dp[i-1][j]+a[i]-a[i-1])。初始化dp中的值为无穷大，dp[1][1]=0。

D.Yet Another Subarray Problem

令dp[i]表示右边界为a[i]时的最佳答案。，根据该公式将j（左边界）分为两种情况：

1、i-j+1<=m即i-j+1<m+1，即i-j<m，此时dp[i]=sum[i]-sum[j-1]-k

2、i-j>=m，此时dp[i]=dp[i-m]+sum[i]-sum[i-m]-k

取较大值（最佳值）即可。

 1 #include<iostream>
 2 #include<sstream>
 3 #include<fstream>
 4 #include<algorithm>
 5 #include<cstring>
 6 #include<iomanip>
 7 #include<cstdlib>
 8 #include<cctype>
 9 #include<vector>
10 #include<string>
11 #include<cmath>
12 #include<ctime>
13 #include<stack>
14 #include<queue>
15 #include<map>
16 #include<set>
17 #define mem(a,b) memset(a,b,sizeof(a))
18 #define random(a,b) (rand()%(b-a+1)+a)
19 #define ll long long
20 #define ull unsigned long long
21 #define e 2.71828182
22 #define Pi acos(-1.0)
23 using namespace std;
24 const int MAXN=3e5+5;
25 const int INF=1<<30;
26 int a[MAXN];
27 ll dp[MAXN],sum[MAXN];
28 int n,m,k;
29 ll read()
30 {
31     ll s=1,x=0;
32     char ch=getchar();
33     while(!isdigit(ch)) {if(ch=='-') s=-1;ch=getchar();}
34     while(isdigit(ch)) {x=10*x+ch-'0';ch=getchar();}
35     return x*s;
36 }
37 int main()
38 {
39     n=read();m=read();k=read();
40     ll ans=-INF;
41     for(int i=1;i<=n;++i) a[i]=read(),sum[i]=sum[i-1]+a[i];
42     for(int i=1;i<=n;++i)
43     {
44         for(int j=max(i-m+1,1);j<=i;++j) dp[i]=max(dp[i],sum[i]-sum[j-1]-k);
45         if(i>=m) dp[i]=max(dp[i],dp[i-m]+sum[i]-sum[i-m]-k);
46         ans=dp[i]>ans?dp[i]:ans;
47     }
48     cout<<ans<<endl;
49     return 0;
50 }

View Code