2019-08-08 17:47 已编辑苏州大学算法工程师

关注

CCPC-Wannafly Winter Camp Day5 (Div2, onsite)

A. Cactus Draw

Description:

你有一棵树，你想把它画在平面上，使得没有边相交。

Input:

第一行两个整数 $n, m (1 \leq n \leq 1000, 1 \leq m \leq 2000)$ ，表示点数和边数。

接下来 $m$ 行，每行两个正整数 $u, v (1 \leq u, v \leq n, u \neq v)$ ，保证不存在重边。

Output:

输出 $n$ 行，每行两个整数 $x_{i}, y_{i} (1 \leq x_{i}, y_{i} \leq n)$ ，表示将第 $i$ 个点画到 $(x_{i}, y_{i})$ 的位置，要求图中的每对边如果有公共点，那么只能在端点相交，否则不能相交。

如果有多组解，那么输出任意的解即可。

Sample Input:

5 4
1 2
2 3
1 4
1 5

Sample Output:

1 1
2 2
3 3
2 4
2 5

题目链接

显然将树按照层序放置不会相交，所以可以通过dfs或bfs分层防止节点

AC代码:

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

const int maxn = (int)(1e3 + 5);

struct Edge {int V, Next;};

int Tot;
int Head[maxn];
Edge edges[maxn << 1];

void AddEdge(int U, int V) {
	edges[Tot] = (Edge){V, Head[U]};
	Head[U] = Tot++;
	edges[Tot] = (Edge){U, Head[V]};
	Head[V] = Tot++;
}

struct Point {int X, Y;};

int N, M;
int Pos[maxn];
Point Ans[maxn];

void Dfs(int Cur, int Pre, int Depth) {
	Ans[Cur] = (Point){Pos[Depth]++, Depth};
	for (int i = Head[Cur]; ~i; i = edges[i].Next) {
		if (edges[i].V == Pre) continue;
		Dfs(edges[i].V, Cur, Depth + 1);
	}
}


int main(int argc, char *argv[]) {
	scanf("%d%d", &N, &M);
	for (int i = 1; i <= N; ++i) Pos[i] = 1;
	for (int i = 1; i <= N; ++i) Head[i] = -1;
	for (int i = 1, U, V; i <= M; ++i) {
		scanf("%d%d", &U, &V);
		AddEdge(U, V);
	}
	Dfs(1, 0, 1);
	for (int i = 1; i <= N; ++i) printf("%d %d\n", Ans[i].X, Ans[i].Y);
	return 0;
}

D. Doppelblock

Description:

你有一个 $n * n$ 的矩阵，一开始都是空的，你要在其中填入 $1$ 到 $n - 2$ 的数字和字符 $X$ 。

要求每行每列中 $1$ 到 $n - 2$ 中的每个数都恰好出现了一次，并且恰好有两个字符 $X$ 。

同时对于第 $i$ 行，要求两个 $X$ 之间的数字之和为 $r_{i}$ ，第 $i$ 列，要求两个 $X$ 之间的数字之和为 $c_{i}$ 。

Input:

多组数据，第一行一个整数 $T (1 \leq T \leq 50)$ ，表示数据组数。

对于每组数据，第一行一个整数 $n (5 \leq n \leq 7)$ 。

接下来两行，每行 $n$ 个整数，分别表示 $r_{1}, r_{2}, \dots, r_{n}$ 和 $c_{1}, c_{2}, \dots, c_{n}$ 。

Output:

对于每组数据，输出一个 $n$ 个长度为 $n$ 的字符串，表示你填入的数字和字符。

数据之间用一个空行隔开。数据保证存在唯一解。

Sample Input:

2
5
4 3 0 1 0
6 5 0 2 3
7
5 7 3 2 12 3 11
8 6 4 2 9 11 9

Sample Output:

X13X2
3X12X
12XX3
23X1X
XX231

253X41X
4X52X31
142X3X5
X2X4153
3X4152X
51X3X42
X3152X4

题目链接

爆搜所有摆放，对不符合要求的摆放情况（行、列 $X$ 之间之和不等于对应 $r_{i} (c_{i})$ ）进行剪枝

但这样剪枝还会超时，需要继续剪枝优化

考虑行、列 $X$ 之间需要等于相对应的 $r_{i} 或 c_{i}$ 那么 $X$ 之外的部分也应该等于 $\sum_{i = 1}^{n - 2} i - r_{i} (c_{i})$ ，所以也可以对 $X$ 之外大于此数的情况进行剪枝

AC代码:

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

const int maxn = (int)(1e1 + 5);

int T;
int N;
int Map[maxn][maxn];
int R[maxn], C[maxn];
int RPrefix[maxn];
int CPrefix[maxn];
int RXPrefix[maxn];
int CXPrefix[maxn];
int RVis[maxn][maxn];
int CVis[maxn][maxn];
bool Flag;
int All;

void Init() {
    All = 0;
    for (int i = 1; i <= N - 2; ++i) All += i;
    for (int i = 1; i <= N; ++i) RXPrefix[i] = 0;
    for (int i = 1; i <= N; ++i) CXPrefix[i] = 0;
    for (int i = 1; i <= N; ++i) RPrefix[i] = 0;
    for (int i = 1; i <= N; ++i) CPrefix[i] = 0;
    for (int i = 1; i <= N; ++i)
        for (int j = 1; j <= N; ++j)
            Map[i][j] = 0;
}

void Clean(int &X, int &Y, int &Key) {
    if (RVis[X][0] == 2 || RVis[X][0] == 0) RPrefix[X] -= Key;
    else if (RVis[X][0] == 1) RXPrefix[X] -= Key;
    if (CVis[Y][0] == 2 || CVis[Y][0] == 0) CPrefix[Y] -= Key;
    else if (CVis[Y][0] == 1) CXPrefix[Y] -= Key;
    RVis[X][Key]++; CVis[Y][Key]++;
}

void Display() {
    for (int i = 1; i <= N; ++i) {
        for (int j = 1; j <= N; ++j) {
            printf("%c", Map[i][j] == 0 ? 'X' : Map[i][j] + '0');
        }
        printf("\n");
    }
    printf("\n");
}

void Dfs(int X, int Y) {
    if (X == N + 1 && Y == 1) {
        Flag = true;
        return;
    }
    for (int i = 0; i <= N - 2; ++i) {
        if (RVis[X][i] > 0 && CVis[Y][i] > 0) {
            RVis[X][i]--; CVis[Y][i]--;
            Map[X][Y] = i;
            if (RVis[X][0] == 2 || RVis[X][0] == 0) RPrefix[X] += i;
            else if (RVis[X][0] == 1) RXPrefix[X] += i;
            if (CVis[Y][0] == 2 || CVis[Y][0] == 0) CPrefix[Y] += i;
            else if (CVis[Y][0] == 1) CXPrefix[Y] += i;
            if (RPrefix[X] > (All - R[X])) {Clean(X, Y, i); return;}
            if (CPrefix[Y] > (All - C[Y])) {Clean(X, Y, i); return;}
            if (RXPrefix[X] > R[X]) {Clean(X, Y, i); return;}
            else if (i == 0 && RVis[X][0] == 0 && RXPrefix[X] < R[X]) {
                Clean(X, Y, i);
                continue;
            }
            if (CXPrefix[Y] > C[Y]) {Clean(X, Y, i); return;}
            else if (i == 0 && CVis[Y][0] == 0 && CXPrefix[Y] < C[Y]) {
                Clean(X, Y, i);
                continue;
            }
            if (Y == N) Dfs(X + 1, 1);
            else Dfs(X, Y + 1);
            if (Flag) return;
            Clean(X, Y, i);
        }
    }
}

int main(int argc, char *argv[]) {
    scanf("%d", &T);
    for (int Case = 1; Case <= T; ++Case) {
        scanf("%d", &N);
        for (int i = 1; i <= N; ++i) scanf("%d", &R[i]);
        for (int i = 1; i <= N; ++i) scanf("%d", &C[i]);
        Init();
        for (int i = 1; i <= N; ++i) {
            for (int j = 0; j <= N - 2; ++j) {
                if (j == 0) RVis[i][j] = CVis[i][j] = 2;
                else RVis[i][j] = CVis[i][j] = 1;
            }
        }
        Flag = false;
        Dfs(1, 1);
        Display();
    }
    return 0;
}

H. Nested Tree

Description:

你有一棵 $n$ 个点树 $T$ ，然后你把它复制了 $m$ 遍，然后在这 $m$ 棵树之间又加了 $m - 1$ 条边，变成了一棵新的有 $n m$ 个点的树 $T_{2}$ 。

求 $T_{2}$ 中所有点对的距离和，由于答案很大，对 $1 0^{9} + 7$ 取模。

Input:

第一行两个正整数 $n, m (1 \leq n, m \leq 1 0^{3})$ 。

接下来 $n - 1$ 行，每行两个正整数 $u, v (1 \leq u, v \leq n)$ 表示 $T$ 中的一条边。

接下来 $m - 1$ 行，每行四个正整数 $a, b, u, v (1 \leq a, b \leq m, 1 \leq u, v \leq n)$ 表示 $T$ 的第 $a$ 份拷贝中的 $u$ 点与 $T$ 的第 $b$ 份拷贝中的 $v$ 点之间连了一条边。

保证 $T$ 与 $T_{2}$ 都是一棵树。

Output:

输出一行表示答案。

Sample Input:

3 3
1 2
2 3
1 2 2 1
1 3 3 2

Sample Output:

102

题目链接

直接建立一棵有 $n m$ 个节点的树，其每条边的贡献为此树除此边外两部分节点数之积，dfs搜索每个节点子树节点数统计计算即可

AC代码:

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

const int mod = (int)(1e9 + 7);
const int maxn = (int)(1e6 + 5);

struct Edge {
    int V, Next;
};

int Tot;
int Head[maxn];
Edge edges[maxn << 1];

void AddEdge(int U, int V) {
    edges[Tot] = (Edge){V, Head[U]};
    Head[U] = Tot++;
    edges[Tot] = (Edge){U, Head[V]};
    Head[V] = Tot++;
}

int N, M;
long long Dp[maxn];
long long Ans;

long long Dfs(int Cur, int Pre) {
    Dp[Cur] = 1;
    for (int i = Head[Cur]; ~i; i = edges[i].Next) {
        if (edges[i].V == Pre) continue;
        Dp[Cur] += Dfs(edges[i].V, Cur);
        Ans = (Ans + (Dp[edges[i].V] * (N * M - Dp[edges[i].V])) % mod) % mod;
    }
    return Dp[Cur];
}

int main(int argc, char *argv[]) {
    scanf("%d%d", &N, &M);
    Tot = 0;
    for (int i = 1; i <= N * M; ++i) Head[i] = -1;
    for (int i = 1, U, V; i < N; ++i) {
        scanf("%d%d", &U, &V);
        for (int j = 1; j <= M; ++j) AddEdge((j - 1) * N + U, (j - 1) * N + V);
    }
    for (int i = 1, A, B, U, V; i < M; ++i) {
        scanf("%d%d%d%d", &A, &B, &U, &V);
        AddEdge((A - 1) * N + U, (B - 1) * N + V);
    }
    Ans = 0;
    Dfs(1, 0);
    printf("%lld\n", Ans);
    return 0;
}

J. Special Judge

Description:

有一个 $n$ 个点 $m$ 条边的图画在了平面上，你想知道有多少对边之间对应的线段相交。

特别地，对于图中的一对边，如果有公共点且只在对应的端点相交，那么我们不认为这对边相交。

Input:

第一行两个整数 $n, m (1 \leq n \leq 1000, 1 \leq m \leq 2000)$ ，表示点数和边数。

接下来 $m$ 行，每行两个整数 $(u, v)$ 表示一条 $u$ 与 $v$ 之间的无向边，保证图中没有重边和自环。

接下来 $n$ 行，每行两个整数 $x_{i}, y_{i} (0 \leq x_{i}, y_{i} \leq 1 0^{9})$ 表示图中第 $i$ 个顶点的坐标，保证所有的坐标两两不同。

Output:

输出一个整数，表示答案。

Sample Input:

4 6
1 2
1 3
1 4
2 3
2 4
3 4
0 0
0 1
1 1
1 0

Sample Output:

题目链接

线段判断是否规范相交的简单题，这里我写的有些麻烦，其实只用叉积与点积结合判断即可

AC代码:

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

const int maxn = 1e3 + 5;
const long double eps = 1e-8;

struct Edge {
    int U, V;
};

Edge edges[maxn << 1];

int Sgn(double Key) {
    if (fabs(Key) < eps) {
        return 0;
    }
    return Key < 0 ? -1 : 1;
}

struct Point {
    double X, Y;
};

typedef Point Vector;

bool operator == (Point Key1, Point Key2) {
    return Sgn(Key1.X - Key2.X) == 0 && Sgn(Key1.Y - Key2.Y) == 0;
}

Vector operator + (Vector Key1, Vector Key2) {
    return (Vector){Key1.X + Key2.X, Key1.Y + Key2.Y};
}

Vector operator - (Vector Key1, Vector Key2) {
    return (Vector){Key1.X - Key2.X, Key1.Y - Key2.Y};
}

double operator * (Vector Key1, Vector Key2) {
    return Key1.X * Key2.X + Key1.Y * Key2.Y;
}

double operator ^ (Vector Key1, Vector Key2) {
    return Key1.X * Key2.Y - Key1.Y * Key2.X;
}

struct Line {
    Point S, T;
};

typedef Line Segment;

bool IsParallel(Line Key1, Line Key2) {
    return Sgn((Key1.S - Key1.T) ^ (Key2.S - Key2.T)) == 0;
}

bool IsSegInterSeg(Segment Key1, Segment Key2) {
    return
            Sgn(max(Key1.S.X, Key1.T.X) - min(Key2.S.X, Key2.T.X)) >= 0 &&
            Sgn(max(Key2.S.X, Key2.T.X) - min(Key1.S.X, Key1.T.X)) >= 0 &&
            Sgn(max(Key1.S.Y, Key1.T.Y) - min(Key2.S.Y, Key2.T.Y)) >= 0 &&
            Sgn(max(Key2.S.Y, Key2.T.Y) - min(Key1.S.Y, Key1.T.Y)) >= 0 &&
            Sgn((Key2.S - Key1.T) ^ (Key1.S - Key1.T)) * Sgn((Key2.T - Key1.T) ^ (Key1.S - Key1.T)) <= 0 &&
            Sgn((Key1.S - Key2.T) ^ (Key2.S - Key2.T)) * Sgn((Key1.T - Key2.T) ^ (Key2.S - Key2.T)) <= 0;
}

Point Cross(Line Key1, Line Key2) {
    double Temp = ((Key1.S - Key2.S) ^ (Key2.S - Key2.T)) / ((Key1.S - Key1.T) ^ (Key2.S - Key2.T));
    return (Point){Key1.S.X + (Key1.T.X - Key1.S.X) * Temp, Key1.S.Y + (Key1.T.Y - Key1.S.Y) * Temp};
}

int N, M;
Point points[maxn];
long long Cnt;
Vector Vec1, Vec2;

bool Check(Segment Key1, Segment Key2) {
    if (IsParallel(Key1, Key2)) {
        if (Key1.S == Key2.S) {
        }
        else if (Key1.S == Key2.T) {
            swap(Key2.S, Key2.T);
        }
        else if (Key1.T == Key2.S) {
            swap(Key1.S, Key1.T);
        }
        else if (Key1.T == Key2.T) {
            swap(Key1.S, Key1.T);
            swap(Key2.S, Key2.T);
        }
        Vec1 = Key1.T - Key1.S; Vec2 = Key2.T - Key2.S;
        if (Sgn(Vec1.X) == Sgn(Vec2.X) && Sgn(Vec1.Y) == Sgn(Vec2.Y)) {
            return false;
        }
        return true;
    }
    return true;
}

int main(int argc, char *argv[]) {
    scanf("%d%d", &N, &M);
    for (int i = 1, U, V; i <= M; ++i) {
        scanf("%d%d", &U, &V);
        edges[i] = (Edge){U, V};
    }
    for (int i = 1; i <= N; ++i) {
        scanf("%lf%lf", &points[i].X, &points[i].Y);
    }
    for (int i = 1; i <= M; ++i) {
        for (int j = i + 1; j <= M; ++j) {
            if (edges[i].U == edges[j].U || edges[i].U == edges[j].V ||
                edges[i].V == edges[j].U || edges[i].V == edges[j].V) {
                if (Check((Segment){points[edges[i].U], points[edges[i].V]}, (Segment){points[edges[j].U], points[edges[j].V]})) {
                    continue;
                }
            }
            if (IsSegInterSeg((Segment){points[edges[i].U], points[edges[i].V]}, (Segment){points[edges[j].U], points[edges[j].V]})) {
                Cnt++;
            }
        }
    }
    printf("%lld", Cnt);
    return 0;
}