牛客挑战赛72

A

核心代码如下：

vector<int>nums;
    for(int i=0;i<T;++i){
        cin>>temp;
        nums.push_back(temp);
    }
    for(int i=1;i<T-1;++i){
        if(nums[i]<nums[i-1]&&nums[i]<nums[i+1])ans++;
    }

B

B题思路就是用优先队列去存储分数和下标，一开始小于6全部入堆，答案扔0

如果等于6了，看分数，分数大就踢人，并且把踢的人的下标扔进答案，不然就不管他，就扔0

#include<iostream>
#include<algorithm>
#include<cstring>
#include<queue>
#include<cmath>
#include<map>

#define x first
#define y second
#define pb push_back
#define PI acos(-1)
#define alli(a) a+1,a+1+n
#define all(a) a.begin(),a.end()

using namespace std;
typedef long long LL;
typedef pair<double,int> PII;
typedef unsigned __int128 ll;
const int N=2e5+5,M=2*N,MOD=1e9+7;

int n,m;
double a[N];
char s[N];
bool vis;
priority_queue<PII,vector<PII>,greater<PII>> q;
int main(){int T=1;
	ios::sync_with_stdio(0);
  cin.tie(0),cout.tie(0);
	// cin>>T;
	while(T--){
    cin>>n;
    for(int i=1;i<=n;i++){
      cin>>a[i];
    }
    vector<int> v;
    for(int i=1;i<=n;i++){
      if(q.size()<6){
        v.pb(0);
        q.push({a[i],i});
        m++;
      }else if(q.top().x<a[i]){
        v.pb(q.top().y);
        q.pop();
        q.push({a[i],i});
        m++;
      }else v.pb(0);
    }
    cout<<m<<'\n';
    for(auto j:v) cout<<j<<' ';
		// cout<< (r!=inf?r:-1)<<'\n';
    // cout<< (vis?"YES\n":"NO\n");
	}
	return 0;
}

C

题意：给定一棵树，带点权。建立一个无向完全图，边 (u,v) 的权值为 lca(u,v) 的权值。求一条哈密顿路径，使边权和最大。输出这个边权和。n≤300。

假设哈密顿路径是有向的，则可以看作每个点对应着一条入边一条出边（除了起点终点）

维护 f[x][i] 表示以 x为根的子树中有 i 个点的出边经过根 x 时子树的答案。

考虑转移，将 x 的一个儿子 y 的答案合并到 x 的答案：

\(f'[x][i+j-k]=\min\{f[x][i]+f[y][j]+k\cdot val[x]\}\)

另外，由于更新前后的 f 不同，所以用 f′ 表示用子树 y 更新后的 f 。最后用 f[1][1]表示答案。

#include<bits/stdc++.h>
using namespace std;
using ll=long long;
#define int long long
#define rep(i,a,n) for(int i=a;i<=n;i++)
#define frep(i,a,n) for(int i=a;i>=n;i--)
#define PII pair<int,int>
#define lowbit(x) (x&(-x))
const int mod=1e9+7;
const double pai=acos(-1.0);
#define ios ios::sync_with_stdio(0); cin.tie(0),cout.tie(0);
#define LF(x)   fixed<<setprecision(x)
const int N=1000;
int n,a[N];
int f[N][N];
int siz[N];
int s[N];
#define inf 1e18
vector<int>g[N];
void dfs(int x)
{
    siz[x]=1;
    rep(i,0,n)
    {
        f[x][i]=-inf;
    }
    f[x][1]=0;
    for(int y:g[x])
    {
        dfs(y);
        rep(i,0,n)
        {
            s[i]=-inf;
        }
        rep(i,0,siz[x])
        {
            rep(j,0,siz[y])
            {
                rep(k,0,min(i,j)*2)
                {
                    if(i+j-k)
                    {
                        s[i+j-k]=max(s[i+j-k],f[x][i]+f[y][j]+k*a[x]);
                    }
                }
            }
        }
        siz[x]+=siz[y];
        rep(i,0,n)
        {
            f[x][i]=s[i];
        }
    }
}
signed main()
{
cin>>n;
rep(i,1,n)
{
    cin>>a[i];
}
rep(i,2,n)
{
    int x;
    cin>>x;
    g[x].push_back(i);
}
dfs(1);
cout<<f[1][1];
return (0-0);
}