2019杭电多校1补题笔记

发表于 更新于 分类于 阅读次数：
很久以前存在了draft里面,然后2019年11月11日17:11:37 发出去

D-1004

题目

Vacation

题意

N+1辆车,距离斑马线s,车长l,速度v,按距离斑马线的距离大到小排序，保证s(i) >= s(i+1) + l(i+1),求出s0车头过线的时间

题解

  1. 把第 i 辆车追上第 i + 1 辆车当作一个事件，显然只有 n 个事件，且第 i 辆车追上第i + 1 辆车只可能会对第 i − 1 辆车追上第 i 辆车的时间产生影响，且时间一定是变小，因此可以维护车之间的距离和速度来计算事件发生时间，用堆来找出最早发生的事件，不停处理直到 0 车通过停车线。复杂度为 O(n log n)。
  2. 上述做法比较麻烦，可以直接二分最终时间，然后从第一辆车开始递推求出每辆车的最终位置。复杂度为 O(n log C)，也可以过。
  3. O(N)算法，就是最终通过停止线的时候，一定是一个车后面堵着剩余所有的车，那么影响时间的就只有最前面这辆车，所以对于每一辆车，假设是它是和 0 车堵在一起的最靠前的一辆车，那么可以计算出一个值，所有的车的计算值的最大值就是答案。

详解O(N)

就是你想象比较后面的情况，是后面所有的车被前面某一辆车给堵住了，这辆最前面的车当然没有在过线前被其他的车堵住，不然那堵住它的车就成了真正的最前面的那辆车，所以最后的答案就是最前面的那辆车的(s+l+其后所有的除了0车以外车的长度和)/v . 因为0号车车头过线就是胜利了啊 注意是从后面的车向前面的车进行sum+=,经过了那辆最前面的车之后,其前面的车因为走的快或者离得远所以不会成为堵车队列一员，所以他们这样子叠加起来的时间值并不会超过答案的值

自己手写一遍AC码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include<bits/stdc++.h>
using namespace std;
int n;
struct car{
    int l,s,v;
};

int main(){
    ios::sync_with_stdio(false);
    while(cin>>n){
        vector<car> c(n+1);
        for(int i=0;i<=n;i++) cin>>c[i].l;
        for(int i=0;i<=n;i++) cin>>c[i].s;
        for(int i=0;i<=n;i++) cin>>c[i].v;
        /* 注意使用`1.0*` */
        double sum = 0; double ans = 1.0*c[0].s/c[0].v;
        for(int i=1;i<=n;i++){
            ans = max(ans,(c[i].s+(sum+=c[i].l))/c[i].v);
        }
        cout<<fixed<<setprecision(10)<<ans<<endl;
    }
    return 0;
}

String-1009

题目链接

String

题意

给你一个串，求满足条件的字串，字串(subarray要连续，这里求subsequence时不用连续，但是要保持前后顺序)必须满足一些条件，这些条件是:第i个字母的数量必须在[Li,Ri]区间内

题解

一位位地构造答案字符串，每次贪心地加能加入的最小的字符 (判断能否加入只要判断加入之后原字符串剩下的后缀中的每种字符的数目能否足够满足条件)

自己手写一遍AC码

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
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=1000000007;
const int inf = 0x3f3f3f3f;
const int M = 1e5+7;
string s,ans;
int l[26],r[26],used[26];
int n,k;
/*字母后的各字母后缀和数组*/
int cnt[M][26];
/*字母下标记录数组*/
vector<int> g[26];

int main(){
    ios::sync_with_stdio(false);cin.tie(0);
    while(cin>>s){
        cin>>k;
        for(int i=0;i<26;i++) cin>>l[i]>>r[i];
        /*init*/
        ans.clear();
        memset(used,0,sizeof(used));
        int n = int(s.length());
        for(int i=0;i<26;i++) cnt[n][i]=0,g[i].clear();
        for(int i=n-1;i>=0;i--) for(int j=0;j<26;j++) cnt[i][j]+=cnt[i+1][j]+(s[i]==('a'+j));
        for(int i=0;i<n;i++) g[s[i]-'a'].push_back(i);
        vector<int>::iterator head[26];
        for(int i=0;i<26;i++) head[i]=g[i].begin();
        int last = -1;
        /*solve*/
        for(int i=0;i<k;i++){
            bool f=0;
            for(int j=0;j<26;j++){
                if(used[j] == r[j]) continue;
                /*subsequence时不用连续，但是要保持前后顺序,所以可以共用同一个last*/
                while(head[j]!=g[j].end() && (*head[j]) <= last) head[j]++;
                if(head[j] == g[j].end()) continue;
                used[j]++;
                bool flag = 1;
                int pos = *head[j],sum=0;

                /*注意这里是pos+1,因为现在讨论的是本位已经使用的情况下,对其他位置的影响*/
                for(int p=0;p<26;p++){
                    if(cnt[pos+1][p] + used[p] < l[p]) flag = 0;
                    sum += max(l[p] - used[p],0);
                }
                /*后面的位置的所有字母要达到的最小总和如果超过了能用的量,
                能使用的 位置 不够了
                就说明此位置不能放'a'+j字母*/
                if(sum > k-(i+1)) flag = 0;
                sum = 0;
                for(int p=0;p<26;p++) sum += min(cnt[pos+1][p],r[p]-used[p]);
                /*后面的位置的所有字母最多放的位置个数和如果小于剩余的位置
                能使用的 位置 填不满了
                就说明此位置不能放'a'+j字母*/
                if(sum < k-(i+1)) flag = 0;
                if(!flag) used[j]--;
                else{
                    ans+='a'+j;
                    f = 1;
                    last = pos;
                    break;
                }
            }
            if(!f){
                cout<<"-1"<<endl;
                goto end;
            }
        }
        cout<<ans<<endl;
        end:;
    }

    return 0;
}