当前位置：首页 > news >正文

20251108上午考试总结

news 2026/3/27 3:22:58

考试情况：

Problem	T1	T2	T3	T4	all
want scores	100pts	100pts	40pts	0pts	240pts
scores	100pts	100pts	0pts	0pts	200pts

前言：

今天太难了！！！

T1

~~出题人的良心馈赠！~~

就是一个简单的诈骗贪心和模拟。

#include <bits/stdc++.h>using namespace std;
#define ll long long
#define ull unsigned long long
#define db double
#define inf (1 << 30)
#define lnf (1LL << 60)
#define all(x) x.begin(),x.end()
typedef pair<int,int> PII;
const int N = 2e5 + 7;
const int P = 998244353;
int n,a[N];
signed main(){//freopen("monster.in","r",stdin);//freopen("monster.out","w",stdout);scanf("%d",&n);for(int i = 1;i <= n;i++){scanf("%d",&a[i]);}sort(a+1,a+n+1);int ans = 0;for(int i = 1;i <= n;i++){if(ans > a[i])ans++;else  ans--;}printf("%d\n",ans);return 0;
}

T2:

思路零：枚举 \((i,j,k)\)，判一下就好了。

时间复杂度：\(O(n^3)\)，空间复杂度：\(O(n)\)。

预估分数：\(20pts\)。

void solve(){rep(i,1,n-2){rep(j,i+1,n-1){rep(k,j+1,n){if(a[i] > a[j] && a[j] < a[k]){ans = max(ans,a[i] + a[j] + a[k]);}}}}return;
}

思路一：枚举 \(a_j\)，看看左边最大的是否比他大，右边最大是否比他大，再相加。

时间复杂度：\(O(n^2)\)，空间复杂度：\(O(n)\)。

预估分数：\(40pts\)。

void solve(){rep(j,1,n){int mx1 = -inf,mx2 = -inf;rep(i,1,j - 1){mx1 = max(mx1,a[i]);}rep(k,j + 1,n){mx2 = max(mx2,a[k]);}if(mx1 < a[j] || mx2 < a[j]) continue;ans = max(ans,mx1 + mx2 + a[j]);}
}

思路二：好像第二个循环是可以用前缀最大值和后缀最大值（~~st表~~）来优化成 \(O(1)\) 的。

时间复杂度：\(O(n)\)，空间复杂度：\(O(n)\)。

预估分数：\(100pts\)。

~~可怜的邱明轩啊！！！~~

void solve(){scanf("%d",&n);for(int i = 1;i <= n;i++)scanf("%d",&a[i]);pre_max[0] = INT_MIN;for(int i = 1;i <= n;i++)pre_max[i] = max(pre_max[i-1],a[i]);nxt_max[n+1] = INT_MIN;for(int i = n;i >= 1;i--)nxt_max[i] = max(nxt_max[i+1],a[i]);for(int i = 1;i <= n;i++){if(pre_max[i-1] > a[i] && nxt_max[i+1] > a[i])ans = max(ans,1LL * pre_max[i-1] + nxt_max[i+1] + a[i]);}printf("%lld\n",ans == -lnf ? 0 : ans);
}

注意：ans 初始值要是 \(-inf\)。

题外话：（邱明轩的代码）

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define ull long longint const N=5e5+10;
int n;
ll an[N],fmx[N],bmx[N],ans=LLONG_MIN;void value(){cin>>n;fmx[0]=bmx[n+1]=LLONG_MIN;for(int i=1;i<=n;i++){cin>>an[i];fmx[i]=max(fmx[i-1],an[i]);}for(int i=n;i>=1;i--)    bmx[i]=max(bmx[i+1],an[i]);for(int i=2;i<n;i++){if(fmx[i-1]>an[i] && an[i]<bmx[i+1])    ans=max(ans,fmx[i-1]+an[i]+bmx[i+1]);}if(ans==LLONG_MIN)   cout<<0; // if(true) cout << 0;else    cout<<ans;return;
}int main(){freopen("sum.in","r",stdin);freopen("sum.out","w",stdout);int T=1;//cin>>T;while(T--)  value();return 0;
}