三面错题与反思

2024-11-11

1.dp的运用

题目链接：E-四叠半的电影_2024HUT实验室三面 (nowcoder.com)

#include <bits/stdc++.h>
#define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0)
using namespace std;
typedef pair<int,int>PII;
typedef long long ll;
const int N=2e5+10;
int a[N];
bool mark[N];
int main()
{
	IOS;
	int n,k;
	cin>>n>>k;
	for(int i=1;i<=n;i++)cin>>a[i];
	int dp[n+1][k+1];
	memset(dp,0x7f,sizeof(dp));
	for(int i=0;i<=n;i++)dp[i][0]=0;
	for(int i=2;i<=n-1;i++){
		for(int j=1;j<k;j++){
			dp[i][j]=min(dp[i-1][j],dp[i-2][j-1]+a[i]);
		}
	}
	cout<<dp[n-1][k-1];
	return 0;
}

2.滑动窗口

题目链接：J-青青子衿悠悠我心_2024HUT实验室三面 (nowcoder.com)

#include <bits/stdc++.h>
#define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0)
using namespace std;
typedef pair<int,int>PII;
typedef long long ll;
const int N=2e5+10;
//int a[N],s[N];
bool mark[N];
int main() 
{
	IOS;
    int t;
    cin>>t;
    while(t--){
        int n,m;
        cin>>n>>m;
        vector<int>a(n);
        for(int i=0;i<n;i++)cin>>a[i];
        sort(a.begin(),a.end());
        int maxx=-1;
        int l=0,sum=0;
        for(int r=0;r<n;r++){
            sum+=a[r];
            while(a[r]-a[l]>1||sum>m){
                sum-=a[l];
                l++;
            }
            maxx=max(maxx,sum);
        }
        cout<<maxx<<endl;
    }
    return 0;
}

3.unordered_set(自动排序的set运用)

题目链接：C-奶龙の考验_2024HUT实验室三面 (nowcoder.com)

#include <bits/stdc++.h>
#define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0)
using namespace std;
typedef pair<int,int>PII;
typedef long long ll;
const int N=2e5+10;
bool mark[N];
int main()
{
	IOS;
	unordered_set<ll>se;
	ll n,a;
	double sum = 0;
	cin>>n;
	while(n--){
		cin>>a;
		se.insert(a);
	}
	ll len=se.size();
	while(len)
	{
		sum+=1.0/len;
		len--;
	}
	printf("%.8lf",sum);
	return 0;
}