20241003 模拟赛
这场...打得还行吧。（至少没有爆零
A. 旋律的总数
难度：橙
签到题。
只要第一个都选 \(1\)，就能保证不同。
答案为 \(m^{n-1}\)。
#include<bits/stdc++.h>
#define ll long long
#define mod 1000000007
using namespace std;
int T;
ll n,m;
ll quickpow(ll a,ll b){
ll ret=1,base=a;
while(b){
if(b&1)ret=ret*base%mod;
base=base*base%mod;
b>>=1;
}
return ret;
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0),cout.tie(0);
// freopen("sum.in","r",stdin);
// freopen("sum.out","w",stdout);
cin>>T;
while(T--){
cin>>n>>m;
cout<<quickpow(m,n-1)<<'\n';
}
return 0;
}
B. 水果加工
难度：绿-蓝
正解用的背包，我打的暴力+卡时75pts。
但我们聪明的机房大神懒得想那么多，折半搜索（meet in the middle）搞定！
#include<bits/stdc++.h>
#define ll long long
#define pii pair<ll,ll>
using namespace std;
const ll N=45;
ll n,a[N],b[2],c[2][N],d[2][N],u[2][N],mid;
vector<pii>vec[N][N],w[N][N];
vector<pii>vec2[N][N],w2[N][N];
/*
dfs传的参代表的含义
x：第 x 个农场
sum1：所有水果均运输完毕的时间
sum2：所有工厂完成加工的时间
cnt1：工厂 1 用掉的机器
cnt2：工厂 2 用掉的机器
*/
void dfs(ll x,ll sum1,ll sum2,ll cnt1,ll cnt2){
if(x>n/2){
vec[cnt1][cnt2].push_back({sum1,sum2});
return;
}
//这段代码的含义：vec2[第一个工厂用了cnt1个机器][第二个工厂用了cnt2个机器]
//.push_back({工厂1完成加工的总时间, 工厂2完成加工的总时间});
//就相当于存一下搜到的状态
for(ll i=0;i<=a[x];i++){//对于每个农场 x，第一个工厂分到 i 吨，则第二个工厂分到 (a[x] - i) 吨
if(c[0][x]*(i!=0)+cnt1<=b[0]&&c[1][x]*(i!=a[x])+cnt2<=b[1]){
ll mx1=max(sum1,max(d[0][x]*i,d[1][x]*(a[x]-i)));
ll mx2=max(sum2,max(u[0][x]*i,u[1][x]*(a[x]-i)));
ll mx3=cnt1+c[0][x]*(i!=0);
//加上工厂 1 用掉的机器，i = 0 时第一个工厂不需要开生产线(因为没有分给第一个工厂的)
ll mx4=cnt2+c[1][x]*(i!=a[x]);
//加上工厂 2 用掉的机器，i = a[x] 时第二个工厂不需要开生产线
dfs(x+1,mx1,mx2,mx3,mx4);
}
}
}
void dfs2(ll x,ll sum1,ll sum2,ll cnt1,ll cnt2){
if(x>n){
vec2[cnt1][cnt2].push_back({sum1,sum2});
return;
}
for(ll i=0;i<=a[x];i++){
if(c[0][x]*(i!=0)+cnt1<=b[0]&&c[1][x]*(i!=a[x])+cnt2<=b[1]){
ll mx1=max(sum1,max(d[0][x]*i,d[1][x]*(a[x]-i)));
ll mx2=max(sum2,max(u[0][x]*i,u[1][x]*(a[x]-i)));
ll mx3=cnt1+c[0][x]*(i!=0);
ll mx4=cnt2+c[1][x]*(i!=a[x]);
dfs2(x+1,mx1,mx2,mx3,mx4);
}
}
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0),cout.tie(0);
// freopen("fruit.in","r",stdin);
// freopen("fruit.out","w",stdout);
cin>>n;
for(ll i=1;i<=n;i++)cin>>a[i];
cin>>b[0]>>b[1];
for(ll i=1;i<=n;i++)cin>>c[0][i];for(ll i=1;i<=n;i++)cin>>c[1][i];
for(ll i=1;i<=n;i++)cin>>d[0][i];for(ll i=1;i<=n;i++)cin>>d[1][i];
for(ll i=1;i<=n;i++)cin>>u[0][i];for(ll i=1;i<=n;i++)cin>>u[1][i];
mid=n/2;
dfs(1,0,0,0,0);
dfs2(n/2+1,0,0,0,0);
for(ll i=0;i<=b[0];i++){
for(ll j=0;j<=b[1];j++){
sort(vec[i][j].begin(),vec[i][j].end());
vector<pii> tmp;
ll si=vec[i][j].size();
for(ll x=0;x<si;x++)
if(!x||vec[i][j][x].first!=vec[i][j][x-1].first)
tmp.push_back(vec[i][j][x]);
si=tmp.size();
for(ll x=0;x<si;x++)
if(!x||tmp[x].second<tmp[x-1].second)
w[i][j].push_back(tmp[x]);
}
}
for(ll i=0;i<=b[0];i++){
for(ll j=0;j<=b[1];j++){
sort(vec2[i][j].begin(),vec2[i][j].end());
vector<pii>tmp;
ll si=vec2[i][j].size();
for(ll x=0;x<si;x++)
if(!x||vec2[i][j][x].first!=vec2[i][j][x-1].first)
tmp.push_back(vec2[i][j][x]);
//去掉一些重复状态，first第一次出现时，此时的second肯定是最小的，因此保留第一个出现的。
si=tmp.size();
for(ll x=0;x<si;x++)
if(!x||tmp[x].second<tmp[x-1].second)
w2[i][j].push_back(tmp[x]);
//此时first是递增的，当且仅当此时的 se 小于前一个的 se 才有可能成为答案
}
}
ll ans=1e18;
for(ll i=0;i<=b[0];i++)
for(ll j=0;j<=b[1];j++)
for(ll k=0;k<=b[0]-i;k++)
for(ll l=0;l<=b[1]-j;l++)
for(auto x:w[i][j])
for(auto y:w2[k][l])
ans=min(ans,max(x.first,y.first)+max(x.second,y.second));
cout<<ans;
return 0;
}
C. 最佳位置
难度：绿-蓝
打的暴力寄了...
最初想法是搞一个空段的结构体，用set维护区间长度，但细想发现删除操作很难搞，于是考虑再来一个set维护坐的位置。
#include<bits/stdc++.h>
#define ll long long
#define mxn 300010
#define pb push_back
using namespace std;
ll n,m,seat[mxn];//编号i的人所坐的位置
struct segment{//空段,包含了[begin,end]这一整段
int l,r;
int get_max()const{
if(l==1)return 1;//如果是最左边,肯定选最左边的
else if(r==n)return n;//如果是最右边,肯定选最右边的
else return (l+r)/2;
}
int len()const{
if(l!=1&&r!=n)return (r-l+2)/2;
else return r-l+1;//如果begin==1&&end==n,则全场都空着,会来到位置1.
}
segment(int _l,int _r){
l=_l,r=_r;
}
};
struct num_cmp{
bool operator()(const segment &a,const segment &b)const{
return a.l<b.l;
}
};
struct len_cmp{
bool operator()(const segment &a,const segment &b)const{
if(a.len()==b.len())return a.l<b.l;
else return a.len()>b.len();
}
};
bool operator!=(const segment &a,const segment &b){
return a.l!=b.l||a.r!=b.r;
}
bool operator==(const segment &a,const segment &b){
return !(a!=b);
}
set<segment,num_cmp> numset; //一个按开始位置
set<segment,len_cmp> lenset; //一个按距离
void insrt(segment s){
numset.insert(s);
lenset.insert(s);
return;
}
void erse(segment &s){
assert(*numset.find(s)==s);
assert(*lenset.find(s)==s);
numset.erase(s),lenset.erase(s);
return;
}
int sit(int pers){
segment s=*lenset.begin();//根据距离来选择最近的
vector<segment> in;
int pos=s.get_max();//选择最佳座位坐下
if(pos>s.l)in.pb(segment(s.l,pos-1));//讨论需要增加的空段
if(pos<s.r)in.pb(segment(pos+1,s.r));
erse(s);
for(int i=0;i<in.size();i++)insrt(in[i]);
return pos;
}
void leave(int pers){
vector<segment> out;
if(pers!=1){
segment pre=*(--numset.lower_bound(segment(pers,-1)));//找到out_pos的前面一个空段
if(pre.r==pers-1)out.pb(segment(pre));
}
if(pers!=n&&numset.lower_bound(segment(pers,-1))!=numset.end()){
segment nxt=*(numset.lower_bound(segment(pers,-1)));
if(nxt.l==pers+1)out.pb(nxt);
}
segment ins=segment(0,0);
if(out.size()==2)ins=segment(out[0].l,out[1].r);//首尾相接
else if(out.size()==1){
if(out[0].r==pers-1)ins=segment(out[0].l,pers);//只接左边
else ins=segment(pers,out[0].r);//只接右边
}
else if(out.size()==0)ins=segment(pers,pers);
for(int i=0;i<out.size();i++)erse(out[i]);
insrt(ins);
return;
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0),cout.tie(0);
freopen("location.in","r",stdin);
freopen("location.out","w",stdout);
cin>>n>>m;
insrt(segment(1,n));//先插进去1个(1,n)的,表明一整段都是空的
for(int i=1;i<=2*m;i++){
int a;cin>>a;
if(seat[a])leave(seat[a]);
else seat[a]=sit(a);
}
for(int i=1;i<=m;i++)cout<<seat[i]<<'\n';
return 0;
}
D. 跑步路线
难度：绿
最小生成树+lca。
当初死磕t2磕疯了，没看见，眼睛真是瞎了。
注意开int128。
#include<bits/stdc++.h>
#define ll long long
#define mxn 200010
#define pb push_back
#define lit __int128_t
using namespace std;
struct edge{
ll u,v,w;
}e[mxn];
bool operator<(const edge &a,const edge &b){
return a.w<b.w;
}
struct edge2{
ll v,w;
edge2(ll _v,ll _w){
v=_v,w=_w;
}
};
int n,m,f[mxn],lg[mxn];
int fa[mxn][30],dep[mxn],fath[mxn];
ll sze[mxn],dis[mxn];
ll k,tim;
lit ans=0;
vector<edge2> t[mxn];
int fnd(int x){
if(x==f[x])return x;
return f[x]=fnd(f[x]);
}
void kruskal(){
sort(e+1,e+m+1);
int cnt=0;
for(int i=1;i<=m;i++){
int u=e[i].u,v=e[i].v;
int fu=fnd(u),fv=fnd(v);
if(fu==fv)continue;
f[fu]=fv;
cnt++;
t[u].pb(edge2(v,e[i].w));
t[v].pb(edge2(u,e[i].w));
if(cnt>=n-1)break;
}
return;
}
void dfs(int u,int f){
fa[u][0]=f,dep[u]=dep[f]+1,fath[u]=f;
for(int i=1;i<=lg[dep[u]];i++)
fa[u][i]=fa[fa[u][i-1]][i-1];
for(int i=0;i<t[u].size();i++){
int v=t[u][i].v;
if(v==f)continue;
dis[v]=dis[u]+t[u][i].w;
dfs(v,u);
}
return;
}
int lca(int a,int b)
{
if(dep[a]<dep[b])
swap(a,b);
while(dep[a]>dep[b])
a=fa[a][lg[dep[a]-dep[b]]-1];
if(a==b)return a;
for(int i=lg[dep[a]]-1;i>=0;i--)
if(fa[a][i]!=fa[b][i])
a=fa[a][i],b=fa[b][i];
return fa[a][0];
}
void lcainit(){
for(int i=1;i<=n;i++)lg[i]=lg[i-1]+(1<<lg[i-1]==i);
dfs(1,0);
return;
}
void print(lit a){
if(a>=10)print(a/10);
putchar(a%10+'0');
return;
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0),cout.tie(0);
// freopen("run.in","r",stdin);
// freopen("run.out","w",stdout);
cin>>n>>m;
for(int i=1;i<=m;i++){
cin>>e[i].u>>e[i].v>>e[i].w;
f[i]=i;
}
kruskal();
lcainit();
cin>>k>>tim;
int uu,vv;
cin>>uu;
for(int i=1;i<k;i++){
cin>>vv;
if(uu==vv)continue;
int lc=lca(uu,vv);
ll diss=dis[uu]+dis[vv]-2*dis[lc];
ll d=dep[uu]+dep[vv]-2*dep[lc];
ans+=(lit)d*(lit)tim;
ans+=(lit)diss;
uu=vv;
}
ans-=(lit)tim;
print(ans);
return 0;
}