竞赛讨论区 > 【官方题解】2020牛客NOIP赛前集训营-普及组（第三场）
头像
0o_love_o0
发布于 2020-10-23 08:00
+ 关注

【官方题解】2020牛客NOIP赛前集训营-普及组（第三场） 精

普及T1

签到题。

反转串后按字符开头 sort，然后相同字符开头的按评分 sort。

或者读入时按字符结尾归类，然后一类的按评分 sort。

查询输出。

注意空间。

写法一：

#include <bits/stdc++.h>
using namespace std;

const int A = 1e5 + 5;
int n, m;
struct node {
  int val, id;
  string x;
  inline void reverse() {
    int len = x.size() - 1;
    for (int i = 0; i <= len / 2; i++) swap(x[i], x[len - i]);
    return;
  }
} a[A];
int w[A];

inline bool cmp1(node u, node v) { return u.x < v.x; }

inline bool cmp2(node u, node v) {
  if (u.val != v.val) return u.val > v.val;
  return u.id < v.id;
}

signed main() {
  cin >> n >> m;
  for (int i = 1; i <= n; i++) {
    cin >> a[i].x >> a[i].val;
    a[i].id = i;
    a[i].reverse();
  }
  sort(a + 1, a + 1 + n, cmp1);
  for (int i = 1; i <= n; i++) {
    w[a[i].x[0] - 'a'] = i;
    if (a[i].x[0] != a[i - 1].x[0]) {
      int pos = i;
      while (a[pos + 1].x[0] == a[pos].x[0]) pos++;
      sort(a + i, a + pos + 1, cmp2);
      i = pos;
    }
  }
  w[26] = n + 1;
  for (int i = 26; ~i; i--)
    if (!w[i]) w[i] = w[i + 1];
  for (int i = 1; i <= n; i++) a[i].reverse();
  while (m--) {
    char x;
    cin >> x;
    int k;
    cin >> k;
    int num = x - 'a';
    if (w[num + 1] - w[num] < k)
      puts("Orz YYR tql");
    else
      cout << a[w[num] + k - 1].x << '\n';
  }
  return 0;
}

写法二：

#include <bits/stdc++.h>
#define ll long long
using namespace std;
int n, m;
struct pr {
  int id, sc;
  string c;
};
vector<pr> a[28];
char s[55];
bool cmp(pr x, pr y) { return x.sc != y.sc ? x.sc > y.sc : x.id < y.id; }
int main() {
  scanf("%d%d", &n, &m);
  for (int x, i = 1; i <= n; ++i) {
    scanf("%s%d", s, &x);
    a[s[strlen(s) - 1] - 'a'].push_back(pr{i, x, s});
  }
  for (int i = 0; i < 26; ++i) sort(a[i].begin(), a[i].end(), cmp);
  int p;
  while (m--) {
    scanf("%s%d", s, &p);
    s[0] -= 'a';
    if (p > a[s[0]].size())
      printf("Orz YYR tql\n");
    else
      cout << (a[s[0]][p - 1].c) << endl;
  }
  return 0;
}

普及T2

首先枚举 ，预处理出每个 的出现次数，然后枚举每个 与 中的数，将贡献相加即可。

时间复杂度 

#include<bits/stdc++.h>
#define int long long
using namespace std;
int Read() {
    int x = 0, f = 1; char ch = getchar();
    while(!isdigit(ch)) {if(ch == '-')  f = -1; ch = getchar();}
    while(isdigit(ch)) {x = (x << 3) + (x << 1) + ch - '0'; ch = getchar();}
    return x * f;
}
int tong[5005], ans;
int gcd(int a, int b) {return (a % b == 0) ? b : gcd(b, a % b);}
signed main() {
    int n = Read();
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= n; j++)
            ++tong[gcd(i, j)];
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= n; j++)
            ans += tong[i] * gcd(i, j);
    cout << ans << endl;
    return 0;
}

普及T3

subtask 1

暴力随便怎么写都可过，这里不详讲。

#include<bits/stdc++.h>
using namespace std;
int Read() {
    int x = 0, f = 1; char ch = getchar();
    while(!isdigit(ch)) {if(ch == '-')  f = -1; ch = getchar();}
    while(isdigit(ch)) {x = (x << 3) + (x << 1) + ch - '0'; ch = getchar();}
    return x * f;
}
int first[1000005], nxt[1000005], to[1000005], tot = 0;
void Add(int x, int y) {
    nxt[++tot] = first[x];
    first[x] = tot;
    to[tot] = y;
}
int n, m, k, l, r, fa[500005], ts[500005], dep[500005], yts[500005], dis[500005];
void dfs(int u, int f) {
    fa[u] = f;  dep[u] = dep[f] + 1;
    for(int e = first[u]; e; e = nxt[e]) {
        int v = to[e];
        if(v == f)  continue;
        dfs(v, u);
    }
}
int getlca(int x, int y) {
    if(dep[x] < dep[y])  swap(x, y);
    while(dep[x] != dep[y])  x = fa[x];
    while(x != y)  x = fa[x], y = fa[y];
    return x;
}
int getdis(int x, int y) {
    return dep[x] + dep[y] - 2 * dep[getlca(x, y)];
}
signed main() {
    freopen("Tree41.in", "r", stdin);
    freopen("Tree41.out", "w", stdout);
    double st = clock();
    memset(dis, 0x7f, sizeof(dis));
    n = Read(), m = Read(), k = Read(), l = Read(), r = Read();
    for(int i = 1; i < n; i++) {
        int x = Read(), y = Read();
        Add(x, y); Add(y, x);
    }
    dfs(1, 0);
    for(int i = 1; i <= m; i++) {
        int x = Read();
        ts[x] = 1;
        for(int j = 1; j <= n; j++)
            dis[j] = min(dis[j], getdis(x, j));
    }
    for(int i = 1; i <= n; i++)
        if(dis[i] >= l && dis[i] <= r && !ts[i])  yts[i] = 1;  
    for(int i = 1; i <= k; i++) {
        int x = Read(), ans = 0;
        for(int i = 1; i <= n; i++) {
            if(ts[i])  ans += getdis(x, i) * getdis(x, i);
            else if(yts[i])  ans += getdis(x, i);
        }
        printf("%d\n", ans);
    }
    double ed = clock();
    cerr << ed - st << endl;
    return 0;
}

subtask 2

观察到上述做法在求 lca 方面还可以优化，使用倍增求 lca 可在 的时间复杂度内通过。

#include<bits/stdc++.h>
using namespace std;
int Read() {
    int x = 0, f = 1; char ch = getchar();
    while(!isdigit(ch)) {if(ch == '-')  f = -1; ch = getchar();}
    while(isdigit(ch)) {x = (x << 3) + (x << 1) + ch - '0'; ch = getchar();}
    return x * f;
}
int first[1000005], nxt[1000005], to[1000005], tot = 0;
void Add(int x, int y) {
    nxt[++tot] = first[x];
    first[x] = tot;
    to[tot] = y;
}
int n, m, k, l, r, ts[500005], dep[500005], yts[500005], dis[500005], fa[500005][21];
void dfs(int u, int f) {
    dep[u] = dep[f] + 1;  fa[u][0] = f;
    for(int i = 1; i <= 20; i++)  fa[u][i] = fa[fa[u][i - 1]][i - 1];
    for(int e = first[u]; e; e = nxt[e]) {
        int v = to[e];
        if(v == f)  continue;
        dfs(v, u);
    }
}
int getlca(int x, int y) {
    if(dep[x] < dep[y])  swap(x, y);
    for(int i = 20; i >= 0; i--)
        if(dep[x] - (1 << i) >= dep[y])  x = fa[x][i];
    if(x == y)  return x;
    for(int i = 20; i >= 0; i--)
        if(fa[x][i] != fa[y][i])  x = fa[x][i], y = fa[y][i];
    return fa[x][0];
}
int getdis(int x, int y) {
    return dep[x] + dep[y] - 2 * dep[getlca(x, y)];
}
signed main() {
    memset(dis, 0x7f, sizeof(dis));
    n = Read(), m = Read(), k = Read(), l = Read(), r = Read();
    for(int i = 1; i < n; i++) {
        int x = Read(), y = Read();
        Add(x, y); Add(y, x);
    }
    dfs(1, 0);
    for(int i = 1; i <= m; i++) {
        int x = Read();
        ts[x] = 1;
        for(int j = 1; j <= n; j++)
            dis[j] = min(dis[j], getdis(x, j));
    }
    for(int i = 1; i <= n; i++)
        if(dis[i] >= l && dis[i] <= r && !ts[i])  yts[i] = 1;  
    for(int i = 1; i <= k; i++) {
        int x = Read(), ans = 0;
        for(int i = 1; i <= n; i++) {
            if(ts[i])  ans += getdis(x, i) * getdis(x, i);
            if(yts[i])  ans += getdis(x, i);
        }
        printf("%d\n", ans);
    }
    return 0;
}

subtask 3

由于数据是一条链，所以可以用线段树在 的复杂度内预处理出所有旪超能力，具体是先标记距离每个点 的点为不可能为旪超能力，所有点标记完后再处理每个超能力周围 的旪超能力，最后 内扫一遍每个点，判断是否为旪超能力。

处理完后对于点 ，如果点 有超能力，那么就对 执行区间加 ，对 执行区间加 ，旪超能力同理，可以用线段树解决。

subtask 4

由于菊花图深度只有 ，所以预处理旪超能力可以暴力。

然后我们对于 与其它点分开处理， 的贡献直接暴力加，对于其它点，我们按照标号顺序建一棵线段树，计算一个点对其它点的影响时，我们判断它是否为 。如果是 的话，我们就对线段树执行整体加 或 ~~（其实还是 ）~~， 如果是其它点的话，我们就将线段树其它点进行区间加 或 ，对于 号点我们直接加 。

subtask 5

我们考虑以每个点为根时的 DP 方程式，我们记 表示 ， 表示 ， 表示 ， 表示子树内超能力个数， 表示子树内旪超能力个数，那么我们有：
$$

直接展开 得
$$
由于每个点都可以为根，所以写一个 DP 就好了。

我们再考虑如何处理旪超能力，由于树的边权均为 ，所以再 bfs 即可，也可以再写一个 DP 来处理旪超能力。

#include<bits/stdc++.h>
#define int long long
using namespace std;
int Read() {
    int x = 0, f = 1; char ch = getchar();
    while(!isdigit(ch)) {if(ch == '-')  f = -1; ch = getchar();}
    while(isdigit(ch)) {x = (x << 3) + (x << 1) + ch - '0'; ch = getchar();}
    return x * f;
}
int first[1000005], nxt[1000005], to[1000005], tot = 0;
void Add(int x, int y) {
    nxt[++tot] = first[x];
    first[x] = tot;
    to[tot] = y;
}
int n, m, k, l, r, dis[500005], ts[500005], yts[500005], vis[500005];
void bfs() {
    queue<int> q;
    for(int i = 1; i <= n; i++)
        if(ts[i])  q.push(i), q.push(0), vis[i] = 1;
    while(!q.empty()) {
        int u = q.front(); q.pop();
        int t = q.front(); q.pop();
        dis[u] = t;
        for(int e = first[u]; e; e = nxt[e]) {
            int v = to[e];
            if(!vis[v]) {
                q.push(v); vis[v] = 1;
                q.push(t + 1);
            }
        }
    }
    for(int i = 1; i <= n; i++)
        if(dis[i] >= l && dis[i] <= r)  yts[i] = 1;
    memset(dis, 0, sizeof(dis));
}
int cnt[500005], ycnt[500005], ydis[500005], dis2[500005], ans[500005];
void dfs1(int u, int fa) {
    cnt[u] = ts[u];  ycnt[u] = yts[u];
    for(int e = first[u]; e; e = nxt[e]) {
        int v = to[e];
        if(v == fa)  continue;
        dfs1(v, u);
        cnt[u] += cnt[v];
        ycnt[u] += ycnt[v];
        dis2[u] += dis2[v] + dis[v] * 2 + cnt[v];
        dis[u] += dis[v] + cnt[v];
        ydis[u] += ydis[v] + ycnt[v];
    }
}
void dfs2(int u, int fa) {
    for(int e = first[u]; e; e = nxt[e]) {
        int v = to[e];
        if(v == fa)  continue;
        if(cnt[u] > cnt[v])  dis2[v] += (dis2[u] - dis2[v] - dis[v] * 2 - cnt[v]) + (dis[u] - dis[v] - cnt[v]) * 2 + (cnt[u] - cnt[v]);
        dis[v] += cnt[u] - cnt[v] + (dis[u] - dis[v] - cnt[v]);
        ydis[v] += ycnt[u] - ycnt[v] + (ydis[u] - ydis[v] - ycnt[v]);
        cnt[v] = cnt[u], ycnt[v] = ycnt[u];
        dfs2(v, u);
    }
}
signed main() {
    n = Read(), m = Read(), k = Read(); l = Read(), r = Read();
    for(int i = 1; i < n; i++) {
        int x = Read(), y = Read();
        Add(x, y); Add(y, x);
    }
    for(int i = 1; i <= m; i++)
        ts[Read()] = 1;
    bfs(); dfs1(1, 0); dfs2(1, 0);
    for(int i = 1; i <= n; i++)  ans[i] = dis2[i] + ydis[i];
    for(int i = 1; i <= k; i++)  printf("%lld\n", ans[Read()]);
    return 0;
}

普及T4

首先勇士只会增加防，于是打每只怪的回合数是不变的。然后又因为在任何时候防都不可能大于怪物的攻，所以每时每刻都一定有伤害，所以1防对每只怪的效果是不变的。效果即是降低伤害，以下称作减伤。

可以这么考虑，最小化受到的伤害，相当于最大化减伤。

定义怪物 的回合数为 ，拿到的蓝宝石数量为 ，定义 为一只怪的性价比，设为 。

首先考虑菊花图的情况：考虑一个最优的打怪序列 ，若交换 和 ，目前减伤的变化为 ，因为交换后的序列一定不更优，

于是有：

移项得：

于是只需要按性价比排序，依次打即可。

然后考虑菊花图加强版的情况：用到了以下一个结论：**如果一只怪a挡在b前面（必须打a才能打b），如果，则打完a后立即打b一定最优。**

证明：假设存在一个最优的打法为：打完a后又打了一连串的怪后才打b，根据前面的证明，所有一定大于，（否则不会在b前面打），又因为，所以所有 ，那这一连串的怪应该在a之前打会更优，矛盾，于是不存在任何怪会在打了之后打，然后打，即打之后会立即打。

于是可以从叶子开始，如果此节点比父节点的性价比高，就将两个节点缩为一个节点（），缩完后整棵树就成了一个以性价比为关键字的大根堆。然后将当前能达到的节点的性价比为关键字放入堆中，依次取出最大的，并更新当前能达到的节点。最终得到的序列即是打怪顺序。

#include<bits/stdc++.h>
#define int long long
using namespace std;
int Read() {
    int x = 0, f = 1; char ch = getchar();
    while(!isdigit(ch)) {if(ch == '-')  f = -1; ch = getchar();}
    while(isdigit(ch)) {x = (x << 3) + (x << 1) + ch - '0'; ch = getchar();}
    return x * f;
}
int first[200005], nxt[200005], to[200005], tot = 0;
void Add(int x, int y) {nxt[++tot] = first[x]; first[x] = tot; to[tot] = y;}
int fa[100005], b[100005], a[100005], d[100005], hh[100005], val[100005], HH[100005], Val[100005], tim[100005];
int vis[100005], sc[100005];
int ffa[500005];
int findfa(int x) {return (ffa[x] == x) ? x : ffa[x] = findfa(ffa[x]);}
void fight(int x) {
    //cout << x << endl;
    b[1] -= (a[x] - d[1]) * hh[x];
    d[1] += val[x];
}
void dfs(int u, int F) {
    fa[u] = F;
    for(int e = first[u]; e; e = nxt[e]) {
        int v = to[e];
        if(v == F)  continue;
        dfs(v, u);
    }
}
vector<int> Nxt[100005];
void Do(int u) {
    fight(u); sc[u] = 1;
    for(int i = 0; i < Nxt[u].size(); i++) {
        Do(Nxt[u][i]);
    }
}
signed main() {
    priority_queue<pair<double, int> > q;
    int n; scanf("%lld", &n);
    for(int i = 1; i < n; i++) {
        int x, y;
        scanf("%lld%lld", &x, &y);
        Add(x, y); Add(y, x);
    }
    dfs(1, 0);
    scanf("%lld%lld%lld", &b[1], &a[1], &d[1]);
    for(int i = 2; i <= n; i++) {
        scanf("%lld%lld%lld%lld", &b[i], &a[i], &d[i], &val[i]);
        hh[i] = b[i] / (a[1] - d[i]);  HH[i] = hh[i]; Val[i] = val[i];
        if(b[i] % (a[1] - d[i]) == 0)  --hh[i], --HH[i];
        q.push(make_pair(1.0 * val[i] / hh[i], i));
    }
    sc[1] = 1;
    for(int i = 1; i <= n; i++)  ffa[i] = i;
    while(!q.empty()) {
        int u = q.top().second; q.pop();
        if(vis[u])  continue;  vis[u] = 1;
        if(sc[fa[u]])  {Do(u); continue;}
        HH[findfa(fa[u])] += HH[u], Val[findfa(fa[u])] += Val[u];
        Nxt[ffa[fa[u]]].push_back(u);
        ffa[u] = ffa[fa[u]];
        q.push(make_pair(1.0 * Val[ffa[fa[u]]] / HH[ffa[fa[u]]], ffa[fa[u]]));
    }
    cout << b[1] << endl;
    return 0;
}
2024最新求职资料大礼包领取
真题
历年笔试真题附答案
图森未来2020校招笔试卷（三）
2018七牛云校招笔试题（卷三）
映客2020春招研发E卷
全部 >
面经
面试常考问题整理
腾讯三面已上岸
22届-国企上岸经验分享
Springboot全套注解解析《看不懂算我输》
全部 >
内推
员工内推码获取
小鹏内推来了！共1000多个岗位！
拼多多核心部门内推实习&校招
【美团】校招社招内推，所有岗位，进度可查，消息必回
全部 >
大家都在关注
校招日程表 笔试日历 ai模拟面试 面试宝典 剑指offer 知识点专项练习

全部评论

(9) 回帖
加载中...
话题 回帖
返回全部帖子

本文相关内容

等你来战

查看全部

热门推荐

牛客竞赛，专业的竞技算法训练平台

扫描二维码，进入QQ群

扫码关注“比赛自动姬”