CF2048F悬10RMB+1关求调!拍不出错,有一组大的小数据但不太可调
查看原帖
CF2048F悬10RMB+1关求调!拍不出错,有一组大的小数据但不太可调
452438
_Minecraft12345楼主2025/1/24 20:26

这是代码,WA on T2

#include<bits/stdc++.h>
#define int long long
using namespace std;
long long a[200010],b[200010];
stack<int>s;
int ls[200010],rs[200010];
long long dp[200010][67];
void dfs(int x) {


	//dp[x][k]=LONG_LONG_MAX;
	if(ls[x]&&rs[x]) {
		dfs(ls[x]);
		dfs(rs[x]);
		for(int k=0; k<=63; k++) {
			for(int i=0; i<=k; i++) {
				dp[x][k]=max(max(dp[ls[x]][i],dp[rs[x]][k-i]),a[x]);
			}
		}
		for(int k=1; k<=63; k++) {
			dp[x][k]=min(dp[x][k],dp[x][k-1]/b[x]);
		}
	} else if(ls[x]) {
		dfs(ls[x]);
		for(int k=0; k<=63; k++) {
			dp[x][k]=max(a[x],dp[ls[x]][k]);
		}
		for(int k=1; k<=63; k++) {
			dp[x][k]=min(dp[x][k],dp[x][k-1]/b[x]);
		}
	} else if(rs[x]) {
		dfs(rs[x]);
		for(int k=0; k<=63; k++) {
			dp[x][k]=max(a[x],dp[rs[x]][k]);
		}
		for(int k=1; k<=63; k++) {
			dp[x][k]=min(dp[x][k],dp[x][k-1]/b[x]);
		}
	} else {
		dp[x][0]=a[x];
		for(int k=1; k<=63; k++)dp[x][k]=dp[x][k-1]/b[x];
	}

}
signed main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int T;
	cin>>T;
	while(T--) {
		while(!s.empty())s.pop();
		int n;
		cin>>n;
		for(int i=1; i<=n; i++) {
			cin>>a[i];
			a[i]--;
		}
		for(int i=0; i<=n; i++) {
			for(int j=0; j<=63; j++)dp[i][j]=LONG_LONG_MAX;
			ls[i]=rs[i]=0;
		}
		b[0]=1;
		s.push(0);
		for(int i=1; i<=n; i++) {
			cin>>b[i];
			while(!s.empty()) {
				int t=s.top();
				if(b[t]<b[i]) {
					ls[i]=rs[t];
					rs[t]=i;
					s.push(i);
					break;
				}
				s.pop();
			}
			assert(!s.empty());
		}
		for(int i=1;i<=n;i++)for(int j=0;j<=63;j++)dp[i][j]=4000000000000000000;
		dfs(0);
		for(int i=0; i<=63; i++) {
			if(dp[0][i]==0) {
				cout<<i<<'\n';
				break;
			}
		}
	}
	return 0;
}

可以加钱,只要调过,感谢大佬awa

2025/1/24 20:26
加载中...