A 世界

file:
world.in
world.out
1s，512MB

题目描述

在 $zty$ 的梦中，有这样一个奇怪的世界：

世界初始时为一个$n*n$个格子的正方形平面，每个格子都有一个唯一且不会更改的标号。

初始时，左下角格子的标号为$(1, 1)$，右上角格子的标号为$(n, n)$。

初始时，$zty$位于标号为$(1, 1)$的格子。

对于$zty$来说，他可以向上下左右移动。一次移动只会走到相邻的格子。例如，在没有任何消除格子操作的情况下（详见下方题目描述），若$zty$当前所在格子标号为(2, 2)，向右移动后所在格子标号为(3, 2)，向上移动后所在格子标号为(2, 3)。

$zty$在改造这个世界。除了移动之外，他可以实施操作，消除当前所在位置的格子。格子消除后，该格子左面的格子会和右面的格子左右相邻，上面的格子会和下面的格子上下相邻。

例如，在初始的世界中，消除标号为(2, 2)的格子，则

（以下 (x, y) 代表标号为 (x, y) 的格子）

(3, 2)的左边会由(2, 2)变成(1, 2)

(1, 2)的右边会由(2, 2)变成(3, 2)

(2, 1)的上面会由(2, 2)变成(2, 3)

(2, 3)的下面会由(2, 2)变成(2, 1)

若再消除标号为(2, 3)的格子，则

(2, 1) 的上面会由(2, 2)变成(2, 4)

(2, 4) 的下面会由(2, 2)变成(2, 1)

(1, 3) 的右面会由(2, 3)变成(3, 3)

(3, 3) 的左面会由(2, 3)变成(1, 3)

除此之外，还有查询操作，询问zty当前所在的格子的标号。

zty的操作，还会遵循以下规则：

1、若此时位于世界的边缘，且此次移动操作会导致zty越界，则此次移动不会执行。例如，在zty位于初始局面的标号为(1,1)的格子时，若向下 / 左移动，则不会执行。

2、若执行“消除当前格子”的操作，当且仅当zty离开该格子后，其才会被消除。例如，zty位于标号(2,2)的格子时，执行了一次“消除当前格子”的操作，则在zty离开(2, 2)前，标号为(2, 2)格子仍然存

在。对应到题目操作中的解释为：若此时查询所在格子的标号，仍为(2, 2)

3、任意两个“消除当前格子”的操作之间，一定间隔着至少一次移动操作。

输入格式

第一行两个整数$n(1 ≤ n ≤ 500)$，表示世界起始的大小，其含义见题目描述。

第二行一个整数$T(T ≤ 10^6)$，代表操作的次数。

接下来$T$ 行，每行一个字符。

若字符为 $W/ S /A /D$，分别代表此次向上 / 下 / 左 / 右移动。

若字符为$B$，代表实行一次消除操作。

若字符为$P$ ，代表一次查询操作，询问$zty$当前所在格子的标号。

输入数据保证任意两个消除操作之间，一定间隔着至少一次移动操作（符合上述规则三）。

输出格式

设$|P|$为输入数据中字符$P$ 的个数。

输出共$|P|$行，每行一个形如 (x, y) 的坐标，表示当前当前所在的格子的标号.

样例1

15
14
W
B
S
A
W
S
D
P
W
A
W
S
P
D

(2, 1)
(2, 2)

每次操作后所在格子的标号：

(1, 2) (1, 2) (1, 1) (1, 1) (1, 3) (1, 1) (2, 1) (2, 1) (2, 2) (2, 2) (2, 3) (2, 2) (2, 2) (3, 2)

数据范围

本题共有10个测试点。

对于$30\%$的数据，$1 ≤ n ≤ 20，1 ≤ T ≤ 20$。

对于$50%$的数据，$1 ≤ n ≤ 100，1 ≤ T ≤ 10^4$。

对于$100\%$的数据，$1 ≤ n ≤ 500，1 ≤ T ≤ 10^6$。

解法

• Dancing Links
• 模拟（很奇怪的可过）

代码

两种解法，Dancing Links是后面补的，考试的时候模拟过了哈哈～

Dancing Links

#include <iostream>
#include <vector>
using namespace std;

struct Loc {
    int x, y;
};
struct Link {
    Loc left, right, up, down;
    Loc num;
};

int n, m;
vector<vector<Link>> e;
int curx, cury;

bool chk(int x, int y) {
    return x >= 1 && y >= 1 && x <= n && y <= n;
}

void ebuild() {
    int nx = 1, ny = 1;
    for (int j = 1; j <= n; j++) {
        for (int i = n; i >= 1; i--) {
            e[i][j].num.x = nx;
            e[i][j].num.y = ny;
            ny++;
            int nxn = i, nyn = j - 1;
            if (chk(nxn, nyn)) e[i][j].left = { nxn, nyn };
            nxn = i, nyn = j + 1;
            if (chk(nxn, nyn)) e[i][j].right = { nxn, nyn };
            nxn = i - 1, nyn = j;
            if (chk(nxn, nyn)) e[i][j].up = { nxn, nyn };
            nxn = i + 1, nyn = j;
            if (chk(nxn, nyn)) e[i][j].down = { nxn, nyn };
        }
        nx++;
        ny = 1;
    }
}

void emove(char op) {
//    cout << "CURR:" << curx << " ," << cury << endl;
//    cout << "MOVE:" << op << endl;
    int ncurx = 0, ncury = 0;
    if (op == 'W') {
        ncurx = e[curx][cury].up.x;
        ncury = e[curx][cury].up.y;
    } else if (op == 'S') {
        ncurx = e[curx][cury].down.x;
        ncury = e[curx][cury].down.y;
    } else if (op == 'A') {
        ncurx = e[curx][cury].left.x;
        ncury = e[curx][cury].left.y;
    } else {
        ncurx = e[curx][cury].right.x;
        ncury = e[curx][cury].right.y;
    }
    if (chk(ncurx, ncury)) {
        curx = ncurx;
        cury = ncury;
    }
//    cout << "CURR:" << curx << " ," << cury << endl;
}

void edel() {
    int upx = e[curx][cury].up.x, upy = e[curx][cury].up.y;
    int downx = e[curx][cury].down.x, downy = e[curx][cury].down.y;
    int leftx = e[curx][cury].left.x, lefty = e[curx][cury].left.y;
    int rightx = e[curx][cury].right.x, righty = e[curx][cury].right.y;
    if (upx != 0) e[upx][upy].down = { downx, downy };
    if (downx != 0) e[downx][downy].up = { upx, upy };
    if (leftx != 0) e[leftx][lefty].right = { rightx, righty };
    if (rightx != 0) e[rightx][righty].left = { leftx, lefty };
}

int main() {
    freopen("world.in", "r", stdin);
    freopen("world.out", "w", stdout);
    cin >> n;
    e.resize(n + 1, vector<Link>(n + 1));
    ebuild();
    cin >> m;
    curx = n;
    cury = 1;
    while (m--) {
        char op;
        cin >> op;
        if (op == 'P') {
            cout << "(" << e[curx][cury].num.x << ", " << e[curx][curx].num.y << ")" << endl;
        } else if (op == 'B') {
            edel();
        } else {
            emove(op);
        }
    }
    return 0;
}

模拟

#include <iostream>
#include <vector>
using namespace std;

int n;
vector<vector<char>> graph;
vector<vector<tuple<int, int>>> number;
int curr_x, curr_y;

void number_init() {
    int xtot = 1, ytot = 1;
    for (int j = 1; j <= n; j++) {
        for (int i = n; i >= 1; i--) {
            number[i][j] = make_tuple(xtot, ytot++);
        }
        xtot++;
        ytot = 1;
    }
    
//    for (int i = 1; i <= n; i++) {
//        for (int j = 1; j <= n; j++) {
//            auto [x, y] = number[i][j];
//            cout << '(' << x << ' ' << y << ')' << ' ';
//        }
//        cout << endl;
//    }
}

void move(char op) {
    if (op == 'W') {
//        if (curr_x - 1 < 1) return;
//        curr_x--;
        int x = curr_x;
        while (true) {
            x--;
            if (x < 1) return;
            if (!graph[x][curr_y]) break;
        }
        curr_x = x;
    } else if (op == 'S') {
//        if (curr_x + 1 > n) return;
//        curr_x++;
        int x = curr_x;
        while (true) {
            x++;
            if (x > n) return;
            if (!graph[x][curr_y]) break;
        }
        curr_x = x;
    } else if (op == 'A') {
//        if (curr_y - 1 < 1) return;
//        curr_y--;
        int y = curr_y;
        while (true) {
            y--;
            if (y < 1) return;
            if (!graph[curr_x][y]) break;
        }
        curr_y = y;
    } else {
//        if (curr_y + 1 > n) return;
//        curr_y++;
        int y = curr_y;
        while (true) {
            y++;
            if (y > n) return;
            if (!graph[curr_x][y]) break;
        }
        curr_y = y;
    }
}

int main() {
    freopen("world.in", "r", stdin);
    freopen("world.out", "w", stdout);
    
    int t;
    cin >> n;
    cin >> t;
    graph.resize(n + 1, vector<char>(n + 1));
    number.resize(n + 1, vector<tuple<int, int>>(n + 1));
    number_init();
    curr_x = n;
    curr_y = 1;
    while (t--) {
        char op;
        cin >> op;
        if (op == 'B') {
            graph[curr_x][curr_y] = 1;
        } else if (op == 'P') {
            auto [x, y] = number[curr_x][curr_y];
            cout << '(' << x << ", " << y << ')' << endl;
        } else {
            move(op);
        }
    }
    return 0;
}

B 集合

file:
set.in
set.out
2s,512M

题目描述

小$A$和小$B$是好朋友，他们所在的城市是一个由$n$个路口和$n$ − 1条街道构成的连通图。

路口的编号分别为1到$n$。小$A$经常活动的路口记为集合$S$；小$B$经常活动的路口记为集合$T$ 。他们想知道两个集合中任意两点的距离之和，即$\sum_{x\in S}\sum_{y\in T} dis(x, y)$。

答案对998244353取模。

输入描述

第一行一个整数$n$，表示路口的数目。

接下来$n - 1$行，每行三个数字$x$、$y$、 $c$，从$x$号路口到$y$号路口有一条距离为$c$的街道。

接下来一行，第一个整数$s$，表示$S$集合的点的数目。接下来$s$个整数，描述$S$集合。

接下来一行，第一个整数$t$，表示$T$ 集合的点的数目。接下来$t$个整数，描述$T$集合。

输出格式

一行，一个整数，表示答案。

样例1

6
1 3 1
5 6 1
3 5 1
2 3 1
2 4 1
3 1 3 5
3 2 4 6

19

数据范围

对于$20\%$的数据：$1≤ n≤ 10^2 , c = 1$。

对于$40\%$的数据：$1≤ n≤ 10^4 , 0≤c≤ 10^5$。

对于$100\%$的数据：$1≤ n≤ 10^6 , 0≤c≤ 2147483647$。

解法

考虑经过每一条边的点对的个数。

枚举每一条边，把树分成两部分，考虑每一边点的数量与另一边乘起来，累加 ans。

代码

#include <iostream>
#include <vector>
using namespace std;

const size_t MOD = 998244353;

size_t n, s, t;
vector<size_t> sz_s, sz_t;
vector<vector<tuple<size_t, size_t>>> e;
size_t ans;
size_t x, y, c;

void dfs(size_t u, size_t fn) {
    for (auto [v, w] : e[u]) {
        if (v == fn) continue;
        dfs(v, u);
        sz_s[u] += sz_s[v];
        sz_t[u] += sz_t[v];
        
        // 重点在这
        size_t a = sz_t[v] * (s - sz_s[v]) % MOD;
        size_t b = sz_s[v] * (t - sz_t[v]) % MOD;
        ans += (a + b) * w % MOD ;
        ans %= MOD;
    }
}

int main() {
    freopen("set.in", "r", stdin);
    freopen("set.out", "w", stdout);
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n;
    e.resize(n + 1);
    sz_s.resize(n + 1);
    sz_t.resize(n + 1);
    for (size_t i = 0; i < n - 1; i++) {
        cin >> x >> y >> c;
        e[x].emplace_back(make_tuple(y, c));
        e[y].emplace_back(make_tuple(x, c));
    }
    cin >> s;
    for (size_t i = 0; i < s; i++) {
        cin >> x;
        sz_s[x] = 1;
    }
    cin >> t;
    for (size_t i = 0; i < t; i++) {
        cin >> x;
        sz_t[x] = 1;
    }
    dfs(1, 0);
    cout << ans << endl;
    return 0;
}

C 填数游戏

file:
number.in
number.out
1s,512M

题目描述

现在有一个$n∗m$的矩阵，矩阵中每个格子只能填1或−1，小$A$已经提前在矩阵中填好了$k$个格子，现在他问小$B$，有多少种不同的方法填剩下的格子，使得矩阵满足任意一行或一列中所有数的积都是$−1$？（两种方法不同当且仅当两种方法中某个格子填的数不同）。小 $B$ 乞求小 $A$ 降低题目难度，于是小 $A$ 又给出了一个条件，$k$严格小于$n$和$m$的最大值，且最后的答案模$p$就可以了。

输入格式

输入第一行包含两个整数$n$和$m$，代表矩阵的大小。

第二行包含一个整数$k$，代表已经填好的格子数。

接下来k行，每行三个整数$a, b, c$，代表第$a$行，第$b$列，填了数$c$。

最后一行包含一个整数$p$，代表需要将答案模$p$。

输出格式

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

样例1

2 2 
1 
2 2 -1 
2333

1

样例2

983 533 
3 
1 3 1 
4 2 -1 
100 100 1 
666666666

195328496

数据范围

对于$30\%$的数据，$1 ≤ n∗m ≤ 21$。

对于$70\%$的数据，$1 ≤ n* m ≤ 1000$。

其中有$10\%$的数据，$1 ≤ n, m ≤ 1000, k = 0$

对于$100\%$的数据，$1 ≤ n, m ≤ 1000000, 0 ≤ k < max (n, m), 1 ≤ a ≤ n, 1 ≤ b ≤ m,c=1/−1 , 2 ≤ p ≤ 10^9 + 7$

数据保证不会出现一个格子填两次

解法

设行数为 max(n, m)。

行确定了列一定确定了。

k <= max(n, m) 则保证一定有一行空的。

每个格子只有两种状态，填到最后一个格子是确定的。

减去已经确定的格子统计方案数即可。

n, m 一个为奇数一个为偶数会导致无解，特判掉。

代码

#include <iostream>
#include <vector>
using namespace std;

int n, m, k, mod;
vector<char> val;
vector<int> cnt;
vector<int> f;
int ans = 1;

int main() {
    freopen("number.in", "r", stdin);
    freopen("number.out", "w", stdout);
    
    bool flag = false;
    cin >> n >> m;
    if (n < m) {
        swap(n, m);
        flag = true;
    }
    val.resize(n + 1, 1);
    cnt.resize(n + 1);
    f.resize(m + 1);
    cin >> k;
    while (k--) {
        int a, b, c;
        cin >> a >> b >> c;
        if (flag) swap(a, b);
        cnt[a]++;
        val[a] *= c;
    }
    cin >> mod;
    if ((n + m) % 2 == 1) {
        cout << "0" << endl;
        return 0;
    }
    for (int i = 1; i <= n; i++) {
        if (cnt[i] == 0) {
            swap(cnt[i], cnt[n]);
            swap(val[i], val[n]);
            break;
        }
    }
    f[0] = 1;
    for (int i = 1; i <= m; i++) {
        f[i] = f[i - 1] * 2 % mod;
    }
    for (int i = 1; i <= n - 1; i++) {
        if (cnt[i] < m) {
            ans = 1LL * ans * f[m - cnt[i] - 1] % mod;
        }
    }
    
    cout << ans << endl;
    
    return 0;
}

D 字符串匹配

file:
string.in
string.out
1s,512M

题目描述

给定两个整数$N$和$M$，以及两个由小写字母组成的字符串$S$和$T$，我们按以下要求生成两个字符串$A$和$B$：

1、 字符串$A$和$B$的长度相等；

2、 $A$由$S$重复$N$次产生；

3、 $B$是由$T$重复$M$次产生。

如果$A$中的第$i$个字符与$B$中的第$i$个字符相同，则视为匹配。给定$N、M、S、T$，请编写一个程序求$A$和$B$的匹配字符数。

输入格式

第一行两个用空格整数$N$和$M$。

第二行和第三行分别为$S$和$T$。

数据保证$A$和$B$相等。

输出格式

输出为一个整数，表示$A$和$B$的匹配字符数。

样例1

3 5
ababa
aba

8

样例2

30 20
abbb
bbaabb

70

数据范围

$40\%$的数据满足 $A\le 10^5$；

另有$30\%$的数据满足$N,M\le 10^9 ；|S|,|T|\le 10$（$|S|$表示$S$的长度）；

$100\%$的数据满足 $N,M\le 10^9 ；|S|,|T|\le 10^6$。

解法

按 s.size() 和 t.size() 先算出字符串 s 和 t 按最大公约数统计的匹配数。

再根据乘法原理乘以 n 和 m 的最大公约数即可。

代码

#include <iostream>
#include <vector>
using namespace std;

size_t n, m, d;
string s, t;
vector<vector<size_t>> cnt;
size_t ans;

size_t gcd(size_t a, size_t b) {
    if (b == 0) return a;
    return gcd(b, a % b);
}

int main() {
    freopen("string.in", "r", stdin);
    freopen("string.out", "w", stdout);

    cin >> n >> m;
    cin >> s >> t;
    d = gcd(s.size(), t.size());
    cnt.resize(26, vector<size_t>(d + 1));
    for (size_t i = 0; i < s.size(); i++)
        cnt[s[i] - 'a'][i % d]++;
    for (size_t i = 0; i < t.size(); i++)
        ans += cnt[t[i] - 'a'][i % d];
    cout << ans * gcd(n, m) << endl;
    return 0;
}

后记

后三题的分全是暴力凑的哈哈哈哈哈。

有点好笑，这次我算是知道为什么不要空题了。 :D