首页 > 代码库 > 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);}
View Code

 

电梯

(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);} 
View Code

 

 

乒乓球

(game.cpp/c/pas)

(1s/256M)

问题描述

GobMichael常在一起打乒乓球。他们是这样决定比赛的输赢的:比赛由若干大局组成;谁最先赢下s大局谁就获得比赛的胜利;在每一大局中,谁先得t分就获得本大局的胜利。

 

在一次比赛中,他们只记录了比赛中的每一分是谁得的,但忘记了记录st。现在给出比赛的每一分的得分情况,求出所有可能的stGob保证,得分表是完整的,也就是在比赛恰好在最后一人,得到最后一分后结束。

 

输入格式(game.in)

第一行一个整数N,代表比赛一共得到了多少分。

第二行N个整数,代表比赛中每一分是谁得到的;1代表Gob2代表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);}
View Code

 

2017 济南综合班 Day 5