首页 > 代码库 > 2017 济南综合班 Day 5
2017 济南综合班 Day 5
毕业考试
(exam.cpp/c/pas)
(1s/256M)
问题描述
快毕业了,Barry希望能通过期末的N门考试来顺利毕业。如果他的N门考试平均分能够达到V分,则他能够成功毕业。现在已知每门的分数不能够超过R;他的第i门考试目前得分为Ai,如果想要在这门科目增加一分则需要多写Bi篇论文。Barry想知道,如果想要毕业的话,他最少需要写多少篇论文?
输入格式(exam.in)
第一行三个整数,N, R, V,分别代表考试科目数,每门考试的最高分,需要达到的平均分。
接下来的N行每行两个整数A, B,分别代表这门考试的目前得分与增加一分需要多写的论文数。
输出格式(exam.out)
一个整数,代表他要毕业最少需要写的论文数。
样例输入
5 5 4
3 1
3 2
5 2
4 7
2 5
样例输出
4
数据范围及约束
对于30%的数据,N<=5, R<=3;
对于100%的数据,N<=100,000, R<=1000,000,000, 1<=V<=R
保证答案不超过10^18.
#include<cstdio>#include<algorithm>using namespace std;int n,r,v;long long tot,tmp,ans;struct node{ int now,more; bool operator < (node p) const { return more<p.more; } }e[100001];void out(long long x){ if(x/10) out(x/10); putchar(x%10+‘0‘);}void read(int &x){ x=0; int f=1; char c=getchar(); while(c<‘0‘|| c>‘9‘) { if(c==‘-‘) f=-1; c=getchar(); } while(c>=‘0‘ && c<=‘9‘) { x=x*10+c-‘0‘; c=getchar(); } x*=f;}int main(){ freopen("exam.in","r",stdin); freopen("exam.out","w",stdout); read(n); read(r); read(v); for(int i=1;i<=n;i++) read(e[i].now),read(e[i].more),tmp+=e[i].now ; sort(e+1,e+n+1); tot=1ll*v*n; int i=1; while(tmp!=tot) { if(r-e[i].now+tmp<=tot) tmp+=(r-e[i].now),ans+=1ll*(r-e[i].now)*e[i].more; else ans+=1ll*(tot-tmp)*e[i].more,tmp=tot; i++; } out(ans);}
电梯
(lift.c/cpp/pas)
(1s/256M)
问题描述
无所事事的Cinzo决定用坐电梯的方式来打发时间。他住在一个N层的房子中,最底下为1层,最高处为N层。他从他家所在的第A层出发,并决定连续坐K次电梯。
但由于迷信的缘故,B在中国被视为是不幸运的,所以整座楼并没有第B层。也是因为这个原因,如果Cinzo想从第X层出发到达第Y层,他希望Y能满足|X - Y| < |X - B|。
每次电梯到达后,Cinzo都会将电梯所到的层数记录在小本子上;K次电梯都坐完后,他将得到一个长度为K的数列。现在,Cinzo想知道,他可能写出多少个不同的数列?
输入格式(lift.in)
一行四个整数,N,A,B,K,分别代表电梯的层数,Cinzo最初的位置,不幸运的层数,以及乘坐电梯的次数。
输出格式(lift.out)
一个整数,代表不同的数列数。(结果对1000,000,007取模)
样例输入
5 2 4 2
样例输出
2
数据范围与约束
对于20%的数据,N<=10, K<=5;
对于60%的数据,N,K<=100;
对于100%的数据,N,K<=5000。
#include<cmath>#include<cstdio>#include<algorithm>#define mod 1000000007using namespace std;int n,a,b,k,ans;long long f[5001][5001];int sum[5001];int main(){ freopen("lift.in","r",stdin); freopen("lift.out","w",stdout); scanf("%d%d%d%d",&n,&a,&b,&k); for(int i=1;i<=n;i++) { if(abs(a-i)<abs(a-b) && i!=a) f[i][1]=1; sum[i]=sum[i-1]+f[i][1]; } for(int t=2;t<=k;t++) { for(int i=1;i<b;i++) f[i][t]=(f[i][t]+sum[(b+i+1)/2-1]-sum[i]+sum[i-1]+mod)%mod; for(int i=b+1;i<=n;i++) f[i][t]=(f[i][t]+sum[i-1]-sum[(b+i)/2+1-1]+sum[n]-sum[i]+mod)%mod; for(int i=1;i<=n;i++) sum[i]=(sum[i-1]+f[i][t])%mod; } for(int i=1;i<=n;i++) ans=(ans+f[i][k])%mod; printf("%d",ans);}
乒乓球
(game.cpp/c/pas)
(1s/256M)
问题描述
Gob和Michael常在一起打乒乓球。他们是这样决定比赛的输赢的:比赛由若干大局组成;谁最先赢下s大局谁就获得比赛的胜利;在每一大局中,谁先得t分就获得本大局的胜利。
在一次比赛中,他们只记录了比赛中的每一分是谁得的,但忘记了记录s和t。现在给出比赛的每一分的得分情况,求出所有可能的s和t。Gob保证,得分表是完整的,也就是在比赛恰好在最后一人,得到最后一分后结束。
输入格式(game.in)
第一行一个整数N,代表比赛一共得到了多少分。
第二行N个整数,代表比赛中每一分是谁得到的;1代表Gob,2代表Michael。
输出格式(game.out)
第一行一个整数M,代表共有多少种可能的s,t情况。
接下来M行每行两个整数si, ti,代表一种可能的s,t情况。M种情况按照s从小到大输出;在s相等时按照t从小到大输出。
样例输入1
5
1 2 1 2 1
样例输出1
2
1 3
3 1
样例输入2
5
1 2 2 2 1
样例输出2
0
样例输入3
10
1 1 2 1 1 1 2 2 1 1
样例输出3
3
1 7
3 2
7 1
数据范围与约束
对于50%的数据,N<=1000;
对于100%的数据,1<=N<=100,000。
枚举t,二分小局结束位置
#include<cstdio>#include<algorithm>#define N 100001using namespace std;int n,a[N],sum1[N],sum2[N];struct node{ int s,t; bool operator < (node p)const { if(s!=p.s) return s<p.s; return t<p.t; }}ans[N];int main(){ freopen("game.in","r",stdin); freopen("game.out","w",stdout); scanf("%d",&n); for(int i=1;i<=n;i++) scanf("%d",&a[i]); for(int i=1;i<=n;i++) if(a[i]==1) sum1[i]=sum1[i-1]+1,sum2[i]=sum2[i-1]; else sum1[i]=sum1[i-1],sum2[i]=sum2[i-1]+1; int last,l,r,mid,tmp,cnt1,cnt2,now; int tot=0; for(int i=1;i<=n;i++) { last=0; cnt1=cnt2=0; while(1) { l=last+1,r=n,mid,tmp=-1; while(l<=r) { mid=l+r>>1; if(sum1[mid]-sum1[last]>=i || sum2[mid]-sum2[last]>=i) tmp=mid,r=mid-1; else l=mid+1; } if(tmp==-1) break; if(sum1[tmp]-sum1[last]==i) cnt1++,now=1; else cnt2++,now=2; if(tmp==n) { if(cnt1==cnt2 || cnt1>cnt2 && now==2 || cnt2>cnt1 && now==1) break; ans[++tot].t=i, ans[tot].s=max(cnt1,cnt2); break; } last=tmp; } } sort(ans+1,ans+tot+1); printf("%d\n",tot); for(int i=1;i<=tot;i++) printf("%d %d\n",ans[i].s,ans[i].t);}
2017 济南综合班 Day 5