2020牛客NOIP赛前集训营-普及组（第六场）

A 七七七七

分析

由于每次的答案的增长是以指数增长的，所以直接枚举日期的复杂度为 $O(\log n)$ 。那就直接暴力枚举就可以了。总的复杂度为 $O(\log n)$
。

代码

#include<bits/stdc++.h>
using namespace std;
int read() {int x;scanf("%d",&x);return x;}
int main() {
    int n = read();
    int sum = 0;
    for(int i = 1,c = 1;;i = i * 7,c++) {
        sum += i;
        if(sum >= n) {
            cout << c << endl;
            return 0;
        }
    }
}

B 平面旅行

分析

我们可以发现，任意两个节点的距离一定是，不经过中间节点直接到达。所以对于一个节点来说，对答案的贡献为 $\min\{dis(i,i-1),dis(i,P_j)\}$ 其中 $P_j$ 表示特殊节点。总的复杂度为 $O(nm)$ 。

代码

#include<bits/stdc++.h>
using namespace std;
const int N = 5100;
int read() {int x;scanf("%d",&x);return x;}
struct Node{int x,y;}s[N];
int p[N];
int dis(int a,int b) {
    return abs(s[a].x-s[b].x) + abs(s[a].y-s[b].y);
}
int main() {
    int n = read(),m = read();
    for(int i = 1;i <= n;i++) {
        s[i].x = read();s[i].y = read();
    }
    for(int i = 1;i <= m;i++) p[i] = read();
    int ans = 0;
    for(int i = 2;i <= n;i++) {
        int res = dis(i,i-1);
        for(int j = 1;j <= m;j++) res = min(res,dis(i,p[j]));
        ans += res;
    }
    cout << ans << endl;
}

C 小球下落

分析

对于所有球来说，我们并不在意球的标号。只要需要最后占据的是最优答案的那几个节点。我们发现不管怎样我们是想球越低越好的，所以可以开一个桶，桶中保存最大值。那么每次遇到一个 $'o'$ 我们就弹出桶中的最大值。而如果我们发现有 $'x'$ 分开了上下边界，我们就必须把桶情况，由于宽度为 $2$ 。我们可以枚举 $'x'$ 的每种情况。加上堆的复杂度为 $O(n\log n)$ 。

代码

#include<bits/stdc++.h>
using namespace std;
const int N = 310000;
int read() {int x;scanf("%d",&x);return x;}
char ch[N][2];
priority_queue<int> heap;
int n;
void solve() {while(!heap.empty()) heap.pop();}
int main() {
    scanf("%d\n",&n);int ans = 0;
    for(int i = 1;i <= n;i++) scanf("%s",ch[i]);
    ch[n + 1][1] = ch[n + 1][0] = 'x';
    for(int i = n;i >= 1;i--) {
        int x = 0;
        if(ch[i][0] == 'x' && ch[i][1] == 'x') solve();else
        if(ch[i][0] == 'x' && ch[i+1][1] == 'x') solve();else 
        if(ch[i+1][0] == 'x' && ch[i][1] == 'x') solve();
        for(int j = 0;j < 2;j++) if(ch[i][j] != 'x') heap.push(i);
        for(int j = 0;j < 2;j++) {
            if(ch[i][j] == 'o') {
                ans += heap.top() - i;
                heap.pop();
            }
        }
    }
    cout << ans << endl;
    return 0;
}

D 自由世界

分析

类似 $B$ 题的分析，我们的答案仍然为 $\min\{dis(i,i-1),dis(i,P_j)\}$ ，只是 $dis(u,v)$ 现在表示为最短路，而不是直接距离。那么我们跑 $n$ 次最短路就可以了。那么总的复杂度为 $O(nm\log n)$ 。

代码

#include<bits/stdc++.h>
using namespace std;
const int N = 5100;
int read() {int x;scanf("%d",&x);return x;}
#define pii pair<int,int>
vector<pii> G[N];
priority_queue<pii> heap;
int n,p[N],dis1[N],dis2[N],m,k;
void solve(int *dis) {
    static bool vis[N];
    memset(vis,0,sizeof(vis));
    while(!heap.empty()) {
        int x = heap.top().second;heap.pop();
        if(vis[x]) continue;
        vis[x] = 1;
        for(auto e : G[x]) {
            int y = e.first,w = e.second;
            if(dis[y] > dis[x] + w) {
                dis[y] = dis[x] + w;
                heap.push(pii(-dis[y],y));
            }
        }
    }
}
int main() {
    n = read();m = read();k = read();
    for(int i = 1,a,b,c;i <= m;i++) {
        a = read();b = read();c = read();
        G[a].push_back(pii(b,c));G[b].push_back(pii(a,c));
    }
    for(int i = 1;i <= k;i++) p[i] = read();
    memset(dis1,0x3f,sizeof(dis1));
    for(int i = 1;i <= k;i++) {
        dis1[p[i]] = 0;heap.push(pii(0,p[i]));
    }
    solve(dis1);int ans = 0;
    for(int i = 2;i <= n;i++) {
        memset(dis2,0x3f,sizeof(dis2));
        dis2[i - 1] = 0;heap.push(pii(0,i - 1));
        solve(dis2);
        ans += min(dis1[i],dis2[i]);
    }
    cout << ans << endl;
}