CF-1028-B. Gellyfish and Baby's Breath（仔细审题，排列会让问题变简单）

思路讲解

唉，要仔细审题，题目说了这是一个排列就好做很多。

AC代码

https://codeforces.com/contest/2116/submission/322330827

源代码

// Problem: B. Gellyfish and Baby's Breath
// Contest: Codeforces - Codeforces Round 1028 (Div. 2)
// URL: https://codeforces.com/contest/2116/problem/B
// Memory Limit: 256 MB
// Time Limit: 1000 ms
// by znzryb
// 
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>
#define all(vec) vec.begin(),vec.end()
#define CLR(i,a) memset(i,a,sizeof(i))
#define fi first
#define se second
#define pb push_back
#define SZ(a) ((int) a.size())
#define FOR(i, a, b) for (int i = (a); i <= (b); ++i)
#define ROF(i, a, b) for (int i = (a); i >= (b); --i)
#define getFro(vec) (vec.empty()?0:vec.front())
#define getBac(vec) (vec.empty()?0:vec.back())
#define debug(var) cerr << #var <<":"<<var<<"\n";
#define DEBUG(variable) do { std::cerr << #variable << ":"; for (const auto& elem : \
variable) { std::cerr << elem << " ";}std::cerr << "\n";} while (0)
#define uniVec(var) do {  sort(var.begin(),var.end());var.resize(unique(var.begin(), \
var.end())-var.begin());} while (0)
#define debugN(var,N) do{ std::cerr<<#var<<":"; FOR(i,1,N){ std::cerr<<var[i]<<" "; } \ 
std::cerr<<"\n"; }while(0)
#define debugMap(variable) do { std::cerr << #variable << ":\n"; for (const auto \
& pair : variable) \
{ std::cerr << "  " << pair.first << " => " << pair.second << "\n"; } \
std::cerr << std::endl; } while (0)
#define lson(var) (var<<1)
#define rson(var) ((var<<1)+1)
#define vecMxx(vec,x) (vec.end()-lower_bound(all(vec),x))	// vec中大于x的数有几个

using namespace std;

typedef long long ll;typedef unsigned long long ull;
typedef double DB;typedef long double LD;
typedef __int128 i128;typedef pair<DB,DB> pdd;typedef pair<ll,bool> plb;
typedef pair<ll,ll> pll;
typedef array<ll,3> arr3;typedef array<ll,2> arr2;
constexpr ll MAXN=static_cast<ll>(1e5)+10,INF=static_cast<ll>(1e18)+3;
constexpr ll mod= 998244353;
constexpr double eps=1e-8;

ll N,M,Q[MAXN],X,K,lT,P[MAXN];
/*

*/
ll mxP[MAXN],mxQ[MAXN];
ll ans[MAXN];
ll binpow(ll a,ll k,const ll &p){	// 迭代快速幂
	ll res=1;
	while(k>0){
		if((k&1)==1) res=a*res%p;
		a=a*a%p;
		k>>=1;
	}
	return res;
}
arr2 ps[MAXN];
inline void solve(){
	scanf("%lld",&N);
	FOR(i,0,N-1){
		scanf("%lld",&P[i]);
		mxP[i]=max(mxP[i-1<0?0:i-1],P[i]);
	}
	FOR(i,0,N-1){
		scanf("%lld",&Q[i]);
		mxQ[i]=max(mxQ[i-1<0?0:i-1],Q[i]);
	}
	ll mx=0,idx=0;
	FOR(i,0,N-1){
		if(P[i]>mx){
			mx=P[i];
			idx=i;
			ans[i]=binpow(2,mx,mod)+binpow(2,Q[0],mod);
			ps[i][0]=mx,ps[i][1]=Q[i-idx];
		}else{
			ans[i]=binpow(2,mx,mod)+binpow(2,Q[i-idx],mod);
			ps[i][0]=mx,ps[i][1]=Q[i-idx];
		}
	}
#ifdef LOCAL
    FOR(i,0,N-1){
    	debug(ans[i]);
    	debug(ps[i][0]);
    	debug(ps[i][1]);
    }
#endif
	mx=0,idx=0;
	FOR(i,0,N-1){
		if(Q[i]>mx){
			mx=Q[i];
			idx=i;
			if(mx>ps[i][0]){
				ans[i]=binpow(2,mx,mod)+binpow(2,P[i-idx],mod);
			}else if(mx==ps[i][0]){
				if(P[i-idx]>ps[i][1]){
					ans[i]=binpow(2,mx,mod)+binpow(2,P[i-idx],mod);
				}
			}
		}else{
			if(mx>ps[i][0]){
				ans[i]=binpow(2,mx,mod)+binpow(2,P[i-idx],mod);
			}else if(mx==ps[i][0]){
				if(P[i-idx]>ps[i][1]){
					ans[i]=binpow(2,mx,mod)+binpow(2,P[i-idx],mod);
				}
			}
		}
	}
	FOR(i,0,N-1){
		ans[i]%=mod;
		if(ans[i]<0) ans[i]+=mod;
		printf("%d ",ans[i]);
	}
	printf("\n");
}

int main()
{
	// ios::sync_with_stdio(false);
	// cin.tie(0);cout.tie(0);
	
	scanf("%lld",&lT);
	while(lT--){
		solve();
	}
	// solve();
	return 0;
}
/*
AC https://codeforces.com/contest/2116/submission/322330827

*/

心路历程（WA，TLE，MLE……）