EA 的练习赛 2 题解

未完待续……

一些简单的题目就口胡了……

A. ix35 的等差数列

枚举哪一个位置不动，然后枚举公差。用map记录。

时间复杂度为\(O(n\log ^2 n)\)。

/*
{
######################
#       Author       #
#        Gary        #
#        2021        #
######################
*/
#include<bits/stdc++.h>
#define rb(a,b,c) for(int a=b;a<=c;++a)
#define rl(a,b,c) for(int a=b;a>=c;--a)
#define LL long long
#define IT iterator
#define PB push_back
#define II(a,b) make_pair(a,b)
#define FIR first
#define SEC second
#define FREO freopen("check.out","w",stdout)
#define rep(a,b) for(int a=0;a<b;++a)
#define SRAND mt19937 rng(chrono::steady_clock::now().time_since_epoch().count())
#define random(a) rng()%a
#define ALL(a) a.begin(),a.end()
#define POB pop_back
#define ff fflush(stdout)
#define fastio ios::sync_with_stdio(false)
#define check_min(a,b) a=min(a,b)
#define check_max(a,b) a=max(a,b)
using namespace std;
//inline int read(){
//    int x=0;
//    char ch=getchar();
//    while(ch<'0'||ch>'9'){
//        ch=getchar();
//    }
//    while(ch>='0'&&ch<='9'){
//        x=(x<<1)+(x<<3)+(ch^48);
//        ch=getchar();
//    }
//    return x;
//}
const int INF=0x3f3f3f3f;
typedef pair<int,int> mp;
/*}
*/
int n,w,a[300000+233];
map<mp,int> m;
int main(){
	scanf("%d%d",&n,&w);
	rb(i,1,n) scanf("%d",&a[i]);
	int rest=1;
	rb(i,2,n){
		rb(j,0,(a[i]-1)/(i-1)){
			m[II(j,a[i]-(i-1)*j)]++;
		}
	}
	for(auto ite=m.begin();ite!=m.end();++ite){
		if(1ll*(ite->FIR).SEC+1ll*(n-1)*(ite->FIR).FIR<=w)
			check_max(rest,ite->SEC+((ite->FIR).SEC==a[1]));
	} 
	cout<<n-rest<<endl; 
	return 0;
}

D. 送给好友的礼物

算法1：

首先可以存储下面没有草莓的有草莓的节点。

可以发现只需要走到每一个这个点就ok了。

然后把他们以dfs序排序。

然后dp就好了，时间复杂度为\(O(N^3)\)。

算法2：

树形dp。

\(dp_{i,j}\)表示两个人遍历以\(i\)为根的子树，其中一个人花费了\(j\)的时间另一个人花费了的最少时间。

然后背包就好了！

时间复杂度为\(O(n^3)\)的，可以过了。

这题是口胡没有代码……