noip2011day2题解

描述

给定一个多项式(ax + by)^k，请求出多项式展开后x^n * y^m项的系数。

格式

输入格式

共一行，包含5个整数，分别为a，b，k，n，m，每两个整数之间用一个空格隔开。

输出格式

输出共1行，包含一个整数，表示所求的系数，这个系数可能很大，输出对10007取模后的结果。

样例1

样例输入1[复制]

 

1 1 3 1 2

样例输出1[复制]

 

3

限制

1s

提示

对于30%的数据，有0 ≤ k ≤ 10；
对于50%的数据，有a = 1, b = 1；
对于100%的数据，有0 ≤ k ≤ 1000，0 ≤ n, m ≤ k，且n+m = k，0 ≤ a，b ≤ 1,000,000.

dp

 1 #include
 2 #include
 3 #include
 4 using namespace std;
 5 long long a,b,k,m,n,a1=1,b1=1,answer=1,f[2][1005]={0};
 6 
 7 int main()
 8 {
 9     cin>>a>>b>>k>>n>>m;
10     f[0][0]=f[0][1]=1;
11     for(int i=1;i)
12     {
13         f[i%2][0]=f[i%2][i+1]=1;
14         for(int j=1;j<=i;j++)
15          f[i%2][j]=(f[(i+1)%2][j]+f[(i+1)%2][j-1])%10007;
16     }
17     for(int i=0;i)
18     {
19         a1*=a;
20         a1%=10007;
21     }
22     for(int i=0;i)
23     {
24         b1*=b;
25         b1%=10007;
26     }
27     answer*=a1*b1;
28     answer%=10007;
29     answer*=f[(k-1)%2][n];
30     answer%=10007;
31     cout<endl;
32     return 0;
33 }

描述

小 T 是一名质量监督员，最近负责检验一批矿产的质量。这批矿产共有n个矿石，从1到n逐一编号，每个矿石都有自己的重量wi以及价值vi。检验矿产的流程是：
1、给定m个区间[Li，Ri]；
2、选出一个参数W；
3、对于一个区间[Li，Ri]，计算矿石在这个区间上的检验值Yi：
Yi=(∑j1)∗(∑jvj) ,  j∈[Li,Ri]且wj≥W">Yi=(∑j1)?(∑jvj) ,  j∈[Li,Ri]且wj≥WYi=(∑j1)?(∑jvj) ,  j∈[Li,Ri]且wj≥W
j是矿石编号

这批矿产的检验结果Y 为各个区间的检验值之和。即：Y=∑i=1mYi">Y=∑i=1mYiY=∑i=1mYi
若这批矿产的检验结果与所给标准值S相差太多，就需要再去检验另一批矿产。小T不想费时间去检验另一批矿产，所以他想通过调整参数W的值，让检验结果尽可能的靠近标准值S，即使得S-Y的绝对值最小。请你帮忙求出这个最小值。

格式

输入格式

第一行包含三个整数n，m，S，分别表示矿石的个数、区间的个数和标准值。

接下来的n行，每行2个整数，中间用空格隔开，第i+1行表示i号矿石的重量wi和价值vi 。

接下来的m行，表示区间，每行2个整数，中间用空格隔开，第i+n+1行表示区间[Li,Ri]的两个端点Li和Ri。注意：不同区间可能重合或相互重叠。

输出格式

输出只有一行，包含一个整数，表示所求的最小值。

样例1

样例输入1[复制]

 

5 3 15
1 5
2 5
3 5
4 5
5 5
1 5
2 4
3 3

样例输出1[复制]

 

10

限制

1s

提示

样例说明：当W选4的时候，三个区间上检验值分别为20、5、0，这批矿产的检验结果为25，此时与标准值S相差最小为10。

对于10%的数据，有1 ≤ n，m ≤ 10；
对于30%的数据，有1 ≤ n，m ≤ 500；
对于50%的数据，有1 ≤ n，m ≤ 5,000；
对于70%的数据，有1 ≤ n，m ≤ 10,000；
对于100%的数据，有1 ≤ n，m ≤ 200,000，0 < wi, vi ≤ 10^6，0 < S ≤ 10^12，1 ≤ Li ≤ Ri ≤ n。

二分

 1 #include
 2 #include
 3 #include
 4 #include
 5 using namespace std;
 6 int n,m,l[200010],r[200010],w[200010],y[200010];
 7 long long S,Y,ansy,ans=1000000000000000,s[200010]={0},d[200010]{0},mleft=0,mright=0,mid,tree[200010]={0};
 8 long long change(long long x,long long y)
 9 {
10     if(x>y)return x-y;
11     return y-x;
12 }
13 
14 int main()
15 {
16     cin>>n>>m>>S;
17     for(int i=1;i<=n;i++)scanf("%d%d",&w[i],&y[i]);
18     for(int i=1;i<=m;i++)scanf("%d%d",&l[i],&r[i]);
19     
20     for(int i=1;i<=n;i++) 
21      if(w[i]>mright)mright=w[i];
22     mright+=100;
23     while(mleft<mright)
24     {
25         mid=(mleft+mright)/2;
26         
27         for(int i=1;i<=n;i++)
28         if(w[i]>=mid)
29         {
30             s[i]=s[i-1]+y[i];
31             d[i]=d[i-1]+1;
32         }
33         else
34         {
35             s[i]=s[i-1];
36             d[i]=d[i-1];
37         }
38         
39         Y=0;
40         for(int i=1;i<=m;i++)
41          Y+=(s[r[i]]-s[l[i]-1])*(d[r[i]]-d[l[i]-1]);
42         if(change(Y,S)change(Y,S);
43         if(Y>S)mleft=mid+1;
44         else mright=mid;
45     }
46     cout<endl;
47     return 0; 
48 }

描述

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

设共有m个游客，每位游客需要乘车1次从一个景点到达另一个景点，第i位游客在Ti分钟来到景点Ai，希望乘车前往景点Bi（Ai

一个乘客的旅行时间，等于他到达目的地的时刻减去他来到出发地的时刻。因为只有一辆观光车，有时候还要停下来等其他乘客，乘客们纷纷抱怨旅行时间太长了。于是聪明的司机ZZ给公交车安装了k个氮气加速器，每使用一个加速器，可以使其中一个Di减1。对于同一个Di可以重复使用加速器，但是必须保证使用后Di大于等于0。

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

格式

输入格式

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

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

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

输出格式

共一行，包含一个整数，表示最小的总旅行时间。

样例1

样例输入1[复制]

 

3 3 2
1 4
0 1 3
1 1 2
5 2 3

样例输出1[复制]

 

10

限制

1s

提示

样例说明：

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

公交车在第1分钟从1号景点出发，第2分钟到达2号景点，第5分钟从2号景点出发，第7分钟到达3号景点。

第1个旅客旅行时间7 - 0 = 7分钟；
第2个旅客旅行时间2 - 1 = 1分钟；
第3个旅客旅行时间7 - 5 = 2分钟。

总时间7 + 1 + 2 = 10分钟。

数据范围：

对于10%的数据，k = 0；
对于20%的数据，k = 1；
对于40%的数据，2 ≤ n ≤ 50，1 ≤ m ≤ 1,000，0 ≤ k ≤ 20，0 ≤ Di ≤ 10，0 ≤ Ti ≤ 500；
对于60%的数据，1 ≤ n ≤ 100，1 ≤ m ≤ 1,000，0 ≤ k ≤ 100，0 ≤ Di ≤ 100，0 ≤ Ti ≤ 10,000；
对于100%的数据，1 ≤ n ≤ 1,000，1 ≤ m ≤ 10,000，0 ≤ k ≤ 100,000，0 ≤ Di ≤ 100，0 ≤ Ti ≤ 100,000。

贪心，考虑每个人对答案的影响只与下车时间有关，所以选择下车人数最大的段加速

 1 #include
 2 #include
 3 #include
 4 using namespace std;
 5 int n,m,k;
 6 int a[10000],b[10000],t[10000],d[1000];
 7 int weight[1000]={0},arrive[1000]={0},start[1000]={0};
 8 int Max(int a,int b)
 9 {
10     if(a>b)return a;
11     return b;
12 }
13 
14 int main()
15 {
16     cin>>n>>m>>k;
17     for(int i=0;i1;i++)scanf("%d",&d[i]);
18     for(int i=0;i)
19     {
20         scanf("%d%d%d",&t[i],&a[i],&b[i]);
21         weight[b[i]-1]++;
22         start[a[i]-1]=Max(start[a[i]-1],t[i]);
23     }
24     for(int i=1;i)
25      arrive[i]=Max(arrive[i-1],start[i-1])+d[i-1];
26     while(k--)
27     {
28         int max=0,sum=0,mark=-1;
29         for(int j=n-2;j>=0;j--)
30         {
31             if(arrive[j+1]<=start[j+1])sum=0;
32             sum+=weight[j+1];
33             if(d[j]>0&&sum>max)max=sum,mark=j;
34         }
35         if(mark==-1)break;
36         d[mark]--;
37         for(int i=1;i)
38          arrive[i]=Max(arrive[i-1],start[i-1])+d[i-1];
39     }
40     int sum=0;
41     for(int i=1;i)
42      arrive[i]=Max(arrive[i-1],start[i-1])+d[i-1];
43     for(int i=0;i)
44      sum+=arrive[b[i]-1]-t[i];
45     cout<endl;
46     return 0;
47 }