前言
难度不好说，感觉是东拼西凑的题，但是除了 \(T1\) 都不简单。
-
\(T1~100pts:\)
贪心+四边形不等式。
-
\(T2~70pts:\)
读假题了，是最大 \(w_i\) 不是固定 \(w_i\) ，做法是 二分答案+DP ，不过需要单调队列优化，不会这玩意儿赛后学了好久 \(qwq\) 。
但是读假题了还能拿 \(70pts\) 。
-
\(T3~0pts:\)
不会，没思路，建树都每建明白。
题解给了一半，正解没给，给了个复杂度 \(O(n^2)\) 的要过 \(3e5\) ，
差评！ -
\(T4~0pts:\)
本来人手骗 \(20pts\) 的，\(continue\) 加错地方了，喜提 \(0pts\) 。
T1 排序
-
题意：
给定 \(4n\) 个数 \(s_i\) ，分别 \(n\) 组，对于每组 \(4\) 个数 \(a,b,c,d\) ，求所有组 \(|ab-cd|\) 的最大和。
-
解法：
-
导入一个常识：
已知 \(s\) ，将其拆分为 \(s=a+b\) ，若想 \(a\times b\) 尽可能小，则 \(|a-b|\) 尽可能大；若想 \(a\times b\) 尽可能大，则 \(|a-b|\) 尽可能小。
和相同周长的 \(S_{正方形}>S_{长方形}\) 是一个道理。
先将所有 \(s_i\) 排序，设 \(ab>cd\) 。
将所有 \(s_i\) 分为大的和小的两组，\(a,b\) 相邻搭配，\(c,d\) 分别从两边取即可。
直接看代码就行了，签到题。
-
点击查看代码
#include<bits/stdc++.h>
#define int long long
#define endl '\n'
using namespace std;
const int N=4e5+10;
template<typename Tp> inline void read(Tp&x)
{
x=0;register bool z=1;
register char c=getchar();
for(;c<'0'||c>'9';c=getchar()) if(c=='-') z=0;
for(;'0'<=c&&c<='9';c=getchar()) x=(x<<1)+(x<<3)+(c^48);
x=(z?x:~x+1);
}
int n,a[N],ans,sum;
signed main()
{
#ifndef ONLINE_JUDGE
freopen("in.txt","r",stdin);
freopen("out.txt","w",stdout);
#endif
read(n);
for(int i=1;i<=4*n;i++)
read(a[i]);
stable_sort(a+1,a+1+4*n);
for(int i=1,j=4*n;i<=n,j>=2*n+1;i++,j-=2)
ans+=a[j]*a[j-1]-a[i]*a[2*n-i+1];
cout<<ans;
}
T2 牛吃草
- 题意：
此处注意他是延伸距离最大为 \(w_i\) ，不是固定 \(w_i\) ，赛时因为这个读假题了 \(qwq\) 。
-
部分分：
-
\(70pts:\)
读假题的情况，二份答案+ \(O(n)的DP\) 。
定义 \(f[i][1]\) 为第 \(i\) 个位置上放的最大覆盖长度，反之 \(f[i][0]\) 就是不放的情况。
转移方程为:
\(f[i][1]=\max(f[i-len[i]][1],f[i-len[i]][0])+len[i];\)
\(f[i][0]=\max(f[i-1][1],f[i-1][0])\) 。
此处 \(len_i\) 为其真实的 \(w_i\) ，因为他左端点顶到头就 \(1\) 了，再往前就负了，比如不管 \(w_1\) 为多少，\(len_1\) 都 \(=1\) 。
因为读假题了， \(DP\) 自然成 \(O(n)\) 了。
复杂度最坏情况下 \(O(n\log(n))\) ，实则只要 \(f_i>=s\) 就说明满足，跳出就行了，所以真实复杂度远小于此。
点击查看代码
#include<bits/stdc++.h> #define int long long #define endl '\n' using namespace std; const int N=5e5+10; template<typename Tp> inline void read(Tp&x) { x=0;register bool z=1; register char c=getchar(); for(;c<'0'||c>'9';c=getchar()) if(c=='-') z=0; for(;'0'<=c&&c<='9';c=getchar()) x=(x<<1)+(x<<3)+(c^48); x=(z?x:~x+1); } int n,s,l,r,maxx,mid,ans,w,f[N][2]; struct aa { int l,len; }a[N]; bool DP(int x,int s) { for(int i=1;i<=n;i++) f[i][0]=f[i][1]=0; for(int i=1;i<=n;i++) { if(a[i].len>=x) f[i][1]=max(f[a[i].l-1][1],f[a[i].l-1][0])+a[i].len; f[i][0]=max(f[i-1][1],f[i-1][0]); if(f[i][1]>=s||f[i][0]>=s) return 1; } return 0; } signed main() { #ifndef ONLINE_JUDGE freopen("in.txt","r",stdin); freopen("out.txt","w",stdout); #endif read(n); for(int i=1;i<=n;i++) read(w), a[i].l=max(1ll,i-w+1), a[i].len=i-a[i].l+1, maxx=max(maxx,a[i].len); read(s); s=ceil(double(n*s/100.0)); l=1,r=maxx; while(l<=r) { mid=(l+r)>>1; if(DP(mid,s)) ans=max(ans,mid),l=mid+1; else r=mid-1; } cout<<ans; } -
\(90pts:\)
把题读真了，发现还需要套一层循环。
循环 \(j=\{i-len_i\sim i-size\}\) ，那么转移方程为：
\(f[i][1]=\max(\{f[i][1],f[j][1]+i-j,f[j][0]+i-j\});\)
\(f[i][0]\) 和 \(70pts\) 的一样。
这样复杂度最坏就成了 \(O(n^2\log(n))\) ，虽然真实情况比这小，但还是会 \(TLE\) 两个点。
点击查看代码
#include<bits/stdc++.h> #define int long long #define endl '\n' using namespace std; const int N=5e5+10; template<typename Tp> inline void read(Tp&x) { x=0;register bool z=1; register char c=getchar(); for(;c<'0'||c>'9';c=getchar()) if(c=='-') z=0; for(;'0'<=c&&c<='9';c=getchar()) x=(x<<1)+(x<<3)+(c^48); x=(z?x:~x+1); } int n,s,l,r,maxx,mid,ans,w,f[N][2]; struct aa { int l,len; }a[N]; bool DP(int x,int s) { f[0][0]=f[0][1]=0; for(int i=1;i<=n;i++) { f[i][1]=0; for(int j=i-a[i].len;j<=i-x;j++) f[i][1]=max({f[i][1],f[j][1]+i-j,f[j][0]+i-j}); f[i][0]=max(f[i-1][1],f[i-1][0]); if(f[i][1]>=s||f[i][0]>=s) return 1; } return 0; } signed main() { #ifndef ONLINE_JUDGE freopen("in.txt","r",stdin); freopen("out.txt","w",stdout); #endif read(n); for(int i=1;i<=n;i++) read(w), a[i].l=max(1ll,i-w+1), a[i].len=i-a[i].l+1, maxx=max(maxx,a[i].len); read(s); s=ceil(double(n*s/100.0)); l=1,r=maxx; while(l<=r) { mid=(l+r)>>1; if(DP(mid,s)) ans=max(ans,mid),l=mid+1; else r=mid-1; } cout<<ans; }
-
-
正解：
在 \(90pts\) 的做法上使用单调队列优化 \(DP\) 。
∵ 题目数据范围中给了 \(w_{i-1}\geq w_i-1\) ，
∴ \(i-1-w_{i-1}\leq i-1-(w_i-1)\) ，
∴ \(i-1-w_{i-1}\leq i-w_i\) 。
由此，可以使用单调队列优化 \(DP\) 。
至于这玩意之前给跳了 \(qwq\) ，
反正会的肯定会的。点击查看代码
#include<bits/stdc++.h> #define int long long #define endl '\n' using namespace std; const int N=5e5+10; template<typename Tp> inline void read(Tp&x) { x=0;register bool z=1; register char c=getchar(); for(;c<'0'||c>'9';c=getchar()) if(c=='-') z=0; for(;'0'<=c&&c<='9';c=getchar()) x=(x<<1)+(x<<3)+(c^48); x=(z?x:~x+1); } int n,s,l,r,maxx,mid,ans,w,f[N][2],t,head,tail,len[N]; struct aa { int id,num; }q[N]; bool DP(int x,int s) { head=1,tail=0; f[0][1]=f[0][0]=0; for(int i=1;i<=n;i++) { f[i][0]=f[i][1]=0; if(i>=x) { t=max(f[i-x][1],f[i-x][0])+n-(i-x); while(head<=tail&&q[tail].num<t) tail--; q[++tail].num=t; q[tail].id=i-x; while(head<=tail&&q[head].id<i-len[i]) head++; } f[i][0]=max(f[i-1][1],f[i-1][0]); f[i][1]=max(f[i][1],(head>tail?0:q[head].num)+i-n); if(f[i][1]>=s||f[i][0]>=s) return 1; } return 0; } signed main() { #ifndef ONLINE_JUDGE freopen("in.txt","r",stdin); freopen("out.txt","w",stdout); #endif read(n); for(int i=1;i<=n;i++) read(w), l=max(1ll,i-w+1), len[i]=i-l+1, maxx=max(maxx,len[i]); read(s); s=ceil(double(n*s/100.0)); l=1,r=maxx; while(l<=r) { mid=(l+r)>>1; if(DP(mid,s)) ans=max(ans,mid),l=mid+1; else r=mid-1; } cout<<ans; }