2013-2014 Summer Petrozavodsk Camp, Andrew Stankevich Contest 44 (ASC 44)

发表于 | 更新于 | 阅读次数：
本文字数： 7.7k | 阅读时长 ≈ 7 分钟

暑训最后一场组队训练赛，特么故意的，把别人的WF练习题给我们写，写了半天才签到两题。靠！

B - Braess’s Paradox

Gym - 100518B

题意：有几个点，每个点到下一个点之间有两条路。上面一条路的通过时间是 AK1+B,下面一条通过时间是CK2+D，要两条路通过的时间数尽量相同，K1+K2=1(K1,K2是经过的人流量占总人数的比例)。然后中间的点可以建驿站，如果中间的点不建驿站，就相当于直接从起点到终点，只有两条路，如果建了驿站，就相当于从起点到驿站，再从驿站到终点。

题解：前两个直接算出来就行，一个驿站都不建，就相当于两条路，把所有点上面那条路，ai.bi,加起来就是上面那一条路的A,B，同理，下面一条路就是所有的,ci,di加起来。每个都建就是相当于一个个点走过去，暴力啊，一个点到另一个点的时间，然后全加起来就行了。后面两个就是求最小通过时间的和最大通过时间，看似很难，其实就是一个很简单的DP，N^2的复杂度不会超时。首先预处理从起点到当前点的A,B,C,D。然后每个点的时间就是从前面某一个点建驿站的最小值，最大值转移过来。直接过来上面路的A，B就用两个前缀相减。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
 #include<iostream>
#include<algorithm>
#include<cstring>
#include<string>
#include<vector>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<queue>
#include<map>
#include<set>
#include<stack>
#include<bitset>

using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll,int> P;

#define bug printf("*********\n");
#define debug(x) cout<<"["<<x<<"]" <<endl;
#define mid (l+r)/2
#define chl 2*k+1
#define chr 2*k+2
#define lson l,mid,chl
#define rson mid,r,chr
#define pb push_back
#define mem(a,b) memset(a,b,sizeof(a));

const long long mod=1e9+7;
const int maxn=5e3+5;
const int INF=0x7fffffff;
const int inf=0x3f3f3f3f;
const double eps=1e-8;
int n;
int a[maxn],b[maxn],c[maxn],d[maxn];
double qza[maxn],qzb[maxn],qzc[maxn],qzd[maxn];
double dp1[maxn],dp2[maxn];
double ans1,ans2,ans3,ans4;
int main() {
    freopen("braess.in","r",stdin);
    freopen("braess.out","w",stdout);
    scanf("%d",&n);
    for(int i=1; i<=n; i++) {
        scanf("%d%d%d%d",&a[i],&b[i],&c[i],&d[i]);
    }
    double A=0,B=0,C=0,D=0;
    for(int i=1; i<=n; i++) {       //第一种结果都不建，A相当于所有点之间的a[i]相加
        A+=a[i];
        B+=b[i];
        C+=c[i];
        D+=d[i];
    }
    double k;
    if(A+C!=0) {                    
        k=min(1.0,(D+C-B)/(A+C));//k1最大值不能超过1 
        ans1=k*A+B;
        if(k<=0) {              //k1最小值不能小于0，如果小于等于0说明所有人都走下面一条路
            ans1=C+D;
        }
    } else {
        ans1=min(B,D);          //如果AC都等于零，那就直接判断B，D大小
    }
    ans2=0;
    for(int i=1; i<=n; i++) {
        A=a[i];                 //所有的点一个个算
        B=b[i];
        C=c[i];
        D=d[i];
        double temp;
        if(A+C!=0) {
            k=min(1.0,(D+C-B)/(A+C));
            temp=k*A+B;
            if(k<=0) {
                temp=C+D;
            }
        } else {
            temp=min(B,D);
        }
        ans2+=temp;
    }
    for(int i=1; i<=n; i++) {           //求前缀
            qza[i]=qza[i-1]+a[i];
            qzb[i]=qzb[i-1]+b[i];       
            qzc[i]=qzc[i-1]+c[i];
            qzd[i]=qzd[i-1]+d[i];
        dp1[i]=inf;
    }
    dp1[0]=0;
    for(int i=1; i<=n; i++) {
        for(int j=0; j<i; j++) {
            A=qza[i]-qza[j];
            B=qzb[i]-qzb[j];            //ABCD等于上一个状态和当前状态的差值，
            C=qzc[i]-qzc[j];
            D=qzd[i]-qzd[j];
            double temp;
            if(A+C!=0) {
                k=min(1.0,(D+C-B)/(A+C));
                temp=k*A+B;
                if(k<=0) {
                    temp=C+D;
                }
            } else {
                temp=min(B,D);
            }
            dp1[i]=min(dp1[i],dp1[j]+temp);     //dp1保留最小值，从j驿站转移到i驿站的最小值
            dp2[i]=max(dp2[i],dp2[j]+temp);     //最大值
        }
    }
    ans3=dp1[n];
    ans4=dp2[n];
    printf("%.10f\n%.10f\n%.10f\n%.10f\n",ans1,ans2,ans3,ans4);

    return 0;
}

I - Intelligent Tourist

Gym - 100518I

题意：有N场考试，第i考试需要复习pi天，考试时间是di，考试的时间没法复习，如果没有复习多天那场考试就不会去，就会去复习其他考试，中间有些天有活动，活动时间是s-t活动时间不会去复习，问最多能通过机场考试。

题解：贪心，这题贼他妈傻逼，漏看了一个条件，DEBUG一个小时。。。，从后面往前面扫，每次选需要复习时间最少的一场考试，因为这个时间只能给后面的所以不用担心选的考试时间已经过了，至于考试时间不能复习，你直接把考试也当作复习的时间，不去考试就相当于少复习这种科目一天，去了就相当于多复习一天。。。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
 #include<iostream>
#include<algorithm>
#include<cstring>
#include<string>
#include<vector>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<queue>
#include<map>
#include<set>
#include<stack>
#include<bitset>

using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll,int> P;

#define bug printf("*********\n");
#define debug(x) cout<<"["<<x<<"]" <<endl;
#define mid (l+r)/2
#define chl 2*k+1
#define chr 2*k+2
#define lson l,mid,chl
#define rson mid,r,chr
#define pb push_back
#define mem(a,b) memset(a,b,sizeof(a));

const long long mod=1e9+7;
const int maxn=1e5+5;
const int INF=0x7fffffff;
const int inf=0x3f3f3f3f;
const double eps=1e-8;
int n,m;
struct one {
    ll d,p;
    int id;
    bool operator<(const one a)const {
        return d<a.d;
    }
} X;
struct two {
    ll st,en;
    bool operator<(const two a)const {
        return st<a.st;
    }
} H;
priority_queue<one> q1;
priority_queue<two> q2;
priority_queue<P,vector<P>,greater<P> >q;

int main() {
    freopen("intelligent.in","r",stdin);
    freopen("intelligent.out","w",stdout);
    while(~scanf("%d",&n)&&n) {
        vector<int> v;
        for(int i=0; i<n; i++) {
            scanf("%I64d%I64d",&X.d,&X.p);
            X.p++;
            X.id=i+1;
            q1.push(X);
        }
        scanf("%d",&m);
        for(int i=0; i<m; i++) {
            scanf("%I64d%I64d",&H.st,&H.en);
            q2.push(H);
        }

        while(q2.size()) {
            if(q2.top().st>q1.top().d) {
                q2.pop();
            } else break;
        }
        while(q1.size()) {
            X=q1.top();
            q1.pop();
            ll temp;
            if(q1.size()==0)temp=0;
            else temp=q1.top().d;
            ll tim=0;
            tim=X.d-temp;
            while(q2.size()) {
                H=q2.top();
                if(H.st>temp) {
                    q2.pop();
                    tim-=H.en-H.st+1;
                } else break;
            }

            if(X.p==0) {
                v.push_back(X.id);
            } else q.push(P(X.p,X.id));

            while(tim>0&&q.size()) {
                P temp2=q.top();
                q.pop();
                if(tim>=temp2.first) {
                    tim-=temp2.first;
                    v.push_back(temp2.second);
                } else {
                    temp2.first-=tim;
                    tim=0;
                    q.push(temp2);
                }
            }
        }
        while(q1.size())q1.pop();
        while(q2.size())q2.pop();
        while(q.size())q.pop();
        sort(v.begin(),v.end());
        int ans=v.size();
        printf("%d\n",ans);
        for(int i=0; i<ans; i++) {
            printf("%d",v[i]);
            if(ans==i+1)printf("\n");
            else printf(" ");
        }
        if(ans==0)puts("");
    }
    return 0;
}