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
    
         #include
     
          #include
      
           #include
       
            #include
        
             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 100005    int n,k;    int a[MN],b[MN];    long long ans;    std::pair
         
           P; std::priority_queue
          
           
             > 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
    
         #include
     
          #include
      
           #include
       
            #include
        
             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
        
       
      
     
    

T3 水题(water)

Solution

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

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

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

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

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

两个做法本质相同

这是用MST的：

#include
    
         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
    

---

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