NOIP试题集锦

115 LL a,b,c;

116 for(LL i=1;i

117 scanf(\,&a,&b,&c); 118 addedge(a,b,c); 119 }

120 scanf(\,&m); 121 fail();

122 for(LL i=1;i<=m;i++) scanf(\,&p[i]); 123 LL ans,l=0,r=1000000000000LL; 124 prework(); 125 while(l<=r){

126 LL mid=(l+r)>>1; 127 if(check(mid)){ 128 ans=mid; 129 r=mid-1; 130 } else l=mid+1; 131 }

132 printf(\,ans); 133 }

2013年10月15日 noip2012 国王游戏 描述

恰逢H国国庆，国王邀请n位大臣来玩一个有奖游戏。首先，他让每个大臣在左、右手上面分别写下一个整数，国王自己也在左、右手上各写一个整数。然后，让这n位大臣排成一排，国王站在队伍的最前面。排好队后，所有的大臣都会获得国王奖赏的若干金币，每位大臣获得的金币数分别是：排在该大臣前面的所有人的左手上的数的乘积除以他自己右手上的数，然后向下取整得到的结果。 国王不希望某一个大臣获得特别多的奖赏，所以他想请你帮他重新安排一下队伍的顺序，使得获得奖赏最多的大臣，所获奖赏尽可能的少。注意，国王的位置始终在队伍的最前面。 格式

输入格式

第一行包含一个整数n，表示大臣的人数。

第二行包含两个整数a和b，之间用一个空格隔开，分别表示国王左手和右手上的整数。接下来n行，每行包含两个整数a和b，之间用一个空格隔开，分别表示每个大臣左手和右手上的整数。 输出格式

输出只有一行，包含一个整数，表示重新排列后的队伍中获奖赏最多的大臣所获得的金币数。 数据

对于20%的数据，有1≤ n≤ 10，0 < a、b < 8； 对于40%的数据，有1≤ n≤20，0 < a、b < 8； 对于60%的数据，有1≤ n≤100；

对于60%的数据，保证答案不超过10^9；

对于100%的数据，有1 ≤ n ≤1,000，0 < a、b < 10000。

--------------------------------------------------------------------------------

正解= 贪心+高精. 贪心证明 :

设存在 相邻大臣A(l1,r1),B(l2,r2),A,B前左手乘积为Sum : 当A在B前时:

则Ans=max(Sum/r1,Sum*l1/r2) ; 当B在A前时:

则Ans=max(Sum/r2,Sum*l2/r1) ; 显然 Sum*l2/r1>Sum/r1 ; Sum*l1/r2>Sum/r2 ; 所以当 Sum*l2/r1>Sum*l1/r2

即 l2*r2>l1*r1 时 A应在B前 同理

即 l2*r2

所以按 l*r 从小到大排序在进行模拟即为正解. 代码如下:

1 #include 2 #include 3 #include 4 #include 5 #include 6 #include

7 #define INF 99999999 8 #define LL long long 9 //using namespace std; 10 struct STR{

11 int s[3000]; 12 }ans,sum; 13 struct P{ 14 int l,r; 15 }p[1001]; 16 int n;

17 bool cmp(const P &x,const P &y){ 18 return x.l*x.r

20 void time(STR &a,int b){

21 int L=a.s[0];

22 for(int i=1;i<=L;i++) a.s[i]*=b; 23 for(int i=1;i<=L;i++){

24 a.s[i+1]+=a.s[i]/10000; 25 a.s[i]%=10000; 26 }

27 while(a.s[L+1]){ 28 ++L;

29 a.s[L+1]+=a.s[L]/10000; 30 a.s[L]%=10000; 31 }

32 a.s[0]=L; 33 }

34 void Max(STR &a,STR b){

35 if(a.s[0]b.s[0]) return ; 37 for(int i=a.s[0];i;i--){

38 if(a.s[i]b.s[i]) return ; 40 } 41 }

42 STR div(STR a,int b){ 43 int x=0,L=a.s[0]; 44 STR c;

45 memset(c.s,0,sizeof(c.s)); 46 for(int i=L;i>=1;i--){ 47 x=x*10000+a.s[i]; 48 c.s[i]=x/b; 49 x%=b; 50 }

51 while(!c.s[L]) --L; 52 c.s[0]=L; 53 return c; 54 }

55 void put(STR a){

56 printf(\,a.s[a.s[0]]);

57 for(int i=a.s[0]-1;i;i--) printf(\,a.s[i]); 58 }

59 int main(){

60 freopen(\,\,stdin); 61 freopen(\,\,stdout); 62 scanf(\,&n);

63 for(int i=0;i<=n;i++) scanf(\,&p[i].l,&p[i].r); 64 std :: sort(p+1,p+1+n,cmp);

65 sum.s[0]=sum.s[1]=1; 66 time(sum,p[0].l);

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

68 Max(ans,div(sum,p[i].r)); 69 time(sum,p[i].l); 70 }

71 put(ans); 72 }

2013年10月18日 noip2011 公交观光 描述

风景迷人的小城Y市，拥有n个美丽的景点。由于慕名而来的游客越来越多，Y市特意安排了一辆观光公交车，为游客提供更便捷的交通服务。观光公交车在第0分钟出现在1号景点，随后依次前往2、3、4……n号景点。从第i号景点开到第i+1号景点需要Di分钟。任意时刻，公交车只能往前开，或在景点处等待。 设共有m个游客，每位游客需要乘车1次从一个景点到达另一个景点，第i位游客在Ti分钟来到景点Ai，希望乘车前往景点Bi（Ai

那么ZZ该如何安排使用加速器，才能使所有乘客的旅行时间总和最小？ 格式

输入格式

第1行是3个整数n, m, k，每两个整数之间用一个空格隔开。分别表示景点数、乘客数和氮气加速器个数。

第2行是n-1个整数，每两个整数之间用一个空格隔开，第i个数表示从第i个景点开往第i+1个景点所需要的时间，即Di。

第3行至m+2行每行3个整数Ti, Ai, Bi，每两个整数之间用一个空格隔开。第i+2行表示第i位乘客来到出发景点的时刻，出发的景点编号和到达的景点编号。

输出格式

共一行，包含一个整数，表示最小的总旅行时间。 数据范围 样例说明：

对D2使用2个加速器，从2号景点到3号景点时间变为2分钟。