BUPT2017 springtraining(15) #3

A.签到题

#include <cstdio>

double a[] = {0.4, 0.16, 0.063, 0.025, 0.010, 0.004};

int main() {

    int n;

    double m;

    scanf("%d", &n);;

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

        scanf("%lf", &m);

        printf("Case #%d: ", i);

        if(m >= ) puts("Too Bright");

        else if(m < 0.004) puts("Invisible");

        else for(int j = ;j < ;j ++) {

            if(m >= a[j]) {

                printf("%d\n", j + );

                break;

            }

        }

    }

    return ;

}

B.很明显的一个做法是我们把 n 个exchange 按 Ri 从小到大排序

对于每个exchage查询获得Ri的最少时间 tim = min( time[Ri] , time[max_money] )

再用 tim + Ti 尝试更新获得Vi需要的最少时间即可

最后ans = min( time[m], time[max_money] )

实现方法则是 sort + 线段树

另外一种奇特的实现方法把线段树换成了树状数组

我们可以看到查询是向后查询，修改是向前修改

而常见的树状数组多为向前查询 i -= lowbit(i)，向后修改 i += lowbit(i)...

所以那个我没有看懂...或者可以倒过来？

但是我们找到了另一种思路，类似于堆优化dijkstra的思路

我们对 n 个 exchange 同上述方法排序

小根堆中元素为 pair (s, time) ，time为关键字

time表示获得 s 的最小时间

显然会有每次堆顶元素中， s 严格单增

然后我们用 last_s < Ri <= now_s 的所有 exchange 尝试进行更新即可

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

struct node {

    int v, r, t;

    bool operator < (const node &a) const {

        return r < a.r;

    }

}a[];

struct Node {

    int s;

    ll tim;

    bool operator < (const Node &a) const {

        return tim > a.tim;

    }

};

int t, n, m;

priority_queue <Node> q;

int main() {

    ios::sync_with_stdio(false);

    ll ans;

    Node tmp;

    cin >> t;

    int i, st;

    for(int p = ;p <= t;p ++) {

        ans = -;

        cin >> n >> m;

        while(!q.empty()) q.pop();

        for(i = ;i <= n;i ++) cin >> a[i].v >> a[i].r >> a[i].t;

        sort(a + , a + n + );

        q.push((Node){, }), st = ;

        while(!q.empty()) {

            tmp = q.top();

            q.pop();

            if(tmp.s >= m) {

                ans = tmp.tim;

                break;

            }

            for(i = st;i <= n;i ++) {

                if(a[i].r > tmp.s) break;

                if(a[i].v <= tmp.s) continue;

                q.push((Node){a[i].v, tmp.tim + a[i].t});

            }

            st = i;

        }

        printf("Case #%d: %lld\n", p, ans);

    }

    return ;

}

C.签到题...看清题，大根堆和小根堆都合法，居然还有左大右小的 bst 也可以...

#include <iostream>

using namespace std;

int n, t, a[];

char s[][] = {"Neither", "Heap", "BST", "Both"};

int is_greater_heap() {

    for(int i = ;i *  <= n;i ++)

        if((i *  +  <= n && a[i *  + ] < a[i]) || a[i * ] < a[i]) return ;

    return ;

}

int is_less_heap() {

    for(int i = ;i *  <= n;i ++)

        if((i *  +  <= n && a[i *  + ] > a[i]) || a[i * ] > a[i]) return ;

    return ;

}

int is_greater_bst() {

    for(int i = ;i *  <= n;i ++)

        if((i *  +  <= n && a[i *  + ] < a[i]) || a[i * ] > a[i]) return ;

    return ;

}

int is_less_bst() {

    for(int i = ;i *  <= n;i ++)

        if((i *  +  <= n && a[i *  + ] > a[i]) || a[i * ] < a[i]) return ;

    return ;

}

int main() {

    ios::sync_with_stdio(false);

    cin >> t;

    for(int i = ;i <= t;i ++) {

        cin >> n;

        for(int j = ;j <= n;j ++) cin >> a[j];

        printf("Case #%d: %s\n", i, s[is_greater_heap() | is_less_heap() | is_greater_bst() | is_less_bst()]);

    }

    return ;

}

F.你就数对各个字母

然后看到前一个的最后 'g' 可以被下一个再用一次就行了

#include <iostream>

using namespace std;

int main() {

    ios::sync_with_stdio(false);

    int t, g, o, d, m, n, r, i, k;

    string s;

    cin >> t, getline(cin, s);

    for(int p = ;p <= t;p ++) {

        getline(cin, s);

        g = o = d = m = n = r = i = k = ;

        for(int j = ;j < s.size();j ++) {

            g += (s[j] == 'g');

            o += (s[j] == 'o');

            d += (s[j] == 'd');

            m += (s[j] == 'm');

            n += (s[j] == 'n');

            r += (s[j] == 'r');

            i += (s[j] == 'i');

            k += (s[j] == ' ');

        }

        printf("Case #%d: %d\n", p, min(min(min(g - , o / ), min(d, m)), min(min(n / , r), min(i, k))));

    }

    return ;

}

K.一个比较直观的东西是

min(A & (~B), A & B)至少能去掉 A 中一半的1对吧...所以很快就能变成0了

看到了比较适合本菜鸡的最良心的题解在这里

#include <cstdio>

typedef unsigned long long uint;

int t, n;

uint a[];

uint min(uint x, uint y){

    return x < y ? x : y;

}

uint dfs(uint k, int i) {

    if(i > n) return k;

    return min(dfs(k & a[i], i + ), dfs(k & (~a[i]), i + ));

}

int main() {

    scanf("%d", &t);

    for(int p = ;p <= t;p ++) {

        scanf("%d", &n);

        for(int i = ;i <= n;i ++)

            scanf("%llu", &a[i]);

        if(n > ) {

            printf("Case #%d: 0\n", p);

            continue;

        }

        printf("Case #%d: %llu\n", p, min(dfs(a[], ), dfs(~a[], )));

    }

    return ;

}

巴特西

BUPT2017 springtraining(15) #3

最新文章

热门文章