【水题合集】6.10考试 – 徐亦轲的博客

听说明天会考的难一些

1.汽艇

暴力搞起

枚举人数，排序贪心

// <boat.cpp> - 06/10/16 08:01:34
// This file is created by XuYike's black technology automatically.
// Copyright (C) 2015 ChangJun High School, Inc.
// I don't know what this program is.

#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <cmath>
using namespace std;
typedef long long lol;
int gi(){
    int res=0,fh=1;char ch=getchar();
    while((ch>'9'||ch<'0')&&ch!='-')ch=getchar();
    if(ch=='-')fh=-1,ch=getchar();
    while(ch>='0'&&ch<='9')res=res*10+ch-'0',ch=getchar();
    return fh*res;
}
const int MAXN=1010;
const int INF=1e9;
int c[MAXN],d[MAXN];
int sb[MAXN];
inline bool cmp(int x,int y){return x>y;}
int main(){
    freopen("boat.in","r",stdin);
    freopen("boat.out","w",stdout);
    int n=gi();
    for(int i=1;i<=n;i++)c[i]=gi();
    for(int i=1;i<=n;i++)d[i]=gi();
    int ans=0,tot=0;
    for(int k=n;k;k--){
        int cnt=0,now=0;
        for(int i=1;i<=n;i++)
            if(c[i]-d[i]*(k-1)>0)sb[++cnt]=c[i]-d[i]*(k-1);
        if(cnt<k)continue;
        sort(sb+1,sb+cnt+1,cmp);
        for(int i=1;i<=k;i++)now+=sb[i];
        if(now>ans)ans=now,tot=k;
    }
    printf("%d\n%d",ans,tot);
    return 0;
}

// <boat.cpp> - 06/10/16 08:01:34

// This file is created by XuYike's black technology automatically.

// I don't know what this program is.

#include <iostream>

#include <vector>

#include <algorithm>

#include <cstring>

#include <cstdio>

#include <cmath>

using namespace std;

typedef long long lol;

int gi(){

int res=0,fh=1;char ch=getchar();

while((ch>'9'||ch<'0')&&ch!='-')ch=getchar();

if(ch=='-')fh=-1,ch=getchar();

while(ch>='0'&&ch<='9')res=res*10+ch-'0',ch=getchar();

return fh*res;

}

const int MAXN=1010;

const int INF=1e9;

int c[MAXN],d[MAXN];

int sb[MAXN];

inline bool cmp(int x,int y){return x>y;}

int main(){

freopen("boat.in","r",stdin);

freopen("boat.out","w",stdout);

int n=gi();

for(int i=1;i<=n;i++)c[i]=gi();

for(int i=1;i<=n;i++)d[i]=gi();

int ans=0,tot=0;

for(int k=n;k;k--){

int cnt=0,now=0;

for(int i=1;i<=n;i++)

if(c[i]-d[i]*(k-1)>0)sb[++cnt]=c[i]-d[i]*(k-1);

if(cnt<k)continue;

sort(sb+1,sb+cnt+1,cmp);

for(int i=1;i<=k;i++)now+=sb[i];

if(now>ans)ans=now,tot=k;

}

printf("%d\n%d",ans,tot);

return 0;

}

2.上网

dp一下

其实这题也可以用网络流做

// <net.cpp> - 06/10/16 08:01:35
// This file is created by XuYike's black technology automatically.
// Copyright (C) 2015 ChangJun High School, Inc.
// I don't know what this program is.

#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <cmath>
using namespace std;
typedef long long lol;
int gi(){
    int res=0,fh=1;char ch=getchar();
    while((ch>'9'||ch<'0')&&ch!='-')ch=getchar();
    if(ch=='-')fh=-1,ch=getchar();
    while(ch>='0'&&ch<='9')res=res*10+ch-'0',ch=getchar();
    return fh*res;
}
const int MAXN=500010;
const int INF=1e9;
int bt,b[MAXN],next[MAXN],to[MAXN],val[MAXN];
inline void add(int x,int y,int c){next[++bt]=b[x];b[x]=bt;to[bt]=y;val[bt]=c;}
int dp[MAXN];
int main(){
    freopen("net.in","r",stdin);
    freopen("net.out","w",stdout);
    int n=gi(),T=gi();
    for(int i=1;i<=n;i++){
        int m=gi();
        while(m--){
            int x=gi(),y=gi(),c=gi();
            add(y,x-1,c);
        }
    }
    for(int t=1;t<=T;t++){
        dp[t]=dp[t-1];
        for(int i=b[t];i;i=next[i])dp[t]=max(dp[t],dp[to[i]]+val[i]);
    }
    printf("%d",dp[T]);
    return 0;
}

// <net.cpp> - 06/10/16 08:01:35

// This file is created by XuYike's black technology automatically.

// I don't know what this program is.

#include <iostream>

#include <vector>

#include <algorithm>

#include <cstring>

#include <cstdio>

#include <cmath>

using namespace std;

typedef long long lol;

int gi(){

int res=0,fh=1;char ch=getchar();

while((ch>'9'||ch<'0')&&ch!='-')ch=getchar();

if(ch=='-')fh=-1,ch=getchar();

while(ch>='0'&&ch<='9')res=res*10+ch-'0',ch=getchar();

return fh*res;

}

const int MAXN=500010;

const int INF=1e9;

int bt,b[MAXN],next[MAXN],to[MAXN],val[MAXN];

inline void add(int x,int y,int c){next[++bt]=b[x];b[x]=bt;to[bt]=y;val[bt]=c;}

int dp[MAXN];

int main(){

freopen("net.in","r",stdin);

freopen("net.out","w",stdout);

int n=gi(),T=gi();

for(int i=1;i<=n;i++){

int m=gi();

while(m--){

int x=gi(),y=gi(),c=gi();

add(y,x-1,c);

}

for(int t=1;t<=T;t++){

dp[t]=dp[t-1];

for(int i=b[t];i;i=next[i])dp[t]=max(dp[t],dp[to[i]]+val[i]);

}

printf("%d",dp[T]);

return 0;

}

3.集合

这题太屌了我不会做

不过显然是在取两个的时候最优

弄了个80分骗分（向总机子真是太慢了）

// <gather.cpp> - 06/10/16 08:01:35
// This file is created by XuYike's black technology automatically.
// Copyright (C) 2015 ChangJun High School, Inc.
// I don't know what this program is.

#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <cmath>
using namespace std;
typedef long long lol;
int gi(){
    int res=0,fh=1;char ch=getchar();
    while((ch>'9'||ch<'0')&&ch!='-')ch=getchar();
    if(ch=='-')fh=-1,ch=getchar();
    while(ch>='0'&&ch<='9')res=res*10+ch-'0',ch=getchar();
    return fh*res;
}
const int MAXN=1000010;
const int INF=1e9;
struct sb{
    int l,r;
    bool operator <(const sb b) const {return l==b.l?r<b.r:l<b.l;}
}s[MAXN];
int main(){
    freopen("gather.in","r",stdin);
    freopen("gather.out","w",stdout);
    int n=gi();lol ans=0;
    for(int i=1;i<=n;i++)s[i].l=gi(),s[i].r=gi();
    sort(s+1,s+n+1);
    int lim=8e6/n;
    for(int i=1;i<=n;i++)
        for(int j=i+1;j<=n&&j<=i+lim;j++)
            ans=max(ans,1ll*(max(s[i].r,s[j].r)-min(s[i].l,s[j].l))*(min(s[i].r,s[j].r)-max(s[i].l,s[j].l)));
    printf("%lld",ans);
    return 0;
}

// <gather.cpp> - 06/10/16 08:01:35

// This file is created by XuYike's black technology automatically.

// I don't know what this program is.

#include <iostream>

#include <vector>

#include <algorithm>

#include <cstring>

#include <cstdio>

#include <cmath>

using namespace std;

typedef long long lol;

int gi(){

int res=0,fh=1;char ch=getchar();

while((ch>'9'||ch<'0')&&ch!='-')ch=getchar();

if(ch=='-')fh=-1,ch=getchar();

while(ch>='0'&&ch<='9')res=res*10+ch-'0',ch=getchar();

return fh*res;

}

const int MAXN=1000010;

const int INF=1e9;

struct sb{

int l,r;

bool operator <(const sb b) const {return l==b.l?r<b.r:l<b.l;}

}s[MAXN];

int main(){

freopen("gather.in","r",stdin);

freopen("gather.out","w",stdout);

int n=gi();lol ans=0;

for(int i=1;i<=n;i++)s[i].l=gi(),s[i].r=gi();

sort(s+1,s+n+1);

int lim=8e6/n;

for(int i=1;i<=n;i++)

for(int j=i+1;j<=n&&j<=i+lim;j++)

ans=max(ans,1ll*(max(s[i].r,s[j].r)-min(s[i].l,s[j].l))*(min(s[i].r,s[j].r)-max(s[i].l,s[j].l)));

printf("%lld",ans);

return 0;

}

4.新斯诺克

把每个数都减去m后问题可以转化为求和为正的区间个数

那么就是求前缀和的正序对

然而我个垃圾并没有看出来逆序对写了个nlog2n的分治

// <snooker.cpp> - 06/10/16 08:01:35
// This file is created by XuYike's black technology automatically.
// Copyright (C) 2015 ChangJun High School, Inc.
// I don't know what this program is.

#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <cmath>
using namespace std;
typedef long long lol;
int gi(){
    int res=0,fh=1;char ch=getchar();
    while((ch>'9'||ch<'0')&&ch!='-')ch=getchar();
    if(ch=='-')fh=-1,ch=getchar();
    while(ch>='0'&&ch<='9')res=res*10+ch-'0',ch=getchar();
    return fh*res;
}
const int MAXN=100001;
const int INF=1e9;
lol a[MAXN];
lol ls[MAXN],rs[MAXN];
lol work(int l,int r){
    if(l>r)return 0;
    int m=(l+r)>>1;
	ls[0]=rs[0]=0;
    for(int i=m-1;i>=l;i--)ls[m-i]=ls[m-i-1]+a[i];
    for(int i=m+1;i<=r;i++)rs[i-m]=rs[i-m-1]+a[i];
    sort(ls,ls+m-l+1);
    sort(rs,rs+r-m+1);
    int p=0;lol res=0;
    for(int i=m-l;i>=0;i--){
        while(p<=r-m&&ls[i]+rs[p]+a[m]<=0)p++;
        res+=r-m-p+1;
    }
    return res+work(l,m-1)+work(m+1,r);
}
int main(){
    freopen("snooker.in","r",stdin);
    freopen("snooker.out","w",stdout);
    int n=gi(),m=gi();
    for(int i=1;i<=n;i++)a[i]=gi()-m;
    printf("%lld",work(1,n));
    return 0;
}

// <snooker.cpp> - 06/10/16 08:01:35

// This file is created by XuYike's black technology automatically.

// I don't know what this program is.

#include <iostream>

#include <vector>

#include <algorithm>

#include <cstring>

#include <cstdio>

#include <cmath>

using namespace std;

typedef long long lol;

int gi(){

int res=0,fh=1;char ch=getchar();

while((ch>'9'||ch<'0')&&ch!='-')ch=getchar();

if(ch=='-')fh=-1,ch=getchar();

while(ch>='0'&&ch<='9')res=res*10+ch-'0',ch=getchar();

return fh*res;

}

const int MAXN=100001;

const int INF=1e9;

lol a[MAXN];

lol ls[MAXN],rs[MAXN];

lol work(int l,int r){

if(l>r)return 0;

int m=(l+r)>>1;

ls[0]=rs[0]=0;

for(int i=m-1;i>=l;i--)ls[m-i]=ls[m-i-1]+a[i];

for(int i=m+1;i<=r;i++)rs[i-m]=rs[i-m-1]+a[i];

sort(ls,ls+m-l+1);

sort(rs,rs+r-m+1);

int p=0;lol res=0;

for(int i=m-l;i>=0;i--){

while(p<=r-m&&ls[i]+rs[p]+a[m]<=0)p++;

res+=r-m-p+1;

}

return res+work(l,m-1)+work(m+1,r);

}

int main(){

freopen("snooker.in","r",stdin);

freopen("snooker.out","w",stdout);

int n=gi(),m=gi();

for(int i=1;i<=n;i++)a[i]=gi()-m;

printf("%lld",work(1,n));

return 0;

}