毕业考试
(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[];
void out(long long x)
{
if(x/) out(x/);
putchar(x%+'');
}
void read(int &x)
{
x=; int f=; char c=getchar();
while(c<''|| c>'') { if(c=='-') f=-; c=getchar(); }
while(c>='' && c<='') { x=x*+c-''; 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=;i<=n;i++) read(e[i].now),read(e[i].more),tmp+=e[i].now ;
sort(e+,e+n+);
tot=1ll*v*n;
int i=;
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 1000000007
using namespace std;
int n,a,b,k,ans;
long long f[][];
int sum[];
int main()
{
freopen("lift.in","r",stdin);
freopen("lift.out","w",stdout);
scanf("%d%d%d%d",&n,&a,&b,&k);
for(int i=;i<=n;i++)
{
if(abs(a-i)<abs(a-b) && i!=a) f[i][]=;
sum[i]=sum[i-]+f[i][];
}
for(int t=;t<=k;t++)
{
for(int i=;i<b;i++) f[i][t]=(f[i][t]+sum[(b+i+)/-]-sum[i]+sum[i-]+mod)%mod;
for(int i=b+;i<=n;i++) f[i][t]=(f[i][t]+sum[i-]-sum[(b+i)/+-]+sum[n]-sum[i]+mod)%mod;
for(int i=;i<=n;i++) sum[i]=(sum[i-]+f[i][t])%mod;
}
for(int i=;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 100001
using 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=;i<=n;i++) scanf("%d",&a[i]);
for(int i=;i<=n;i++)
if(a[i]==) sum1[i]=sum1[i-]+,sum2[i]=sum2[i-];
else sum1[i]=sum1[i-],sum2[i]=sum2[i-]+;
int last,l,r,mid,tmp,cnt1,cnt2,now; int tot=;
for(int i=;i<=n;i++)
{
last=; cnt1=cnt2=;
while()
{
l=last+,r=n,mid,tmp=-;
while(l<=r)
{
mid=l+r>>;
if(sum1[mid]-sum1[last]>=i || sum2[mid]-sum2[last]>=i) tmp=mid,r=mid-;
else l=mid+;
}
if(tmp==-) break;
if(sum1[tmp]-sum1[last]==i) cnt1++,now=;
else cnt2++,now=;
if(tmp==n)
{
if(cnt1==cnt2 || cnt1>cnt2 && now== || cnt2>cnt1 && now==) break;
ans[++tot].t=i, ans[tot].s=max(cnt1,cnt2);
break;
}
last=tmp;
}
}
sort(ans+,ans+tot+);
printf("%d\n",tot);
for(int i=;i<=tot;i++) printf("%d %d\n",ans[i].s,ans[i].t);
}