C2020 2020.12.26模拟赛

信息学——模拟赛

考试情况

期望得分：

实际得分：

T1 Prob1

$1^o$ 分析

看着感觉像个树型DP，后来发现贪心算一遍就好了。

对于当前节点$x$（当前节点只有1个病毒），计算他有多少个儿子，然后做倍增操作，直到病毒树大于儿子数。

然后给每个儿子送一个病毒，递归操作即可。

正确性：

//The code is from dawn_sdy
#include<bits/stdc++.h>
using namespace std;
inline int read() {
    int x = 0;
    char c = getchar();
    bool f = 0;
    while(!isdigit(c)) f |= (c == '-'), c = getchar();
    while(isdigit(c)) x = (x * 10) + (c ^ 48), c = getchar();
    return f ? -x : x;
}
const int maxn = 1e5 + 5;
int n;
struct node {
    int v, nex;
}edge[maxn << 1];
int head[maxn], len, ans;
inline void make_map(int u, int v) {
    len++; edge[len].nex = head[u]; edge[len].v = v; head[u] = len;
}
inline void Search(int x, int fa) {
    int sum = 0, cnt = 1;
    for(register int i = head[x]; i; i = edge[i].nex) {
        int y = edge[i].v;
        if(y == fa) continue;
        sum++;
    } 
    while(cnt <= sum) cnt <<= 1, ans++;
    for(register int i = head[x]; i; i = edge[i].nex) {
        int y = edge[i].v;
        if(y == fa) continue;
        ans++, Search(y, x);
    }
}
int main() {
//  freopen("prob1.in", "r", stdin);
//  freopen("prob1.out", "w", stdout);
    n = read();
    for(register int i = 1; i < n; ++i) {
        int u = read(), v = read(); make_map(u, v), make_map(v, u);
    }
    Search(1, 0); printf("%d", ans);
    return 0;
}

T2 Prob2

$1^o$ 分析

考场上想的算法其实是对的，打shi了。

显然，为了方便，我们让矩阵的端点由已知点确定（换句话说就是左下端点，右上端点一定是已知点）

这个时候子集的数量就是矩阵的数量，所以我们只要考虑能构造出多少矩阵就好了。

先将所有点按 $y$ 为第一关键字，$x$ 为第二关键字排序。

那么，我们可以枚举出矩阵限制 $y$ 坐标的两点，记为 $a$ 与 $b$ ，然后以端点为这两点的矩形往左右拓展。（类似于扫描线）

设在 $a$ 之上的点有 $x$ 个，在 $b$ 之下的点有 $y$ 个（ $a$ 在 $b$ 之上）

则贡献为 $x * y$。

考虑 $x$ 与 $y$ 如何求出，考场上写的是树状数组，后来发现一遍二位前缀和预处理即可。

注意空集的情况！！！

//The code is from dawn_sdy
#include<bits/stdc++.h>
#define int long long
using namespace std;
inline int read() {
    int x = 0;
    char c = getchar();
    bool f = 0;
    while (!isdigit(c)) f |= (c == '-'), c = getchar();
    while (isdigit(c)) x = (x * 10) + (c ^ 48), c = getchar();
    return f ? -x : x;
}
const int maxn = 2505;
int n;
struct Point{
    int x, y;
}point[maxn];
int lsx[maxn], lsy[maxn], sum[maxn][maxn], ans;
inline bool operator <(Point a, Point b){ return a.y != b.y ? a.y < b.y : a.x < b.x;  }
inline int Calc(int x1, int y1, int x2, int y2) { return sum[x2][y2] - sum[x2][y1 - 1] - sum[x1 - 1][y2] + sum[x1 - 1][y1 - 1]; }
signed main(){
//    freopen("prob2.in","r",stdin);
//    freopen("prob2.out","w",stdout);
    n = read();
    for(register int i = 1; i <= n; ++i) lsx[i] = point[i].x = read(), lsy[i] = point[i].y = read();
    sort(lsx + 1, lsx + n + 1), sort(lsy + 1, lsy + n + 1);
    for(register int i = 1; i <= n; ++i) {
        point[i].x = lower_bound(lsx + 1, lsx + n + 1, point[i].x) - lsx;
        point[i].y = lower_bound(lsy + 1, lsy + n + 1, point[i].y) - lsy;
        sum[point[i].x][point[i].y] = 1;
    }
    for(register int i = 1; i <= n; ++i) 
        for(register int j = 1; j <= n; ++j) {
            sum[i][j] += sum[i - 1][j] + sum[i][j - 1] - sum[i - 1][j - 1];
        }
    sort(point + 1, point + n + 1);
    for(register int i = 1; i <= n; ++i)
        for(register int j = i; j <= n; ++j) {
            int minn = min(point[i].x, point[j].x), maxx = max(point[i].x, point[j].x);
            ans += Calc(1, point[i].y, minn, point[j].y) * Calc(maxx, point[i].y, n, point[j].y);
        }
    printf("%lld", ans + 1);
    return 0;
}

T3 Prob3

$1^o$ 分析

由于只有 $N,E$ 两个方向，所以只有 $N$ 的奶牛与 $E$ 的奶牛会互相相撞。

把每个奶牛的路径看成一条射线，容易求出所有的交点。

但还有两个问题。

$\text{First}$，由于每个奶牛被阻碍后就会停下，所以有可能我们会多算一些交点。

考虑开一个标记数组，标记已经相遇过的线。

但是我们不知道相遇形成的顺序。

但由于只有 $N,E$ 方向的线，所以相遇的顺序一定是按坐标从左下到右上的。

即我们按照$x$为第一关键字，$y$为第二关键字，给交点排序即可。

$\text{Second}$，我们要知道两头奶牛相撞到底是哪头撞的哪头。

这个很简单，算一下走的距离，比较一下就好。

那最后的答案如何算？

考虑由于传递性的存在，设奶牛$x$阻碍了奶牛$y$，可得：

//The code is from dawn_sdy
#include<bits/stdc++.h>
using namespace std;
inline int read() {
    int x = 0;
    char c = getchar();
    bool f = 0;
    while (!isdigit(c)) f |= (c == '-'), c = getchar();
    while (isdigit(c)) x = (x * 10) + (c ^ 48), c = getchar();
    return f ? -x : x;
}
const int maxn = 1005;
int n, lenN, lenE, lenP, Ans[maxn];
bool Vst[maxn];
struct Point {
    int id, x, y;
    inline void Add(int id0, int x0, int y0) { id = id0, x = x0, y = y0;  }
}North[maxn], East[maxn], Cow[maxn];
inline bool operator <(Point a, Point b) { return a.x > b.x && a.y < b.y; }
struct node {
    int x, y, idx, idy;
    inline void Add(int x0, int y0, int idx0, int idy0) { x = x0, y = y0, idx = idx0, idy = idy0; }
}Point[maxn * maxn];
inline bool operator <(node a, node b){ return a.x != b.x ? a.x < b.x : a.y < b.y; }
int main(){
 //   freopen("prob3.in","r",stdin);
//    freopen("prob3.out","w",stdout);
    n = read();
    char c;
    for(register int i = 1; i <= n; ++i) {
        while(!isalpha(c =  getchar()));
        int x = read(), y = read(); Cow[i].Add(i, x, y);
        if(c == 'N') North[++lenN].Add(i, x, y);
        else East[++lenE].Add(i, x, y);
    }
    for(register int i = 1; i <= lenN; ++i)
        for(register int j = 1; j <= lenE; ++j)
            if(North[i].x > East[j].x && North[i].y < East[j].y) Point[++lenP].Add(North[i].x, East[j].y, East[j].id, North[i].id);
    sort(Point + 1, Point + lenP + 1);
    for(register int i = 1; i <= lenP; ++i) {
        if(Vst[Point[i].idx]||Vst[Point[i].idy]) continue;
        int Disx = Point[i].x - Cow[Point[i].idx].x, Disy = Point[i].y - Cow[Point[i].idy].y;
        if(Disx < Disy) Vst[Point[i].idy] = 1, Ans[Point[i].idx] += (Ans[Point[i].idy] + 1);
        if(Disy < Disx) Vst[Point[i].idx] = 1, Ans[Point[i].idy] += (Ans[Point[i].idx] + 1);
    }
    for(register int i = 1; i <= n; ++i) printf("%d\n", Ans[i]);
    return 0;
}