听说明天会考的难一些
1.汽艇
暴力搞起
枚举人数,排序贪心
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 |
// <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; } |
2.上网
dp一下
其实这题也可以用网络流做
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 |
// <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; } |
3.集合
这题太屌了我不会做
不过显然是在取两个的时候最优
弄了个80分骗分(向总机子真是太慢了)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 |
// <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; } |
4.新斯诺克
把每个数都减去m后问题可以转化为求和为正的区间个数
那么就是求前缀和的正序对
然而我个垃圾并没有看出来逆序对写了个nlog2n的分治
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 |
// <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; } |