NOIP2021模拟17
NOIP2021模拟17
宝藏
不难发现答案关于\(x_i\)单调(当一个数在\(x_i\)大时能作为中位数，那么\(x_i\)小时同样也能)
所以我们先对原序列按\(w_i\)排序
设\(f_i\)表示新序列第\(i\)个点作为中位数时\(x_i\)最大能为多少
我们考虑对于每个位置\(i\)求出\(g_i=\max_{j=i}^nf_j\)然后求答案时使用二分
从后往前计算\(g\),使用四个\(\tt multiset\)维护前\(i-1\)个数中前\(g_i\)小的数,后\(n-i\)个数中前\(g_i\)小的数
从\(g_i\)推往\(g_{i-1}\)时,直接从\(\tt multiset\)中删除/加入即可
由于\(g_i\)是单调的，所以使用类似于尺取的技巧即可
时间复杂度\(O(n\log n)\),当然，如果不嫌麻烦的话四个\(\tt multiset\)可以换成八个\(\tt priority\_queue\)
#include
using namespace std;
# define ll long long
# define read read1()
# define Type template
Type T read1(){
T t=0;
char k;
bool vis=0;
do (k=getchar())=='-'&&(vis=-1);while('0'>k||k>'9');
while('0'<=k&&k<='9')t=(t<<3)+(t<<1)+(k^'0'),k=getchar();
return vis?-t:t;
}
# define fre(k) freopen(k".in","r",stdin);freopen(k".out","w",stdout)
int s,m,h[300005];
ll sumx,sumy,T;
paira[300005];
multisetqx,qy,q1,q2;
int main(){fre("treasure");
s=read;T=read;m=read;
for(int i=1;i<=s;++i)a[i].first=read,a[i].second=read;
sort(a+1,a+s+1);
for(int i=1;i<=s;++i)q1.insert(a[i].second);
for(int i=s,j=0;i;--i){
auto w=q1.find(a[i].second);
if(w!=q1.end())q1.erase(w);
else{w=qx.find(a[i].second);
sumx-=*w;
qx.erase(w);
if(q1.empty()){
for(int k=i;k;--k)h[k]=h[k+1];
break;
}
sumx+=*q1.begin();
qx.insert(*q1.begin());
q1.erase(q1.begin());
}
while(sumx+sumy+a[i].second<=T&&q1.size()&&q2.size()){
sumx+=*q1.begin();sumy+=*q2.begin();
qx.insert(*q1.begin());qy.insert(*q2.begin());
q1.erase(q1.begin());q2.erase(q2.begin());
++j;
}
if(sumx+sumy+a[i].second<=T)h[i]=j;
else h[i]=j-1;
q2.insert(a[i].second);
if(qy.size()&&*qy.rbegin()>*q2.begin()){
sumy-=*qy.rbegin();sumy+=*q2.begin();
q2.insert(*qy.rbegin());
qy.insert(*q2.begin());
auto w=qy.end();--w;
qy.erase(w);
q2.erase(q2.begin());
}
}
while(m--){
int x=read,l=1,r=s,ans=-1,mid;
while(l<=r)h[mid=l+r>>1]*2+1>=x?l=(ans=mid)+1:r=mid-1;
printf("%d\n",~ans?a[ans].first:-1);
}
return 0;
}
寻找道路
先用一次\(BFS\)把只走\(0\)边能到的点存下来，再以它们为起点跑\(BFS\),后者的\(\tt BFS\)需要用\(\tt vector\)存下距离相同的点，同时转移
#include
using namespace std;
# define ll long long
# define read read1()
# define Type template
Type T read1(){
T t=0;
char k;
bool vis=0;
do (k=getchar())=='-'&&(vis=-1);while('0'>k||k>'9');
while('0'<=k&&k<='9')t=(t<<3)+(t<<1)+(k^'0'),k=getchar();
return vis?-t:t;
}
# define fre(k) freopen(k".in","r",stdin);freopen(k".out","w",stdout)
# define mod 1000000007
int s,m,dis[1000005];
bool vis[1000005];
vectorG[1000005],G1[1000005];
queueq1;
queue >q;
int main(){fre("path");
s=read,m=read;
for(int i=1;i<=m;++i){
int u=read,v=read,w=read;
if(w)G1[u].push_back(v);
else G[u].push_back(v);
}q1.push(1);vis[1]=1;
vectorvec;
while(q1.size()){
int n=q1.front();q1.pop();
vec.push_back(n);
for(int i:G[n])
if(!vis[i]){
dis[i]=(dis[n]<<1)%mod;
vis[i]=1;
q1.push(i);
}
}q.push(vec);
while(q.size()){
vectorx=q.front();q.pop();
vec.clear();
for(int n:x)
for(int i:G[n])
if(!vis[i]){
dis[i]=(dis[n]<<1)%mod;
vis[i]=1;
vec.push_back(i);
}
if(vec.size())q.push(vec);
vec.clear();
for(int n:x)
for(int i:G1[n])
if(!vis[i]){
dis[i]=(dis[n]<<1|1)%mod;
vis[i]=1;
vec.push_back(i);
}
if(vec.size())q.push(vec);
}
for(int i=2;i<=s;++i)printf("%d ",vis[i]?dis[i]:-1);
return 0;
}
猪国杀
设\(dp_{x,i,j}\)表示使用\(i\)张牌，和为\(j\),牌最大值\(\leq x\)的方案数
我们考虑牌从小往大转移
\(dp_{x-1,i,j}{i+v\choose i}\rightarrow dp_{x,i+v,j+v*x}\)
至于对答案的贡献则是\(dp_{x-1,i,j}{i+v\choose i}{n\choose i+v}(A-i)^{n-i-v}(i+\lfloor\frac{m-k}{x}\rfloor)\rightarrow ans\)
前一步时间复杂度为\(O(mAn\ln m)\)
后一步可以通过将\(\lfloor\frac{m-k}{x}\rfloor\)相等的\(k\)合在一起处理,时间复杂度位\(O(mn^2\ln m)\)
所以时间复杂度位\(O(nm\ln m(A+n))\)
打出来就过了。。。可能是因为常数小??
#include
using namespace std;
# define ll long long
# define read read1()
# define Type template
Type T read1(){
T t=0;
char k;
bool vis=0;
do (k=getchar())=='-'&&(vis=-1);while('0'>k||k>'9');
while('0'<=k&&k<='9')t=(t<<3)+(t<<1)+(k^'0'),k=getchar();
return vis?-t:t;
}
# define fre(k) freopen(k".in","r",stdin);freopen(k".out","w",stdout)
# define mod 998244353
ll qkpow(ll n,ll m){
ll t=1;
for(;m;m>>=1,n=n*n%mod)
if(m&1)t=t*n%mod;
return t;
}
int n,m,A,f[105][1005],Pow[1005][105];
ll ans,C[105][105];
int main(){fre("legend");
n=read,m=read;A=read;
int invA=qkpow(A,mod-2);
Pow[0][0]=1;
for(int j=1;j<=A;++j){
Pow[j][0]=1;
for(int i=1;i<=n;++i)Pow[j][i]=1ll*Pow[j][i-1]*j%mod;
}
for(int i=0;i<=n;++i){
C[i][0]=C[i][i]=1;
for(int j=1;j1?ceil(k/(i-1.0)):0.0,la=k;l<=(i==1?0:n)&&(k=la,1);++l){
int v=(m-k)/i;ll t=f[l][k];
while((m-k-1)/i==v&&k 数树
可以先算出\(tree_1\rightarrow tree_2\)映射的数量，再除以\(tree_2\rightarrow tree_2\)映射的数量即为答案
前者使用树上状压背包，后者直接\(m!*m\)枚举即可
时间复杂度\(O(nm^22^m+m!m)\)
#include
using namespace std;
# define ll long long
# define read read1()
# define Type template
Type T read1(){
T t=0;
char k;
bool vis=0;
do (k=getchar())=='-'&&(vis=-1);while('0'>k||k>'9');
while('0'<=k&&k<='9')t=(t<<3)+(t<<1)+(k^'0'),k=getchar();
return vis?-t:t;
}
# define fre(k) freopen(k".in","r",stdin);freopen(k".out","w",stdout)
# define mod 998244353
ll qkpow(ll n,ll m){
ll t=1;
for(;m;m>>=1,n=n*n%mod)
if(m&1)t=t*n%mod;
return t;
}
int s,n;
ll f[3005][1024],dp[3005][1024],ans;
pairE[15];
bool a[15][15];
int tv[15][15];
vectorG[3005],G1[15];
void dfs(int x,int fa){
for(int i:G[x])
if(i!=fa)dfs(i,x);
for(int i=1;i<=n;++i){
memset(f[x],0,8<<10);
f[x][1<>k-1&1)continue;
(f[x][j|tv[i][k]]+=f[x][j]*dp[v][tv[i][k]])%=mod;
}
for(int j=0;j<(1<