「Nhk R1 D」Apocryphal Vir Pulcher

在最后给出了形式化题意。

WA！GAAY！是一个风靡全球的比赛。成千上万的 Gaays 参加这个 OI 比赛，由于 Gaays 实在是太强了，所以她们都 AK 了。

但是，她们并没有一次成型，反而，她们中的某些 WA 了很多发。每次 WA 掉 $i$ 题会掉 $a_i$ rating。众所周知，Gaays 中的内卷很严重，扣的分数不是前 $k$ 小的都会被淘汰。这引起的她们的恐慌，所以她们想知道，第 $k$ 小的扣分到底会是多少。值得一提的是，没有任何一对 Gaays 在每一题WA的次数都相同。

Gaays 找到了你来帮忙，还说不帮忙就把你也变成 Gaay。请你帮帮她们吧。

形式化题意：给出一个长度为 $n$ 的序列 $\{a_i\}$ 。现在可以给出无限组长度为 $n$ 的序列 $\{c_i\geqslant0\}$ 。

定义两个序列 $P$ ， $Q$ 相等当且仅当 $\forall i$ ，有 $P_i=Q_i$ 。

对于所有不相等的 $\{c_j\}$ ，可以求出一个序列 $\{x_i=\sum\limits_{j=1}^{n}a_jc_j\}$ ，求 $\{x_i\}$ 中的第 $k$ 小值。

对于 $100\%$ 的数据， $n \le 80$ ， $2 \le k \le 10^6$ ， $1\leqslant a_i\leqslant10^6$ 。

#include<bits/stdc++.h> using namespace std; #define ll long long const ll inf=1e9; int mo=1000000007,st=0; int n,m,k,f[10000000],no; int ksm(int a,int b){ int ret=1; for (;b;b/=2,a=1ll*a*a%mo) if (b&1) ret=1ll*ret*a%mo; return ret; } int main(){ scanf("%d%d",&n,&k); int m=4000000; f[0]=1; for (int i=1;i<=n;i++){ int x;scanf("%d",&x); for (int j=x;j<=m;j++){ f[j]+=f[j-x]; if (f[j]>k) f[j]=k; } } for (int i=0;i<=m;i++){ if (f[i]>=k){ cout<<i;return 0; } k-=f[i]; } }

详情