T1
考场想的是 \(dp_{i,j}\) 表示已经拿了 \(i\) 个瓜子， \(j\) 个瓜子壳的期望次数，然后发现不会转移，于是死了，后来发现最多拿 \(3n-2\) 次，于是想算出每种次数的方案数，然而不合法的不会搞，于是死了。
正解的dp跟一开始想的一样，然而不会推。
所以可以去推概率，然后最后拿次数一乘就是期望。
设 \(dp_{i,j}\) 表示当前拿了 \(i\) 个瓜子，用了 \(j\) 次的概率。
转移则枚举当前拿的是瓜子还是瓜子壳即可。
不过由 \((i-1,j-1),(i,j-1)\) 转移到 \((i,j)\) 一直错，可能是自己写假了，改成由 \((i,j)\) 转移到 \((i+1,j+1),(i,j+1)\) 就对了。
Code
#include<cstdio>
#include<cctype>
#define re register
const int MAX = 2e3+3;
#define int long long
#define scanf oma=scanf
const int mod = 998244353;
#define freopen file=freopen
int oma;
FILE* file;
namespace some
{
struct stream
{
template<typename type>inline stream &operator >>(type &s)
{
bool w=0; s=0; char ch=getchar();
while(!isdigit(ch)){ w|=ch=='-'; ch=getchar(); }
while(isdigit(ch)){ s=(s<<1)+(s<<3)+(ch^48); ch=getchar(); }
return s=w?-s:s,*this;
}
}cin;
int n,m,inv[MAX*3];
int dp[MAX][MAX*3],ans;
auto quickpow = [](int a,int b,int res = 1)
{
while(b)
{
if(b&1)
{ res = res*a%mod; }
a = a*a%mod,b >>= 1;
}
return res;
};
#define debug(s) printf("%s\n",s)
}using namespace some;
namespace OMA
{
auto main = []() -> signed
{
//#define local
#ifdef local
debug("look here! if you want submit,please closed this");
freopen("node.in","r",stdin); freopen("my.out","w",stdout);
#endif
freopen("eat.in","r",stdin); freopen("eat.out","w",stdout);
cin >> n; m = 3*n-2,inv[1] = 1;
for(re int i=2; i<=m; i++)
{ inv[i] = (mod-mod/i)*inv[mod%i]%mod; }
dp[1][1] = 1;
for(re int i=1; i<n; i++)
{
for(re int j=1; j<=3*i; j++)
{
(dp[i+1][j+1] += dp[i][j]*(n-i)%mod*inv[n+2*i-j]%mod) %= mod;
(dp[i][j+1] += dp[i][j]*(3*i-j)%mod*inv[n+2*i-j]%mod) %= mod;
}
}
for(re int i=n; i<=m; i++)
{ (ans += dp[n][i]*i%mod) %= mod; /*printf("dp[n][%lld]=%lld\n",i,dp[n][i]);*/ }
printf("%lld\n",ans);
return 0;
};
}
signed main()
{ return OMA::main(); }
T2
40pts：暴力主席树。
40+20pts： \(k=1\) 的部分分，直接单调栈即可。
100pts：
一个数要成为第 \(k\) 大，则要求这段区间内有 \(k-1\) 个比它大的数，拿个双向链表写就行。
Code
//#pragma GCC optimize(3)
#include<cstdio>
#include<cctype>
#define re register
const int MAX = 5e5+3;
#define long long long
#define scanf oma=scanf
#define freopen file=freopen
int oma;
FILE* file;
namespace some
{
struct stream
{
template<typename type>inline stream &operator >>(type &s)
{
bool w=0; s=0; char ch=getchar();
while(!isdigit(ch)){ w|=ch=='-'; ch=getchar(); }
while(isdigit(ch)){ s=(s<<1)+(s<<3)+(ch^48); ch=getchar(); }
return s=w?-s:s,*this;
}
}cin;
long ans;
int n,k,a[MAX],val[81][2];
#define debug(s) printf("%s\n",s)
}using namespace some;
namespace Data_Structures
{
struct node
{ int pre,next,id; }list[MAX];
#define id(p) list[p].id
#define pre(p) list[p].pre
#define next(p) list[p].next
}using namespace Data_Structures;
namespace OMA
{
auto main = []() -> signed
{
//#define local
#ifdef local
debug("look here! if you want submit,please closed this");
freopen("node.in","r",stdin); //freopen("my.out","w",stdout);
#endif
freopen("kth.out","w",stdout); freopen("kth.in","r",stdin);
cin >> n >> k; id(a[0] = n+1) = 0,id(a[n+1] = n+2) = n+1;
for(re int i=1; i<=n; i++)
{ cin >> a[i];}
for(re int i=1; i<=n; i++)
{ list[a[i]] = (node){a[i-1],a[i+1],i}; }
for(re int i=1,p1,p2; i<=n; i++)
{
p1 = p2 = -1;
for(re int j=i; j&&p1<k; j=pre(j))
{ val[++p1][0] = id(j); }
for(re int j=i; j&&p2<k; j=next(j))
{ val[++p2][1] = id(j); }
for(re int j=1; j<=p1; j++)
{
if(k-j<p2)
{ ans += 1ll*i*(val[j-1][0]-val[j][0])*(val[k-j+1][1]-val[k-j][1]); }
}
pre(next(i)) = pre(i),next(pre(i)) = next(i);
}
printf("%lld\n",ans);
return 0;
};
}
signed main()
{ return OMA::main(); }