洛谷4月月赛R1 Happy Poppin' Party Train

来自FallDream的博客,未经允许,请勿转载,谢谢。


听学长说的就来玩一玩,随便乱打打  没想到一堆人被取消了成绩,莫名混了个Rank3

还有第一题数据肯定是有问题

------------------------------------------

T1 邦邦的大合唱站队/签到题

N个偶像排成一列,他们来自M个不同的乐队。每个团队至少有一个偶像。

现在要求重新安排队列,使来自同一乐队的偶像连续的站在一起。重新安排的办法是,让若干偶像出列(剩下的偶像不动),然后让出列的偶像一个个归队到原来的空位,归队的位置任意。

请问最少让多少偶像出列?  n<=100000 m<=20

题解:这个应该很好想到状压dp吧 用f[i]表示选的乐队的状态是i的最小出列人数,那么枚举一个乐队转移一下就好了,至于算要出列多少人,可以差分一下。复杂度$m*2^{m}$

/*然后我来教你们怎么AC

首先,快速读入统统删掉,加了快速读入只有20分,其它全是T。

然后呢,虽然我们只需要差分数组,但是呢,必须把ai读入到数组里,不能读到变量。读到变量只有70,不信自己试试。大概是数据有问题,数组会溢出。

最后呢,写写代码,cin或者scanf随意。*/

数据已经修正了,没毛病。我貌似被这个从100坑到了60

#include<iostream>
#include<cstdio>
#include<cstring>
#define MN 200000
#define MM 30
#define int long long
using namespace std;
int X;
//inline int read()
//{
// cin>>X;return X;
/* int x = 0 , f = 1; char ch = getchar();
while(ch < '0' || ch > '9'){ if(ch == '-') f = -1; ch = getchar();}
while(ch >= '0' && ch <= '9'){x = x * 10 + ch - '0';ch = getchar();}
return x * f;*/
//} int n,m,s[MN+];
int f[MM+][MN+],size[MN+],tot[(<<)+],F[(<<)+]; main()
{
// freopen("sb.in","r",stdin);
cin>>n>>m;
for(register int i=;i<=n;i++)
{
cin>>s[i];
for(register int j=;j<=m;j++) f[j][i]=f[j][i-];
++f[s[i]][i];++size[s[i]];
}
for(register int i=;i<<<m;i++)
for(register int j=;j<m;j++)
if((<<j)&i) tot[i]+=size[j+];
memset(F,,sizeof(F));F[]=;
for(register int i=;i<<<m;i++)
for(register int j=;j<=m;j++)
if(i&(<<(j-)))
F[i]=min(F[i],F[i^(<<(j-))]+size[j]-f[j][tot[i]]+f[j][tot[i]-size[j]]);
printf("%lld\n",F[(<<m)-]);
return ;
}

B.开心派对小火车

Aqours铁路公司旗下有N个站,编号1,2,..,N。

有各停(各站停车)电车特急电车两种。特急车会在si..sm,一共M个车站停车。

相邻的两站(即编号为i的车站和编号为洛谷4月月赛R1  Happy Poppin' Party Train的车站,而不是特急电车停车的相邻的两站)之间,各停电车要运行A分钟,特急需要B分钟。我们认为列车一直匀速运行,不考虑停车和加减速。

现在要加一种快速电车,要求其停站覆盖所有的特急电车的停站,而相邻的两站要运行C分钟。为了要快,决定刚好停K个站(k>m,包括特急的所有车站)。如果一个站可以停多种电车,那么旅客可以在这一站换乘。不过只能向前坐车,不能往回坐。

你需要设计一种快速列车的设站方案,要求旅客在T分钟**乘车时间(等车和换乘时间不计)**内,可以从1号站到尽可能多数量的站。你只需要告知能有几站可以达到。

n,a,b,c<=10^9,  m,k<=3000 ,T<=10^18

题解:答案肯定是你做B车到一个站,转C车,然后做A车,所以对于每一个段,你都右端点贪心,也就是每次选择目前能到的点建站。然后把这些塞到一个堆里,每次取出最大,重新算一下塞回去就行了。

复杂度只有klogm,不是很懂。

#include<iostream>
#include<cstdio>
#include<queue>
#define pa pair<int,int>
#define mp(x,y) make_pair(x,y)
#define ll long long
using namespace std;
inline int read()
{
int x = , f = ; char ch = getchar();
while(ch < '' || ch > ''){ if(ch == '-') f = -; ch = getchar();}
while(ch >= '' && ch <= ''){x = x * + ch - '';ch = getchar();}
return x * f;
} int n,m,k,a,b,c,s[],r[];
ll ans,T,t[];
priority_queue<pa>q; void push(int x)
{
if(r[x]==s[x+]-) return;++r[x];
ll time=(T-t[x]-1LL*(r[x]-s[x])*c);
if(time<)return;
int R=(int)min(1LL*(s[x+]-),r[x]+time/a);
q.push(mp(R-r[x]+,x));
r[x]=R;
} int main()
{
n=read();m=read();k=read();a=read();b=read();c=read();
scanf("%lld",&T);
for(int i=;i<=m;i++) s[i]=read();s[m+]=n+;
for(int i=;i<=m;i++)
{
t[i]=1LL*b*(s[i]-s[]);
if(t[i]>T) continue;
r[i]=(int)min(1LL*s[i+]-,s[i]+(T-t[i])/a);
ans+=r[i]-s[i]+;
}
for(int i=;i<m;i++) if(t[i]<=T)push(i);else break;
for(int i=;i<=k-m&&!q.empty();i++)
{
pa x=q.top();q.pop();
ans+=x.first;push(x.second);
}
printf("%lld\n",ans-);
return ;
}

C.什么?这场比赛有C题?

D.Bushiroad的偶像派对

Bushiroad的派对有N个校园偶像团体,可能来自编号1-N的学校。每个学校可能有多个团体参加,也有可能没有团体参加。在所有的团体都演出完后,进行人气投票。

我们已经掌握分别了中场时和结束时的两张人气排行表。给出排行表从人气高到低排序,并给出每个组的学校编号(你却不知道具体是哪个团体)

可是,结束时的表是不太准确的。因为基于这样的一个事实:某个团体的结束时的人气不会低于中场的人气,而且每个团体的学校不会改变。结束的表产生一些矛盾。

负责统计的人为了不想背锅,希望尽可能少修改结束时的排行表的某些团体的学校(人气值不能改),使其不矛盾,请问至少要修改多少个呢?

题解:现场只会yy了一个费用流,只过了70%的点。

大概就是把每个结束时的人气拆成两个点,表示相同学校和不同学校,然后限制这两个点只能流1,两个点都向比他大的下一个点连边(第二个点往同颜色连边)。每个中场的点和第一个大等他的随意学校和相同学校(如果有)连边,和不同学校的点的连边设置费用1,跑一次费用流。这个能通过70%,也就是5000的数据

正解:贪心

从小到大拿结束时的人气去匹配。显然如果能匹配到相同学校的一定最优,那么只要能判断即可。这个可以通过线段树维护  每个点在他之前还有几个点可以被选  的最小值实现

费用流70%

#include<iostream>
#include<cstdio>
#include<queue>
#include<cstring>
#include<vector>
#include<algorithm>
#define S 0
#define MAXN 200000
#define INF 200000000
#define getchar() (SS==TT&&(TT=(SS=B)+fread(B,1,1<<15,stdin),SS==TT)?0:(*SS++))
using namespace std;
char B[<<],*SS=B,*TT=B;
inline int read()
{
int x=;char ch=getchar();
while(ch<''||ch>'')ch=getchar();
while(ch>=''&&ch<=''){x=x*+ch-''; ch=getchar();}
return x;
} int ans=,pi=,T,d[MAXN*+],head[MAXN*+],n,m,cnt=,t[MAXN+],p[MAXN+],t2[MAXN+],p2[MAXN+];
bool mark[MAXN*+];
struct edge{
int w,to,next,c;
}e[];
vector<int> v[MAXN+];
deque<int> q; void insw(int f,int t,int w,int c)
{
e[++cnt].next=head[f];head[f]=cnt;
e[cnt].to=t; e[cnt].w=w;e[cnt].c=c;
} void ins(int f,int t,int w,int c){insw(f,t,w,c);insw(t,f,,-c);} bool modlabel()
{
q.push_back(T);
for(int i=;i<=T;i++) d[i]=INF;d[T]=;
while(!q.empty())
{
int u=q.front();q.pop_front();
for(int i=head[u];i;i=e[i].next)
if(e[i^].w&&d[u]+e[i^].c<d[e[i].to])
{
d[e[i].to]=d[u]+e[i^].c;
if(d[e[i].to]<=d[q.size()?q.front():])
q.push_front(e[i].to);
else
q.push_back(e[i].to);
}
}
for(int i=;i<=T;i++)
for(int j=head[i];j;j=e[j].next)
e[j].c+=d[e[j].to]-d[i];
pi+=d[S];
return d[S]!=INF;
} int dfs(int x,int f)
{
if(x==T) return ans+=pi*f,f;
mark[x]=;
int used=,nown;
for(int i=head[x];i;i=e[i].next)
if(!mark[e[i].to]&&!e[i].c&&e[i].w)
{
nown=dfs(e[i].to,min(f-used,e[i].w));
e[i].w-=nown;e[i^].w+=nown;
used+=nown;if(used==f) return f;
}
return used;
} int get(int x)
{
int l=,r=n,mid,ans;
while(l<=r)
{
mid=l+r>>;
if(p2[mid]<x) r=mid-;
else ans=mid,l=mid+;
}
return ans;
} int get2(int x,int c)
{
int l=,r=v[c].size()-,mid,ans=-;
while(l<=r)
{
mid=l+r>>;
if(p2[v[c][mid]]<x) r=mid-;
else ans=v[c][mid],l=mid+;
}
return ans;
} int main()
{
n=read();T=n*+;
for(register int i=;i<=n;i++) t[i]=read(),p[i]=read();
for(register int i=;i<=n;i++)
{
t2[i]=read();p2[i]=read();
v[t2[i]].push_back(i);
}
for(register int i=;i<=n;i++) ins(S,i,,),ins(i+*n,T,,);
for(register int i=;i<=n;i++)
{
int x=get(p[i]),y=get2(p[i],t[i]);
ins(i,x+n,,);if(y!=-)ins(i,y+*n,,);
if(i<n) ins(i+n+,i+n,INF,);
ins(i+n,i+*n,,);ins(i+*n,i+*n,,);
}
for(register int i=;i<=n;i++) for(register int j=;j<v[i].size();j++)
ins(v[i][j]+*n,v[i][j-]+*n,INF,);
while(modlabel())
do memset(mark,,sizeof(bool)*(T+));
while(dfs(S,INF));
printf("%d\n",ans);
return ;
}

贪心

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<vector>
#define INF 200000000
using namespace std;
inline int read()
{
int x = , f = ; char ch = getchar();
while(ch < '' || ch > ''){ if(ch == '-') f = -; ch = getchar();}
while(ch >= '' && ch <= ''){x = x * + ch - '';ch = getchar();}
return x * f;
} int n,ans,Last[];
vector<int> v[];
struct Node{int l,r,x,val;}T[];
struct P{int kind,t,x,last;
bool operator <(const P&y)const{return x==y.x?kind>y.kind:x<y.x;}
}p[]; void pushdown(int x)
{
int ad=T[x].val,l=x<<,r=x<<|;
T[x].val=;
T[l].val+=ad;T[r].val+=ad;
T[l].x+=ad;T[r].x+=ad;
} void build(int x,int l,int r)
{
if((T[x].l=l)==(T[x].r=r)){ T[x].x=INF;return;}
int mid=l+r>>;
build(x<<,l,mid);build(x<<|,mid+,r);
T[x].x=min(T[x<<].x,T[x<<|].x);
} void renew(int x,int l,int r,int ad)
{
if(T[x].l==l&&T[x].r==r){T[x].x+=ad;T[x].val+=ad;return;}
if(T[x].val) pushdown(x);
int mid=T[x].l+T[x].r>>;
if(r<=mid) renew(x<<,l,r,ad);
else if(l>mid) renew(x<<|,l,r,ad);
else renew(x<<,l,mid,ad),renew(x<<|,mid+,r,ad);
T[x].x=min(T[x<<].x,T[x<<|].x);
} bool check(int from)
{
renew(,from+,n,-);
if(T[].x>=) return true;
renew(,from+,n,); return false;
} void change(int x,int k,int ad)
{
if(T[x].l==T[x].r){T[x].x=ad;return;}
if(T[x].val) pushdown(x);
int mid=T[x].l+T[x].r>>;
change(x<<|(k>mid),k,ad);
T[x].x=min(T[x<<].x,T[x<<|].x);
} int main()
{
ans=n=read();
for(int i=;i<=n;i++)
p[i].t=read(),p[i].x=read(),p[i].kind=;
for(int i=;i<=n;i++)
p[i+n].t=read(),p[i+n].x=read();
for(int i=n,j=n;i;--i)
{
while(j>&&p[j+n].x<p[i].x) --j;
p[i].last=n-j;
}
sort(p+,p+n*+);
build(,,n);
for(int i=,j=;i<=n<<;j+=(p[i++].kind)^)
if(p[i].kind)
v[p[i].t].push_back(i);
else
{
if(v[p[i].t].size())
{
int u=v[p[i].t][v[p[i].t].size()-];
if(p[u].last==n||check(p[u].last))
{
v[p[i].t].pop_back();--ans;
}
else change(,j,i-*j);
}
else change(,j,i-*j);
}
printf("%d\n",ans);
return ;
}
上一篇:初识quartz 并分析 项目中spring整合quartz的配置【原创+转载】


下一篇:MyBatis6:MyBatis集成Spring事物管理(下篇)