多校冲刺 noip 10.27
满意？？不可能
最后两个题仍然是一点点的思路都没有
所以我只能去做前两个题
这就是我三分钟看题并打出树剖\(LCA\)的理由？？
因为\(LCA\)的深度忘记乘二了，导致最后一题爆零了
T1 宝藏
这个我仍然简单做法，依旧是用\(STL\)水掉了别人用各种树过掉的题
所以是否可以枚举中位数判断
于是我们有了一种二分的做法
二分中位数的位置，对左右两边进行排序，分别取最小的\(\frac{x}{2}\)个
这样的话，复杂度远远不够
发现单调性：中位数随着个数的增加而减少
这样我们可以用双指针了，不需要二分了
那么排序可不可以省略呢？？
我们可以用一个按照时间排序的\(set\)
只需要维护前\(\frac{x}{2}\)里时间最大的那个，动态更新时间和就好了
AC_code
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define fo(i,x,y) for(int i=(x);i<=(y);i++)
#define fu(i,x,y) for(int i=(x);i>=(y);i--)
const int N=3e5+5;
int n,q,T,ans[N];
struct node{
int w,t,id;
node(){}
node(int x,int y,int z){w=x;t=y;id=z;}
bool operator < (node a)const{
if(t==a.t)return id<a.id;
return t<a.t;
}
bool operator <= (node a)const{
if(t==a.t)return id<=a.id;
return t<=a.t;
}
}sca[N];
bool com(node a,node b){return a.w==b.w?a.id<b.id:a.w<b.w;}
set<node> lef,rig;
signed main(){
freopen("treasure.in","r",stdin);
freopen("treasure.out","w",stdout);
scanf("%lld%lld%lld",&n,&T,&q);
fo(i,1,n)scanf("%lld%lld",&sca[i].w,&sca[i].t),sca[i].id=i;
sort(sca+1,sca+n+1,com);
fo(i,1,n-1)lef.insert(sca[i]);
int now=n,le=0,ri=0;
node ml=node(0,0,0),mr=node(0,0,0);
lef.insert(ml);rig.insert(mr);
set<node>::iterator it;
bool flag=false;
for(int x=1;x<=n;x+=2){
//cout<<x<<endl;
if(next(lef.find(ml))==lef.end()&&flag){ans[x]=-1;continue;}
while(le+ri+sca[now].t>T&&now){
rig.insert(sca[now]);
it=rig.find(mr);
if(sca[now]<=mr)ri+=sca[now].t-mr.t,mr=*--it;
now--;
it=lef.find(ml);
if(sca[now]<=ml){
if(++it!=lef.end())ml=*it;
else {flag=true;break;}
le+=ml.t-sca[now].t;
}
lef.erase(sca[now]);
}
//cout<<"SBV"<<endl;
if(++lef.find(ml)==lef.end()&&flag){ans[x]=-1;continue;}
ans[x]=sca[now].w;
it=rig.find(mr);//cout<<"fuck"<<endl;
if(next(it)==rig.end()){
rig.insert(sca[now]);
it=rig.find(mr);
if(sca[now]<=mr)ri+=sca[now].t-mr.t,mr=*--it;
now--;
it=lef.find(ml);
if(sca[now]<=ml){
if(++it!=lef.end())ml=*it;
else {flag=true;continue;}
le+=ml.t-sca[now].t;
}
lef.erase(sca[now]);
}
it=rig.find(mr);mr=*next(it);ri+=mr.t;
it=lef.find(ml);
if(next(it)!=lef.end())ml=*next(it),le+=ml.t;
else flag=true;
}
//cout<<"SBV"<<endl;
fo(i,1,q){
int x;scanf("%lld",&x);
printf("%lld\n",ans[x]);
}
return 0;
}
T2 寻找道路
其实考场上的时候，我直接打了个最短路，取模比大小，呵呵呵
只要将所有为0的点先放到队列中，跑\(bfs\)
这样我们可以一直保证队列中的数是有序的，那么每一个点第一次被更新就是最小值
记得取队首的时候，要把所有距离相等的都取出来一起更新
AC_code
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define fo(i,x,y) for(int i=(x);i<=(y);i++)
#define fu(i,x,y) for(int i=(x);i>=(y);i--)
const int N=1e6+5;
const int mod=1e9+7;
const int inf=0x3f3f3f3f3f3f3f3f;
int ksm(int x,int y){
int ret=1;
while(y){
if(y&1)ret=ret*x%mod;
x=x*x%mod;y>>=1;
}return ret;
}
int n,m;
struct node{
int to,nxt,val;
}e[N*2];
int head[N],rp;
void add_edg(int x,int y,int z){
e[++rp].to=y;
e[rp].val=z;
e[rp].nxt=head[x];
head[x]=rp;
}
queue<int> q;
int dis[N],dep[N],ji[N],cnt;
bool vis[N];
void dfs(int x){
dis[x]=0;dep[x]=0;vis[x]=true;
for(int i=head[x],y;i;i=e[i].nxt){
if(e[i].val)continue;
y=e[i].to;
if(vis[y])continue;
dfs(y);
}
}
signed main(){
freopen("path.in","r",stdin);
freopen("path.out","w",stdout);
memset(dis,0x3f,sizeof(dis));
memset(dep,0x3f,sizeof(dep));
scanf("%lld%lld",&n,&m);
for(int i=1,x,y,z;i<=m;i++){
scanf("%lld%lld%lld",&x,&y,&z);
add_edg(x,y,z);
}
dfs(1);
fo(i,1,n)if(dis[i]==0)q.push(i);
int las,now;
while(!q.empty()){
las=dep[q.front()];now=dis[q.front()];cnt=0;
while(dep[q.front()]==las&&dis[q.front()]==now&&!q.empty())ji[++cnt]=q.front(),q.pop();
fo(s,1,cnt){
int x=ji[s];
for(int i=head[x],y;i;i=e[i].nxt){
if(e[i].val)continue;
y=e[i].to;
if(vis[y])continue;
dis[y]=(dis[x]*2+e[i].val)%mod;
dep[y]=dep[x]+1;
q.push(y);vis[y]=true;
}
}
fo(s,1,cnt){
int x=ji[s];
for(int i=head[x],y;i;i=e[i].nxt){
if(!e[i].val)continue;
y=e[i].to;
if(vis[y])continue;
dis[y]=(dis[x]*2+e[i].val)%mod;
dep[y]=dep[x]+1;
q.push(y);vis[y]=true;
}
}
}
fo(i,2,n)printf("%lld ",dis[i]==inf?-1:dis[i]);
return 0;
}
T3 猪国杀
看到这个题的题目时我心态崩了
但是看完题心态没了
所以我一直在想一个可以拿到部分分的\(dp\)
然而我发现我的\(dp\)算重了，于是没有办法，就打了个暴力走人了
正解确实是\(dp\)，不过好像不是我能力范围之内可以推出来的
首先有一个经典转化，对答案加上某一个数，相当于把这个数拆成很多个一，分散到方案数中
那么我们设\(f_i\)表示选取的牌数大于\(i\)的方案数，这样选了几张牌就会加几遍
考虑如何求出来这个数组
因为我们选取的牌一定是最小的那几张，所以我们直接按照牌的点数大小排序
同样是按照这个顺序去\(dp\)，这样就可以很方便的做了
但是转移的时候别忘了乘上可重集排列的组合数
首先我们枚举已经确定的序列的最大值，然后枚举当前的最大值有多少个，然后后面就直接乘上瞎选的方案数就好了
枚举当前最大值以及个数，那么我们就确定了前面的值的最大值以及他们的和的上界
设\(g_{i,j,k}\)表示有多少个⻓度为\(i\)的正整数序列满足每一个数字不大于\(j\)且所有数字总和不超过\(k\)的方案数
这个是可以容斥的
\(g_{i,j,k}=\sum\limits_{t=0}^{i}(-1)^t {i \choose t} {k-t*(j-1) \choose i}\)
这个请读者自行理解
最终的式子就是
\(f_i=\sum\limits_{j=1}^{A}\sum\limits_{k=1}^{n-i}g_{i,j-1,m-kj}{n\choose i}\sum\limits_{t=k}^{n-i}{n-i \choose t}(A-j)^{n-i-t}\)
\(ans*A^n=\sum\limits_{i=0}^{n}f_i\)
直接带入求值就行了，但是注意剪枝，没有贡献的地方直接停止
AC_code
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define fo(i,x,y) for(int i=(x);i<=(y);i++)
#define fu(i,x,y) for(int i=(x);i>=(y);i--)
const int N=105;
const int M=1005;
const int mod=998244353;
int ksm(int x,int y){
int ret=1;
while(y){
if(y&1)ret=ret*x%mod;
x=x*x%mod;y>>=1;
}return ret;
}
int n,m,A,ans;
int jc[M],inv[M],km[M][M];
int C(int n,int m){
if(n<0||m<0||n<m)return 0;
return jc[n]*inv[m]%mod*inv[n-m]%mod;
}
signed main(){
freopen("legend.in","r",stdin);
freopen("legend.out","w",stdout);
scanf("%lld%lld%lld",&n,&m,&A);
jc[0]=1;fo(i,1,1000)jc[i]=jc[i-1]*i%mod;
inv[0]=1;inv[1000]=ksm(jc[1000],mod-2);
fu(i,999,1)inv[i]=inv[i+1]*(i+1)%mod;
km[0][0]=1;
fo(i,1,A){
km[i][0]=1;
fo(j,1,n)km[i][j]=km[i][j-1]*i%mod;
}
fo(i,0,n)fo(j,1,A)fo(k,1,n-i){
if(m<j*k)continue;
int bas=1,res1=0,res2=0;
fo(t,0,i)res1=(res1+C(i,t)*C(m-k*j-t*(j-1),i)%mod*bas+mod)%mod,bas=-bas;
fo(t,k,n-i)res2=(res2+C(n-i,t)*km[A-j][n-i-t]%mod)%mod;
ans=(ans+res1*res2%mod*C(n,i))%mod;
}
printf("%lld",ans*ksm(ksm(A,n),mod-2)%mod);
return 0;
}
T4 数树
这个？？不会，树形\(dp\)忒难
看代码吧
AC_code
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define fo(i,x,y) for(int i=(x);i<=(y);i++)
#define fu(i,x,y) for(int i=(x);i>=(y);i--)
const int N=3005;
const int M=15;
const int mod=998244353;
int ksm(int x,int y){
int ret=1;
while(y){
if(y&1)ret=1ll*ret*x%mod;
x=1ll*x*x%mod;y>>=1;
}return ret;
}
int n,m;
int ans,sum;
struct graph1{
int fa[N];
vector<int> e[N];
void add_edg(int x,int y){
e[x].push_back(y);
e[y].push_back(x);
}
}t1;
struct graph2{
int fa[M],son[M];
vector<int> e[M];
void add_edg(int x,int y){
e[x].push_back(y);
e[y].push_back(x);
}
void dfs(int x,int f){
fa[x]=f;son[x]=(1<<x-1);
for(int y:e[x])if(y!=f)dfs(y,x),son[x]|=son[y];
}
}t2;
int f[N][1<<10],tmp[1<<10];
void dp(int x,int fa){
fo(i,1,m)f[x][1<<i-1]=1;
for(int y:t1.e[x]){
if(y==fa)continue;
dp(y,x);
fo(i,1,(1<<m)-1)tmp[i]=f[x][i];
fo(s,1,(1<<m)-1){
if(!f[x][s])continue;
fo(i,1,m){
if(s&t2.son[i])continue;
if(!f[y][t2.son[i]])continue;
f[x][s|t2.son[i]]=(f[x][s|t2.son[i]]+1ll*tmp[s]*f[y][t2.son[i]]%mod)%mod;
}
}
}
ans=(1ll*ans+f[x][(1<<m)-1])%mod;
}
int p[M];
vector<int> now[N];
const bool operator == (vector<int> &a,vector<int> &b){
if(a.size()!=b.size())return false;
for(int i=0;i<a.size();i++)if(a[i]!=b[i])return false;
return true;
}
signed main(){
freopen("count.in", "r", stdin);
freopen("count.out", "w", stdout);
scanf("%d",&n);
for(int i=1,x,y;i<n;i++){
scanf("%d%d",&x,&y);
t1.add_edg(x,y);
}
scanf("%d",&m);
for(int i=1,x,y;i<m;i++){
scanf("%d%d",&x,&y);
t2.add_edg(x,y);
}
fo(i,1,m){
fo(x,1,n)fo(s,1,(1<<m)-1)f[x][s]=0;
t2.dfs(i,0);dp(1,0);
}
fo(i,1,m)p[i]=i;
fo(i,1,m)sort(t2.e[i].begin(),t2.e[i].end());
do{
fo(i,1,m)now[p[i]]=t2.e[i];
fo(i,1,m){
for(int &j:now[i])j=p[j];
sort(now[i].begin(),now[i].end());
}
bool flag=true;
fo(i,1,m)if(!(now[i]==t2.e[i])){flag=false;break;}
if(flag)sum++;
}while(next_permutation(p+1,p+m+1));
ans=1ll*ans*ksm(sum,mod-2)%mod;
printf("%d",ans);
}