noip2011day2

P1313 计算系数

题目描述

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

输入输出格式

输入格式：

输入文件名为factor.in。

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

输出格式：

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

输入输出样例

输入样例#1：

1 1 3 1 2

输出样例#1：

说明

【数据范围】

对于30% 的数据，有 0 ≤k ≤10 ；

对于50% 的数据，有 a = 1，b = 1；

对于100%的数据，有 0 ≤k ≤1,000，0≤n, m ≤k ，且n + m = k ，0 ≤a ，b ≤1,000,000。

noip2011提高组day2第1题

题解：二项式定理

#include <bits/stdc++.h>

using namespace std;
const int M = 10007;
const int maxn = 1005;
#define ll long long
ll fac[1005];
ll mul(ll a, ll b){
    ll rt = 1;
    for( ; b; b>>=1, a=(a*a)%M)
        if(b & 1)rt = (rt*a)%M;
    return rt;
}
ll exgcd(ll a, ll b, ll &x, ll &y){
    if(!b){
        x = 1;
        y = 0;
        return a;
    }
    ll x0, y0;
    ll d = exgcd(b, a%b, x0, y0);
    x = y0;
    y = x0 - (a/b)*y0;
    return d;
}
ll inv(ll a){
    ll x, y;
    ll d = exgcd(a, M, x, y);
    if(d != 1)return -1;
    return (x%M + M)%M; 
}
int main()
{
    //freopen("factor.in","r",stdin);
    //freopen("factor.out","w",stdout);
    ll a,b,k,n,m;
    cin>>a>>b>>k>>n>>m;
    fac[0] = 1;
    for(int i = 1; i <= k; i++)fac[i] = fac[i-1] * i % M;
    ll A = mul(a, n);
    ll B = mul(b, m);
    ll q = inv(fac[n]), p = inv(fac[m]);
    cout<<(fac[k]* q % M * p % M *(A * B) % M ) % M<<endl;
    return 0;
}

View Code

#include <bits/stdc++.h>

using namespace std;
const int M = 10007;
const int maxn = 1005;
#define ll long long
ll comb[maxn][maxn];
void init(ll k){
    for(int i = 0; i <= (int)k; i++)
        for(int j = 0; j <= i; j++)
            if(!j || j == i)comb[i][j] = 1;
            else comb[i][j] = (comb[i-1][j] + comb[i-1][j-1]) % M;
}
ll mul(ll a, ll b){
    ll rt = 1;
    for( ; b; b>>=1, a=(a*a)%M)
        if(b & 1)rt = (rt*a)%M;
    return rt;
}
int main()
{
    //freopen("factor.in","r",stdin);
    //freopen("factor.out","w",stdout);
    ll a,b,k,n,m;
    cin>>a>>b>>k>>n>>m;
    init(k);
    ll A = mul(a, n);
    ll B = mul(b, m);
    cout<<(comb[k][n] * A * B)%M<<endl;
    return 0;
}

View Code

P1314 聪明的质监员

题目描述

小T 是一名质量监督员，最近负责检验一批矿产的质量。这批矿产共有 n 个矿石，从 1到n 逐一编号，每个矿石都有自己的重量 wi 以及价值vi 。检验矿产的流程是：

1 、给定m 个区间[Li,Ri]；

2 、选出一个参数 W；

3 、对于一个区间[Li,Ri]，计算矿石在这个区间上的检验值Yi：

这批矿产的检验结果Y 为各个区间的检验值之和。即：Y1+Y2...+Ym

若这批矿产的检验结果与所给标准值S 相差太多，就需要再去检验另一批矿产。小T

不想费时间去检验另一批矿产，所以他想通过调整参数W 的值，让检验结果尽可能的靠近

标准值S，即使得S-Y 的绝对值最小。请你帮忙求出这个最小值。

输入输出格式

输入格式：

输入文件qc.in 。

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

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

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

输出格式：

输出文件名为qc.out。

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

输入输出样例

输入样例#1：

输出样例#1：

说明

【输入输出样例说明】

当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 。

题解：二分+前缀数组，非动态的就不要老搞线段树

#include <bits/stdc++.h>

using namespace std;
#define ll long long
#define For(a,b,c) for(int a=b;a<=c;a++)
const int maxn = 200005;
ll w[maxn],v[maxn],sum[maxn];
int n,m,cnt[maxn];
struct Q{int l,r;}q[maxn];
inline ll mymax(ll a,ll b){return a > b ? a : b; }
ll check(int k){
    ll ans = 0;
    cnt[0] = sum[0] = 0;
    For(i, 1, n)
        if(w[i] >= k)sum[i] = sum[i-1]+v[i], cnt[i]=cnt[i-1]+1;
        else sum[i] = sum[i-1], cnt[i] = cnt[i-1];
    For(i, 1, m){
        int l = q[i].l, r = q[i].r;
        ans += 1LL*(cnt[r]-cnt[l-1]) * (sum[r]-sum[l-1]);
    }
    return ans;
}

inline void read(ll &x){
    ll f=1;x=0;char s=getchar();
    while(s<'0'||s>'9'){if(s=='-')f=-1;s=getchar();}
    while(s>='0'&&s<='9'){x=x*10+s-'0';s=getchar();}
    x*=f;
}
int main()
{
   // freopen("qc.in","r",stdin);
    //freopen("qc.out","w",stdout);
    ll S, L = 0, R = 0, an1=-1,an2=-1;
    scanf("%d%d",&n,&m);
    read(S);
    For(i, 1, n)read(w[i]),read(v[i]), R = mymax(R, w[i]);
    For(i, 1, m)scanf("%d%d",&q[i].l,&q[i].r);
    while(L <= R){
        ll M = (L + R) >> 1;
        ll ans = check(M);
        if(ans > S) an1 = ans, L = M + 1;
        else an2 = ans, R = M - 1;
        //cout<<an1<<" "<<an2<<" "<<M<<" "<<L<<" "<<R<<endl;
    }
    ll qq = min(abs(an1 - S), abs(an2 - S));
    printf("%lld
",qq);
    return 0;
}

View Code

P1315 观光公交

题目描述

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

设共有m 个游客，每位游客需要乘车1 次从一个景点到达另一个景点，第i 位游客在Ti 分钟来到景点 Ai ，希望乘车前往景点Bi （Ai<Bi ）。为了使所有乘客都能顺利到达目的地，公交车在每站都必须等待需要从该景点出发的所有乘客都上车后才能出发开往下一景点。

假设乘客上下车不需要时间。

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

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

输入输出格式

输入格式：

输入文件名为bus.in。

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

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

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

输出格式：

输出文件名为bus.out。共一行，包含一个整数，表示最小的总旅行时间。

输入输出样例

输入样例#1：

输出样例#1：

说明

【输入输出样例说明】

对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 ≤ T i ≤ 500；

对于60% 的数据，1 ≤ n ≤ 100，1 ≤ m ≤ 1,000，0 ≤ k ≤ 100 ，0 ≤ Di ≤ 100，0 ≤ T i ≤ 10,000 ；

对于100%的数据，1 ≤ n ≤ 1,000，1 ≤ m ≤ 10,000 ，0 ≤ k ≤ 100,000，0 ≤ Di ≤ 100 ，0 ≤ T i ≤ 100,000。

noip2011提高组day2第3题

题解：贪心，开几个数组arrive[i]表示到第i个站的时间， las[i]表示i站最后到的一个人，nxt[i]表示从第i站出发到那个点之前都满足arrive[i] > las[i], sum[i]表示到i站下车的人及之前的和；

最开始想到同一个贡献应该尽量人多，但有一个问题加速以后到下一站又要等人，所以加速要满足arrive[i] > las[i]，满足条件的一段都可以加速；

每次能减则减，每加速一次动态修改又跑（思考为什么最优）

#include <bits/stdc++.h>

using namespace std;
#define For(a,b,c) for(int a=b;a<=c;a++)
const int inf = 1000000008, maxn = 1005, maxm = 10005;

int d[maxn], las[maxn], sum[maxn], nxt[maxn], cnt[maxn], arrive[maxn];
struct person{int t,st,ed;}p[maxm];
int main()
{
    //freopen("bus.in","r",stdin);
    //freopen("bus.out","w",stdout);
    int n,m,k,ans = 0;
    scanf("%d%d%d",&n,&m,&k);
    For(i, 1, n-1)scanf("%d",&d[i]);
    For(i, 1, m){
        scanf("%d%d%d",&p[i].t,&p[i].st,&p[i].ed);
        sum[p[i].ed]++;
        las[p[i].st] = max(las[p[i].st], p[i].t);
    }
    For(i, 2, n)sum[i] += sum[i-1];

    while(1){
        int best = 1;

        For(i, 2, n)arrive[i] = max(arrive[i-1],las[i-1]) + d[i-1];

        nxt[n] = n;
        for(int i = n-1; i >= 1; i--){
            nxt[i] = nxt[i+1];
            if(arrive[i+1] <= las[i+1])nxt[i] = i + 1;
        }
        while(best<=n-1 && !d[best])best++;
        if(best == n || !k)break;

        For(i, best+1, n-1)
            if(d[i] && sum[nxt[i]]-sum[i] > sum[nxt[best]]-sum[best])
                best = i;
        if(sum[nxt[best]] - sum[best] == 0)break;
        int dd = inf;
        For(i, best+1, nxt[best]-1) dd = min(dd, arrive[i]-las[i]);
        dd = min(dd, k);
        dd = min(dd, d[best]);
        k -= dd;
        d[best] -= dd;
    }

    For(i, 1, m)ans += (arrive[p[i].ed] - p[i].t);
    printf("%d
",ans);
    return 0;
}

View Code