# D

# 题目大意

有一个无限大的二维网格，在坐标 $(0,0)$ 处有一堆篝火。
在时间 $t=0$ ，只有单元格 $(0,0)$ 存在烟雾。
给你一个长度为 $N$ 的字符串 $S$ ，由 "N"、"W"、"S"、"E" 组成。在 $t=1,2,\dots,N$ 时刻，会依次发生以下情况：

风吹起，当时存在的所有烟雾按如下方式移动：
- 如果 $S$ 的 $t-th$ 字符是 N ，则 $(r,c)$ 单元格中的烟雾会移动到 $(r-1,c)$ 单元格。
- 如果是 W ， $(r,c)$ 单元格中的烟雾会移动到 $(r,c-1)$ 单元格。
- 如果是 S ， $(r,c)$ 单元格中的烟雾会移动到 $(r+1,c)$ 单元格。
- 如果是 E ，则 $(r,c)$ 单元格中的烟雾会移动到 $(r,c+1)$ 单元格。
如果 $(0,0)$ 单元格中没有烟雾，则会在 $(0,0)$ 单元格中产生新的烟雾。
高桥站在 $(R,C)$ 单元格。对于每个整数 $1 \le t \le N$ ，判断 $(R,C)$ 单元格在 $t+0.5$ 时间是否存在烟雾，并按照要求的格式打印回复。

# 数据范围

$N$ 是介于 $1$ 和 $200000$ （含）之间的整数。
$S$ 是长度为 $N$ 的字符串，由 N 、 W 、 S 、 E 组成。
$R$ 和 $C$ 是介于 $-N$ 和 $N$ （含）之间的整数。
$(R,C) \neq (0,0)$

# 题解

这题很典，如果正向考虑的话，每次都需要移动很多很多烟的位置，考虑到题目数据范围，显然这样会直接 $T$ 了
对于这种变化很多容易 $T$ 的题目，通常应该转换一下思维，在题目众多变量中，找不变的量或者变化较少容易计算的量
对于这题，为什么我们不考虑，对篝火和人的移动进行分析呢？
如果风往一个方向吹，那不妨转换成篝火在原地留下一个烟雾，并且人和篝火往相反的方向走

C++

int n, x, y, ghx = 0, ghy = 0;
map<PII, int> cnt;
map<char, int> mp = {
    {'N', 1}, {'S', 2}, {'E', 3}, {'W', 4}
};
int dx[] = {0, 1, -1, 0, 0};
int dy[] = {0, 0, 0, -1, 1}; 

void solve() {
    cin >> n >> x >> y;
    for (int i = 1; i <= n; i++) {
        char dir;
        cin >> dir;
        int direction = mp[dir];
        
        cnt[{ghx, ghy}] = 1;
        
        x += dx[direction], y += dy[direction]; 
        ghx += dx[direction], ghy += dy[direction];
        
        if (cnt[{x, y}] == 1)
            cout << 1;
        else
            cout << 0;
    }
}

# E

# 题目大意

这个问题是一个交互式问题 (在这个问题中，你的程序和法官系统通过输入和输出进行交流)。
给你一棵树 $G$ ，其中有 $N$ 个顶点，编号为 $1$ 至 $N$ 。第 $i$ 条边连接着顶点 $U_i$ 和 $V_i$ .
你们将用这棵树 $G$ 和高桥玩一个游戏。首先，你们决定谁是第一名，谁是第二名。然后，从第一位玩家开始，轮流进行以下操作：

选择一对满足以下两个条件的整数 $(i,j)$ $(i, j)$ 和 $1 \le i < j \le N$ $1 \leq i < j \leq N$ ，然后添加一条连接顶点 $i$ $i$ 和 $j$ $j$ 到 $G$ $G$ 的边。
- $G$ 没有连接顶点 $i$ 和 $j$ 的边。
- 添加一条连接顶点 $i$ 和 $j$ 的边不会产生奇循环。
  无法进行这一操作的棋手输棋，而另一方棋手赢棋。请与高桥先生下这盘棋并获胜。

什么是奇数循环？
当且仅当满足以下所有条件时， $G$ 的顶点 $(v_0,v_1,...,v_k)$ 序列才称为奇数循环：

$k$ 是奇数。
$v_0 = v_k$ .
每一个 $1\leq i \leq k$ 都有一条边连接 $v_{i-1}$ 和 $v_{i}$ .

# 数据范围

$2 \leq N \leq 100$
$1 \le U_i < V_i \le N$
The given graph is a tree.
All input values are integers.

# 题解

这题本质是一个二分图问题，最后的图会是一个二分图
只需要先染色，然后对于 $1$ 和 $2$ 的点分别进行两两组合，组合后，去掉已经有的边
把没有的边存 $set$ 里，如果是奇数条，就先手，否则后手

注意，这题是交互题，不能关同步流，而且输出换行得用 $endl$ ，不然会全部超时

C++

int n, u, v;
vector<int> g[110];
int color[110];
set<PII> vis, ans;

bool dfs(int u, int c) {
    color[u] = c;

    for (auto t : g[u]) {
        if (color[t] == 0 && !dfs(t, 3 - c))
            return false;

        if (color[t] == c)
            return false;
    }

    return true;
}

void solve() {
    cin >> n;

    for (int i = 1; i <= n - 1; i++) {
        cin >> u >> v;
        g[u].push_back(v), g[v].push_back(u);

        if (u > v)
            swap(u, v);

        vis.insert({ u, v });
    }

    for (int i = 1; i <= n; i++)
        if (color[i] == 0)
            dfs(i, 1);

    vector<int> col1, col2;

    for (int i = 1; i <= n; i++) {
        if (color[i] == 1)
            col1.push_back(i);
        else
            col2.push_back(i);
    }

    for (int i = 0; i < col1.size(); i++)
        for (int j = 0; j < col2.size(); j++) {
            int a = min(col1[i], col2[j]), b = max(col1[i], col2[j]);

            if (vis.find({ a, b }) == vis.end())
                ans.insert({ a, b });
        }

    if (ans.size() & 1) {
        cout << "First" << endl;
        cout << (*ans.begin()).first << " " << (*ans.begin()).second << endl;
        ans.erase(ans.begin());
    }
    else
        cout << "Second" << endl;

    int x, y;
    while (cin >> x >> y) {
        if (x == -1 && y == -1) {
            cout << endl;
            break;
        }

        if (x > y)
            swap(x, y);
        ans.erase({ x, y });
        cout << (*ans.begin()).first << " " << (*ans.begin()).second << endl;
        ans.erase(ans.begin());
    }
}

# D

# 题目大意

# 数据范围

# 题解

# E

# 题目大意

# 数据范围

# 题解

高精度

专题四【基础算法】