T1 购物(buy)

这是题面

Solution

总共买x个第i种商品的收益fi(x)=x(ai-xbi) (小于0对0取max可以看成不买)

fi(x)-fi(x-1)=ai-(2x-1)bi

可以看成买第x个第i种商品的收益是ai-(2x-1)bi

记下每种商品买了几个，用堆贪心即可

#include<iostream>#include<cstdio>#include<cstring>#include<queue>#include<algorithm>inline int read(){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<<1)+(x<<3)+ch-'0';ch=getchar();}return x*f;}#define MN 100005int n,k;int a[MN],b[MN];long long ans;std::pair<int,int> P;std::priority_queue<std::pair<int,int> > que;int main(){freopen("buy.in","r",stdin);freopen("buy.out","w",stdout);n=read(),k=read();register int i;for(i=1;i<=n;i++){a[i]=read();b[i]=read();que.push(std::make_pair(std::max(a[i]-b[i],0),i)); }for(i=1;i<=k;i++){P=que.top();que.pop();ans+=P.first;int num=std::max(P.first-b[P.second]*2,0);que.push(std::make_pair(num,P.second));}printf("%lld\n",ans);return 0;}

T2 集合(set)

这是题面

Solution

直接算比较难算，考虑计算倒着把集合变回去需要多少步

每轮操作可以让一些元素减1，没减1的元素可以两个合并成一个

不难证明，如果一个元素非0，先减1，变成0了再合并一定最优

那么每轮操作就是把非0的数全部减1，0两两合并

每轮操作维护当前有几个0，并判断当前最小的非0数是否已经变成0，不难算出答案

#include<iostream>#include<cstdio>#include<cstring>#include<queue>#include<algorithm>inline int read(){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<<1)+(x<<3)+ch-'0';ch=getchar();}return x*f;}#define MN 1000005 int a[MN],n,ans,num0;int main(){freopen("set.in","r",stdin);freopen("set.out","w",stdout);n=read();register int i,j;for(i=1;i<=n;i++) a[i]=read();std::sort(a+1,a+n+1);for(i=1;i<=n;){for(j=i;a[j+1]==a[j]&&j<n;j++);ans+=a[j]-a[i-1];for(int k=1;k<=a[j]-a[i-1];k++) num0=(num0+1)/2;num0+=j-i+1;i=j+1;}for(;num0!=1;num0=(num0+1)/2,++ans);printf("%d\n",ans);return 0;}

T3 水题(water)

这是题面

Solution

对每个(i,j)求出最小的bij满足从(i,j)出发只走不超过bij的格子能走出矩阵，bij-aij即是答案

我们把所有格子按aij排序，依次加入矩阵，当一个格子第一次与网格边缘处于同一个连通块时，即求出了

这个格子的bij，用一些并查集的技巧不难维护

也可以把所有网格边缘看成一个点，再对于每两个相邻的格子，把他们之间的边权设为两者aij的较大值，

那么对这张图求最小生成树，最小生成树上网格边缘到每个点路径上的最大值就是bij

两个做法本质相同

这是用MST的：

#include<bits/stdc++.h>inline int read(){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<<3)+(x<<1)+ch-'0';ch=getchar();}return x*f;}struct edge{int f,t,w;}e[91005<<1];int cnt=0;struct Edge{int t,w,nex;}E[91005<<1];int pin=0,hr[90005];inline void ins(int f,int t,int w){e[++cnt]=(edge){f,t,w};}inline void Ins(int f,int t,int w){E[++pin]=(Edge){t,w,hr[f]};hr[f]=pin;E[++pin]=(Edge){f,w,hr[t]};hr[t]=pin;}int a[305][305],b[305][305],n,m,id[305][305],f[90005],fidx[90005],fidy[90005];inline bool cmp(const edge&a,const edge&b){return a.w<b.w;}inline int getf(int x){return x==f[x]?x:f[x]=getf(f[x]);}inline void dfs(int fa,int x,int val){register int i;for(i=hr[x];i;i=E[i].nex)if(E[i].t^fa){b[fidx[E[i].t]][fidy[E[i].t]]=std::max(val,E[i].w);dfs(x,E[i].t,std::max(val,E[i].w));} }int main(){freopen("water.in","r",stdin);freopen("water.out","w",stdout);n=read();m=read();register int i,j;for(i=1;i<=n;i++) for(j=1;j<=m;j++) a[i][j]=read(),id[i][j]=(i-1)*m+j,f[id[i][j]]=id[i][j],fidx[id[i][j]]=i,fidy[id[i][j]]=j;for(i=1;i<=n;i++) for(j=1;j<m;j++) ins(id[i][j],id[i][j+1],std::max(a[i][j],a[i][j+1]));for(i=1;i<n;i++) for(j=1;j<=m;j++) ins(id[i][j],id[i+1][j],std::max(a[i][j],a[i+1][j]));for(i=1;i<=n;i++) ins(0,id[i][1],std::max(0,a[i][1])),ins(0,id[i][m],std::max(0,a[i][m]));for(j=1;j<=m;j++) ins(0,id[1][j],std::max(0,a[1][j])),ins(0,id[n][j],std::max(0,a[n][j]));std::sort(e+1,e+cnt+1,cmp);int ff,ft;for(i=1;i<=cnt;i++){if((ff=getf(e[i].f))==(ft=getf(e[i].t))) continue;f[ff]=ft;Ins(e[i].f,e[i].t,e[i].w);}dfs(-1,0,-1);for(i=1;i<=n;i++){for(j=1;j<=m;j++) printf("%d ",b[i][j]-a[i][j]);puts("");}return 0;}

---

Blog来自PaperCloud，未经允许，请勿转载，TKS！

转载于:https://www.cnblogs.com/PaperCloud/p/9495925.html

总结

以上是生活随笔为你收集整理的[20180817]校内模拟赛的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。