5月集训Day6考试

啊，算导复杂度分析没好好看啊：（

目录

• • • 算循环loop
    • 最大化max
    • 打隔膜game

算循环loop

O(1)公式算法。。。把n，m有关的循环分开写在乘一起，互不相干；
噗噗大神矩阵快速幂%%%

#include <cstdio>
#include <iostream>
using namespace std;

const unsigned long long P=(unsigned long long)(1e9+7),P_INV=166666668;

int main(){
    freopen("loop.in","r",stdin);
    freopen("loop.out","w",stdout);
unsigned long long n,m;
cin>>n>>m;
    n%=P,m%=P;
unsigned long long ansn=((((n*n)%P)*n%P+3*(n*n)%P+2*n)%P*P_INV)%P;
unsigned long long ansm=((((m*m)%P)*m%P+3*(m*m)%P+2*m)%P*P_INV)%P;
unsigned long long tmp=(ansn*ansm)%P;
//printf("%lld",tmp);
cout<<tmp;
    fclose(stdin);
    fclose(stdout);
return 0;
}

---

最大化max

枚举左右边界，上下边界用前缀和+单调队列

#include <cstdio>
#include <cstring>
using namespace std;
#define max(a,b) (a>b ? a:b)

inline int read();

const long long INF=~0ULL>>1;
const int MAXN=305;
int mat[MAXN][MAXN],n,m,tail,pos[MAXN];
long long pre[MAXN],q[MAXN];

inline int find(const long long &x){
int l=1,r=tail,mid,ret=-1;
while(r>=l){
        mid=(l+r)>>1;
if(x>q[mid]){
            ret=mid;
            r=mid-1;
        }
else l=mid+1;
    }
return ret;
}

int main(){
    freopen("max.in","r",stdin);
    freopen("max.out","w",stdout);
    scanf("%d%d",&n,&m);
for(int i=1;i<=n;++i){
for(int j=1;j<=m;++j)
            scanf("%d",&mat[i][j]);
    }
int ans=0;
for(int i=1;i<=m;++i){
        memset(pre,0,sizeof(pre));
for(int j=i,wid,len;j<=m;++j){
for(int k=1;k<=n;++k)
                pre[k]+=mat[k][j];
            wid=j-i+1,len=ans/wid;
if(len>=n) continue;
q[0]=INF,tail=0;
            long long sum=0;
//for(l=1;l<=len;++l)
            //  sum+=pre[l];
for(int now,p,l=1;l<=n;++l){
                sum+=pre[l];
if(sum>=0) ans=max(ans,l*wid);
else{
                    p=find(sum);
if(p!=-1)
                        ans=max((l-pos[p])*wid,ans);
                }
if(sum<q[tail]){
q[++tail]=sum;
pos[tail]=l;
                }
            }
        }
    }
printf("%d",ans);
    fclose(stdin);
    fclose(stdout);
return 0;
}

---

打隔膜game

这贪心。。。
先放大[/滑稽]，枚举群攻次数就好了。。。

#include <cstdio>
#include <algorithm>
using namespace std;
#define min(a,b) (a<b ? a:b)

inline long long read();

const int MAXN=100005;
long long h[MAXN],tmp[MAXN],n,m;

int main(){
    freopen("game.in","r",stdin);
    freopen("game.out","w",stdout);
    n=read(),m=read();
for(long long i=1;i<=n;++i)
        h[i]=read();
    sort(h+1,h+n+1);
long long ans=~0ULL>>1,now;
for(long long i=0,rest;i<=m;++i){
        now=0;
for(long long j=1;j<=n;++j){
if(h[j]<=i){
                tmp[j]=0;
                now+=h[j]-1;
            }
else{
                tmp[j]=h[j]-i;
                now+=i;
            }
        }
        rest=m-i;
for(long long j=1,rd;j<=n;++j){
if(tmp[j]){
                rd=min(rest,(tmp[j]>>1));
                rest-=rd;
                rd+=tmp[j]-(rd<<1);
                now+=rd*(n-j+1)-1;
            }
        }
        ans=min(ans,now);
    }
printf("%lld",ans);
    fclose(stdin);
    fclose(stdout);
return 0;
}

inline long long read(){
char c; long long x;
while(c=getchar(),c<'0' || '9'<c);
    x=c-'0';
while(c=getchar(),'0'<=c && c<='9')
        x=x*10+c-'0';
return x;
}